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

作     者：邓见凯 王磊 尹爱华 DENG Jian-kai;WANG Lei;YIN Ai-hua

作者机构：武汉科技大学计算机科学与技术学院湖北武汉430065 智能信息处理与实时工业系统湖北省重点实验室湖北武汉430065 江西财经大学软件与通信工程学院江西南昌330013 

出 版 物：《计算机工程与科学》 (Computer Engineering & Science)

年 卷 期：2018年第40卷第2期

页      面：331-340页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：湖北省教育厅科学技术研究计划指导性项目(B2016003) 

主　　题：矩形Packing 拟人算法 全局优化 启发式 

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