融合学习策略和邻域搜索的飞蛾火焰算法

郭佳丽，王秋萍，王晓峰

西安理工大学 理学院，西安710054

随着全球经济一体化和信息技术的发展，制造企业面临的困难越来越艰巨，如全球经济放缓、生产成本上升、资源环境约束等。生产调度问题作为制造系统的一个核心问题，主要研究资源的分配问题，针对不同的任务，制定相应的优化目标，最后找到最优或者近似最优的解决方案。合理的智能调度策略可以优化协调企业整体的生产、运输和管理，提高企业的生产效率并节约生产成本，推动智能制造的进一步发展，因此对调度问题的研究具有重要意义。作业车间调度问题（Job Shop Scheduling Problem，JSSP）作为最基础、最广泛的组合优化调度问题，具有NP难性[1]。传统的用于解决JSSP的确定性算法如列举法、整数规划、拉格朗日松弛法和分支定界法通常被用来解决小规模调度问题，当问题规模增大时，由于确定性计算方法的局限性，因此在有限的时间内很难得到最优解。在过去的二十多年，以模拟生物行为为基础的群智能优化算法如粒子群算法[2]、蚁群算法[3]、萤火虫算法[4]等，创造了一种称为“种群”的潜在解，通过种群内个体之间的相互合作与竞争所产生的群体智能来寻优，在最优化领域得到广泛的关注和迅速的发展，为人们解决实际的优化问题提供了新的思路和手段。诸多学者使用群智能优化算法以及它们的改进算法求解作业车间调度问题，并验证了这些方法的有效性。如Adil等[5]测试了教学算法在组合优化问题上的性能。采用一种基于最大位置值规则的随机密钥方法获得JSSP的工件排列。利用Giffler和Thompson算法构造调度表，有效地解决了作业车间调度和流水车间调度问题。张梅等[6]针对教学算法局部搜索能力不足的缺陷，提出基于个体差异化自学习的改进教学算法，使学习过程不仅考虑个体间的相互学习，还应考虑个体的自我学习能力，并将改进的教学算法用于求解作业车间调度问题。Asadzadeh[7]提出具有动态迁移策略的并行人工蜂群算法来求解作业车间调度问题。在该方法中，人工蜂群算法由位于网络不同主机上的多个蜂群组成，不同的蜂群以并行方式更新。动态迁移策略用于确定蜂群何时与其邻域个体进行信息交流。Zhao等[8]考虑到Shuffled Complex Evolution算法存在求解精度低、收敛速度慢等缺点，提出一种新的策略改变个体的进化，使产生的新解更接近全局最优解，并将改进的算法用于求解作业车间调度问题。Wang等[9]将混沌理论和“围绕最优搜索”策略与基本生物地理学优化算法相结合，使其更快、更稳定地收敛到作业车间调度问题的全局最优解。对于作业车间调度问题的求解，这些方法虽然弥补了确定性方法寻找全局最优解的缺陷，但在求解某些调度问题时仍存在易陷入局部最优，无法获得全局最优的问题，因此开展作业车间调度问题与群智能优化算法的研究仍然是生产调度领域的重要问题。

基于上述文献，为获得更精确和有效的结果，本文对基本飞蛾火焰算法进行改进并用于作业车间调度问题。飞蛾火焰优化算法（Moth Flame Optimization algorithm，MFO）[10]是Mirjalili受飞蛾在夜间使用横向定位飞行这一生物行为的启发，于2015年提出的一种元启发式算法。一个飞蛾的位置对应于求解问题的一个解，火焰储存了到目前为止飞蛾群体能够找到的最优解。MFO算法选用对数螺旋更新机制，螺旋的起点是飞蛾，终点为火焰的位置。飞蛾可以收敛到火焰周围的任意一个位置，保证了火焰周围的开发。给每一个飞蛾分配火焰列表中的一个火焰，每次迭代基于最好位置更新火焰列表，增加了对搜索空间的探索，降低了算法陷入局部最优的可能性。在迭代过程中，自适应减少火焰数量平衡了算法的探索与开发能力。

