改进激素算法求解置换流水车间调度问题

郑 堃，练志伟，王玉国，朱长建，顾新艳，刘 轩

(1. 南京工程学院汽车与轨道交通学院 南京 211167；
2. 中德智能制造研究院 南京 211800)

置换流水车间调度问题(permutation flow shop scheduling problem, PFSP)是流水车间调度中经典的问题之一，也是实际工程应用最广泛的规划问题。目前，精确方法、启发式方法和元启发式方法是求解PFSP 常用的3 类方法。精确方法不适合求解复杂度会呈指数增加的调度问题[1]。启发式方法[2]可快速给出确定的调度方案，但过分依赖局部调度规则。元启发式方法又称为智能优化算法，是目前求解PFSP 的重点研究方法。

智能优化算法又可分为进化算法(evolution algorithm, EA)、群智能算法(swarm intelligence, SI)和局部搜索算法(local search, LS)等。EA 通过模仿自然界的进化过程抽象而来，是PFSP 的主要处理手段。EA 中应用最广泛与深入的是遗传算法(genetic algorithm, GA)[3]，文献[4-5]针对GA 存在的缺点进行改进，并用现有的PFSP 标准算例进行验证，证明其改进的有效性。SI 是受自然界种群的群体智能行为启发，如共生生物搜索算法(symbiotic organisms search, SOS)[6]是根据自然界的共生关系启发得出的。LS 通常根据PFSP 的特点设计相应的邻域操作，并利用该邻域操作对当前局部最优解进行深度挖掘，如文献[7]研究了3 个基本邻域操作求解PFSP 的性能，并与粒子群(particle swarm optimization, PSO)算法相结合，取得了不错的效果。

GA 的深入研究使其在多个领域获得了广泛应用[8-9]。GA 的操作主要包括选择、交叉以及变异这3 个基本遗传算子，其中交叉算子是GA 区别于其他EA 的重要特征，是GA 产生新个体的主要方法。文献[10]首次利用提出的两点交叉(two-points crossover, TPX)探索PFSP 解空间，取得了不错的效果，被多次引用[11-12]，但TPX 的交叉点为随机选取，所以存在冗余度高和算法中后期效率低等缺陷。文献[4]针对GA 本身不具备记忆功能而导致优质解易丢失、收敛速度慢和最终解的质量低等缺点，提出保优机制和选择策略，按一定保优比例，将优质解遗传到下一代种群中。文献[5]利用限优策略保持种群多样性，解决GA 陷入局部等问题。因此有学者提出混合算法，即将智能算法中的各类算法进行混合，作为适用域拓展和算法性能提高的重要手段，如文献[13]将SOS 与LS 结合，提出了混合共生生物搜索算法(hybrid symbiotic organisms search, HSOS)，采用标准算例集证明其优越性和稳定性，在优化过程中可同时满足探索(exploitation)和开发(exploration)、集中性(intensification)和广泛性(diversification)，但会增加算法的计算复杂度和搜索时间。

近年来，学者们进一步提出了生物学和生产制造系统相结合的方法。文献[14-15]在这方面研究颇多。利用生物体的激素调节对体内各种激素的调控具有较好的自适应性和稳定性等优点，文献[16]提出了基于激素调节规律的改进型自适应遗传算法(improved adaptive genetic algorithm, IAGA)，并结合作业车间调度问题进行了验证；
文献[17-18]将激素调节规律应用至PSO 的速度更新公式和惯性因子来求解PFSP 和混合流水车间调度问题。目前基于激素调节的算法已被证实能有效克服种群进化缓慢、个体早熟等缺陷问题，但受激素浓度的影响，一般激素浓度的计算方法使激素调节规律在目标函数较大时，出现了失调现象，因而无法保证基于激素调节的算法能具有更好的优化结果。

综上所述，在采用GA 求解PFSP 问题时，为解决常用选择算子中TPX 的缺陷、全局最优解收敛困难问题以及IAGA 的局限性，本文提出了基于改进激素浓度计算法的IAGA(improved hormone concentration calculation method-iaGA, IHCCMIAGA)。该算法主要将激素调节机制引入到选择算子中，通过改进激素浓度的计算方法，使基于激素调节规律的参数在目标函数值较大时仍有较好的灵敏度；
采用了精确取点的ITPX 算子进行交叉，提高算法的探索能力；
通过建立优良基因库及免疫因子，保存并监控每代进化过程的优质解，同时将多种扰动操作和局部搜索算法进行组合，设置湮灭因子并利用免疫因子映射的影子标记优质染色体来共同引导局部搜索，提高算法的局部开发特性。

PFSP 描述为：有n个相互独立工件{J1,J2,····,Jn}，使用m台加工机器{M1,M2,····,Mm}，每个工件在每台机器上的加工时间都不相同。调度目标为优化工件的加工顺序使得最后的完工时间最小，此过程需满足如下约束。

1) 初始时刻，所有工件和加工机器准备就绪；

2) 机器之间的顺序是固定的，所有工件需以相同的顺序经过每台机器；

3) 任意时刻一台机器只可加工一个工件；

4) 机器一旦开始加工，则不能中断；

5) 工件之间存在先后排序。

PFSP 的数学模型描述如下：假设p(i,j)表示工件j在机器i上的加工时间，且工件之间的排序为集合O(O1,O2,····,On)，工件在机器上的加工顺序为机器1～机器m，则n个工件在m台机器上的完工时间C(i,Oj)分别为：

因此，求解PFSP 的目标函数为min{Cmax(O)}。

2.1 IHCCM-IAGA 流程

IHCCM-IAGA 流程如图1 所示，该算法能很好地弥补传统GA 的不足，使得改进算法在求解的性能上拥有更大优势。

图1 IHCCM-IAGA 流程框图

由图中可知，IHCCM-IAGA 算法较普通GA流程的主要差别为激素的应用、优良基因库和免疫因子的引入、两种交叉方式的实现、变异算子与局部搜索的融合以及种群湮灭算子和湮灭因子的建立。其具体执行步骤如下。

1) 确定参数。包括种群N和基因库规模NP、迭代次数G、种群湮灭因子Af、自适应选择门槛Po、交叉概率Pc和变异概率Pm等一些参数；

2) 利用反向学习法生成初始种群法和初始化UMax；

3) 评价种群中每个染色体的适应度值，计算自适应选择门槛Po、交叉概率Pc和变异概率Pm，并判断是否更新UMax，同时根据要求更新基因库或初始化基因库；
如果达到最大迭代次数则输出最优解或近似最优解，其中输出解为免疫因子携带的染色体和其适应度值，结束运行；
否则执行步骤4)；

4) 生成随机概率P或P1，若P＜Pc，则在种群和优良基因库各选一个染色体进行ITPX 交叉，否则，P＜1-Pc或P1＜1-Pc时，在种群选出两个染色体进行ITPX 交叉，其中如果从种群选取染色体，则按选择操作选取个体，否则随机选取；

5) 若随机概率P＜Pc，则按变异规则进行局部搜索变异和多样性变异，产生下一代种群；

6) 更新当前迭代次数g，并检查免疫因子携带的适应度值是否有改变，若有改变，则不对当前种群做任何变动，且重置累计迭代次数的计算；
否则更新累计迭代次数，并检测累计迭代次数是否达到湮灭门槛，若达到湮灭门槛，则对当前种群实行湮灭和更新湮灭因子Af，同时重置累计迭代次数的计算；

7) 返回步骤3)。

2.2 IHCCM-IAGA 原理

2.2.1 基于激素调节的IAGA 参数设计

通常种群进化过程主要分为两个阶段：1)种群进化前期：交叉概率大、变异概率小，有利于种群的快速收敛，较优解不易丢失的特点；
2)种群进化后期：交叉概率小、变异概率大，有利于精细化搜索，种群多样性的保持。但传统GA 的交叉概率和变异概率固定，且参数选择困难，而这极大影响GA 的优化结果。因此，借鉴内分泌激素调节规律的上升和下降函数，文献[16,19]提出了基于激素调节的改进型自适应遗传算法(IAGA)。

同时种群多样性还与选择算子息息相关，因此，有必要设置一个由激素调节的自适应选择门槛。

内分泌激素的基本规律由文献[20]提出，它揭示激素具有单调性和非负性的变化特性，激素调节的上升规律函数Fup(X)和下降规律函数Fdown(X)遵循Hill 函数规律，其公式如下：

式中，X为函数自变量；
D为阀值，且D＞0；
n为Hill 系数，且n≥1；
n和D共同决定上升下降曲线斜率。

图2 为参数D=1，n=1,2,3 情况下的Hill 变化曲线。当参数D不变、n值由小到大时，Hill 曲线收敛的速度越来越快，到达稳定状态所需时间也越来越少。

图2 参数n 对Hill 曲线的影响

如果激素x受激素y调控，则激素x的分泌速度Sx与激素y的浓度Cy的关系为：

式中，Sx0为激素x的基础分泌速率；
α 为常量系数。

将式(7)和式(8)代入式(9)，得：

模仿式(10)和式(11)，设计了与种群优劣程度相关的自适应选择门槛、交叉概率和变异概率因子函数，具体如下。

1) 自适应交叉概率[16]：由式(11)设计出自适应交叉概率为：

2) 自适应变异概率[16]：根据式(10)，设计自适应变异概率为：

2.2.2 参数的选择范围讨论

1) α、β 和γ

α、β 和γ 的取值将影响自适应交叉概率、变异概率和选择门槛的增幅和减幅，其取值范围由式(12)～式(14)确定，可得：

2)nc、nm和no

同样，参数nc、nm和no的取值会对自适应交叉概率、变异概率和选择门槛的进化速度产生影响。一般地，取值范围为1～4 之间的整数。

2.2.3 内分泌激素浓度计算法的改进

激素调节规律与激素的浓度有关，而GA 中的激素浓度由fav决定，一般fav的适应度值主要由目标函数值取倒数(1/Makespan)获得，从而使得激素浓度总是能够与Hill 上升和下降函数呈正相关和负相关的联系，即适应度值越大，适应能力就越强。所以在Makespan 较小时，对激素调节有很好的引导作用，但适应度由目标函数取倒数不仅会有参数的影响，且随着Makespan 越来越大，其适应度值会以降低数量级的形式表达，因此个体适应度值之间的变化量就越小，此时受激素浓度影响的激素调节规律将会出现调节不明显、失调等现象，即选择门槛、交叉概率和变异概率不再严格遵循Hill 下降和上升函数的规律。为此，本文将对计算激素浓度的方法进行改进，以解决激素规律失调的问题。

对激素公式中适应度值的计算方法改进如下：

1) 评价初始种群中每个染色体，记其中最差染色体的最大适应度值max{Cmax(O)}为UMax=max{Cmax(O)}+50；

2) 以UMax为标准，对种群中所有染色体计算标准化适应度值，标准化公式为fSi=UMax-fi，i=1,2,···,N，为种群中每个染色体离目前已知最差染色体的距离；
染色体越好，离最差染色体就越远，其fSi越大，相反，离最差染色体就越近，其fSi就越小；
可见，改进的计算方法可以与激素的调节规律和现实意义成正比，具有可行性。

3) 用标准化适应度值计算激素公式中的fav、fmin和fmax，在种群每次迭代后计算标准适应度值时，如有fSi≤0，则在计算完fav、fmin和fmax后，更新当前UMax，更新方法为计算当代种群中最差染色体的最大适应度值max{Cmax(O)}为UMax=max{Cmax(O)}+50；

激素调节规律除受激素浓度fav调控外，还受激素震荡的影响，激素震荡由fmax与fmin的差值决定。当差值过大时，激素规律则认为种群染色体分布趋于两极化，由激素震荡成为主控因子，调节选择门槛、交叉概率快速增大和变异概率快速减小，以确保种群染色体分布均匀，保持种群的稳定。相反，当差值过小时，激素规律则认为种群染色体分布过于集中、多样性过少，此时激素震荡仍是主控因子，调节选择门槛、交叉概率快速减小和变异概率快速增大，以确保种群染色体分布均匀、增加多样性；
而差值过大或过小，使得激素震荡成为主控因子，无法正确反映种群的实际情况，因此收敛速度不稳定、解的质量也难以保证。为此，只有在差值合适时，激素浓度才是主控因子，而一般激素浓度的计算方法可以做到此点，且受激素震荡的微调作用。为此，本文对标准化的fmin改为fmin=fav/2+fmin，使改进后的激素浓度计算法与一般激素浓度计算法具有相同的调节作用。

3.1.1 染色体的编码

用 集 合O={O1,O2,···,On}表 示 工 件 在 机 器1～机器m上的加工顺序，集合O中的元素用工件的整数编号表示，用集合J={J1,J2,···,Jn}表示工件集，从而构造出基于工件编号的整数编码，例如7 个工件的集合O={1,3,4,2,6,5,7}所对应工件的加工顺序为J1→J3→J4→J2→J6→J5→J7。

本文将采用文献[21]提出的反向学习法(opposition-based learning, OBL)，设工件编号的最小数为1，最大数为n，当前工序的工件编号为Oi，则Oi的反向学习Oi的编号如为：

3.1 初始化种群

3.1.2 初始化方法

因此本文的初始化过程如下。

1) 设置初始种群个体数为N，随机初始化N个染色体，生成初始种群P1；
然后对种群P1 中的所有染色体进行如图3 所示的反向学习，生成初始种群P2；

图3 染色体的反向学习

2) 将初始种群P1 和P2 合并，计算合并后所有染色体的目标值并从小到大进行排列，选取前N个染色体作为最后的初始种群。

3.2 适应度函数

根据每个染色的集合O编码计算其目标函数值Makespan，并作为其适应度值，即fitness=min{Cmax(O)}。

3.3 选择操作

本文采用文献[22]提出的锦标赛选择方法，并加以改进，确保在种群进化后期能够更好的保持种群多样性。

每次从种群中选择若干个体进行适应度比较，选出最差的个体和最优的个体，若随机值(在0～1 之间随机产生)小于门槛(受激素调节的值)，则选择最优的一个，否则就选择最差的一个。这样可保证在种群进化前期，高性能个体能最大限度的遗传至下一代，以提高种群的全局收敛速度；
在种群进化后期，提高较差个体进入下一代种群的概率，以确保种群多样性，从而更好地克服个体早熟和局部收敛等现象。

