Packing optimization of rectangles based on improved genetic annealing algorithm

Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (7): 259-263.

Previous Articles Next Articles

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

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

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

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

Abstract

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

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

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

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

[1]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[2]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.
[3]	TONG Wenlin, CHEN Dewang, HUANG Yunhu, LYU Yisheng. Fuzzy System Optimization Method Based on Simulated Annealing and Rule Reduction [J]. Computer Engineering and Applications, 2021, 57(16): 142-150.
[4]	QIU Yunfei, GAO Huacong. Hybrid Filter and Improved Adaptive GA for Feature Selection [J]. Computer Engineering and Applications, 2021, 57(11): 95-102.
[5]	YU Zhong, GU Renbin, FAN Jiulun. Research on Channel Access Method of LoRaWAN Based on LBT-SA [J]. Computer Engineering and Applications, 2020, 56(24): 95-101.
[6]	XU Li, LIU Yunhua, WANG Qifu. Application of Adaptive Genetic Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(18): 36-41.
[7]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[8]	YU Wuyang, ZHOU Yang. Study of Unequal Area Facility Layout Problem with Improved Flexible Bay Structure [J]. Computer Engineering and Applications, 2019, 55(14): 221-227.
[9]	LIU Lanfen, YANG Xinfeng. Searching Algorithm for Efficient Paths Based on Hybrid Genetic Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 244-249.
[10]	XIA Yichong, CHEN Qiulian, SONG Renkun. Packing of rectangles using adaptive genetic simulated annealing algorithm [J]. Computer Engineering and Applications, 2018, 54(22): 229-232.
[11]	HAN Xiaolong, LI Shang, YANG Quanye. Strategic supply chain integration research based on genetic algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 214-221.
[12]	SUN Jiazheng, GUO Jun. Improved dual population genetic algorithm for rectangle packing [J]. Computer Engineering and Applications, 2018, 54(15): 139-146.
[13]	WANG Kaipu, ZHANG Zeqiang, ZOU Binsen, MAO Lili. Pareto optimization for multi-objective disassembly line balancing with fuzzy operation times [J]. Computer Engineering and Applications, 2018, 54(1): 256-263.
[14]	ZHANG Liyi1, WANG Ying2, FEI Teng1, ZHOU Xiufei2. Research on low carbon logistics routing optimization based on chaotic-simulated annealing ant colony algorithm [J]. Computer Engineering and Applications, 2017, 53(1): 63-68.
[15]	LI Qingxiang1, ZHAO Xiaofei2. Variable neighborhood search algorithm for solving robot cell scheduling problem——scheduling sequence-dependent setup times [J]. Computer Engineering and Applications, 2016, 52(23): 167-171.

Packing optimization of rectangles based on improved genetic annealing algorithm

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics