武子科，潘 攀+，彭 诚，吕秀莎，梁子涵，张洪光

(1.中国空间技术研究院 北京东方计量测试研究所，北京 100093； 2.北京邮电大学 电子工程学院，北京 100876)

0 引 言

仪表检测工作正由传统的人工检测转变为自动化检测。自动化仪表检测中，为节省批次任务时间同时满足仪表检测顺序约束的资源分配问题，构成了一个作业车间调度问题[1](job shop scheduling problem，JSSP)。由于作业车间调度问题的NP-Hard特性[2]和No-Free-Lunch特性对于不同应用场景没有通用的求解方法[3]，目前已有较多在经典启发式算法上做出改进的算法，如并行迭代的双种群混合遗传算法[4]和混合并行布谷鸟搜索算法[5]，使用邻域搜索的改进Jaya算法[6]和局部邻域搜索算法[7]，以及结合几种算法优势的ALPS-GA算法[8]和混合NSGA-II算法[9]等。鲸鱼优化算法由Mirjalili等[10]提出，是一种源于座头鲸群狩猎的仿生学算法[11,12]。在作业车间调度问题中，已有使用量子旋转门[13]、使用莱维飞行[14]的鲸鱼优化算法，但在具体场景中应用的研究还刚刚起步。

自动化仪表检测工作中的仪表种类较多，且检测差异较大，其调度问题对比经典调度问题具有数据复杂(不同仪表检测时长相差较大)、稳定性要求高的特点。因此，需要有能够同时在有效性和稳定性方面表现更好的算法来提升自动化仪表检测工作的效率。本文根据自动化仪表检测中的作业车间调度问题特点，提出了一种基于生命力选择的精英鲸鱼优化算法，达到了提高检测效率、节省检测成本的目的。首先，介绍了作业车间调度问题的相关定义和模型；然后，提出了基于生命力选择的精英鲸鱼优化算法；最后，在标准数据集和北京东方计量测试研究所自动化仪表检测的实际调度问题中进行了仿真实验，验证了算法的有效性和稳定性。

1 作业车间调度模型

作业车间调度问题模型由工件集J={J1,J2,…,Jn} 和对其进行加工的机器集M={M1,M2,…,Mm} 组成，每个工件Ji均按照自身的加工顺序在对应机器Mk上执行相应的工序Oik。相关的参数定义见表1。对于该问题有如下假设：

(1)每个工件需按照自身加工顺序在对应机器上完成加工；

(2)工件工序有固定的加工时间，且加工过程不能中断；

(3)一台机器同一时刻只能加工一个工件；

(4)一个工件同一时刻只能被一台机器加工；

(5)0时刻所有机器和工件均可用；

(6)不考虑机器故障及工件到达延迟等问题。

本文使用整数规划模型[5]来描述作业车间调度问题，并以最小化Cmax为优化目标，如式(1)～式(4)所示。式(1)为目标函数；式(2)表示每个工件的加工顺序对应于该工件指定的加工顺序；式(3)表示每台机器一次只能加工一个工件；式(4)表示每个工件在每台机器上的完工时间为非负数

(1)

cik-tik+G(1-aihk)≥cih,i=1,2,…,n;h,k=1,2,…,m

(2)

cjk-cik+G(1-xijk)≥tjk,i,j=1,2,…,n;k=1,2,…,m

(3)

cik≥0,i=1,2,…,n;k=1,2,…,m

(4)

表1 参数定义

在自动化仪表检测中，仪表在多个自动化检测设备之间进行检测，将仪表视为工件、自动化检测设备视为机器，则其中的调度问题模型与作业车间调度问题模型一致。因此，对于作业车间调度模型的优化方法同样能够应用于实际自动化仪表检测工作中。

2 求解作业车间调度问题的精英鲸鱼优化算法

2.1 基本鲸鱼优化算法

鲸鱼优化算法(WOA)是一种群体智能优化算法，该算法模拟了自然界中座头鲸群的捕食过程，包括包围猎物、气泡网攻击和搜寻猎物3种行为。鲸鱼优化算法使用座头鲸代表所求可行域中的可行解，从一组随机解开始，在每次迭代中，选取当前最优解作为猎物位置，其余座头鲸随机选择执行其中一种行为来更新自身位置，实现向猎物的靠近，直至完成捕食过程。

2.1.1 包围猎物

座头鲸识别猎物的位置，并将其包围的过程可以用以下数学公式进行表述

D=|C·X*(t)-X(t)|

(5)

X(t+1)=X*(t)-A·D

(6)

A=2a·r1-a

(7)

C=2·r2

(8)

