论文部分内容阅读
摘 要： 针对一维下料优化问题，在对一维下料方案数学模型分析的基础上，提出了基于改进遗传算法的优化求解方案。主要思想是把零件的一个顺序作为一种下料方案，定义了遗传算法中的关键问题：编码、解码方法、遗传算子和适应度函数的定义。该算法设计了一种新颖的遗传算子，包括顺序交叉算子、线性变异算子、扩展选择算子。根据这一算法开发出了一维下料方案的优化系统。实际应用表明，该算法逼近理论最优值，而且收敛速度快，较好地解决了一维下料问题。
关键词： 一维下料； 遗传算法； 最优交叉； 优化
中图分类号：TH122；TP391.7 文献标志码：A 文章编号：1006-8228（2014）01-36-02
0 引言
一维下料优化问题是讨论从一种规格的材料中，分切出各种不同长度的坯料，以使材料的利用率最高。这类优化问题在机械、建筑、木材，甚至布料等行业中具有广泛而实际的应用。一维下料问题属于NP难问题。国内外关于这方面的研究十分活跃，并且提出了不少优化算法，如Dyckhoff H.提出的线性规划方法[1]以及Sarker B. R.提出的动态规划方法[2]等。但这些算法过于复杂，也未能有效地解决巨大数量切割方式的优选问题。本文讨论以传统遗传算法为基础，改进了传统的交叉算子、变异算子和选择算子，实现了不错的效果，能够在较短的时间内得到利用率较高的排样方式。
1 一维下料问题的数学模型
1.1 问题定义
1.2 数学模型
根据问题描述，首先找到这些零件的组合方式，即哪几个零件组合使得每一个原材料的余料最小，假设有m种下料方式。根据每种零件的需求量，求取每一种下料方式应用的次数：
求出每种下料方式所产生的余料长度：
2 一维下料方案优化问题的求解方法
2.1 编码方法
2.2 解码方法
由编码方法产生个体的编码后，需通过解码算法得到其所需原材料的数目，计算其适应度值后，才能对该个体进行评价，相应的解码算法如下。
2.3 适应度函数
对于一维下料问题，用适应度函数来评价遗传算法时，适应度越大，解的質量越好，自然的想法是取所需原材料总概数的倒数，但当二种方案需要原材料根数相同时，则最后一根余料较长者显然更优，所以本算法采用的适应度函数是：，其中Qm为所用的原材料数量，L'为最后根原材料所用的长度。那么适应度最高为1。
3 一维下料方案遗传算法的求解过程
3.1 初始种群
3.2 遗传算子
⑴ 交叉算子
基于生物进化学说，两个优秀的父辈得到的子代往往是比较优良的，而两个较差的父辈得到的子代往往不会优秀。因此本算法交叉算子的设计采用顺序交叉的方案[4]，即将父辈按适应度降序排序后，采用双点交叉算子按顺序相邻二二交叉，该算子是在父序列P1中随机产生两个交叉位b1与b2，在这两个随机位之内的元素将复制到新的序列Pnew的对应位置。剩余的元素按父序列P2的先后顺序依次复制到Pnew，得到新的序列Pnew。以同样的方法得到另一个新的子序列Qnew。
⑵ 变异算子
传统遗传算法的变异算子主要有位置变异与颠倒位序变异。位置变异是在序列中随机得到两个随机位，并将这两个随机位的元素加以对换。颠倒位序变异是在序列中随机得到一个随机位，并在这随机位之后的元素加以颠倒。本算法还采用了模拟基因突变的缺失与增添。缺失是父序列中随机取出一个变异位，在该变异位之后的位都向前移一位，最后将取出的变异位添加到最末位。增添是在父序列上随机得到一个变异位。将在此变异位之后的位都向后移一位，最后将父序列中最后的位添加到变异位得到新的子序列。由这两种算子加上传统的位置变异与颠倒序列变异，在变异概率下，有一定概率执行前面四种变异算子，这样一来进化的多样性会大大提高，更有概率能接近最优解。
传统的变异率是恒定不变的。基于生物进化学说，两个优秀的父代得到的子代往往是比较优良的，而两个较差的父代往往得到的子代不会优秀。所以在遗传算法进化的初期，上一代的适应度往往不会太高，经过交叉之后往往也不尽如人意。因此较高的变异率则是有助于尽快地进化得到较好的下一代。而在进化的后期，上一代的适应度往往趋近于最高，较高的变异率有可能破坏原有的优良基因，导致子代的适应度降低。基于这样考虑，该系统采用线性的变异率，变异率随着遗传代数的增加而降低。变异率的线性变化公式为：R=（0.8G-g）/G+0.1，其中R为当前代数的变异率，G表示的是遗传算法需要进化的总代数，而g表示当前的进化代数。可以看出变异率的范围是从0.1到0.9。这是因为在进化的后期也需要一定的变异率用来提高下代种群的适应度。
⑶ 选择算子
传统的遗传算法是由上一代经过交叉与一定概率的变异得到两个下一代。而有可能存在的问题就是在上一代经过交叉之后就得到了适应度较高的个体，再经过变异之后适应度有所降低。因此本算法采用扩展选择算子，由上一代经过交叉后得到两个子代，与由这两个子代个体经过一定概率的变异得到两个子代个体并存。最后将得到的子代与父代通过计算适应度筛选出nScale个最优个体交给下一次进化。如此就避免进化途中的浪费，错过适应度较高的解。
3.3 结束条件
重复执行上面的⑴、⑵、⑶步骤，直到最好解的适应度值达到要求或满足了预定的进化代数，才能停止计算，并输出最优解。
4 计算实例
为了测试本算法的性能，我们借鉴文献[5]中的例子。原材料长3m，需切割的零件分别为长2.2m的3件、长1.8m的3件、长1.2m的4件、长0.5m的6件、长0.3m的6件。求最优下料方案（不考虑切口损失）。
文献[5]采用启发式多级序列线性优化方法计算，能保证高的材料利用率，而且计算速度也高。但随着零件规模的扩大，计算时间也会爆炸。而基于改进遗传算法的求解方法虽然对同一问题需要多次运行，从多种下料方案中择优，但计算仅用0.6s就取得了最好解，而且是求解组合爆炸问题的最好选择。表1和表2是文献[5]与本文算法的对比。
表2若不计编号8的原料，则余下的原料利用率都为100%。而编号8的原料具备最长的余料，还可以进一步利用。计算结果很理想。
5 结束语
本文针对工程实际中的一维下料问题，提出了求解该类问题的改进遗传算法，该算法设计简单，原理易于理解。实例计算结果证实了本算法的有效性，而且计算时间较短，同时，原材料的利用率也达到了较高的水平，对同一问题多次运行可以给出多种利用率相近的方案，便于从多个优化结果中择优，可以满足生产的需要。今后对于排样问题的研究，还须对多目标优化给予重视，以满足各种生产环境的需求。
参考文献：
[1] Dyckhoff H. A New Linear Programming Approach to the Cutting
Stock Problem[J].Opns Res，1981.29（6）：1094-1104
[2] Sarker B R. An optimum solution for one dimensional slitting
problems：A Dynamic Programming Approach[J].J opl Res Soc，1988.39（8）：749-755
[3] 贾志新，殷国富，胡晓兵等.一维下料方案的遗传算法优化[J].西安交
通大学学报，2002.36（9）：967-970
[4] 吴迪，李长荣等.基于蜂群遗传算法的一维优化下料问题[J].计算机
技术与发展，2010.20（10）：82-85
[5] 王小东，李刚，欧宗瑛.一维下料优化的一种新算法[J].大连理工大学
学报，2004.44（3）：407-411
关键词： 一维下料； 遗传算法； 最优交叉； 优化
中图分类号：TH122；TP391.7 文献标志码：A 文章编号：1006-8228（2014）01-36-02
0 引言
一维下料优化问题是讨论从一种规格的材料中，分切出各种不同长度的坯料，以使材料的利用率最高。这类优化问题在机械、建筑、木材，甚至布料等行业中具有广泛而实际的应用。一维下料问题属于NP难问题。国内外关于这方面的研究十分活跃，并且提出了不少优化算法，如Dyckhoff H.提出的线性规划方法[1]以及Sarker B. R.提出的动态规划方法[2]等。但这些算法过于复杂，也未能有效地解决巨大数量切割方式的优选问题。本文讨论以传统遗传算法为基础，改进了传统的交叉算子、变异算子和选择算子，实现了不错的效果，能够在较短的时间内得到利用率较高的排样方式。
1 一维下料问题的数学模型
1.1 问题定义
1.2 数学模型
根据问题描述，首先找到这些零件的组合方式，即哪几个零件组合使得每一个原材料的余料最小，假设有m种下料方式。根据每种零件的需求量，求取每一种下料方式应用的次数：
求出每种下料方式所产生的余料长度：
2 一维下料方案优化问题的求解方法
2.1 编码方法
2.2 解码方法
由编码方法产生个体的编码后，需通过解码算法得到其所需原材料的数目，计算其适应度值后，才能对该个体进行评价，相应的解码算法如下。
2.3 适应度函数
对于一维下料问题，用适应度函数来评价遗传算法时，适应度越大，解的質量越好，自然的想法是取所需原材料总概数的倒数，但当二种方案需要原材料根数相同时，则最后一根余料较长者显然更优，所以本算法采用的适应度函数是：，其中Qm为所用的原材料数量，L'为最后根原材料所用的长度。那么适应度最高为1。
3 一维下料方案遗传算法的求解过程
3.1 初始种群
3.2 遗传算子
⑴ 交叉算子
基于生物进化学说，两个优秀的父辈得到的子代往往是比较优良的，而两个较差的父辈得到的子代往往不会优秀。因此本算法交叉算子的设计采用顺序交叉的方案[4]，即将父辈按适应度降序排序后，采用双点交叉算子按顺序相邻二二交叉，该算子是在父序列P1中随机产生两个交叉位b1与b2，在这两个随机位之内的元素将复制到新的序列Pnew的对应位置。剩余的元素按父序列P2的先后顺序依次复制到Pnew，得到新的序列Pnew。以同样的方法得到另一个新的子序列Qnew。
⑵ 变异算子
传统遗传算法的变异算子主要有位置变异与颠倒位序变异。位置变异是在序列中随机得到两个随机位，并将这两个随机位的元素加以对换。颠倒位序变异是在序列中随机得到一个随机位，并在这随机位之后的元素加以颠倒。本算法还采用了模拟基因突变的缺失与增添。缺失是父序列中随机取出一个变异位，在该变异位之后的位都向前移一位，最后将取出的变异位添加到最末位。增添是在父序列上随机得到一个变异位。将在此变异位之后的位都向后移一位，最后将父序列中最后的位添加到变异位得到新的子序列。由这两种算子加上传统的位置变异与颠倒序列变异，在变异概率下，有一定概率执行前面四种变异算子，这样一来进化的多样性会大大提高，更有概率能接近最优解。
传统的变异率是恒定不变的。基于生物进化学说，两个优秀的父代得到的子代往往是比较优良的，而两个较差的父代往往得到的子代不会优秀。所以在遗传算法进化的初期，上一代的适应度往往不会太高，经过交叉之后往往也不尽如人意。因此较高的变异率则是有助于尽快地进化得到较好的下一代。而在进化的后期，上一代的适应度往往趋近于最高，较高的变异率有可能破坏原有的优良基因，导致子代的适应度降低。基于这样考虑，该系统采用线性的变异率，变异率随着遗传代数的增加而降低。变异率的线性变化公式为：R=（0.8G-g）/G+0.1，其中R为当前代数的变异率，G表示的是遗传算法需要进化的总代数，而g表示当前的进化代数。可以看出变异率的范围是从0.1到0.9。这是因为在进化的后期也需要一定的变异率用来提高下代种群的适应度。
⑶ 选择算子
传统的遗传算法是由上一代经过交叉与一定概率的变异得到两个下一代。而有可能存在的问题就是在上一代经过交叉之后就得到了适应度较高的个体，再经过变异之后适应度有所降低。因此本算法采用扩展选择算子，由上一代经过交叉后得到两个子代，与由这两个子代个体经过一定概率的变异得到两个子代个体并存。最后将得到的子代与父代通过计算适应度筛选出nScale个最优个体交给下一次进化。如此就避免进化途中的浪费，错过适应度较高的解。
3.3 结束条件
重复执行上面的⑴、⑵、⑶步骤，直到最好解的适应度值达到要求或满足了预定的进化代数，才能停止计算，并输出最优解。
4 计算实例
为了测试本算法的性能，我们借鉴文献[5]中的例子。原材料长3m，需切割的零件分别为长2.2m的3件、长1.8m的3件、长1.2m的4件、长0.5m的6件、长0.3m的6件。求最优下料方案（不考虑切口损失）。
文献[5]采用启发式多级序列线性优化方法计算，能保证高的材料利用率，而且计算速度也高。但随着零件规模的扩大，计算时间也会爆炸。而基于改进遗传算法的求解方法虽然对同一问题需要多次运行，从多种下料方案中择优，但计算仅用0.6s就取得了最好解，而且是求解组合爆炸问题的最好选择。表1和表2是文献[5]与本文算法的对比。
表2若不计编号8的原料，则余下的原料利用率都为100%。而编号8的原料具备最长的余料，还可以进一步利用。计算结果很理想。
5 结束语
本文针对工程实际中的一维下料问题，提出了求解该类问题的改进遗传算法，该算法设计简单，原理易于理解。实例计算结果证实了本算法的有效性，而且计算时间较短，同时，原材料的利用率也达到了较高的水平，对同一问题多次运行可以给出多种利用率相近的方案，便于从多个优化结果中择优，可以满足生产的需要。今后对于排样问题的研究，还须对多目标优化给予重视，以满足各种生产环境的需求。
参考文献：
[1] Dyckhoff H. A New Linear Programming Approach to the Cutting
Stock Problem[J].Opns Res，1981.29（6）：1094-1104
[2] Sarker B R. An optimum solution for one dimensional slitting
problems：A Dynamic Programming Approach[J].J opl Res Soc，1988.39（8）：749-755
[3] 贾志新，殷国富，胡晓兵等.一维下料方案的遗传算法优化[J].西安交
通大学学报，2002.36（9）：967-970
[4] 吴迪，李长荣等.基于蜂群遗传算法的一维优化下料问题[J].计算机
技术与发展，2010.20（10）：82-85
[5] 王小东，李刚，欧宗瑛.一维下料优化的一种新算法[J].大连理工大学
学报，2004.44（3）：407-411