目前MFO算法已成功用于求解最优潮流计算[11]、解决最优无功调度[12]和多级阈值图像分割[13]等实际优化问题。与其他群智能算法一样，基本飞蛾火焰算法也存在后期种群多样性不足，火焰数量的减少可能使算法陷入局部最优等缺点。为解决这些问题，对基本飞蛾火焰算法做以下方面改进：（1）将拟反向学习策略引入到火焰更新过程，增加火焰种群的多样性，提高了算法的全局探索能力。在迭代后期，有助于火焰从局部最优中跳出。（2）对飞蛾种群基于适应度值排序并分为两组，其中一组使用排序配对学习策略增加飞蛾个体间的信息交流，产生新的飞蛾个体解。另一组使用交换、插入、反转三种邻域算子产生邻域解，以增加飞蛾种群的多样性，提高算法的局部开发能力。本文提出了一种融合学习策略和邻域搜索的飞蛾火焰算法（Hybrid Moth Flame Algorithm with Learning Strategy and Neighborhood Search，LNHMFO）。选取30个CEC 2017测试函数进行实验，测试结果和统计分析表明了所提算法的求解精度和稳定性得到了改善。此外，通过对ORLibrary中的案例进行测试，实验结果表明，所提算法与文献中的方法相比，在解决作业车间调度问题上更有效、更鲁棒。

1 作业车间调度问题描述

JSSP可描述为：车间内n个工件要在m台机器上进行加工，每个工件有m道工序，每道工序在不同的机器上进行加工。各个工件在m台机器上均有其自身固定的加工顺序，并且各道工序的加工时间是确定的。每台机器在同一时刻最多只能加工一个工件，每道工序必须等到其所有前继工序加工完毕后才能开始加工，每个工序的加工过程不能中断。JSSP的目标是在现有的约束条件下合理安排每台机器上工件的加工顺序，使某些调度指标达到最优。本文选用的调度指标为完成所有工件所需的加工时间（makespan）最短。

用整数规划模型表示作业车间调度问题[6]：假设J=1,2,…,n为工件集合，M=1,2,…,m为机器集合，其目标函数和约束条件为：

其中，i,j=1,2,…,n，h,k=1,2,…,m，R为一个足够大的正数，cik为第i个工件在第k台机器上的完工时间，t ik为第i个工件在第k台机器上的加工时间。

2 基本的飞蛾火焰优化算法

MFO算法是受飞蛾在夜间使用横向定位飞行这一生物行为的启发提出的一种新的元启发式算法。其中飞蛾表示在搜索空间中移动的搜索个体，而火焰是到目前为止飞蛾获得的最佳位置。每只飞蛾以所对应的火焰作为寻优指导，不断调整自己的飞行轨迹向全局最优解靠拢。MFO算法具体描述如下。

（1）种群初始化

在MFO算法中，假设飞蛾是候选解，问题的变量是飞蛾在搜索空间中的位置。飞蛾种群用矩阵表示如下：

其中，n表示飞蛾的个数，d表示变量的个数。

对于所有飞蛾，用一个数组OM来存储相应的适应度值，如公式（7）所示：

在MFO算法中另一个关键的组成部分是火焰，火焰位置是与飞蛾位置相同维度的变量矩阵：

同样对于所有火焰，用数组OF来存储相应的适应度值，如公式（9）所示：

（2）位置更新过程

MFO算法给每只飞蛾分配一个特定的火焰，使用对数螺旋来更新飞蛾的位置，公式如下：

其中，D i=|F j-Mi|是飞蛾Mi与火焰F j之间的距离，b是与螺旋形状相关的常数，随机数t∈[-1,1],t=-1表示离火焰最近的位置，t=1表示离火焰最远的位置。在优化过程中，为了进一步增强开发能力，假定t是[r,1]中的随机数，r从-1线性递减到-2。

