基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法

何琨莫旦增许如初黄文奇

华中科技大学;

摘要：

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.

关键词：Packing问题、布局优化、拟物、平衡约束、粗精调技术

所属期刊栏目：36

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61173180;中央高校基本科研业务费HUST:2010MS099;the National Natural Science Foundation of China61173180;the Fundamental Research Funds for the Central UniversitiesHUST:2010MS099

在线出版日期：2013-10-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1224-1234