3.4 交叉操作

3.4.1 ITPX 算子

对基于工件编号整数排列的编码方式，一般采用TPX[10]来产生子代，如图4 所示，此方法容易出现冗余、效率低等问题，无法高效地对解空间进行搜索，因此最后解的质量得不到保障。

图4 TPX 交叉算子

本文将在此交叉算子的基础上进行改进，提出一种精确的取点方式ITPX，具体步骤如下。

1) 对两个父代染色体从左向右依次等基因位对比，标注等基因位值不同的基因位，记作集合T={T1,T2,···,Ts}，其中T1为两父代染色体第一不同的基因位，Ts为两父代染色体最后不同的基因位，T1至Ts的基因位距离称为最大不同基因位区间；

2) 设置两个交叉点分别为n1、n2，且n2＞n1。n1和n2分两次从集合T中选取基因位作为其交叉点。当n1从集合T选取交叉点时，n1第一个交叉点必须从染色体的第一个基因位开始选取(不管染色体第一基因位是否为不同基因位)，记为a0；
n1其余交叉点从集合T中按1～s的顺序选取，记为a1，同时若从集合中选取的第一个基因位T1为染色体第一基因位，则按顺序重新选取，直至集合T选取完毕。n2则从左向右依次选取交叉点，n2开始交叉点b0选取规则为：若n1=a0，且a0≠T1，则n2开始交叉点为T1，若a0=T1，则n2开始交叉点为a0+1；
若n1选取的交叉点为a1，则n2开始交叉点为a1+1；
n2结束交叉点均为Ts-2。每当n1选取一个交叉点，n2则从b0开始，依次加1，直至结束点Ts-2；
n1只能从集合T中选取Ts-2 之前的点；

3) 当n2从集合T选取交叉点时，n2第一个交叉点必须从染色体的最后一个基因位开始选取，记为an-1；
n2其余交叉点从集合T中按1～s的顺序选取，记为a2，直至集合T选取完毕，其中如果从集合中选取的最后基因位Ts为染色体最后基因位，则提前结束选取。n1则从右向左依次选取交叉点，n1开始交叉点b1选取规则为：若n2=an-1，且an-1≠Ts，则n1开始交叉点为Ts，若an-1=Ts，则n1开始交叉点为an-1-1；
若n2选取的交叉点为a2，则n1开始交叉点为a2-1；
n1结束交叉点均为T1+2。每当n2选取一个交叉点，n1则从b1开始，依次减1，直至结束点T1+2。以上过程，如图5所示。值得注意的是，n2只能从集合T中选取T1+2 之后的点。

图5 ITPX 算子的精确交叉取点方式

通过ITPX 方法生成两父代所有子代，从各自子代集中选取最优的染色体作为下一代，且免疫因子实时监测两父代产生的子代集，以保证优质解的不丢失。同时本文引入优良基因库，并采用两个交叉概率来实现两种交叉方式，一种是分别从优良基因库随机选择染色体，按选择操作从种群中选择染色体以Pc概率进行交叉；
另一种是两个染色体均按选择操作从种群中选取以1-Pc的概率进行交叉。

3.4.2 优良基因库

优良基因库主要分为以下几个部分。

1) 免疫因子：免疫因子主要监控每代种群在交叉算子中所有的子代染色体和变异算子中局部搜索部分，实时更新优于免疫因子所携带的染色体；

2) 免疫因子映射的影子：影子只映射免疫因子携带的值，利用影子标记基因库中适应度值相同，但两两个体H 距离均不同的染色体(两个染色体中不同基因位的个数称为海明距离，简称H 距离)，并对这些染色体从零开始标号，记最大标号为M，利用映射的影子标记优质染色体来引导下一代种群的局部搜索；

3) 优良基因库初始化：设优良基因库最大容量为NP，初始化时，从初始化种群引入适应度由低到高排序的前NP/2 染色体到基因库中，剩余的容量在种群进化时按更新策略填充引入；
同时对免疫因子初始化，记录基因库中适应度最优的染色体；

4) 优良基因库更新策略：在每代种群进化完成时，对基因库更新，更新策略分为两种情况: ①当优良基因库有容量时，评价当代种群中每个染色体，并与当前基因库中最差染色体比较，如果小于，则检查当前染色体是否有与基因库中染色体适应度值相同，如有相同，则计算两个染色体H 距离，若H=0，则不引入，否则引入填充；
②当优良基因库没有容量时，利用替换方法实现更新策略，并重新标记当前基因库中最差染色体及其适应度值。

3.4.3 种群湮灭

