基于变长编码求解一维下料问题的演化算法

An Evolutionary Algorithm of One Dimensional Stock Cutting Problem Based on Variable Length Coding

针对一维下料问题的特点 ,将线性规划方法与演化算法相结合 ,提出了一种基于变长编码求解一维下料问题的演化算法 .该算法设计了一种新颖的遗传算子 ,实现简单 ,求解快速 .实验表明 ,运用该法求解下料问题 ,材料利用率高 ,平均达到 97.5 %以上 ,具有很好的实用价值 .

One dimensional stock cutting problem is a typical combinatorial optimization problem,on which many recent research work are concerning. In this paper, an algorithm for the problem coupling the linear programming and the evolutionary algorithm is proposed, which is based on variable length coding and a designed novel genetic operator. Experiments show that our algorithm is easy of implementation and fast to produce satisfactory results. The usage rate of material is up to 97.5% on average and it is convenient to put into practice.\;