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

A hybrid solving algorithm on two-dimensional irregular graphics nesting problem

作　　者：杜冰 郭晓强 方杰 王朋 饶运清[1] Du Bing;Guo Xiaoqiang;Fang Jie;Wang Peng;Rao Yunqing(State Key Laboratory of Digital Manufacturing Equipment and Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]华中科技大学数字制造装备与技术国家重点实验室,湖北武汉430074

出　　处：《锻压技术》2022年第3期39-45,共7页Forging & Stamping Technology

基　　金：国家自然科学基金资助项目(51975231);中央高校基本科研业务费专项基金资助项目(2019kfyXKJC043)。

摘　　要：针对二维不规则图形排样问题,实现了一种基于启发式定位策略与自适应遗传算法的混合排样算法(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.

关 键 词：二维不规则图形排样问题 混合排样算法 临界多边形 混合放置策略 自适应遗传算法 

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