在迭代的初始阶段有n个火焰，MFO算法自适应减少火焰数量直到保留最后一个最优火焰，如式（11）：

其中，l是当前迭代次数，T是最大迭代次数，n是最大火焰数，flame_no是第l次迭代的火焰数。

迭代过程中火焰数量自适应减少是为了平衡算法的探索与开发能力。随着迭代的进行，火焰的数量越来越少，飞蛾的数量相对会有“多余”，这时让多余的飞蛾围绕第flame_no个火焰更新位置。

3 融合学习策略和邻域搜索的飞蛾火焰算法

MFO算法采用了一种基于火焰矩阵的位置更新机制，具有较好的搜索能力。然而，基于精英保留的贪婪策略可能会使得火焰丧失种群多样性、过早陷入局部最优而使得飞蛾无法跳出。此外，火焰数量自适应减少使得迭代后期围绕第flame_no个火焰的飞蛾数增加，就导致种群多样性丧失[14]。基于此，本文将拟反向学习策略、排序配对学习策略、邻域搜索策略与基本的MFO算法结合以进一步提高算法的搜索能力。

3.1 拟反向学习策略

2005年，Tizhoosh提出了反向学习的概念，主要思想是同时评估当前解和其反向解，择优保留，以此来增强群智能算法的优化性能。反向点的定义如下：

定义1[15]（反向点）若X=(x1,x2,…,x d)是d维空间的点，其中x i∈(a i,b i)，则反向点的定义如式（12）：

反向点采用固定最大最小边界来计算给定点的中心对称点，拟反向点是在反向点和搜索空间的中心点之间产生的随机数，一维空间点x的反向点xo与拟反向点x qo的分布如图1所示。

图1 一维空间的点x、反向点xo与拟反向点x qo

与反向学习策略不同的是，拟反向学习策略同时评估当前解和其拟反向解，择优保留，在处理黑箱优化问题时有更高的机会接近问题的未知最优解。拟反向点的定义如下：

定义2[16]（拟反向点）若X=(x1,x2,…,x d)是d维空间的点，其中x i∈(ai,b i)，则拟反向点的定义如式（13）：

将拟反向学习融入到基本的MFO算法中，计算每个火焰F j的拟反向点，然后，比较火焰F j与的适应度值，保留具有更小适应度值的火焰，并记为。

Rahnamayan等人在文献[17]中证明了拟反向点比反向点有更高的概率接近问题的未知最优解。拟反向学习策略用于火焰更新过程，在搜索空间的中心位置与火焰的反向位置之间随机生成新的火焰，增加了火焰种群的多样性，择优保留。飞蛾围绕保留的火焰寻优，提高了算法的全局搜索能力。MFO算法中火焰随着迭代次数的增加自适应减少，在迭代后期拟反向学习策略有助于火焰跳出局部最优，避免算法早熟收敛。

3.2 排序配对学习策略

在一个学习小组中，实行成对辅导，较差的个体向比它优秀的个体学习来提升自己，这种配对学习行为能够提高整个团体的质量[18]。受这种配对学习行为的启发，本文提出排序配对学习策略（RPL）来实现飞蛾个体间的信息交流，丰富种群多样性，提升整个飞蛾种群的质量。RPL学习框架如图2所示。在标准MFO位置更新之后，对当前飞蛾种群基于适应度值排序，然后所有的飞蛾被划分到两个组中，其中，样本组（GE）包含前一半具有较好适应度值的飞蛾，学习组（GL）包含后一半具有较差适应度值的飞蛾。分别表示GE与GL组中第i个飞蛾的位置，GE与GL组的飞蛾满足以下条件：

图2 排序配对学习过程

为扩大样本和学习者间适应度值的差异，GL组的飞蛾采用如下的学习规则选择学习样本：

并基于文献[19]提出的位置更新方法，对GL组的飞蛾个体根据其与学习样本之间的差异采用式（15）、（16）进行位置更新，如下式：

