带静不平衡约束的矩形装填问题的启发式算法  

Heuristic Algorithm for the Rectangular Packing Problem with Static Non-Equilibrium Constraint

作　　者：刘景发[1,2] 刘思妤 

机构地区：[1]江苏省网络监控工程中心(南京信息工程大学),江苏南京210044 [2]南京信息工程大学计算机与软件学院,江苏南京210044

出　　处：《软件学报》2018年第2期283-298,共16页Journal of Software

基　　金：国家自然科学基金(61373016);江苏省"六大人才高峰"项目(DZXX-041);国家社会科学基金(16ZDA047)~~

摘　　要：卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性.解决这类问题最大的挑战在于需要优化的目标函数具有大量被高能势垒分隔开的局部极小值点.Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已被成功地运用于蛋白质结构预测等优化问题.以卫星舱布局优化问题为背景,将WL抽样算法引入矩形装填问题的求解.针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走.为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,就执行梯度法进行局部搜索.通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法.在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.为了改进算法的搜索效率,还提出了改进的有限圆族法,用于装填物之间的干涉性判断和干涉量计算.通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法.Layout design of satellite module is not only a complex coupling system design problem but also a special optimization problem. It is considered to be NP-hard. The most challenge of solving this problem is that the objective function to be optimized is characterized by a multitude of local minima separated by high-energy barriers. The Wang-Landau（WL） sampling method is an improved Monte Carlo method, which has been successfully applied to solve the protein structure prediction and other optimization problems. Taking satellite layout design as case study, this paper introduces the WL sampling method to solve the rectangular packing problem. In order to guide the WL sampling algorithm to random walk effectively in solution space, rectangular objects-oriented heuristic layout update strategies are proposed. To accelerate the search for the global optimal layout, the gradient method is executed for local search once the Monte-Carlo sweep produces a new layout. By incorporating the local search mechanism and heuristic layout update strategies into the WL sampling algorithm, a heuristic Wang-Landau sampling algorithm is constructed to solve the arbitrary rectangular packing problem with the static non-equilibrium constraint. By adding a static non-equilibrium penalty term on the basis of the extrusive elastic energy, and adopting the translation of the center of mass, the static non-equilibrium constraints of the whole system can be satisfied. Furthermore, to improve the efficiency of the algorithm significantly, an improved finite-circle method is presented to judge and calculate the overlapping depth among objects. The computational results of two sets of benchmarks consisting of ten representative instances from the literature show that the proposed packing algorithm is effective.

关 键 词：静不平衡约束 Wang-Landau抽样算法 启发式策略 卫星舱布局 

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