基于遗传算法的烟草输送机振槽排样优化算法

张世龙，赵罘，薛美荣，李娜

（北京工商大学材料与机械工程学院，北京　100048）

基于遗传算法的烟草输送机振槽排样优化算法

张世龙，赵罘，薛美荣，李娜

（北京工商大学材料与机械工程学院，北京100048）

针对烟草输送机振槽加工材料浪费率高的问题，提出了遗传算法对其进行优化排样。确定了适用于排样优化的编码方式，编写了选择算子，交叉算子及变异算子，在Matlab上编写程序并得到实现。实例测试结果表明通过遗传算法对其进行优化排样可有效提升材料利用率。

振槽；遗传算法；排样优化

0　引言

在烟草生产过程中，烟草输送一般都是通过输送机带动振槽进行往复振动，从而使得烟草在振槽中进行前进运动。由于需要长期进行往复振动，所以振槽比较容易损坏。为了保证稳定生产，需要定期更换振槽。由于烟草输送线比较长，所以振槽也相应比较长，在生产振槽过程中，往往是用多条小矩形母材加以焊接拼接而成。

然而目前多数企业在实际生产中仍是根据目测和经验，采用手工进行排样。排样工人预先用一些材料做出零件模型，当需要在板料上加工某些零件时，把这些零件的模型尽可能紧密地放在板料上，沿模型的轮廓把形状画出来，然后再进行切割。排样工人通过反复排放、比较来寻求较好的排放方案，劳动强度高、工作量大且效率和材料利用率都较低。故本文旨在基于遗传算法提出一个有效的求解输送机振槽排样问题的方法，以期提高材料的利用率。

1　遗传算法

1975年，J.H.Holland教授受生物学中“生物进化”和“自然选择”学说的启发，提出了著名的遗传算法。遗传算法可看成一种全局数值优化，它模拟基因重组与进化的自然过程，把待解问题的参数编成二进制码，称为“基因”，若干基因组成一个“染色体”。许多染色体进行类似于自然选择、杂交和变异的运算，经过多次重复运算（即世代遗传），直至得到最后的优化结果［1］。图1是遗传算法的基本流程图。

1.1数学模型

设振槽展开后矩形的长为L，宽为W。有K种矩形母材，其中长、宽分别为li、wi，即可横放也可竖放，如图2所示。

图1　遗传算法的基本流程图Fig.1 Basic flow figure of genetic algorithm

图2　数学模型图Fig.2 Figure of mathematical model

为了使得只在一个方向上有焊缝，需要所使用母材在宽度方向比目标振槽宽度宽，然后一条一条通过焊接得到最终振槽矩形。因此在纵向方向只能排放一行母材，一行上的母材只能被横放或竖放，假设板材的数量总是足够的。我们用yi表示横放时的零件个数，xi表示竖放时的零件个数。目标函数：

这是一个多维有约束离散优化问题。其已知参数为W、L、wi、li，未知参数为xi、yi。用传统优化方法很难找到有效的算法对其求解。根据遗传算法的特点，我们对这一问题考虑了遗传算法的可行性。为了使问题简单化，将一个矩形件（li，wi）看成（li，wi）和（wi，li）两种不同的矩形件考虑。这样，上面的数学模型变为以下形式。目标函数：

1.2遗传算法模型

（1）编码。染色体编码是指将矩形件排样问题的可行解从其解空间转换到遗传算法能够处理的搜索空间的解。在遗传算法中，用染色体表示问题的一个可能解，其编码方式通常有二进制编码、实数编码和符号编码等［2］。基于问题特点，此处采用十进制编码方式：每个矩形件的编号作为染色体（问题解）的一个基因，所有矩形件编号所构成的序列代表各矩形件的排样顺序，这样的一个序列就是一个染色体。

（2）选择算子。选择算子是为了避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。选择算子采用轮盘赌选择法［3］，具体过程为：①对种群中每个个体预排样，求出每个个体的适应度值，再求出所有个体的适应度值总和；②求出每个个体的相对适应度，也就是被选中概率，pi=Fi/Fsum。其中pi表示第i个个体被选中概率；Fi表示第i个个体的适应度值；Fsum表示所有个体的适应度值之和；③求出每个个体的的累积选择概率；④产生一个随机数rand=［0，1］。若rand＜qi，第一个个体被选中，否则第i个个体被选中，使qi-1＜rand＜qi成立。重复该操作，直到选择的个体数等于初始种群的个体总数。