为了更好地开发空间多样性和探索解空间，利用优良基因库中的免疫因子对种群湮灭是否触发进行判断，其判断过程为：当种群连续累计迭代一定次数后，免疫因子仍不更新，则触发；
当免疫因子有更新时，则重新累计迭代次数。同时，设置湮灭因子Af，种群每湮灭一次，湮灭因子则从初始值依次叠加。湮灭因子主要用来影响变异算子的局部搜索，旨在增强变异的局部搜索特性。

本文对种群80%个体实行湮灭，湮灭方式为将种群前40%的个体实行反向学习，并依次随机打乱生成新染色体，后40%的个体利用随机初始化法生成新染色体。基因库只保留由免疫因子映射影子标记的优质染色体，保留数目不得超过整个基因库最大容量的20%，其余优质染色体实行删除操作，由种群湮灭后的染色体以适应度由低到高排序依次填充基因库，其中免疫因子等不参与湮灭。

3.5 变异操作

本文将具有丰富结构的多种扰动操作和局部搜索算法进行组合，构成组合变异算子，相比在选择-交叉-变异等操作之后再引入局部搜索算法，组合变异算子能更好地维持种群的多样性。

变异过程如图6 所示，主要步骤为：满足变异概率后，变异开始：生成随机概率P1，若P1＜Pm，则开始局部搜索，否则进行多样性变异；
其中当父代染色体的适应度值等于免疫因子映射影子的值(fc=fIfs)，则实施局部搜索1，否则从局部搜索2 开始，若搜索过程当中有新染色体优于免疫因子，则替换后，触发湮灭因子重置准则和直接跳转至多样性变异，即fn＜fIf；
因此图中的“是”表示有更加优质的新染色体，“否”表示无。具体实现如下：扰动操作主要包括① 插入：随机选择染色体的两个不同基因位，将其中一个基因位插入到另一个基因位的前面；
② 反转逆序：随机选择染色体的两个不同基因位，对两个不同基因之间的所有基因反转逆序；
③ 打乱互换：随机选择染色体中一些不同的基因位，然后随机打乱，重新排序；
④ 两点互换：随机选择染色体的两个不同基因位，将这两个不同基因互换。

图6 变异过程

局部搜索主要分成3 部分。

1) 首先利用扰动操作对此父代染色体局部变换，共变换5Af次，生成Af×5 个子代染色体，扰动选择过程为：设置随机整数r，范围为0～5，当r=0 时，采用①；
当r=1 时，采用②；
当r=2 或3 或4 时，采用③；
当r=5 时，采用④。然后评价所有子代染色体，判断fn＜fIf；
否则从父代染色体开始以1-Pc的概率进入循环搜索，如图7 所示。循环搜索分为大循环和小循环，大循环次数为Af，小循环次数为Af×5，衰减系数Q=0.12/Af-(fc-fIf)/(fIf×0.062 4×Af2)；
大循环均从零递增计数，小循环从准许的最大次数递减计数，满足循环次数或fn＜fIf时结束，同时记当前染色体适应度值为f1和f2，染色体为C1和C2；
记当前大循环的次数为T，则衰减值为1+TQ，记当前小循环的次数为t和对染色体C1的更新次数为Count，每次大循环时，初始化Count=0，则小循环过程为：先利用扰动①②④生成新的染色体，根据文献[7]的分析，设随机概率P＜0.15 时，选择②，随机概率P＜0.4或P1＜0.4 时，则选择①，若上述概率都不满足，则选择④，新染色体判断准则和处理分类如下：I. 判断fn＜fIf；
II. 若fn＜f1&fn＜f2，则接受fn，并更新f1、f2、C1、C2和Count；
III. 若fn＞f1&fn＜f2，也接受fn，但只更新f2和C2；
IV. 若fn＞f1&fn＞f2，则计算接受概率Pa=(t×衰减值)/(Af×10)，若随机概率P≤Pa，则接受fn，并更新f2和C2，否则不接受fn，利用C2对当前染色体重置，若随机概率P＞Pa且Count=0，则利用C1和f1对当前染色体和f2重置。

图7 循环搜索

每进入下一次小循环时，则利用C1和f1对C2、f2和当前染色体重置，直至当前大循环结束，输出C1和f1，同时若当前搜索的染色体为子代染色体且输出的f1≠fIfs，则利用C1和f1对当前子代染色体更新。若父代染色体和所有子代染色体循环搜索完毕，且没有fn＜fIf，则随机概率P＜1-Pc，将从子代染色体中随机选取一个替换当前染色体，否则选择子代染色体中最优的个体替换，并进入第二部分局部搜索。

