一种基于改进遗传算法的烟厂卷包排产方法

2021-04-10向伟康殷军普

新型工业化 2021年7期

向伟康，殷军普

（上海威士顿信息技术股份有限公司，上海 200000）

0 引言

遗传算法作为最优化领域中的一个热点得到了广泛应用，但由于其存在算法早期收敛、耗时长、局部搜索能力差等缺陷，在实际应用中一般会基于求解问题进行针对性优化。例如，文献［2］设计了一种改进的遗传算法解决旅行商问题，引入贪婪算法初始化种群并自适应调节交叉与变异；提出了一种基于二代非劣前沿排序遗传算法的城市物流设施选址方法；基于新的编码方式提出了一种基于改进遗传算法的微小图像边缘特征快速识别方法；提出了一种改进的相对快速收敛的遗传算法，并应用到网格任务调度管理，其增加了对染色体的分割与重组[1]。本文则提出了一种基于改进遗传算法的烟厂卷包排产方法，针对烟厂卷包排产问题，采用特殊编码方式、删除了交叉算子、改进了初始化与变异算子并选择精英保留策略，以提高遗传算法的收敛速度。

1 烟厂卷包排产问题描述

烟厂卷包排产是以月为周期，当月要制定下月的生产计划。已知下月的基础数据为n台设备和m个订单。

设备属性：设备号（设备的编号）、可生产牌号（设备能生产的烟支编号）、各牌号生产速度（设备单位时间内生产指定牌号的数量）、换牌时间（从一个牌号切换生产另一个牌号时，停止生产的时间）、工班制度（设备可使用的时间段）。

订单属性：订单号（订单的编号）、需求牌号（订单所需烟支编号）、需求量（订单所需烟支数量）、需求时间点（订单需在该时间点前完成生产）。存在不同订单，需求牌号相同但需求时间点不同的情况。

排产要求：订单不拆分（每一个订单只能由一台设备连续生产）。

排产优先级：订单延期量最少、设备最晚结束时间最小、设备均衡性好。订单延期量为在需求时间点后生产该订单的数量；设备最晚结束时间为所有设备结束时间中最晚的时间点；设备均衡性是指已开启设备结束时间的均方差，值越小则设备均衡性越好[2]。

现在烟厂卷包排产需要解决的问题为：在满足排产要求的前提下，如何将m个订单按序分配给n台设备，使得制定的生产计划最佳。

2 遗传算法求解烟厂卷包排产问题

传统遗传算法求解烟厂卷包排产问题步骤如下：

（1）以订单为基础对生产顺序和生产设备进行编码。生产顺序编码为可由订单乱序后生成，si表示第i个订单乱序后的位置，排产时订单按编码从小到大的顺序进行生产；生产设备编码可从生产该订单的设备集合中随机选取一个，排产时订单按编码指定设备进行生产。现总共有m个订单，第i个订单Oi的编码对应si，c i。因此，一个个体的编码为设置种群规模为N，进行种群初始化。随机生成N个个体，种群的编码集合，每一个代表一个个体。

（2）计算种群中各个个体的适应度。首先，基于各个体编码生成排产计划；其次，根据当前的排产计划计算订单延期量v1、设备最晚结束时间v2、设备均衡性v3；再次，基于整个种群的数据分布分别对v1，v2，v3作最大最小归一化处理；最后计算适应度，ki代表vi所占适应度的比重，建议

（3）轮盘选择法选择N个个体作为新种群。已知现有种群适应度列表，v i表示第i个个体的适应度。首先，计算各个个体被随机选中的概率得到种群中个体的概率分布；然后，按序统计各个个体所代表被选中的区域其中；最后，进行N次轮盘选择，每次随机获取0到1范围内一个数r，找到所属区域即表示本次选择第i个个体。

（4）两两交叉得到新的N个个体作为新种群。首先，将现有种群中个体乱序并两两分为一组；然后，以组为单位从m个订单中随机选择一个本组的目标订单；最后，将组内两个个体中目标订单的生产设备编码互换。