（3）交叉算子。交叉算子在遗传算法中起着关键的作用，通过交叉可产生新的个体。常用的交叉算子有单点交叉、两点交叉、多点交叉等［4］。

设定交叉操作算子的方法如下：在染色体上选择一个位置作为交叉位置，交叉位置之前的基因片段不交叉，交叉位置之后的片段交叉。比较两个参与交叉的染色体，将交叉位置之前的相同基因去除，将交叉位置之前的剩余基因顺序不变的存入数组p［］和q［］中。然后对染色体的交叉部分进行交叉，若交叉部分的基因不等于这两个数组中基因，则直接交换；若与数组中的基因相同，则先把相同基因换成数组p［］或q［］中对应基因之后再交换。

（4）变异算子。变异算子是将染色体中的某些基因位上的基因值加以改变，从而产生一个新的个体。变异算子一方面可以使遗传算法具有局部的随机搜索能力，另一方面有助于遗传算法维持群体的多样性，防止出现早熟现象［5］。

（5）停止准则。遗传算法收敛判断准则较多，比较常见的是根据迭代次数以及解的质量来判断。迭代次数是表示遗传算法运行终止条件的一个主要参数，它表示遗传算法运行到规定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。

2　振槽排样优化实例及分析

本文通过上述的遗传算法编制了计算程序，并在Matlab上进行了实现。在实验中取群体规模N=40，交叉概率Pr=0.7，变异概率Pm=0.05或0.15。企业现用的母材数据如表1所示。

表1　矩形件信息Tab.1 Rectangular parts information

共有4种母材，每种母材的数量都是一定的，现在要加工一个输送机振槽，振槽展开后矩形的长为16000mm，宽为1200mm。为了得到这个振槽，在Matlab上通过500代的迭代计算，当变异概率为0.05时，得到排样的材料利用率为96.69%，当变异概率为0.15时，得到排样的材料利用率为97.65%。

可见本文提出的排样算法在提高板材利用率方面有一定的优越性。

3　结论

本文用遗传算法来求解烟草输送机振槽的排样问题，可有效解决振槽在加工生产中浪费材料和费时、费工的问题。

到目前为止，对优化排样问题的研究，无论是一维、二维还是三维，带约束或不带约束，都没有出现针对这一问题的系统化解决方案。由于问题的多样性，大多数研究都只是停留在对某些算法的部分改进，以适应各自的问题，假如能够建立一套完整的排样理论体系，必将大大推进排样问题的研究，减少重复性工作。

［1］曹炬，周济.矩形件排样优化的一种近似算法［J］.计算机辅助设计与图形学学报，2009，3.

［2］刘德全，滕弘飞.矩形件排样问题的遗传算法求解［J］.小型微型计算机系统，1998，12.

［3］赵新芳，崔耀东，徐莹.矩形件带排样的一种遗传算法［J］.计算机辅助设计与图形学学报，2008，4.

［4］减辉.遗传算法及其应用［J］.武汉科技学院学报，2005，4.

［5］叶军君，殷国富.板材下料优化排样CAD系统的研究［J］.现代制造工程，2004，10.

Optimization Algorithm for Vibration Slot of Tobacco Vibrating Conveyor Based on Genetic Algorithm

ZHANG Shi-Long，ZHAO Fu，XUE Mei-Rong，LI Na
（School of Materias and Mechanical Engineering，Beijing Technology and Business University，Beijing 100048，China）

Aiming at the problem of high wastage rate of vibration slot processing material in tobacco conveyer，the genetic algorithm was proposed to optimize the layout.Encoder mode of layout optimization was determined.The selection operator，crossover operator and mutation operator were designed，and the program was written in Matlab.The test results of the examples show that the method can effectively improve the utilization of materials by the genetic algorithm.

vibration slot；genetic algorithm；layout optimization

TH122

A

10.3969/j.issn.1002-6673.2015.06.014

1002-6673（2015）06-040-03

2015-09-10

项目来源：北京工商大学研究生科研能力提升计划项目资助（2015）

张世龙（1991-），男，河南信阳人，研究生。主要研究方向：机械设计及理论；通讯作者：赵罘（1972-），男，吉林长春人，副教授。