改进多种群杂交遗传算法在作业车间调度的研究

刘兴刚

摘要：通过提出应用最广泛的混合型作业车间的调度问题以及遗传算法的基本原理，并结合生产车间调度问题的特点，对传统单种群遗传算法改进了改进。新遗传算法中加入辅助种群，保证种群的多样性，解决单个种群的遗传算法容易陷入局部收敛而出现早熟的情况。并应用实例对比分析，表明算法在车间调度系统的有效性和合理性。

关键词：车间调度；遗传算法；多种群；并行

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）07-1496-04

1 概述

随着经济全球化趋势的发展，各国制造业进入全球供应链生产体系。大型生产型企业相继转入生产高效率，多品种、小批量和定制化生产模式。供需链环境下的制造业生产调度系统模式，最终提出了生产调度系统的集成化、动态化、高效智能化、柔性化等发展方向。作业车间调度问题（JSP）尤为突出，由于问题计算的复杂性，各种不同规模的车间，生产类型的交叉，很难找到一个适应性，通用性很强的运算机制。遗传算法借鉴生物进化论机制，从一个较大的初始解空间入手，结合生物界优胜劣汰的法则进行求解，具有全局优化、隐含并行、自组织、自适应等特点。

传统的遗传算法有几个较大的缺陷，应用求解JSP问题时存在不足：（1）容易表现近亲结合现象，出现早熟收敛问题；（2）进化后期搜索效率低，使得最终得到的结果往往是局部最优解，不是全局最优解；（3）所求得的最优解的受初始种群的影响较大。

为了克服这些局限性，国内外都对其进行改进。文献[4]应用传统遗传算法（Genetic Algo-rithm，GA）来求解各类车间调度问题，简单、容易实现，说明GA在求解调度问题中的可行性和有效性。文献[2]通过改变交叉和变异概率设计新的算子以及引入新个体，进行多种改进。但综合各个改进，其改进局限于单一种群遗传算法，不能在理论上突破思维界限，故本文引入辅助種群进行改进。

2 建立车间调度的模型

3 遗传算法的改进

3.1 编码方式的设计

目前已经提出的编码方式包括：基于工序、工件、优先规则、完成时间、优先表、机器等。结合已有的工作经验，大型生产型企业会将生产步骤简化，以求各种水平的员工都能尽快适应车间工作。故只需采用经典的基于工序的字符串编码方法即可。定义工件编号为01， 02，…n，每个工件的工序编号为01，02，…k，机床编号为01，02，…m。则每个基因由n、k和m按顺序组成，如：基因010101表示工件01的01工序在设备01上完成。绝大多数生产工序都是路径柔性，在个体生成过程中，随机的机床中选择一个，生成个体的一个基因。这样生成的一个个体表示一个确定路径的工序排序。个体的长度是所有工件的工序数量之和，与机床的数量无关。

3.2 设计约束条件

在大型生产型企业车间调度中， 调度方案应满足3.1中设定的约束条件。综合各类文献，常用的约束条件处理方法有惩罚函数法、解码器法和算子修正法等。结合数学最优化算法的理念，提高约束条件的处理效率，引入可能解的概念，即符合可行解的一个或多个必要约束条件的解集。定义可能解约束条件：每个个体中，表示同一工件工序的基因按照工序号从小到大的顺序排列，即表示同一工件工序的基因中，工序号小的在前面。初始种群生成过程是：

1）随机产生个体的部分基因；（2）由解约束条件决定，生成个体的其他基因，使个体其他基因都属于可能解；（3）根据可行解约束条件， 判断其是否属于可行解，如果是则其加入种群，否则拒绝加入；（4）判断是否达到种群规模要求，是则结束，否则转（1）。经过以上循环，使种群生成过程中大大减少了随机试探的次数，节约了遗传算法的运行时间。

3.3 优化辅助子种群的生成

