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

基于变长编码求解一维下料问题的演化算法 An Evolutionary Algorithm of One Dimensional Stock Cutting Problem Based on Variable Length Coding 李元香 LI Yuan xiang 1 first-author 张进波 ZHANG Jin bo 1 徐静雯 XU Jing wen 1 王琳 WANG Lin 1 武汉大学软件工程国家重点实验室,湖北,武汉,430072 武汉大学软件工程国家重点实验室,湖北,武汉,430072 State Key Laboratory of Software Engineering,Wuhan University State Key Laboratory of Software Engineering,Wuhan University 针对一维下料问题的特点 ,将线性规划方法与演化算法相结合 ,提出了一种基于变长编码求解一维下料问题的演化算法 .该算法设计了一种新颖的遗传算子 ,实现简单 ,求解快速 .实验表明 ,运用该法求解下料问题 ,材料利用率高 ,平均达到 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.\; 下料问题 整数规划 线性规划 演化算法 linear programming integer programming evolutionary algorithm stock cutting problem TP399 国家自然科学基金资助项目 （ 6970 3 0 3 0 11） 2001-03-01 2021-04-01 3