带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.
The circles packing problem with constraints of equilibrium, as a two-dimensional packing problem with the background of satellite module layout design, is an NP hard layout op- timization problem. A mathematical model and two new physical models are established for this problem. And inspired by the process of coarse and fine adjustment in the industry, a Quasi- Physical algorithm based on Coarse and Fine Adjustment (QPCFA) is proposed. Not only can QPCFA keep the diversity of the searching space to facilitate the global search, but also it can do fine search in promising local areas to find the corresponding local optimal solutions. Moreover, the taboo method and the jump pit strategy are combined to improve the performance of this algo- rithm. Experiments on 11 representative instances show that QPCFA achieve new and better results on seven ones and matched the current best records on the other four. In addition, the calculation accuracy is improved considerably.