3.3 基于邻域搜索算子的邻域搜索策略

使用交换、插入这两种邻域搜索算子，对于大多数问题足以得到更好的解。根据实验的经验，对于一些高维的困难问题，需要一个跳出局部最优的策略[1]。本文将反转算子与交换算子、插入算子结合并融入到基本的MFO算法中。对GE组的每个飞蛾，随机选取两个不同的维p与q，从以下三种邻域结构算子中依概率选择一种算子产生飞蛾个体的邻域解。即在[0，1]区间产生一个随机数r,若0＜r≤0.2,则使用交换算子；若0.2＜r≤0.6，则使用插入算子；若0.6＜r≤1，则使用反转算子。

（1）交换算子，交换飞蛾个体第p维与第q维的值，得到新的个体。交换算子的实例如图3所示。

图3 交换算子，p=2且q=7

（2）插入算子，将飞蛾个体第p维的值插入到第q维的位置上，得到新的个体。插入算子的实例如图4所示。

图4 插入算子，p=2且q=7

（3）反转算子，将飞蛾个体第p维与第q维之间的值进行反转，得到新的个体。反转算子的实例如图5所示。

图5 反转算子，p=2且q=7

产生飞蛾的邻域个体后，通过评估两者的适应度值，选择适应度值更小的个体保留至下一代。这种贪婪选择操作既增加了种群的多样性，又保证了解的质量。

3.4 算法描述

LNHMFO算法的步骤描述如下：

步骤1设置算法参数，包括种群规模n，维数d，最大迭代次数T。

步骤2令迭代次数l=0，在搜索空间内随机产生初始飞蛾种群M。

步骤3计算飞蛾种群的适应度值OM。

步骤4根据式（11）计算火焰的数量flame_no。

步骤5若当前迭代次数l=1,则根据OF=sort(OM),F=sort(M)更新火焰种群。否则根据OF=sort(OM l-1,OM l),F=sort(Ml-1,Ml)更新火焰种群，记录第一个火焰为最好个体。

步骤6计算每个火焰的拟反向点。

步骤7根据式（14）更新飞蛾的位置。

步骤8基于适应度值对当前飞蛾种群按升序方式排序。前一半的飞蛾使用邻域搜索策略更新位置，而后一半的飞蛾则使用式（15）～（16）更新位置。通过评估适应度值，选择最优个体保留至下一代。

步骤9判断算法是否达到最大迭代次数，若是，则算法结束，输出最优值。否则令l=l+1，返回步骤3。

以下综合分析了本文算法全局寻优与局部寻优的平衡性。

本文在MFO算法中将拟反向学习策略引入到火焰更新过程，增加火焰种群的多样性，提高了算法的全局探索能力。在迭代后期，有助于火焰从局部最优中跳出。对飞蛾种群基于适应度值排序并分为两组，其中一组使用排序配对学习策略增加飞蛾个体间的信息交流，产生新的飞蛾个体解。另一组使用交换、插入、反转三种邻域算子产生邻域解，以增加飞蛾种群的多样性，提高算法的局部开发能力。三种策略的有效结合平衡了本文算法的探索与开发能力，使其具有更高的求解精度和更强的稳定性。

与反向点相比，拟反向点有更高的概率接近问题的未知最优解，Rahnamayan等人在文献[17]中证明了如下定理：

定理1[17]假设x、xo和x qo分别是候选解及其反向解、拟反向解。x∗是问题的未知最优解，则

其中，d(⋅)是到x∗的距离。

3.5 算法的复杂度分析

MFO算法的计算复杂度依赖于飞蛾的个数n、变量的个数d、最大迭代次数T和每次迭代火焰的排序机制。由于使用了快速排序，在最好和最坏情况下排序的计算复杂度分别是O(nlbn)和O(n2)。所以基本MFO算法的计算复杂度是：