其中，“·”表示点乘，t为当前迭代次数；式(5)中D表示座头鲸与猎物之间的距离， “|·|” 表示取绝对值，X(t) 表示座头鲸在第t次迭代中的位置，X*(t) 表示猎物的位置；式(6)表示座头鲸个体位置更新的方式；A和C表示系数矢量，分别用式(7)和式(8)计算，其中，a在迭代过程中从2线性减少到0，r1和r2为[0,1]中的随机向量。

2.1.2 气泡网攻击

在气泡网攻击过程中，座头鲸首先会吐出气泡将猎物包围在气泡中，然后通过收缩围圈和螺旋上升同时进行的方式靠近猎物。收缩围圈过程与包围猎物过程相同。螺旋上升过程用以下数学公式进行描述

D′=|X*(t)-X(t)|

(9)

X(t+1)=D′·ebl·cos(2πl)+X*(t)

(10)

式(9)中D′表示座头鲸与猎物之间的距离，式(10)中b是用于限定对数螺旋形状的常数，l是在[-1,1]中的随机数。

为了使收缩包围和螺旋上升同步进行，座头鲸在捕食过程中有50%的可能性通过收缩包围或螺旋上升来进行更新位置。此行为用以下数学公式进行描述

(11)

式中：p是[0,1]中的随机数。

2.1.3 搜寻猎物

为了保证鲸鱼优化算法的全局搜索能力，当 |A|≥1时，每个座头鲸根据随机选取的其它座头鲸的位置来更新自身位置信息。此行为用以下数学公式进行描述

D=|C·Xrand-X(t)|

(12)

X(t+1)=Xrand-A·D

(13)

其中，Xrand是随机选取座头鲸的位置。

当 |A|<1时，选择当前最优解作为猎物位置来更新其余座头鲸的位置，并且根据p的值进行收缩包围或螺旋上升。

2.2 基于生命力选择的精英鲸鱼优化算法

鲸鱼优化算法具有结构简单、求解精度高、稳定性好的特点，但仍存在收敛速度慢、容易陷入局部最优等问题。因此，本文提出了精英鲸鱼优化算法，使用生命力选择方法来确定种群中连续表现较差的个体，并使用表现较好个体的变异体或随机生成的新个体进行替换。该方法可以及时淘汰连续表现较差的个体，避免其浪费过多的计算成本；反之，对连续表现较好的个体，则进行深入挖掘，提升种群搜索效率。通过反复迭代，不断更新鲸群位置，使得种群逐渐向最优解收敛。

2.2.1 算法框架

精英鲸鱼优化算法框架如算法1所示。

算法1：精英鲸鱼优化算法

输入：生命力上限Vmax，生命力下限Vmin，选择压力Sp

(1)初始化种群位置Xi(i=1,2,…N)

(2)计算每个个体的适应度

(3)令X*为当前最佳适应度

(4)while(t<最大迭代次数)

(5) fori=1 toNdo:

(6) 生成[0,1]中的随机数r1,r2,p

(7) 按式(7)、 式(8)计算A,C的值

(8) if1(|A|≥1)

(9) 根据式(13)更新第i个个体位置(搜寻猎物

(10) 过程)

(11) else if1(|A|<1)

(12) if2 (p<0.5)

(13) 根据式(6)更新第i个个体位置(包

(14) 围猎物过程)

(15) else if2(p≥0.5)

(16) 根据式(10)更新第i个个体位置(螺

(17) 旋上升过程)

(18) end if2

(19) end if1

(20) end for

(21) 计算每个个体当前的适应度

(22) 根据个体适应度的变化，计算个体生命力

(23) 根据算法2，使用生命力选择方法替换生命力较

(24) 差的个体

(25)end while

2.2.2 编码方法

由于精英鲸鱼优化算法为连续函数的优化算法，而作业车间调度问题为离散的组合优化问题，因此，应对精英鲸鱼优化算法中输出的种群进行离散化处理。本文首先将连续编码进行升序排列，然后将连续编码分配给按照序号升序排列的工件，最后将工件序号填充到连续编码的原位置，得到对应的离散编码。在该编码方案下，所有生成的解均为可行解，每个离散编码序列代表一个可行的调度方案，由工件编号组成，每个工件序号代表该工件工序的顺序执行。

考虑3个工件3台机器的作业车间调度问题，每个工件都需在3台机器上执行一道对应的工序，工件的加工顺序见表2。以算法中某次的连续编码(0.15-0.26-0.36-0.69-0.34-0.59-0.06-0.77-0.82)为例，首先将其升序排列为(0.06-0.15-0.26-0.34-0.36-0.59-0.69-0.77-0.82)，然后将(0.06-0.15-0.26)分配给工件一，将(0.34-0.36-0.59)分配给工件二，将(0.69-0.77-0.82)分配给工件三，最后将工件序号填充到连续编码的原位置，即可得到离散编码(1-1-2-3-2-2-1-3-3)，由于每个工件都有其固定的工序执行顺序，则编码中工件序号的第N次出现，可以表示该工件的第N个工序。则该离散编码对应的执行顺序为(O12-O13-O21-O31-O22-O23-O11-O33-O32)，具体过程如图1所示，甘特图如图2所示。

