基于遗传模拟退火算法的矩形件优化排样

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (7): 259-263.

基于遗传模拟退火算法的矩形件优化排样

杨卫波1，2，王万良1，张景玲3，赵燕伟3

1.浙江工业大学信息工程学院，杭州 310023
2.温州大学物理与电子信息工程学院，浙江温州 325035
3.浙江工业大学特种装配制造与先进加工技术教育部重点实验室，杭州 310014

出版日期:2016-04-01 发布日期:2016-04-19

Packing optimization of rectangles based on improved genetic annealing algorithm

YANG Weibo1，2, WANG Wanliang1, ZHANG Jingling3, ZHAO Yanwei3

1.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China
2.College of Physics and Electronic Information Engineering, Wenzhou University, Wenzhou, Zhejiang 325035, China
3.Key?Lab?of?Special Purpose Equipment and Advanced Manufacturing Technology, Ministry of Education, Zhejiang University of Technology, Hangzhou 310014, China

Online:2016-04-01 Published:2016-04-19

摘要/Abstract

摘要： 为了探索更高效的矩形件优化排样方法，提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法，并采用基于临界多边形的BL定位策略实现矩形件的布局；通过构造启发式算法生成排样初始种群，然后各个种群之间通过相互竞争实现优秀个体的迁移与共享，最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。

关键词: 矩形件排样, 启发式布局算法, 临界多边形, 模拟退火算法, 自适应遗传算法

Abstract: To explore more efficient methods for the packing optimization problem of rectangles, an Improved Adaptive Genetic Simulated Annealing （IAGSA） algorithm is presented. The two-layer coding method based on the packing sequence and rotation variable of rectangular parts is designed, and the bottom-left-condition placement strategy based on no fit polygon is proposed to complete the layout of rectangular parts. The heuristic algorithm is constructed to generate packing initial populations. The migration and sharing of outstanding individual are achieved by mutual competition among all populations, and the optimal solution is found eventually. The simulation results on classic benchmarks demonstrate the feasibility and effectiveness of the presented IAGSA.

Key words: rectangle packing, heuristic layout algorithm, no fit polygon, simulated annealing algorithm, adaptive genetic algorithm

杨卫波1，2，王万良1，张景玲3，赵燕伟3. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7): 259-263.

YANG Weibo1，2, WANG Wanliang1, ZHANG Jingling3, ZHAO Yanwei3. Packing optimization of rectangles based on improved genetic annealing algorithm[J]. Computer Engineering and Applications, 2016, 52(7): 259-263.

[1]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[2]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[3]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[4]	童文林，陈德旺，黄允浒，吕宜生. 结合模拟退火与规则约简的模糊系统优化方法[J]. 计算机工程与应用, 2021, 57(16): 142-150.
[5]	邱云飞，高华聪. 混合Filter与改进自适应GA的特征选择方法[J]. 计算机工程与应用, 2021, 57(11): 95-102.
[6]	禹忠，顾仁彬，范九伦. 基于LBT-SA的LoRaWAN信道接入方法研究[J]. 计算机工程与应用, 2020, 56(24): 95-101.
[7]	徐力，刘云华，王启富. 自适应遗传算法在机器人路径规划的应用[J]. 计算机工程与应用, 2020, 56(18): 36-41.
[8]	陈桂兰，奚宝华，杨兰英. 改进混合粒子群算法的立体车库存取调度[J]. 计算机工程与应用, 2019, 55(19): 263-270.
[9]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[10]	俞武扬，周洋. 改进柔性隔间结构的不等形面积设施布局研究[J]. 计算机工程与应用, 2019, 55(14): 221-227.
[11]	夏以冲，陈秋莲，宋仁坤. 基于自适应遗传模拟退火算法的矩形件排样[J]. 计算机工程与应用, 2018, 54(22): 229-232.
[12]	韩晓龙，李上，杨全业. 基于遗传算法的战略供应链集成研究[J]. 计算机工程与应用, 2018, 54(2): 214-221.
[13]	孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用[J]. 计算机工程与应用, 2018, 54(15): 139-146.
[14]	汪开普，张则强，邹宾森，毛丽丽. 模糊作业时间的拆卸线平衡Pareto多目标优化[J]. 计算机工程与应用, 2018, 54(1): 256-263.
[15]	张立毅1，王迎2，费腾1，周修飞2. 混沌扰动模拟退火蚁群算法低碳物流路径优化[J]. 计算机工程与应用, 2017, 53(1): 63-68.