一种求解二维矩形Packing问题的拟人型全局优化算法

A quasi-human global optimization algorithm for solving the two dimensional rectangular packing problem

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。

We propose a basic algorithm based on corner-occupied action for solving the 2D rectangular packing problem and a three-phase quasi-human global optimization algorithm.In the first phase,an initial configuration is generated.In the second phase,we optimize the priority levels of all rectangles by iteratively calling the local search sub-procedure and off-trap strategy sub-procedure.We adopt two neighborhood structures—swap and insertion instead of a single neighborhood structure in the local search sub-procedure to avoid some limitations.When the search encounters local optimal solutions,the off-trap strategy sub-procedure is called to jump out of the trap and guide the search into more promising areas.In the third phase,the beauty degree enumeration sub-procedure is called to optimize the selection of corner-occupied actions.We also derive two goodness degree theorems.Experiments on six sets of benchmark instances show that the proposed algorithm outperforms the best algorithms in the literature.For the two benchmark instances named zdf6 and zdf7,while the orientation of the rectangles is fixed the proposed algorithm can find better packing configurations than the best results reported in the literature up to now.