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

An Improved Scatter Search for Circles Packing Problem with the Equilibrium Constraint

作　　者：王奕首[1,2] 史彦军[2] 滕弘飞[2,3] 

机构地区：[1]大连理工大学航空航天学院,辽宁大连116024 [2]大连理工大学机械工程学院,辽宁大连116024 [3]大连理工大学计算机科学与工程系,辽宁大连116024

出　　处：《计算机学报》2009年第6期1214-1221,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(50275019;50575031;60674078);国家"八六三"高技术研究发展计划项目基金(2006AA04Z109);大连理工大学科研启动基金(893302)资助~~

摘　　要：以卫星布局为背景的带平衡约束的圆形Packing问题属NP难问题.该文用给出的改进的散射搜索方法求解.一是给出基于极坐标变换的散射搜索多样性生成策略,二是采取基于极角和极径差异度的参考集更新策略,三是用梯度下降法和Nelder-Mead直接搜索法分别作为散射搜索法中不同阶段所产生新解的改进方法,从而构成改进的散射搜索法,提高了散射搜索法的探索和搜索能力.数值实验结果表明了该改进散射搜索法的可行性和有效性.The equilibrium-constrained circles Packing problem with the background of satellite module layout design belongs to NP-hard problem. The authors extend scatter search （SS） to deal with this problem, and propose the improved scatter search. The authors empirically study the coordinate transformation-based diversification method and the reference set update method on the basis of two dissimilarities. The gradient descent algorithm and Nelder-Mead simplex algorithm are adopted to improve the trial solution generated at two different stages in SS, respectively. The improved scatter search can make a tradeoff between exploration and exploitation. Experiment results show the feasibility and effectiveness of the improved scatter search.

关 键 词：带平衡约束Pakcing问题 散射搜索 局部搜索 启发式方法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]