O(MFO)=O(T(O(快速排序)+O(位置更新)))

LNHMFO在基本MFO算法中引入了拟反向学习策略、排序配对学习策略和邻域搜索策略。其中，拟反向学习策略的计算复杂度为O(nd)，排序配对学习策略的计算复杂度为O((n/2)d)，邻域搜索策略的计算复杂度为O((n/2)d)。因此，LNHMFO算法的计算复杂度是：

综上，LNHMFO和基本MFO算法相比，运算量稍微增加了一点，计算复杂度是一样的，但求解精度和稳定性得到了改善。

3.6 数值实验与结果分析

对于随机优化算法，选择适当的测试集来测试其性能是非常有必要的。因此，本节使用具有挑战性的IEEE CEC 2017测试函数来评估LNHMFO算法的寻优性能[20]。测试函数的详细信息见参考文献。将LNHMFO与MFO、LMFO[21]、QOGWO[22]、AWOA[23]、OBSCA[24]算法的结果进行比较。为体现比较公平性，将所有算法的初始化种群设定相同，实验参数统一设置如下：种群规模为50，维数为50，最大迭代次数为1 000。为减少随机性的影响，将所有算法在每个测试函数上独立运行30次。

使用Wilcoxon秩和检验来检验对比算法与LNHMFO之间是否存在显著性差异，取显著性水平α=0.05。表1给出了六种算法在30个测试函数上独立运行30次的实验结果，其中包含平均误差、标准差以及Wilcoxon检验的p-value，加粗数据表示每个测试函数对应的最佳结果，最后一行的“+/=/−”分别表示用Wilcoxon秩和检验时对比算法“优于/无差异/劣于”LNHMFO算法函数的个数。

由表1可知，与MFO、AWOA和OBSCA算法的比较，在几乎所有的函数上，LNHMFO算法明显优于这三种比较算法。LNHMFO优于、劣于和等于LMFO算法的函数个数分别是29、0和1，说明LNHMFO在29个函数上的结果显著优于LMFO算法，在函数F3上的结果与LMFO算法无差异。LNHMFO优于、劣于和等于QOGWO算法的函数个数分别是18、3和9，说明LNHMFO在18个函数上的结果显著优于QOGWO算法，在函数F3、F16、F21上的结果没有QOGWO算法的结果好，在函数F5、F6、F7、F10、F17、F18、F20、F22、F26上的结果与QOGWO算法无差异。在多数情况下LNHMFO是六个算法中标准差最小的，说明其具有较好的稳定性。

图6给出六种算法在部分测试函数上的收敛曲线图。由图可以看出，LNHMFO算法随着迭代次数的增加持续寻优，未出现停止状况，且寻优精度较高。而其他比较算法的曲线下降平缓，在迭代后期出现不同程度的停滞，且寻优精度较低。综上可知，LNHMFO算法具有较快的收敛速度和较高的寻优精度。

表1 6种算法在CEC 2017测试函数上的实验结果

图6 LNHMFO与对比算法的收敛曲线图

在元启发式算法中，多样性可以反映出种群的分布情况，即分散和收敛情况。增加或保持算法的种群多样性，可以相应地提高算法的性能。为比较MFO与LNHMFO算法的种群多样性，本文采用种群中所有个体的距离之和来度量种群的多样性，第l次迭代种群多样性的计算公式如下：其中，n表示种群规模，d表示维数，Mij(l)表示第i个飞蛾在第j维的位置，如果D(l)越大，表明种群多样性越好。图7给出MFO与LNHMFO算法在部分测试函数（F2、F3、F8、F10、F22、F28）上的多样性变化曲线图。由图7可以看出，MFO算法在迭代初期种群多样性快速下降，之后多样性曲线保持平缓下降。相比于MFO算法，LNHMFO在整个迭代过程中保持了较高的多样性，由此说明排序配对学习和邻域搜索策略有利于维持种群多样性。

图7 LNHMFO与MFO算法的多样性变化图

