协同进化遗传算法及在车间调度中的应用①

周艳平,王功明

（青岛科技大学 信息科学技术学院,青岛 266061）

遗传算法（Genetic Algorithm,GA）是进化算法中产生最早、影响最大、应用最为广泛的一种群智能优化算法[1].但遗传算法在理论和应用方面还有很多不足,如收敛速度慢,容易陷入局部最优等问题.

Ehrlich和Rave在研究植物和植食性动物的关系时提出了协同进化这一概念,近年来这一概念已经成为计算智能领域的一个研究热点[2].由于协同进化的搜索能力强,越来越多的优化算法采取了协同进化方式[3-5].协同进化研究的应用领域也在不断扩展,在车间调度[6]、电力调度[7]、机器人路径规划[8]、交通规划[9]等领域都得到了成功应用.

生产调度通过对生产资源的合理安排,以缩短生产时间和成本,使资源能够得到更有效的利用,在生产系统中扮演重要的角色.其应用领域十分广泛,涵盖工业、商业等方方面面.按主流的分类方法,生产调度可分为单机调度、并行机调度、流水车间调度、作业车间调度等.其中流水车间调度模型作为典型生产调度模型之一,是一个NP-hard问题[10].该问题主要是安排待加工工件在加工机器上的加工顺序,最终求解得到的是一个最符合要求的工件加工顺序.流水车间调度问题有很多的求解方法,其中包括精确方法、构造型方法、改进型方法等.精确方法计算量较大,一般适用于小规模问题.构造型方法通过一定的规则来构造问题的解,能够快速构造解,但是解的质量较差.改进型算法从若干解出发,通过对其邻域不断搜索和当前解的替换来改进解的质量,是解决流水车间调度问题的主要研究方向,如遗传算法、协同进化算法等.作为车间调度的典型问题,流水车间调度问题得到了广泛研究和应用[11].

本文在遗传算法和协同进化框架的基础上,提出了一种自适应协同进化遗传算法（Adaptive Co-evolutionary Genetic Algorithm,ACGA）.与传统算法相比,该算法通过两个中间组的进化实现了优质解组和劣质解组个体信息的交互,兼顾了种群内的自我进化和种群间的共同优化; 同时引入了自适应策略,根据个体的进化情况采用了自适应变异因子及自适应灾变几率策略.通过函数优化实验验证了ACGA算法在求解简单问题方面的有效性.接着描述了流水车间调度模型,并且使用ACGA算法求解流水车间调度问题,通过与其他相关算法对该问题求解的对比实验,验证了ACGA算法求解流水车间调度问题的有效性.

1 协同进化遗传算法及函数优化测试

1.1 自适应协同进化遗传算法

协同进化遗传算法的实质是对遗传算法采用协同进化的方式进行优化.遗传算法的操作算子包括选择、交叉和变异3种基本形式,构成了遗传算法强大搜索能力的核心,是模拟自然选择和遗传过程中发生的繁殖、杂交和突变现象的主要载体[12].选择因子是按照一定的规则选择出更加符合要求的多个个体组成一个新的种群,常见的方法包括轮盘赌算法、最佳保留策略等.交叉因子是两个个体互相交换部分染色体,最终得到两个新个体,常见的方法有单点交叉和多点交叉等.变异是对单个个体的染色体按照一定的规则进行变更,最终得到一个新个体,常见方法有单点变异和多点变异等.其中交叉和变异操作会导致原个体部分染色体发生改变,可能产生冲突,需要进行冲突检测.协同进化遗传算法相比遗传算法在一定程度上增强了优化的效果,但仍存在搜索速度慢、经常找不到全局最优解的问题.

ACGA算法结合了遗传算法和协同进化算法,在此基础上引入自适应变异因子以及灾变机制达到自适应的目的,算法流程图如图1所示.

图1 ACGA算法流程图

首先针对收敛速度过慢的问题,ACGA算法采取操作协同.对原始种群根据适应度值进行分组,考虑不同组内各个个体的优良情况以及个体差异情况,优质解组采用多点交叉和单点变异,尽可能的保持更多优良个体; 劣质解组采用多点交叉搭配多点变异,产生更多新个体; 中间组采用单点交叉配合多点变异,完成组与组之间的交叉和变异操作.

针对容易陷入局部最优的问题.在传统算法中,变异率通常采取固定数值.但变异率对于种群优化起着重要作用,不同阶段甚至于不同种群都需要合适的变异率,变异率较大时,容易产生新个体,跳出局部最优;变异率较小时容易保留较优个体.局部最优问题正是由于进化到后期时,变异率较低,无法产生新个体,使得种群内个体的多样性不足.为解决这个问题,考虑采用自适应变异率来动态确定[13],随着迭代次数的增加,变异率也在动态改变,来适应种群的进化.本文根据种群的要求提出了一种自适应变异因子:

其中,F0为变异因子,Gm为最大进化代数,为当前进化代数.