2) 利用基因库被标记的随机染色体对当前父代染色体进行比对，保留相同或不同的基因，对不同或相同的基因全排列搜索或扰动③搜索，生成所有子代染色体，然后评价所有子代染色体，记录其中适应度最小的染色体fmin、适应度最大的染色体fmax和随机一条染色体frand，并判断fn＜fIf；
否则以Pc概率接受fmin染色体，如不满足上述概率，则以1-Pc概率接受frand染色体，若不满足上述所有概率，则接受fmax染色体，且进行第三部分的局部搜索。比对选择方式：若当前染色体经过第一部分局部搜索，则随机概率P＜Po时，保留相同的基因，对不同的基因搜索，否则保留不同基因，对相同的基因搜索；
若当前染色未经过第一部分局部搜索，则随机概率P＜Po时，保留不同基因，对相同的基因搜索，否则保留相同的基因，对不同的基因搜索；
如搜索的基因数超过5 个，则利用扰动③生成120 个子代染色体，否则全排列生成所有子代染色体。

3) 对当前染色体进行循环搜索，大循环次数为随机整数R，范围1～Af，小循环次数为30，衰减系数Q=R1-(fc-fIf)/(fIf×0.285×R)，其中R1为0.004～0.013 的随机数。若记当前大循环的次数为T，则衰减值仍为1+TQ，其循环过程与上述的循环过程一致。

多样性变异：主要采用扰动①②③作为种群多样性保持的策略，设置随机整数r，范围为0～2，当r=0 时，采用扰动①；
当r=1 时，采用扰动②；
当r=2 时，采用扰动③；
不同的扰动操作可以保持丰富的多样性结构。

为了验证本文所提算法的性能，进行以下两个比较实验。

1) 改进激素浓度计算法(IHCCM)与普通激素浓度计算法的对比实验。通过Rec[23]算例测试比较改进激素浓度计算法与普通激素浓度计算法的求解性能，为客观评价改进激素浓度计算法对算法整体性能的提升提供依据。

2) IHCCM-IAGA 对比实验。通过国际标准算例集Carlier[24]、Rec[23]、Taillard[25]测试比较IHCCMIAGA 与其他算法的求解性能，为客观评价IHCCMIAGA 和ITPX 的性能提供依据。同时以上所有比较实验最终输出解均为免疫因子信息。

改进的遗传算法采用DEV C++编程，程序在环境为Intel(R) Core(TM)，主频2.3 GHZ，内存8 GB的个人计算机上运行。经过多次试验比较，设定如表1 所示的实验参数。同时为了节省优化时间和提高算法性能，ITPX 交叉点设定如下选取规则：若集合T的个数为小于等于4，全部选取；
若集合T的个数大于4，但小于等于10，则记集合T的个数为Num，选取个数SN 为5～Num，选取点为从集合T中随机选取SN 个不同的点；
若集合的个数大于10，则选取个数SN 为5～10，选取点为从集合T中随机选取SN 个不同的点。其中n1和n2选取的交叉点一致，针对每个算例分别连续运行20 次，同时使用最佳相对误差 (best relative error,BRE)、平均相对误差 (average relative error, ARE)和最差相对误差 (worst relative error, WRE)评价本文算法结果，其计算公式分别如下：

表1 实验参数

式中，C*为目前该问题已知的最优值；
Cbest为算法在规定次数内求解该算例的最优值；
Cavg为算法在规定次数内求解该算例的平均值；
Cworst为算法在规定次数内求该算例的最差值。

4.1 IHCCM 对比实验

激素浓度测试算法框架不包括种群湮灭和局部搜索变异，改进激素浓度计算法与普通激素浓度计算法下自适应参数均采用如表1 所示的实验参数，为了节省运行时间，迭代次数G改为100。因变异除了可保持多样性还具有较强的局部搜索能力，结合本文具有优良基因库等原因，为了实验数据的有效性和严谨性，将两者的Pm设为可收敛的最大近似值0.41，同时两者采用同一初始种群进化比较。

如图8 所示，“I”表示改进法的参数，如IPcav、IPo等；
“av”表示连续运行20 次的平均参数变化曲线，如Pcav、Poav等；
“1”表示其中的特例，如Pc1、Po1 等。自适应参数主要表现在图8的上、中、下3 个区间的变化曲线。

图8 基于不同激素浓度计算法下的自适应参数变化曲线

图9 为两者连续运行20 次最优解的分布图，其中IHCCM 表示改进浓度计算法，HCCM 表示普通浓度计算法。可以发现，IHCCM 在解的分布上，有13 个优于HCCM，且图中最优解在IHCCM一侧，而HCCM 只有7 个解优于IHCCM，且图中最差解在HCCM 一侧。综上所述，可以发现改进激素浓度计算法相比普通激素浓度计算法在求解较大Makespan 时更具优越性，能有效解决因激素浓度变化量过小而导致激素失调的问题。

图9 不同激素浓度计算法下解的分布比较

4.2 IHCCM-IAGA 对比实验

4.2.1 Carlier 测试集