本文使用一组从-100到100随机生成的个体作为初始种群。

表2 3×3问题加工顺序

图1 编码的离散化和对应的调度方案

图2 离散编码(1-1-2-3-2-2-1-3-3)对应调度顺序的甘特图

2.2.3 生命力选择方法

生命力选择方法是一种广泛适用于优化问题的选择算子[15]，其原理为，使用个体在迭代中取得的进步作为个体的评价标准，如果一个个体在一代中取得了进步，则对该个体进行保护，如果该个体在长期迭代中未能得到进步，则可能被放弃。生命力选择方法通过识别和保护具有旺盛生命力的个体，在种群早熟时抛弃虽然具有较好适应度，但是难以继续取得进步的个体，并提供产生新个体的机会，加强了全局搜索范围、避免了算法提前收敛。

在搜索过程中，种群每个个体的初始生命力被设置为floor((Vmax+Vmin)/2)， 其中floor(·)为向下取整函数。在每次迭代中，首先将适应度最高的个体生命力设置为Vmax，其余个体根据当前适应度和上一代适应度计算生命力，当前适应度小于上一代适应度时，个体生命力计算公式如式(14)所示；当前适应度大于上一代适应度时，个体生命力计算公式如式(15)所示。计算完种群中所有个体的生命力后，将根据个体生命力做出调整，生命力较低的个体将被替换。具体算法过程如算法2所示

(14)

(15)

算法2：生命力选择方法

输入：生命力上限Vmax，生命力下限Vmin，选择压力Sp

(1)将种群中适应度较高的一半组成集合PopA， 适应

(2)度较低的一半组成集合PopB

(3)对于PopA中的每个个体:

(4) if1Vi==Vmin

(5) 生成一个随机数r3∈(0,1)

(6) if2r3

(7) 对该个体执行逆序变异操作

(8) else if2r3≥Sp

(9) 对种群中适应度最高的个体执行逆序变

(10) 异操作，并替换掉当前个体

(11) end if2

(12) end if1

(13)对于PopB中的每个个体:

(14) if3Vi==Vmin

(15) 生成一个随机数r4∈(0,1)

(16) if4r4

(17) 从PopA中随机选择一个个体执行逆序

(18) 变异操作，并替换掉当前个体

(19) else if4r4≥Sp

(20) 随 机生成一个新个体，并替换掉当前个体

(21) end if4

(22) end if3

其中，算法中的逆序变异操作指在个体中选择两个位点，将两个位点间的编码进行逆序重排。如图3所示，随机选取编码中的位置3和位置7，则所选连续编码为(0.36-0.69-0.34-0.59-0.06)，对应离散编码为(2-3-2-2-1)，则转换得到的调度方案为(O21-O31-O22-O23-O11)。对位置为3-7之间的元素进行逆序重排，则得到的连续编码为(0.06-0.59-0.34-0.69-0.36)，由于离散编码与连续编码的大小对应，所以得到的离散编码为(1-2-2-3-2)。因为调度方案与离散编码并非是一一对应关系，而是需要根据工件的实际工序做出调整，所以得到的调度方案并非是原方案的逆序重排，而应是与离散编码相对应的(O11-O21-O22-O31-O33)。

图3 逆序变异过程

2.2.4 性能分析

图4显示了本文提出EWOA算法的搜索过程。使用二维平面表示问题的搜索解空间，灰色五角星代表真实最优解的位置，圆圈代表种群中的个体。在算法初始阶段，对种群进行初始化，使所有个体均匀分布于搜索空间(图4(a))。在WOA搜索阶段，将当前最优个体标记为最优解位置(图4(b)中灰色圆)，所有个体随机的对其进行螺旋包围，或向其它个体靠近，进行全局的搜索。而在一次WOA搜索过程结束后，使用生命力选择算法对种群进行进一步的优化，淘汰掉长期无进步的个体(图4(c)中带网格的圆)，使用新生的个体(图4(c)中黑色圆)对有搜索潜力的区域做进一步挖掘，避免提前收敛的同时提高局部的搜索性能。EWOA算法引入的生命力搜索虽然在每一代的搜索中增加了对生命力的计算工作，但避免了由无搜索潜力的个体带来的计算成本，所以并不会造成过大的计算负荷，可以在有限的计算资源中提升算法的搜索性能。

图4 EWOA算法搜索过程

因此，本文提出的EWOA算法从理论上提升了传统WOA算法的性能，能够更好地适用于优化问题的求解。

3 实验仿真与讨论

3.1 实验设计