在进化初期时,λ趋于0,此时变异因子趋近F0,种群按照正常的变异率进行种群的进化.当进化到后期时,当前迭代次数无限接近于最大迭代次数,此时λ趋于1,变异因子趋近于2F0,变异率增大到原来的2倍.变异率的增加也意味着可以产生更多的新个体以此来增强种群的多样性,而陷入局部最优正是由于种群内个体的多样性不足造成的.由此可见,该变异因子对于缓解局部最优问题起到了一定的效果.

但仅仅通过调整变异率来增强种群多样性的效果是十分有限的.当初始变异率F0较低时,2F0虽然一定程度上有了提高,但程度还不够;初始变异率F0较高时,2F0可能会过大,导致搜索变为随机搜索,这样就不能起到逐代进化的作用.为应对以上情况,本文在引入自适应变异因子的同时引入了灾变机制来进行改善.灾变是生物进化中十分重要的现象,每一次灾变的过程都是生物进化过程中的一个巨大的飞跃,不仅打破了旧基因的垄断,增加了生物的多样性,同时破坏性的改变并没有消灭之前进化的成果,反而是在已有的基础上大大提高了进化程度[14].传统灾变只再次生产新的个体,并未考虑迭代的次数、个体的优良情况.在进化的前期,迭代次数较小,此时需要较大的灾变几率来增强种群多样性;当进化到后期,种群中的个体较优,如果灾变几率过大容易丧失种群进化的成果.因此灾变几率最好动态适应进化的过程.同时,传统灾变并未考虑个体的优良情况,导致优秀个体和较差个体同样进行灾变,破坏了种群的优良基因.因此需要对两种个体分别处理,优秀个体应保持较小的灾变几率,保留优良信息,较差个体保持较大灾变几率,产生新个体增加多样性.为实现上面两种情况,本文采用了叶彦斐等人[15]提出的一种动态自适应概率来替换种群中的个体,公式如下:

其中,i为当前进化代数;N为最大进化代数;Pz为灾变概率;kz为常数;tmax为当前种群最大适应度值;ta为当前种群平均适应度值;tz为灾变个体适应度值.

如式（2）、式（3）所示,首先该自适应概率考虑到了迭代次数的影响,随着迭代次数的增大,u逐渐由0增大到π/2,相应的余弦函数从1到0,使得概率随迭代次数的增大而逐渐减小,防止后期灾变几率过大,破坏优良个体.其次,式（3）考虑到个体的优良情况,当个体适应度低于平均值,说明个体较差,此时采取固定的较高灾变几率产生新个体,反之,优良个体采取了较小的动态灾变几率,防止优良基因被破坏.同时加入精英保留策略,保证种群中的最优个体不会被消灭,指引种群向正确的方向进化.

灾变机制的触发条件也格外重要,本文的灾变触发条件设置为全局最优值连续3次相同,只有在这种情况下才触发灾变机制,否则只采用自适应变异因子.

ACGA算法的步骤如下:

1）初始化进化参数,包括最大迭代次数,种群规模以及3种因子的具体实现形式;

2）随机生成一个初始种群,计算种群中个体的适应度值;

3）对种群内的个体根据适应度值由小到大进行排序,取适应度值较小那部分的前2/3个体组成优质解组,取适应度值较大部分的前2/3个体组成劣质解组,将两部分剩下的1/3部分合并成一个组,命名为中间组;

4）对优质解组采用单点交叉以及单点变异,交叉概率设为0.8,变异概率设为0.03,尽可能的保留优质个体; 对劣质解组采用单点交叉以及多点变异,交叉概率设为0.95,变异概率设为0.1,尽可能的产生更多新的个体; 对中间组采用多点交叉以及单点变异,交叉概率设为0.9,变异概率设为0.07;

5）交叉变异之后得到一个临时种群,计算临时种群中各个个体的适应度值,当临时种群中相对应个体的适应度值小于当前种群中的个体时,就使用临时种群中的这个个体更新当前种群,否则将保持当前种群中的个体;

6）计算最优解连续相同的次数,若次数小于3,则根据式（1）计算当前的变异因子; 若次数大于等于3次时,根据灾变机制进行灾变;

7）判断是否满足终止迭代条件,若是,输出全局最优解以及最优个体; 若否,返回步骤3）继续进行迭代进化.

1.2 函数优化测试

为了检验ACGA算法在优化求解方面的性能,将该算法与GA算法进行了对比,分别采用ACGA算法和GA算法对以下函数进行求解.

该目标函数是传统的多峰函数,在N维可行域中有2N−1局部最优解,其中极小值为0.为了保证实验结果的准确性,2种算法相同参数的数值必须保证一致,包括初始化方法为随机初始化,迭代次数为100,种群规模为90,维度为30等.2种算法的性能对比图如图2所示.

图2 ACGA算法和GA算法的性能比较

从图2可以看出,在迭代次数相同的情况下ACGA算法的求解结果优于GA算法,更加接近全局最优解;在求解结果相同的情况下,ACGA算法的迭代次数也明显小于GA算法的迭代次数.ACGA算法无论在收敛速度还是在求解精度上的表现都要优于GA算法,展现了ACGA算法的优良性能.

2 ACGA算法求解流水车间调度问题