Carlier 算例集为小规模测试集，为了检验本文算法对小规模问题的性能，与混合蝙蝠算法(hybrid bat algorithm, HBA)[26]、基于变邻域搜索的粒子群算法(particle swarm optimization based on variable neighborhood search, PSOVNS)[27]、混合回溯搜索算法(hybrid backtracking search algorithm,HBSA)[28]以及混合共生生物搜索算法(HSOS)[13]进行比较，比较结果如表2 和表3 所示，其中CPU/S为连续运行20 次的平均优化时间。

表2 Car 测试集的最优解比较

表3 Car 测试集的计算结果误差比较

可以发现本文算法与HSOS 一样，在BRE、ARE 和WRE 均可取得最好的测试结果，而其他算法却都会出现细微偏差，说明本文算法不仅具有很好的稳定性，而且具有非常好的局部搜索特性，不易陷入局部最优，这不仅得益于变异中的局部搜索，更得益于ITPX 算子和激素调节下的多样性变异，同时算法的运行时间也在可接受范围内。

4.2.2 Rec 测试集

Rec 算例集为中、大规模的测试集，为了检验本文算法对中、大规模问题的性能，与离散蝙蝠算法(discrete bat algorithm, DBA)[29]、混合差分估计分布算法(differential evolution and estimation of distribution algorithm, DE-EDA)[30]、混合共生生物搜索算法(HSOS)[13]和变参数量子进化算法(variable parameters quantum-inspired evolutionary algorithm,VP-QEA)[31]进行比较，比较结果如表4 所示，其中CPU/S 为连续运行20 次的平均优化时间。

表4 Rec 测试集的计算结果误差比较

从表中可发现，本文算法在21 个Rec 算例取得的误差，绝大数都小于表中所比较的算法，其中有20 个算例的BRE 优于或等于其他算法求解的BRE；
有17 个算例的ARE 优于或等于其他算法的ARE；
有17 个算例的WRE 优于或等于其他算法的WRE。

图10～12 所示为表4 中各个算法在BRE、ARE 和WRE 的曲线图，从图中可以发现不管是BRE 还是ARE、WRE，本文算法的整体曲线均处在其他所有算法的最下面，可见本文算法可以取得非常好的优化效果。本文算法在BRE、ARE 和WRE的平均值上均为最小值，排在所有比较算法中的第一位，表现出本文算法具有很强的稳定性和收敛性。

图10 调度结果最佳相对误差比较

如图13 所示为Rec29 算例的进化曲线图，可见算法在激素调节的作用下，迭代25 次左右就已经收敛于局部最优解，此时自适应选择门槛、交叉概率和变异概率均已达到理论峰值，随后ITPX 将结合变异算子中的局部搜索和湮灭因子等因素，进行精细化搜索，使得算法在中后期仍有很强的搜索能力和局部开发特性，以至在迭代250 次之后仍有下降趋势，直至找到最优解2 287。相比其他算法，均无法找其最优解，且存在一定误差，体现了本文算法的有效性，具有克服个体早熟、增强全局探索能力和局部开发特性。

图11 调度结果平均相对误差比较

图12 调度结果最差相对误差比较

图13 Rec29 算例的进化曲线

因此，在实际生产应用中，若着重实时调度，则IHCCM-IAGA 在激素的调节下可快速收敛于最优解或近似最优解，优化时间较少，如Rec29 算例的近似最优解；
若着重解的质量，则IHCCM-IAGA可在ITPX 的支持下进行精细化搜索，以达到最优解，如Rec29 算例的最优解。

4.2.3 Taillard 测试集

Taillard 算例集由中到超大规模的测试集组成，包 括20×5、20×10、20×20、50×5、50×10、50×20、100×5、100×10、100×20、200×10、200×20、500×20 共12 个不同规模组成的算例集，每个规模有10 个算例，取每种规模最后一个算例作为代表，组成本文的测试集。

为了检验本文算法对中、大和超大规模问题的性能，与混合遗传算法(HGA)[32]、混合共生生物搜索算法(HSOS)[13]、贪心禁忌搜索算法(tabumechanism improved iterated greedy, TMIIG)[33]、离散水波优化算法(discrete water wave optimization algorithm, DWWO)[34]、NEH 启发式算法[35]以及改进的贪心迭代算法(improved iterated greedy algorithm,IIGA)[36]进行比较。比较结果如表5 所示，其中Cav表示该算法在一定运行次数内的平均值。

表5 Taillard 测试集的计算结果比较

本文使用平均错误率(average error, AE)评价算法对Taillard 测试集的性能，计算公式如下：

式中，Cavi为算法求第i算例的平均完工时间；
UB为该算例目前已知解的上界值；
k为算例的数量。

