遗传算法求解一维下料问题

1、遗传算法求解一维下料问题作 者：张勇杰学 号：SA10157018指导老师：李 斌背景知识下料问题(cutting stock problem)是把相同形状的一些原材料分割加工成若干个不同规格大小零件的问题, 这类问题经常出现在计算机科学、工业工程和机械制造等领域, 在工程技术和工业生产中有着重要和广泛的应用。一维下料问题就是对不同长度材料的组合配搭, 以使材料的利用率最高，从而达到节省成本的目的。这类优化问题在型材、管材、金属结构材料、建筑材料等的下料中广泛存在1。精确求解下料问题属于NP问题, 再加上下料方式数等限制后, 这类问题的求解是比较复杂的, 目前还不可能用一个精确的方法来求此问题

2、2。当前，国内外关于这方面的研究比较活跃，涌现出了不少近似算法，如线性规划、动态规划方法等。但当原材料的数量和所需产品的个数都很大时，问题的规模会迅速增加变得非常复杂, 利用这些算法求解不具有可操作性且很难或者几乎不可能得到最优方案。由于下料问题不同于一般的数值性优化, 近年来又出现了应用遗传算法、蚁群算法2、贪婪算法、启发式算法等算法和思想求解下料优化问题, 但这些新的算法不可避免会出现收敛速度慢, 陷入局部极小值, 计算时间长等问题。 1 实验目的本文通过采用遗传算法，对编码方式、选择算子、交叉算子以及适应度函数等进行优化，从而探索一种用来求解一维下料问题的收敛速度较快、结果较为优秀的有效

3、、可行算法。2 技术方案2.1 一维下料问题描述 通常, 在实际生产中, 经常会遇到以下形式的下料问题:给定若干长度一定的原材料, 现要使用这种原材料进行下料, 生产若干种规格、数量不同的零件, 应如何下料才能使材料的利用率最大, 以达到减少材料损失、降低成本、提高经济效益的目的, 这就是典型的一维下料问题1。应用遗传算法求解时，具体的目标有两个：一是使原材料的消耗数最小，二是使原材料余量的最大值尽可能大。2.2 编码方法根据一维下料的实际问题，可以选择以实数表示的各零件长度的一个排列作为一个可行解，对问题的解集进行编码，构成一个染色体，其中每个零件的长度构成一个基因。但是考虑到以上的编码方法

4、在采用传统的单点交叉时，可能会导致非法解的产生。为此，下面采用了一种与上述编码方法一一对应的随机键编码方法。随机键表达首先是由Bean提出的。这种表达方法将解表达为一串（0，1）间的随机数。这些随机数用作解码的分类键3。在一维下料问题中，可以将零件的长度排列用一个初始的一维数组来表示。例如，一个9个零件构成的初始数组可表示为l1，l2，l3，l4，l5，l6，l7，l8，l9 一个9个零件长度构成的染色体为0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78 其中，编码位置i代表li位置i的随机数的大小表示li在编码中的顺序。将这些随机数按升序排列，可得到对

5、应的编码为l6，l1 ，l3 ，l7，l8， l4， l9，l2，l5解空间通过用随机键来表达后，在采用传统的单点交叉后，将不再产生非法解。2.3 适应度函数下料问题的优化目标有二：一是使原材料的消耗数最小，二是使原材料余量的最大值尽可能大。意思就是首先尽量减少产生的废料，其次，在产生的废料一定的情况下，使其中一条整材的废料最长。本文为避免多目标优化可能带来的问题，将两个目标合而为一，采用一个小数来表示消耗的原材料数，即 e=n-lrel0 （2-1）式（2-1）中，e为小数表示的原材料数，n为整数表示的原材料数，lre为废料中最长的一段，l0为原材料的长度。如此，问题即变为单目标优化，即求出

