锻压技术

二维不规则图形排样问题的一种混合求解算法

英文标题：A hybrid solving algorithm on two-dimensional irregular graphics nesting problem

作者：杜冰郭晓强方杰王朋饶运清

分类号：

出版年,卷(期):页码：2022,47(3):39-45

摘要：

针对二维不规则图形排样问题，实现了一种基于启发式定位策略与自适应遗传算法的混合排样算法（AGAHA）。首先，考虑到单一指标的放置策略容易陷入局部最优的问题，提出了一种基于临界多边形（NFP）的混合放置策略，综合考虑排样效果的整体紧密度和局部紧密度。之后，为了提高搜索最优解的效率，在优化图形的顺序时使用了自适应遗传算法，在标准遗传算法的基础上，根据种群适应度的变化，自适应地改变交叉与变异概率。最后，利用文献中的标准测试案例和实际生产中的案例分别进行测试，结果表明：AGAHA算法在多数案例上较普通遗传算法结合BL算法更优，并且在实际案例中也取得了优于人工排样的结果。

For the two-dimensional irregular graphics nesting problem, a hybrid nesting algorithm (AGAHA) based on heuristic placement strategy and adaptive genetic algorithm was implemented. Firstly, considering the problem that the placement strategy of a single index was easy to fall into the local optimum, a hybrid placement strategy based on no-fit polygon (NFP) was proposed, which comprehensively considered the overall compactness and local compactness of the nesting effect. Then, in order to improve the efficiency of searching for the optimal solution, an adaptive genetic algorithm was used when optimizing the order of graphs. Based on the standard genetic algorithm, the crossover and mutation probabilities were adaptively changed according to changes in population fitness. Finally, the standard test cases in the literature and the cases in the actual production were used to test separately. The results show that the AGAHA algorithm is better than the ordinary genetic algorithm combined with BL algorithm in most cases, and in the actual cases, the results of AGAHA algorithm are better than the result of manual nesting.

基金项目：

国家自然科学基金资助项目（51975231）；中央高校基本科研业务费专项基金资助项目（2019kfyXKJC043）

作者简介：杜冰（1998-），男，硕士研究生 E-mail：rover_du@qq.com 通信作者：饶运清（1968-），男，教授，博士生导师 E-mail：ryq@hust.edu.cn

参考文献：

[1]Freeman H, Shapira R. Determining the minimum-area encasing rectangle for an arbitrary closed curve[J]. Communications of the ACM, 1975, 18(7):409-413.

[2]Jakobs S. On genetic algorithms for the packing of polygons[J]. European Journal of Operational Research, 1996, 88(1):165-181.

[3]Dori D, Benbassat M. Efficient nesting of congruent convex figures[J]. Communications of the ACM, 1984, 27(3):228-23.

[4]贾志欣, 殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002，(5):467-470.

Jia Z X, Yin G F, Luo Y. Two-dimensional irregular parts packing with genetic algorithm[J]. Journal of Computer-aided Design & Computer Graphics, 2002，(5):467-470.

[5]于洋, 查建中,唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报,2001，(12):1242-1249.

Yu Y, Zha J Z, Tang X J. Learning based GA and application in packing[J]. Chinese Journal of Computers, 2001，(12):1242-1249.

[6]刘海明, 周炯,吴忻生.应用临界多边形方法与小生境遗传算法求解不规则排样问题[J].小型微型计算机系统,2016,37(5):1002-1007.

Liu H M, Zhou J, Wu X S. Using no-fit polygon method and niche genetic algorithm to solve irregular packing problem[J]. Journal of Chinese Mini-micro Computer Systems, 2016,37(5):1002-1007.

[7]刘胡瑶. 基于临界多边形的二维排样算法研究[D]. 上海：上海交通大学,2007.

Liu H Y. Research of Two Dimensional Nesting Algorithm Based on No Fit Polygon[D]. Shanghai:Shanghai Jiao Tong University, 2007.

[8]Blazewicz J, Hawryluk P, Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem[J]. Annals of Operations Research, 1993, 41(4):313-325.

[9]Pinheiro P R, Amaro Júnior B, Saraiva R D. A random-key genetic algorithm for solving the nesting problem[J]. International Journal of Computer Integrated Manufacturing, 2016, 29(11): 1159-1165.

[10]Baker B S, Coffman J E G, Rivest R L. Orthogonal packing in two dimensions[J]. SIAM Journal on Computing, 1980, 9:846-855.

[11]Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128:34-57.

[12]Art Jr R C. An Approach to the Two Dimensional Irregular Cutting Stock Problem[D]. Cambridge:Massachusetts Institute of Technology, 1966.

[13]Oliveira J F, Gomes A M, Ferreira J S. TOPOS-A new constructive algorithm for nesting problems[J]. OR Spektrum, 2000,22(2):263-284.

[14]李科林. 基于临界多边形的二维不规则排样问题的研究[D].武汉：华中师范大学,2019.

Li K L. Research of Two-dimensional Irregular Layout Problem Based on No-fit Polygon[D]. Wuhan:Central China Normal University, 2019.

[15]汤德佑, 周子琳.基于临界多边形的不规则件启发式排样算法[J].计算机应用,2016,36(9):2540-2544.

Tang D Y, Zhou Z L. No-fit-polygon-based heuristic nesting algorithm for irregular shapes[J]. Journal of Computer Applications,2016,36(9):2540-2544.

[16]唐萍. 衣片排样系统中局部搜索算法及其他相关问题的研究[D].广州：华南理工大学,2011.

Tang P. Research of Local Search Algorithm and Other Related Issues in Clothes Packing System[D]. Guangzhou: South China University of Technology, 2011.

[17]林庆武. 皮革智能排样系统的开发[D].杭州：浙江大学,2006.

Lin Q W. Development of Intelligent Leather Nesting System[D]. Hangzhou: Zhejiang University,2006.

[18]Adamowicz M, Albanno A. Nesting two-dimensional shapes in rectangular modules[J]. Computer Aided Design, 1976, 8(1):27-33.

[19]Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. MIT Press, 1975.

[20]Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(4): 656-667.

[21]ESICUP. EURO special interest group on cutting and packing[EB/OL]. https://www.euro-online.org/websites/esicup, 2021- 01-15.

服务与反馈：

【文章下载】【加入收藏】