基于遗传模拟退火算法的矩形件优化排样
- 文档名称:基于遗传模拟退火算法的矩形件优化排样
- 文档关注次数:65
- 文档格式:纸质版或者PDF电子版(用Acrobat Reader打开)或Word版本doc格式
- 文档大小:1363KB
- 上传者:jinmbb
- 添加时间:2019/05/05
- 内容摘要:
Computer Engineering and Applications计算机工程与应用
2016,52(7)259
基于遗传模拟退火算法的矩形件优化排样
杨卫波2,王万良,张景玲,赵燕伟3
YANG Weibo", WANG Wanliang, ZHANG Jingling, ZHAO Yanwei
1浙江工业大学信息工程学院,杭州310023
2.温州大学物理与电子信息工程学院,浙江温州325035
3.浙江工业大学特种装配制造与先进加工技术教育部重点实验室,杭州310014
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
ANG Weibo, WANG Wanliang, ZHANG Jingling et al. Packing optimization of rectangles based on improved
genetic annealing algorithm. Computer Engineering and Applications, 2016, 52(7): 259-263.
Abstract: To explore more eflicient methods for the packing optimization problem of rectangles, an Improved Adaptive
Genetic Simulated Annealing(AGSA )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
algorith
摘要:为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件
的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局:通过构
造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优
解。标准测试问题的实验结果验证了所提算法的可行性与有效性
关键词:矩形件排样;启发式布局算法;临界多边形;模拟退火算法;自迸应遗传算法
文献标志码:A中图分类号:TP301.6doi:10.3778/jia.1002-8331.1512-0076
的应用,从计算复無度上看,该问题也是一个NP难问
矩形件优化排样问题是指在给定一个宽度固定、高题,因此长期以来吸引着国内外众多学者研究各种方法
度不限的矩形容器(母板)的情况下,将具有一定种类和对其进行求解。
数量的矩形件排放到母板上,使排放的矩形件占据母板
目前,针对矩形件排样问题的求解方法归納起来可
高度最小,即使母板材料的利用率达到最大。该问题在分为精确求解算法、启发式算法和智能优化算法三种类
报刊排版、布料切割、金属下料等工业生产中有着广泛型"。精确算法研究最早,如Lesh等人提出的基于分
基金项口:国家自然科学基金(No.51275477No.61379123,No.61402409);浙江省自然科学基金(No.LQ14F030005)
作者简介:杨波(1977-),男.博十研究生,主要研究方向为智能计算、计算机辅助设计,E- mail: yangweibo hubei(@163.c0m;王
万良(1957-),男,教授,博士生导师,主要研究方向为智能控制;张景玲(1980一),女,博士,讲师,主要研究方向为物
流配送车辆优化调度;赵燕伟(1959-),女,教授,博上生导师,主要研究方向为数字化产品现代设计理论与方法等。
收稿日期:2(015-12-07修回日期:2016-02-23文章编号:1002-831(2016)07-0259-05
CNKI劇络优先出版:2016-03-02,htt;/www.cnki.net/kcms/detail,11.2127,TP20160302.1655,040.html