基于遗传算法的啤酒灌装生产线布局设计研究

贾瑞 李光

摘要：为了体现啤酒灌装生产线布局设计的多样性，通过对传统的遗传算法进行改进，设计了用于啤酒灌装生产线布局设计的编码方式与双目标函数，验证了改进后遗传算法的可行性。

关键词：啤酒灌装生产线;设施布局;遗传算法

0    引言

啤酒灌装生产线布局问题实质上是确定设备在车间中的位置，目前通过智能算法对啤酒灌装生产线进行布局设计的论文较为少见。遗传算法作为一种自适应的优化算法，搜索过程灵活性强，且具有强大的全局寻优能力。本文采用遗传算法对啤酒灌装生产线进行布局设计，提出面向啤酒灌装生产线的布局设计方法。

1    啤酒灌装生产线的组成与说明

啤酒灌装生产线主要包含卸箱机、洗瓶机、验瓶机、灌装压盖机、杀菌机、贴标机、装箱机等。由于啤酒灌装生产线布局形式多样，求解非常困难，本文在进行啤酒灌装生产线布局设计之前做如下假设与定义：

（1）在布局过程中，忽略每台设备的形状和大小，将其视为一个点，重点考虑设备在车间中的位置。本文中用M表示各种设备的集合，M={M1，M2，…，MN}，其中N为设备的数量;（xi，yi）与（xi+1，yi+1）分别表示两个相邻设备的位置坐标。

（2）不同设备间的输送系统用直线表示，忽略其宽度;相邻两个设备间的距离大于0即认为属于可行解。

（3）为便于计算，规定平面布局空间解分别用一维空间解和二维空间解表示。

（4）车间的长、宽，设备的首、末位置分别用L、W、S、E表示。

2    基于啤酒灌装生产线布局设计问题对传统遗传算法进行改进

2.1    确定初始参数与染色体的编码、解码方式

由于本文所研究问题可能存在布局形式多样的情况，因此将相邻设备间输送系统的连接情况分为直道相连和转弯道相连两大类。

本文为解决啤酒灌装生产线布局设计问题，提出的编码与解码方式如图1所示。

图1中，M1～M5表示不同工艺设备;虚线框内M0表示输送系统的转弯点，虚线框内数字表示输送系统间的转弯位置，在编码时可将染色体分为定长与不定长两种情况;后两行分别表示设备在一维空间解中和设备在二维空间解中的位置，其中灰色数字表示设备的首末位置，黑色数字表示其他设备在空间解中的位置。染色体在一维空间解中进行编码，计算适应度值时需要解码，在二维空间解中进行计算，解码公式为：

式中：X为设备在一维空间解中的位置;W为车间的宽度;int（）为取整函数;%为取余运算;x与y分别表示设备在二维空间解中的横纵坐标。

2.2    初始化种群

为避免在计算过程中陷入局部最优解，本文提出初始化两个种群的方法。在种群A中，染色体的长度等于设备的个数，即两两设备间均以直道连接。在种群B中，染色体的长度大于设备的个数，即相邻设备间可能存在一个或多个转弯道。在初始化种群B时，可以初始化一个或多个种群，不同种群分别进化，从而保证布局结果的多样性。

2.3    个体适应度函数值的计算

本文在啤酒灌装生产线布局设计时考虑两个目标。第一个目标的计算式如下：

其中，D为两个相邻设备间的距离之和，期望D最小。为了保证布局结果的多样性，本文中两个相邻设备间的距离用欧式距离计算，w1为该目标的影响权重。

第二个目标的计算式如下：

其中，θi，i+1为任意两个相邻设备间的角度;ai，i+1为两个相邻设备间角度关系的适应度值，一般两个相邻设备间的角度为0、90°、180°、270°，如果ai，i+1不满足角度关系，则对其惩罚;A为两个相邻设备之间角度关系的适应度值之和，A的理想值为0;w2为该目标的影响权重。

综上，个体的最终适应度值可用公式（4）计算：

2.4    选择、交叉、变异操作

本文采用轮盘赌选择法进行选择。交叉操作可让部分优秀基因保留下来产生新的个体，本文选择单点交叉的方式进行交叉操作。变异也是产生新个体的一种方式，在研究过程中发现空间解比较大，因此提出让每一个基因都具备变异能力的策略。

2.5    选择最优结果

经过选择、交叉、变异操作后，会得到多个布局方案。此时，选择比较满意的一个作为参考方案。

3    算法测试与案例

为了测试该算法的可行性，本文在一个10 m×10 m大小的空间内对5台设备进行布局设计。在一维空间解中给定S=23，E=88，初始化1个种群，每个种群中有40个染色体，迭代500次。以目标一进行测试，染色体的适应度函数变化曲线如图2所示。

由图2可知，随着迭代次数的增加，染色体的适应度值越来越大，当迭代到160次左右时趋于稳定，说明在当前初始条件下适应度函数在逐步收敛。布局方案如图3黑线所示，显然两个相邻设备间的距离之和已接近最短。再以目标一和目标二同时进行测试，得到的布局方案如图3灰线所示。综上可知，该算法能快速得到比较满意的布局设计方案。

在一个50 m×40 m大小的空间内对7台设备进行布局设计。假设S=123，E=1 588，w1=0.5，w2=10。初始化2个种群，每个种群中包含100个染色体，迭代5 000次。对目标一和目标二同时进行优化，得到的啤酒灌装生产线布局设计方案如图4所示，设计用时146.385 s。

4    结语

本文通过对遗传算法进行改进，提出了啤酒灌装生产线智能布局设计方法，然后对算法进行了验证，说明了算法的有效性。但是影响啤酒灌装生产线布局设计的影响因素有很多，文中只考虑了两个方面。由于在真正对啤酒灌装生产线进行布局设计时，还需要结合客户的需求，所以在布局设计过程中还有很多参数需要不断调整，这些参数的不同取值都可能会对布局结果产生很大的影响，因此，本文所提方法还需要进一步进行更深层次的研究。

收稿日期：2020-05-27

作者簡介：贾瑞（1993—），男，山西人，硕士硕士生，研究方向：包装生产线布局优化。

通信作者：李光（1975—），男，山东人，副教授，研究方向：包装机械、包装虚拟仿真以及包装动力学。