2.1 流水车间调度问题模型

流水车间调度问题主要是研究n个工件在m台机器上进行流水加工,作为最简单的车间调度模型,该模型要求每个工件都有m道工序,同时每台机器只能加工一道工序,这就意味着每个工件都要经过m台机器的加工; 每个工件在各个机器上的加工顺序相同,各个工件在各机器上的加工时间和准备时间已知,优化目标为最小化最大完工时间.

令Tik表示工件i在机器k上的完工时间,tik表示工件i在机器k上的加工时间,且tik>0,i,j=1,2,…,n,k=1,2,…,m.该流水车间调度问题的目标函数[16]为:

2.2 求解步骤

1）初始化算法求解参数,如种群规模、迭代次数、3种因子的具体实现形式;

2）根据流水车间调度问题,采用特定的编码以及解码方式随机生成一个可以进化的初始种群,根据问题模型计算种群内各个个体的适应度值;

3）根据适应度值由低到高对种群内的个体进行排序,将种群平均分成两部分,并且从两部分中各取该部分适应度值较高的1/3个体组成一个中间组,用来进行种群间的交叉变异,同时将剩下的两部分中适应度值较低种群的取为优质解组,适应度值较高的种群取为劣质解组;

4）根据不同组的个体特点采取不同的操作,优质解组采用多点交叉以及单点变异; 劣质解组采用多点交叉和多点变异; 中间组采用单点交叉和多点变异; 变异因子选取自适应变异因子;

5）操作后得到临时一个种群,计算该种群中各个个体的适应度值,并根据适应度值使用临时种群对原种群进行更新操作;

6）计算全局最优解连续相同的次数,若次数少于3次,根据式（1）计算自适应变异率,并更新之前的变异率; 若次数不少于3次,计算种群的平均适应度,根据式（2）和式（3）分情况计算除最优个体之外的每个个体的灾变几率,将需要灾变的个体根据编码方式随机初始化,使用灾变最新产生的个体贪婪替换原个体;

7）判断是否满足终止条件,若是,则将得到的全局最优解进行解码,生成最优的调度方案; 若否,则返回步骤3,继续进行.

2.3 仿真实验

2.3.1 实验准备

程序运行平台为Windows 10操作系统下的Matlab软件.输入的种群规模为90,最大迭代次数为800,初始灾变概率kz为0.2.优质解组的交叉概率为0.8初始变异概率为0.03; 劣质解组的交叉概率为0.95,初始变异概率为0.1; 中间组的交叉概率为0.9,初始变异概率为0.07.编码采取随机初始化方法.数据集选择TA类[17]车间调度问题,该数据集是由Taillard等给出,包括了12个不同规模的120个典型问题,本次实验选取3种规模的数据集,分别为20×5、50×5以及100×5,在每种规模的数据集下选取一个典型问题,通过这3个规模数据集下的3个典型问题来验证算法.

2.3.2 实验结果与分析

分别采用ACGA算法、MDE算法[13]以及GA算法对上述3种规模的数据集进行流水车间调度问题的求解,以最小化最大完工时间为优化目标.在实验过程中,为使结果更加精准,避免实验偶然性,每种算法在每个数据集分别运行10次.实验结果的参考指标主要为10次结果的平均值以及10次结果的方差,均值和方差越小越好.均值越小,说明算法优化的精度越高;方差越小说明算法的稳定性越高.

仿真结果如表1所示.首先看10次结果的平均值,在同等规模、相同问题的情况下,ACGA算法在每一种问题上都可以得到比MDE算法和GA算法更小的完工时间,而GA算法和MDE算法相比,GA算法更适合较小规模,MDE算法更适合较大规模; 从10次结果的最优值来看,ACGA算法在每种问题下的最优值也小于MDE算法GA算法,而MDE算法与GA算法的对比情况与均值类似; 从10次结果的方差来看,ACGA算法的方差明显要小于GA算法和MDE算法,MDE算法在小规模情况下比GA算法稳定,较大规模下的稳定性不如GA算法,从这3个指标可以看出ACGA算法的求解效果更加稳定.由此可以得出结论,ACGA算法在求解流水车间调度问题方面与GA算法和MDE算法相比,求解结果更加精准,求解效果更加稳定,精确性和稳定性都是最佳的.

表1 3种算法对不同规模调度集的仿真结果

图3给出了使用ACGA算法对数据规模为20×5进行流水车间调度得到的甘特图.

图3 ACGA算法对规模为20×5调度及优化的甘特图

3 结论与展望

本文提出了自适应协同进化遗传算法,该算法通过引入自适应策略、灾变机制以及协同进化思想,适当加快收敛速度,提高优化效果.通过函数优化实验,验证了ACGA算法的可行性和有效性.用ACGA算法求解以最小化最大完工时间为指标的流水车间调度问题,通过与GA算法和MDE算法对比,取得了满意的调度效果,具有一定的应用价值.接下来的研究工作将着重于研究ACGA算法使用不同变异因子及灾变因子的优化效果,以及ACGA算法在其它车间调度问题中的应用.