为验证“拟反向学习策略、排序配对学习策略、邻域搜索策略”的有效性，本文选用单峰函数F1、F2，多峰函数F4、F9，混合函数F12、F13，组合函数F28、F30进行测试实验。将LNHMFO算法与仅使用拟反向学习的飞蛾火焰优化算法（记为QMFO）、仅使用排序配对学习策略的飞蛾火焰优化算法（记为RMFO）、仅使用邻域搜索策略的飞蛾火焰优化算法（记为NMFO）、基本的MFO算法的实验结果进行比较。为体现比较公平性，所有算法采用相同的初始种群，设置统一的参数值，即种群规模为50，维数为50，最大迭代次数为1 000，并将五种算法在每个测试函数上独立运行30次。表2给出了MFO、QMFO、RMFO、NMFO与LNHMFO这五种算法在8个测试函数上的平均误差值和标准差，并将最好的结果标记为黑体。

从表2的比较结果可知，采用单一改进策略的QMFO、RMFO和NMFO算法在8个测试函数上的求解精度和稳定性都优于基本的MFO算法，且三种策略的有效结合使得基本算法的求解精度和稳定性得到更进一步的提高。由此可知，本文提出的改进策略是有效的。

4 LNHMFO算法优化调度方案

4.1 编码方式

编码方式即为调度方案解的构造，在飞蛾火焰算法中，每一个飞蛾对应于该问题的一个解。飞蛾位置的每一维对应于一个工件的一个操作。对于n个工件m个机器的作业车间调度问题，每个飞蛾的位置表示为由实数组成的大小为m×n的行向量。针对要解决的JSSP离散调度优化问题，采用基于工序的编码方式对问题进行编码。可进行举例说明：对于3个工件在3个机器上加工的JSSP问题，搜索空间的维数是3×3维，构造一个调度解（1，2，2，3，1，3，1，2，3），其中，1，2，3为工件编号，第一次出现的“1”表示工件1的第1个工序，第二次出现“1”表示工件1的第2个工序，以此类推，这样编码可使调度解自动满足链式约束。

基本的MFO算法用于求解连续变量的优化问题，而JSSP是一个典型的组合优化问题，其解空间是离散的。因此，设计合适的表示方式实现连续值到离散值的转换，对于解决JSSP是至关重要的。本文通过使用Random-key（RK）编码方法[1]将连续型飞蛾位置向量转换为离散型工件加工序列，这样飞蛾的性能能够被评估。以3×3的JSSP为例解释RK，假设搜索空间中某个飞蛾的位置是[0.3，0.8，1.9，1.3，2.6，1.5，3.2，2.7，0.7]，通过升序的方式对这9个数排序，得到整数序列[1，3，6，4，7，5，9，8，2]，（例如，0.3是最小的数，它排名为1）。在这个整数序列中，整数3、6、9表示操作属于工件1。因为（3 mod 3）+1=1，（6 mod 3）+1=1，（9 mod 3）+1=1。整数1、4、7表示操作属于工件2。因为（1 mod 3）+1=2，（4 mod 3）+1=2，（7 mod 3）+1=2。整数2、5、8表示操作属于工件3。因为（2 mod 3）+1=3，（5 mod 3）+1=3，（8 mod 3）+1=3。这样就得到一个对应于工件的操作排列（2，1，1，2，2，3，1，3，3）。

4.2 解码方式

对调度解的解码过程如下[8]：

步骤1首先将编码的序列转化为工序表。

步骤2基于工序表和工件加工的约束条件对各操作以最早允许加工时间逐一进行加工。

步骤3产生调度方案。

对于一个3×3的JSSP问题，其加工时间和加工的机器如表3所示，假设有一个编码序列为（1，2，3，2，2，3，1，3，1），对应的工序加工序列为（J1，1，J2，1，J3，1，J2，2，J2，3，J3，2，J1，2，J3，3，J1，3），它表示先加工第1工件的第1道工序，再加工第2工件的第1道工序，依次类推，最后加工第1工件的第3道工序，对照机器和工件的工艺约束条件，产生相应的调度方案如下：

