基于改进遗传禁忌搜索算法的二维不规则件排样优化  

Layout optimization on two-dimensional irregular parts based on improved genetic tabu search algorithm

作　　者：梁金龙 毛文志 栾显晔 徐金亭[1] Liang Jinlong;Mao Wenzhi;Luan Xianye;Xu Jinting(School of Automotive Engineering,Dalian University of Technology,Dalian 116024,China;Shandong SIASUN Industrial Software Research Institute Co.,Ltd.,Jinan 250013,China)

机构地区：[1]大连理工大学汽车工程学院,辽宁大连116024 [2]山东新松工业软件研究院股份有限公司,山东济南250013

出　　处：《锻压技术》2024年第4期54-61,89,共9页Forging & Stamping Technology

基　　金：国家自然科学基金资助项目(51975097)。

摘　　要：针对二维不规则钣金件排样问题,提出一种融合临界多边形(NFP)定位和改进遗传禁忌搜索算法的排样优化方法。首先,根据零件的几何特征对其进行分类编码,求解零件类间的NFP,避免NFP的重复计算,同时引入以排样高度最小化为目标的启发式规则,给出零件定位策略的综合评价函数,以提高板材利用率。其次,在零件排序优化时,将遗传算法中的精英群体作为禁忌搜索算法的高质量初始解,减少计算资源消耗。最后,利用欧洲切割和包装特别兴趣小组ESICUP提供的标准算例对所提排样方法进行测试。结果表明:相比传统遗传禁忌搜索算法,所提排样方法的计算效率提升了28.32%~80.23%,并且在与两种现有算法的7个基准测试对比中,所提排样方法均取得了最优排样结果。Aiming at the layout problem of two-dimensional irregular sheet metal parts,an layout optimization method integrating no-fit polygon(NFP)localization and improved genetic tabu search algorithm was proposed.Firstly,the parts were classified and coded according to the geometric characteristics,and the NFP between parts was solved to avoid the repeated calculation of NFP.At the same time,the heuristic rule with the goal of layout height minimization was introduced,and the comprehensive evaluation function of the localization strategy for parts was given to improve the utilization rate of sheet material.Secondly,the elite population in the genetic algorithm was used as the high-quality initial solution of the tabu search algorithm to reduce the consumption of calculational resources in the nesting optimization of parts.Finally,the proposed layout method was tested using benchmark examples provided by the European special interest group on cutting and packing(ESICUP).The results show that compared with the traditional genetic tabu search algorithm,the calculational efficiency of the proposed layout method is improved by 28.32%-80.23%,and the best layout results are achieved by the proposed layout method during the seven benchmark tests compared with the two existing algorithms.

关 键 词：二维不规则件 临界多边形 启发式规则 精英策略 遗传禁忌搜索算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]