从表5 可以发现，IHCCM-IAGA 有9 个算例的Cav均优于或等于其他算法，有3 个算例的Cav略高于HSOS，但均优于除HSOS 外的其他算法，可见IHCCM-IAGA 在Taillard 测试集上也具有较好的优越性。图14 为基于Taillard 测试集不同算法的平均错误率(AE)，可以发现IHCCM-IAGA 的AE 为1.11，均小于其他算法，其中与HSOS 的AE 相差值为0.4，与除HSOS 外的其他算法AE 相差值均超过20，表现出IHCCM-IAGA 具有更好的稳定性和鲁棒性。

图14 基于Taillard 测试集不同算法的平均错误率

综述上面的实验结果与分析，可以发现本文的IHCCM-IAGA 具有更好的局部开发特性和更快的全局收敛速度，使得解在质量上和收敛速度上都有明显提升。

本文提出了一种基于改进激素浓度计算法的IHCCM-IAGA 来求解NP 问题的置换流水车间调度问题。针对传统遗传算法在求解PFSP 中存在的不足和缺陷，使用了一种基于改进激素浓度计算法的IAGA，通过激素的相互促进与抑制，自适应地调整选择门槛、交叉概率和变异概率值，使得种群可自适应各种进化环境，同时引入优良基因库及免疫因子，实现两种交叉方式并监控整个进化过程，避免优质染色体的丢失。最后，为了进一步提高算法在中后期的探索和开发能力，提出了一种ITPX 算子，并结合组合变异算子和种群湮灭算子等，确保IHCCM-IAGA 在收敛速度和求解的质量上能够得到更好应用。通过Rec41 算例比较实验，验证了改进激素浓度计算法的优越性和有效性。通过国际标准算例比较实验，也验证了IHCCMIAGA 和ITPX 的有效性，其在缩减最小完工时间的应用中可取得满意效果。

编 辑 税 红

[23] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research, 1995,22(1): 5-13.

[24] CARLIER J. Ordonnancements à contraintes disjonctives[J]. RAIRO-Operations Research, 1978, 12(4):333-350.

[25] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research,1993, 64(2): 278-285.

[26] TOSUN Ö, MARICHELVAM M K. Hybrid bat algorithm for flow shop scheduling problems[J]. International Journal of Mathematics in Operational Research, 2016,9(1): 125-138.

[27] TASGETIREN M F, LIANG Y C, SEVKLI M, et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research, 2007, 177(3): 1930-1947.

[28] LIN Q, GAO L, LI X, et al. A hybrid backtracking search algorithm for permutation flow-shop scheduling problem[J]. Computers and Industrial Engineering, 2015,85(C): 437-446.

[29] LUO Q, ZHOU Y, XIE J, et al. Discrete bat algorithm for optimal problem of permutation flow shop scheduling[J].The Scientific World Journal, 2014, DOI: 10.1155/2014/630280.

[30] LI Z, GUO Q, TANG L. An effective DE-EDA for permutation flow-shop scheduling problem[J]. 2016 IEEE Congress on Evolutionary Computation. [S.l.]:IEEE, 2016:2927-2934.

[31] 张先超, 周泓. 变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J]. 计算机集成制造系统,2016, 22(3): 774-781.ZHANG X C, ZHOU H. Variable parameters quantuminspired evolutionary algorithm and its application permutation flow-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2016, 22(3): 774-781.

[32] TSENG L Y, LIN Y T. A hybrid genetic algorithm for nowait flowshop scheduling problem[J]. International Journal of Production Economics, 2010, 128(1): 144-152.

[33] DING J Y, SONG S, GUPTA J N D, et al. An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem[J]. Applied Soft Computing, 2015,30(1): 604-613.

[34] ZHAO F, LIU H, ZHANG Y, et al. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2017,91(1): 347-363.

[35] NAWAZ M, ENSCORE E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. The International Journal of Management Science, 1983, 11(1): 91-95.

[36] PAN Q K, WANG L, ZHAO B H. An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion[J]. The International Journal of Advanced Manufacturing Technology, 2008,38(7): 778-786.

猜你喜欢基因库适应度染色体天然生物物种基因库：重庆五里坡国家级自然保护区阅读（高年级）(2022年9期)2022-10-08改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28我国最大藜麦基因库落户山西农谷今日农业(2021年1期)2021-11-268个基因库逾万分种子10月入库Svalbard全球种质库国际种业前沿动态(2020年18期)2020-12-23多一条X染色体，寿命会更长科学之谜(2019年3期)2019-03-28为什么男性要有一条X染色体？科学之谜(2018年8期)2018-09-29一种基于改进适应度的多机器人协作策略郑州大学学报（工学版）(2018年2期)2018-04-13中国首个国家基因库开始运营科学24小时(2016年11期)2016-11-08能忍的人寿命长恋爱婚姻家庭·养生版(2016年9期)2016-09-07基于空调导风板成型工艺的Kriging模型适应度研究中国塑料(2016年11期)2016-04-16