基于改进遗传算法的二维图形优化排样方法

Optimal Layout Method for 2D Graphic Based on Improved Genetic Algorithm

在数控加工过程中,加工图形的排样优化对于提高原材料利用率,节约生产成本具有实际应用价值。采用改进的遗传算法解决这一问题,将普通的遗传算法与改进的交叉,变异算子相结合,并将最优个体保存策略融入算法,扩大了搜索空间,提高了传统遗传算法的搜索能力。在最低水平线算法基础上提出了基于水平轮廓线的最大匹配算法,在有效避免盲目升高水平轮廓线的同时,提高了最低水平线的利用率。将其与改进的遗传算法相结合,综合了两种算法的优点,很好地解决了二维矩形件优化排样问题。试验结果表明,该算法能够起到良好的优化效果。

In the process of NC machining,the optimization processing of graphic layout has practical application value for im- proving the utilization rate of raw materials and saving the cost of production.In this paper,a new design of genetic algo- rithm （GA） is proposed for solving this problem.This improved genetic algorithm combines GA with the improved crossover operator and mutation operator.Moreover,the best individual preservation method is integrated into the algorithm.The im- proved genetic algorithm expands the search space and enhances the GA＇s search capabilities.Furthermore,the maximum matching algorithm is proposed based on the lowest horizontal line algorithm,which effectively avoids blind elevating hori- zontal lines and improves the utilization rate of the lowest horizontal line.