（1）在机器2上加工第1个工件的第1道工序，用时10 s。

（2）在机器2上加工第2个工件的第1道工序，用时5 s。

（3）在机器3上加工第3个工件的第1道工序，用时9 s。

表2 五种算法在部分测试函数上的结果比较

（4）在机器3上加工第2个工件的第2道工序，用时7 s。

（5）在机器1上加工第2个工件的第3道工序，用时4 s。

（6）在机器2上加工第3个工件的第2道工序，用时13 s。

（7）在机器1上加工第1个工件的第2道工序，用时6 s。

（8）在机器1上加工第3个工件的第3道工序，用时8 s。

（9）在机器3上加工第1个工件的第3道工序，用时3 s。

表3 3×3 JSSP的机器序列与工件加工时间

4.3 适应度函数

适应度函数是对调度解进行衡量的重要指标。在利用LNHMFO算法寻找最佳调度方案时，采用所有工件加工的完成时间最短为衡量指标。因此定义的适应度函数为：

其中，cik为第i个工件在第k台机器上的完工时间。

4.4 数值实验与分析

为验证LNHMFO算法求解作业车间调度问题的可行性与有效性，选取OR-Library中具有代表性的15个标准问题进行测试（http：//people.brunel.ac.uk/mastjjb/jeb/orlib/），其大小规模包括6×6、10×5、15×5、10×10、20×5。将LNHMFO算法与MFO算法的数据进行比较以验证LNHMFO算法的改进效果。将LNHMFO算法与PaGA算法[25]、GWO算法[26]、aLSGA算法[27]的结果进行比较以进一步表明NLSMFO算法的寻优精度。比较算法的结果直接取自文献[28]。为体现比较公平性，LNHMFO与MFO算法的参数统一设置如下：种群规模为40，最大迭代次数为500，将两种算法在每个标准问题上分别独立运行20次，运行结果如表4所示。在实验结果中，instance是测试问题的名称，size表示测试问题的规模n×m（n表示工件的个数，m表示机器的个数），BKS表示已知的最优解，EBS表示算法重复运行所求得最优解的平均值，R PD表示相对百分比误差，计算公式如下：

RPD的值越小，BKS与EBS的偏差越小，算法的性能越好。

由表4可知，对于15个不同规模的JSSP问题，基本的MFO算法仅找到6个最优解，而LNHMFO算法找到了13个最优解。说明改进算法具有更强的搜索能力，在有限的时间内能找到更多调度问题的最优解。与PaGA、GWO和aLSGA算法的比较进一步说明本文提出的LNHMFO算法在作业车间调度问题的求解上具有一定的有效性。

5 结束语

作业车间调度作为经典的组合优化难题，一直受到学术界的广泛关注。本文针对以最小化最大完工时间为目标的作业车间调度问题，提出一种融合学习策略和邻域搜索的飞蛾火焰算法以降低局部最优停滞的可能性并提高种群的多样性。对基本的飞蛾火焰算法做了以下改进：（1）将拟反向学习策略嵌入到火焰更新过程，有助于火焰从局部最优中跳出，并且提供了更高的机会接近问题的未知最优解。（2）对飞蛾种群基于适应度值分群，其中一个群采用排序配对学习策略以实现个体间的信息交流，另一个群采用邻域搜索策略以增加种群多样性，这种并行计算能更快地提升整个种群的质量。选取最新的IEEE CEC 2017测试函数进行数值实验，并与元启发式算法的改进版本进行比较，测试结果和统计分析验证了所提算法具有更高的求解精度和稳定性。将所提出的算法用于OR-Library中标准实例的求解，测试结果表明新提出的算法对作业车间调度问题是有效的。

表4 五种算法在标准测试案例上的结果比较