（5）种群中N个个体进行变异。设置生产顺序编码变异概率和生产设备编码变异概率。先判断是否进行生产顺序编码变异，如需变异则对生产顺序编码乱序改变订单生产顺序；后判断每个订单是否进行生产设备编码变异，如需变异则获取除所选生产设备编码外的其它可生产该订单的设备集合，当集合为空则不变异，否则从中随机选择一个作为该订单新的生产设备编码。跳转到（2）。

（2）-（5）步骤不停循环选出最优个体并安排详细的生产计划。

3 改进遗传算法求解烟厂卷包排产问题

本文第2章遗传算法求解烟厂卷包排产问题时存在两个缺点：一是，随机性太大，导致求解速度慢且不易找到最优解。二是，交叉变异操作可能会使种群中个体往差的方向变化，导致算法不收敛。

因此，本章针对这些缺点做了一些改进：一是，在遗传算法初始化与变异过程中利用排产经验指导个体去接近最优解，以提高搜索速度。生产顺序编码时，让要货期早的订单优先生产，使订单延期量尽量少。生产设备编码时，让设备生产的订单量大致相同，使设备最晚结束时间早且设备均衡性好。相比于变异算子，利用排产经验指导交叉算子操作的步骤繁琐且耗时，而直接进行交叉有较大概率导致种群往差的方向变化，故删除交叉算子。二是，种群中个体在变异前保留一半较优的个体，可以防止算法不收敛[3]。

改进遗传算法求解烟厂卷包排产问题步骤如下：

（1）确定烟厂卷包排产的编码方式并初始化种群。改进遗传算法的编码方式与第2章编码方式一致，但初始化种群个体会稍有区别。首先，订单按其要货期从早到晚排序；然后，在要货期相同的订单之间进行乱序，生成生产顺序编码，其与第2章的生产顺序编码相比多添加了一个条件：当o i的要货期

（2）精英保留。计算N个个体的适应度并排序，复制并保存一半较优的个体。

（3）优化变异算子。设置生产顺序编码变异概率、生产设备编码变异概率和全局搜索概率，对N个个体分别进行变异。先进行生产顺序编码变异，基于生产顺序编码变异概率判断生产顺序是否变异，基于全局搜索概率来判断变异方式。如需变异且不为全局搜索，则只将要货期相同的订单进行内部乱序；如需变异且为全局搜索，则所有订单乱序。后进行生产设备编码变异，基于生产设备编码变异概率判断生产设备是否变异，基于全局搜索概率来判断变异方式。如需变异且不为全局搜索，则获取当前订单的所有可生产设备，统计可生产设备已被其它订单选择的次数，未被选择为0次，被目标订单选择的设备加0.5次（次数相同时，生产设备编码变化优先），从被选次数最少的设备中随机选择一个设备作为该订单新的生产设备编码；如需变异且为全局搜索，则获取当前订单除已选设备外的其它可生产设备集合，当集合为空则不变异，否则从中随机选择一个作为该订单新的生产设备编码[4]。

（4）将b中精英个体合并入c中的新种群，计算适应度并排序，选出靠前的N个个体作为新种群。

（2）-（3）-（4）步骤不停循环选出最优个体并安排详细的生产计划。

本文以解决烟厂的卷包排产问题为出发点，采用传统遗传算法来寻找最佳的卷包排产生产计划。但是，由于遗传算法求解速度慢、稳定性差、不易收敛等缺点导致其实用性很差。为了找到产生这些缺点的原因，通过分析遗传算法求解卷包排产生产计划的过程，发现其在选择、交叉、变异等操作过程中种群及个体变好变坏是随机的，例如选择操作在小概率情况下可能抛弃当前的最优个体，交叉变异操作的随机性可能导致个体变坏。为了解决传统遗传算法在实际使用中带来的这些问题，将卷包排产经验与遗传算法相结合，例如为了订单不延期则要货期早的订单肯定优先生产，为了设备均衡性好则让设备生产的订单量大致相同。遗传算法在种群初始化过程中通过卷包排产经验引导种群个体尽量靠近最优解，而在种群迭代过程中通过卷包排产经验引导种群及个体向好的方向随机变化，这样不仅可以大大提高求解速度、而且提高了算法的稳定性。同时，采用精英保留策略可以进一步提高遗传算法的求解速度。最终，形成了针对卷包排产问题的改进遗传算法[5]。