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

Heuristic algorithm based on tabu search for the circular packing problem with equilibrium constraints

作　　者：李刚[1] 刘景发[2,3] 

机构地区：[1]南京信息工程大学数理学院,南京210044 [2]南京信息工程大学网络信息中心,南京210044 [3]南京信息工程大学计算机与软件学院,南京210044

出　　处：《中国科学：信息科学》2011年第9期1076-1088,共13页Scientia Sinica(Informationis)

基　　金：国家公益性行业科研专项(批准号:GYHY200906006);江苏省自然科学基金(批准号:BK2010570);中国博士后科学基金(批准号:20100471350);江苏省博士后科研资助计划(批准号:1001030B);江苏省高校自然科学研究(批准号:09KJB520008);江苏省"青蓝工程"(苏教(2008)30号)资助项目

摘　　要：带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search for solving this problem is put forward.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search from doing repeated work,the algorithm adopts the strategy of tabu search.In the process of tabu search,we improve the traditional neighboring solutions,tabu objects and the acceptance criteria of the current solution effectively.We test two sets of benchmarks consisting of 11 representative instances from the current literatures.The numerical results show that the proposed algorithm breaks the records in 7 out of 11 instances,and obtains the optimal solutions for the other 4 instances.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]