一维下料的改进遗传算法优化

针对一维下料优化问题,在对一维下料方案数学模型分析的基础上,提出了基于改进遗传算法的优化求解方案。主要思想是把零件的一个顺序作为一种下料方案,定义了遗传算法中的关键问题:编码、解码方法、遗传算子和适应度函数的定义。该算法设计了一种新颖的遗传算子,包括顺序交叉算子、线性变异算子、扩展选择算子。根据这一算法开发出了一维下料方案的优化系统。实际应用表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题。

Optimization for one dimensional cutting stock problem based on improved genetic algorithm

One dimensional stock cutting problem is a typical combinatorial optimization problem. In this paper, an improved-genetic algorithm model for solving the one-dimensional cutting stock problem is presented after analyzing the mathematical model. The main idea is to use an order of parts as a solution, and define the key problems in applying genetic algorithm： coding, decoding, and definition of adaption degree functions. A new genetic algorithm is designed to include order crossover operator, linear mutation operator and expand-selection operator. An optimal system for one dimensional cutting stock problem is developed based on the method. The practice shows that the algorithm approaches the theoretical optimal solution, its convergence rate is quick, so that it solves one-dimensional cutting stock problem quite well.