6、e的最小值即可。由于问题转变为求e的最小值，故e不能直接作为适应度参与选择运算。为了加快收敛速度，同时为了给适应度稍好的个体更大的奖励，本文设计的适应度函数为F=(max（num）-num(i)+ +0.000000001)10 （2-2）式（2-2）中，F为适应度值，num为一代群体中小数表示的原材料消耗数（即e的值）的数组。通过式（2-2）的适应度计算，使e值较小的编码的适应度远大于e值较大的编码的适应度。这样，使得算法在前期收敛较快，在后期得到最优解的可能大大增加。2.4 交叉算子本文采用传统的单点交叉，即随机地选择一个断点，交换双亲上断点的右端，生成两个新的个体。与传统的交叉算子不同的

7、是，为了抑制算法的震荡，本文采用了父代与子代竞争的机制，即评估父代与子代四个个体的适应度，从中选择两个适应度较高的个体作为后代输出。2.5 变异算子本算法采用了互换变异的方法3。首先根据变异概率随机地选出变异的染色体，然后随机地选择编码中的两个位置，并将这两个位置的基因相互交换。2.6 算法过程描述（1）初始化，置迭代的最大次数，选择杂交的概率proprepro和变异的概率propvari，种群规模数initsize，并随机生成initsize个个体。（2）对群体依次进行评估，计算适应度，并将适应度最高的个体保留，同时记录其原材料消耗数。（3）对群体执行选择算子，按照适应度选择出较好的个体组成

8、新的群体。（4）按照交叉概率proprepro，随机地选择出待交叉的个体执行交叉运算，交叉产生的新的个体替代原来的个体组成新的群体。（5）按照变异概率propvari，随机地选择出待变异的个体执行变异运算，变异产生的新的个体替代原来的个体组成新的群体。（6）将保留的最优个体放回群体中，替代对应的个体。（7）迭代次数是否已到，若是则执行下一步，否则转（2）。（8）输出最优解，算法结束。3 计算实例利用上面设计的算法对网络布线问题中的网线分割进行优化计算，以下是具体的计算例子。现需总长度2016米, 长度分别为4, 27, 83, 84,9, 22, 10, 48, 85, 64, 17, 32,

9、 38, 41, 50, 30, 53, 43, 3,60, 7, 93, 15, 91, 60, 98, 21, 31, 45, 79, 48, 72, 81, 67,67, 75, 53, 56, 88, 66米的网线40段, 求所需每箱长度为305米的网线箱数及分割方案。4 实验结果及分析图1为程序运行30次后的结果分布图。从图中可以看出，30次实验中计算的原材料消耗数均为7（整数表示），不同的仅是余料的最大值，且最长余料全部分布在116米到119米之间。通过统计计算得出，最长余料的平均值为117.7米，方差为1.0767。不计最大余料时的材料利用率的平均值为99.94% 。图1 30次

10、实验结果分布图表1给出了30次实验中最优的实验结果之一所对应的原材料切割方案。所需网线数为7箱，合计余料长度为119米，最大余料长度为119米，在不计最大余料时，材料的利用率为100% 。整料号1234567合计下料方案60,31,32 48,3,38 43,5067,17,22 60,9,64 6688,81 91 ,4572,93 53,4 837,53,48 79,10 41 ,6730,56,21 98,15 8575 84 27利用长度3053053053053053051862016预料长度000000119119表1 原材料切割方案5 算法的优缺点分析优点：算法在具体问题的实验中

11、，往往能得到很好的解。算法采用了最优保留策略、父代和子代竞争的机制，使得随着繁殖代数的增加，个体的适应度不断增加。算法的适应度函数对优秀解有较高的额外奖励机制，使得对群体执行选择算子时，优秀解被选到的概率大大增加。但这一额外奖励机制却没有导致群体的多样性丧失，这是由于解空间的规模和编码的冗余度都较大的缘故。 缺点： 以实数表示的各零件长度的一个排列对解空间中的一个解进行编码，这样的编码方案具有很高的冗余度，即一种切割方案对应很多种的编码。原因来自两个方面：一是一根原材料切割的n个零件有Ann中排列方式；二是消耗原材料m根，有Amm中排列方式。较高的编码冗余度带来的是算法的收敛时间过长。6 结论本文以实数表示的各零件长度的一个排列对一个可能解进行编码, 其中的每个零件长度为一个基因。同时为了防止算法的震荡和加快算法的收敛，试验中采用了最优保留策略和父代和子代竞争策略。实验结果证明该算法最终能收敛