首先明确多种群并行遗传算法的基本思想：利用多个种群并行进化，引入辅助种群中部分优良个体参与主种群进化，以打破主种群的平衡态达到更高的平衡态， 跳出局部最优。用多个子种群代替原始种群在可行解域进行搜索，生成对原种群进行优化的辅助子种群，将遗传算法分解为在多个子种群间并行进行，并通过子种群间交换信息来增加基因模式数，避免未成熟收敛。为选择出最优个体，需要设置辅助种群的修正条件，并判断个体的优劣。

3.3.1 设置种群的修正条件

通过分析要改进的遗传算法的进化过程可知，最需要改进的阶段就是算法即将进入早熟状态阶段，因此把“接近或进入早熟收敛状态”作为引入辅助种群的进行修正的条件。早熟收敛具体分以下表现：种群不能继续增加最大适值；种群中个体的具有很大的相似性，使得种群的多样性大大降低。结合多位学者的研究表明个体的相似性越高，相应的算法的计算量越大。故通过设定临界遗传代数τ来界定最大适应值增加的幅度。修正条件定义为：大于遗传代数τ后，种群的最大适值没有增加。成熟的遗传算法一般设定遗传代数τ为20～50。

3.3.2 适应度高的个体的选择

3.5 选择、交叉和变异操作

3.5.1 选择操作

采用改进的轮盘赌来选择：首先选择父代个体和交叉变异得到的个体适应值最高的个体，进入下一代进化；然后按照轮盘赌的方法选择p-1个个体进入下一代。使父代个体和其交叉变异得到的个体具有同等的选择机会。不仅将适应度高的个体保留到下一代，而且保证子代的多样性。经实例验证，与传统的轮盘赌比较，大大的提高了收敛速度和质量。

5 结束语

传统的对单一种群的遗传算法改进包括引入各种算子和各种搜索方法进行改进。而此文提出了多种群杂交的改进遗传算法，跳出思维限制并对算法的约束条件处理、编码设计、选择、交叉和变异操作进行了改进。在进化过程中，不断引入辅助种群中优良个体，保持了种群的多样性。与普通改进的自适应遗传算法对比分析表明算法稳定可靠，所提出的新算法不仅收敛速度快，而且收敛效率高，有其自己的特色。

参考文献：

[1] 赵燕伟，吴斌，蒋丽.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造系统（CIMS），2004 3（10）：303-306.

[2] 余琦玮.基于遗传算法的车间调度研究[D].杭州：浙江大学，2004.

[3] Solimanpura M，Vratb P，Shankarc R.A heuristic to minimize makespan of cell scheduling problem[J].International Joural of Production Economics，2004，88：231-241.

[4] 王凌.車间调度及其遗传算法[M].北京：清华大学出版社，2003.

[5] Sujay Malvea，Reha Uzsoyb.A genetic algorithm for minimizing maximum lateness on Parallel identical batch Processing machines with dynamic job arrivals and Incompatible job families[J]. Computers & OperationsResearch，2007，34：3016-3028.

[6] LiYongming，ZhangSujuan，Expert Systems with Applications，2009，36（9）：

[7] 李军华，黎明，袁丽华.一种改进的双种群遗传算法[J].小型微型计算机系统，2008（11）：2099-2102.

[8] 薛明志，钟伟才.正交Multi-agent遗传算法及其性能分析[J].控制与决策，2004，19（3）.

[9] T S Rappaport.Wireless Communications： Principles and Practice[M].Second Edition，Upper Saddle River NJ： Prentice Hall，2002：111-12.

[10] Kevin J Krizmant，Thomas E Biedkatt，Theodore S Rappaportt.Wire-less Position Location： Fundamentals， Implementation Strategies， and Sources of Error[C].In：IEEE 47th Vehicular Technology Conference，Phoenix， AZ：IEEE Computer Society Press，2007.

[11] 王万良，吴启迪，宋毅.求解作业车间调度问题的改进自适应遗传算法[J].系统工程理论与实践 2004，2（25）：58-62.

[12] 杨晓梅，曾建潮.采用多个体交叉的遗传算法求解作业车间问题[J].计算机集成制造系统， 2004，9（10）：1114-1119.