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

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

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