基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

被引：18

作者：

李刚 ^{[1
]}

刘景发 ^{[2
,3
]}

机构：

[1] 南京信息工程大学数理学院

[2] 南京信息工程大学网络信息中心

[3] 南京信息工程大学计算机与软件学院

来源：

中国科学:信息科学 | 2011年 / 41卷 / 09期

基金：

中国博士后科学基金;

关键词：

平衡约束; 装填问题; 启发式算法; 禁忌搜索; 布局优化;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.

引用

页码：1076 / 1088

页数：13

共 19 条

[1]

Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints.[J]..Science China(Information Sciences).2010, 05

[2]

用改进的散射搜索法求解带平衡约束的圆形Packing问题 [J].