为测试精英鲸鱼优化算法求解作业车间调度问题的性能，本文使用了作业车间调度问题标准数据集和北京东方计量测试研究所自动化仪表检测数据集，进行了仿真实验。标准数据集包括OR-Library(http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/jobshop1.txt)中的3个FT实例、4个LA实例和5个ABZ实例，共计12个实例。北京东方计量测试研究所自动化仪表检测实验室由10个机械臂自动检测环节O1～O10组成，30个不同的待检测件均需按不同的顺序要求完成相应检测工作。图5显示了实验室布局情况，和其中两个执行不同检测任务的自动检测环节实物图。本文选取该实验室实际检测中的10组数据作为10个实例，使用编号P1-P10进行区分(https://github.com/ZikeW/JSSP.git)。

图5 自动化仪表检测流水线布局

本文选取近年来求解车间调度问题的高性能算法，即灰狼优化算法[16](GWO)、扩展遗传算法[17](EGA)、改进Jaya算法[18](IJA)和鲸鱼优化算法[10](WOA)作为对比算法。实验中，所有算法的种群规模设置为50；GWO算法的邻域搜索参数设定为10，局部搜索参数设定为30；EGA算法的交叉参数设为0.7，变异参数设为0.1；IJA算法的邻域搜索参数设为0.9；EWOA算法的选择压力设定为0.7，生命力上限设定为11，生命力下限设定为1。所有算法的终止条件均设置为种群进化800代。

针对每个问题，每种算法都运行50次，通过比较50次Cmax的平均值(Mean)，来测试算法的有效性。此外，使用误差棒来表示50次Cmax的标准差，来比较算法的稳定性。

3.2 实验结果与分析

如图6所示，在作业车间标准数据集测试问题中，GWO、EGA和IJA等3种求解车间调度问题的成熟算法和EWOA均表现良好，有着较好的Cmax平均值，而WOA算法未能取得较好的结果。在对实验结果进一步分析后可以发现，除WOA外的4种算法在所有实例中的搜索结果的最小值与文献中记录的实验下限相同或接近。以实例LA31为例，文献中记录的最小值为1784，4种算法搜索到的最小值均为1784，GWO算法搜索到的平均值为1920.3，标准差为39.2；EGA算法搜索到的平均值为1870.7，标准差为41.6；IJA算法搜索到的平均值为1831.1，标准差为38.6；EWOA算法搜索到的平均值为1836.0，标准差为36.5。该实例上的实验结果表明，几种算法均能搜索到实例的最小值，而EWOA算法有着较小的Cmax平均值和最低的标准差。在所有实例的实验结果中，EWOA算法实验结果的平均值与文献中记录的最小值(BKS)较为接近，且有着较小的标准差，虽然部分算法的搜索性能超过了EWOA算法，但EWOA算法的综合表现仍是最优的。以上实验结果说明：①EWOA算法相对于传统的WOA算法能够在相同的迭代次数内获得更好的实验结果，有着显著的搜索性能提升；②尽管有很多算法在标准车间调度问题数据集中取得了优秀的结果，EWOA算法仍是非常有竞争力的算法之一，有着相对更好的有效性和稳定性。

图6 标准实例实验结果

图7显示了在北京东方计量测试研究所自动化仪表检测数据集中的实验情况。WOA算法未能在终止条件内完成收敛，有着极大的平均值和标准差，不能适用于问题的求解。在标准数据集中有着优秀表现的GWO、EGA和IJA等3种算法，表现都较为普通。而EWOA算法在所有问题中都取得了最好的Cmax平均值和标准差，相对于其它算法有着明显较高的有效性和稳定性优势。以上实验结果说明：

EWOA算法相比于GWO、EGA、IJA和WOA算法，更适合于作业车间调度实际问题的求解，可以有效应用于自动化仪表检测实际任务中，能够提升工作效率，节省检测成本。

图7 自动化仪表检测数据集实例实验结果

两组实验结果表明，作业车间调度问题的复杂性对算法的有效性和稳定性有一定影响，能够适用于某种场景的算法未必能够在另一种场景中有着同样优秀的表现。在自动化仪表检测场景中，本文提出的EWOA算法能够很好适应场景的复杂性，同时能够满足场景的有效性和稳定性要求，可以应用于实际调度问题的求解。

4 结束语

鲸鱼优化算法是一种新兴的智能优化算法，多用于连续优化问题，在离散的调度问题中应用较少。本文提出了一种精英鲸鱼优化算法，验证了其在作业车间调度问题的可行性。在标准数据集和北京东方计量测试研究所的自动化仪表检测数据集中进行了仿真实验，验证了提出算法的有效性和稳定性，可以应用于自动化仪表检测的实际工作中。

在未来自动化仪表检测工作调度问题的研究中，仪表检测任务临时增减、工件运输等事件会影响检测工作的统筹调度，如何解决这些在线的自动化仪表检测调度问题，是进一步的研究方向之一。