改进近邻人工蜂群算法求解柔性作业车间调度问题

李瑞 徐华 杨金峰 顾一帆

收稿日期：2023-06-26；修回日期：2023-07-31  基金项目：国家自然科学基金资助项目（62106088）

作者简介：李瑞（1998—），男，安徽马鞍山人，CCF会员，硕士研究生，主要研究方向为智能计算、车间调度；徐华（1978—），女（通信作者），江苏无锡人，副教授，硕导，博士（后），主要研究方向为人工智能、车间调度及大数据（841983007@qq.com）；杨金峰（1998—），男，山东烟台人，硕士研究生，主要研究方向为模糊理论、柔性车间调度；顾一帆（1998—），男，江苏无锡人，硕士研究生，主要研究方向为分布式车间调度、柔性车间调度．

摘  要：为了更好地解决以最小化最大完工时间为目标的柔性作业车间调度问题，提出了一种改进的人工蜂群算法。首先，采用随机选择和反向学习策略来提高初始蜜源的质量。同时，设计了一种新颖的特征表示方式，用于计算蜜源之间的距离。在引领蜂阶段，通过引入交叉和变异策略来优化种群中的近距离蜜源。在探索蜂阶段，引入了六种变邻域方法，以扩大解空间的搜索范围。而在侦查蜂阶段，则根据蜜源的潜力值剔除局部最优个体。在15个数据集上进行了广泛实验，实验结果表明，该改进算法性能明显优于其他四种著名的群智能优化算法。该研究为解决柔性作业车间调度问题提供了一种新的有效方法，对于实际生产调度具有重要的实用价值。

关键词：人工蜂群算法；柔性作业车间调度；特征表示；邻居；变邻域搜索；潜在价值

中图分类号：TP18    文献标志码：A

文章编号：1001-3695（2024）02-018-0438-06

doi：10.19734/j.issn.1001-3695.2023.06.0239

Improved algorithm of near-neighbor artificial bee colony for

flexible Job-Shop scheduling

Li Rui，Xu Hua，Yang Jinfeng，Gu Yifan

（School of Artificial Intelligence & Computer Science，Jiangnan University，Wuxi Jiangsu 214122，China）

Abstract：This paper proposed an improved artificial bee colony algorithm to better address the flexible Job-Shop scheduling problem with the objective of minimizing the makespan.Firstly，it employed random selection and reverse learning strategies to enhance the quality of initial food sources.Simultaneously，it designed a novel feature representation method to calculate the distance between food sources.During the leading bee phase，it introduced cross-over and mutation strategies to optimize nearby food sources in the population.Moreover，in the exploring bee phase，it incorporated six variable neighborhood me-thods to expand the search space of solutions.Subsequently，in the scout bee phase，it eliminated local optima individuals based on the potential value of their food sources.This paper conducted extensive experiments on 15 datasets，and the results demonstrate that the performance of the proposed improved algorithm significantly outperforms that of four other well-known swarm intelligence optimization algorithms.This study provides a novel and effective approach for solving the flexible Job-Shop scheduling problem with the goal of minimizing the makespan，holding important practical value for real-world production scheduling.

Key words：artificial bee colony；flexible Job-Shop scheduling；feature representation；neighbor；variable neighborhood search；potential value

0  引言

由于柔性車间调度问题（flexible Job-Shop scheduling problem，FJSP）考虑了机器柔性，所以在实际生产中具有更广泛的适用性，一直以来都是运筹学领域研究的热点。在FJSP中，每个工件的每道工序可以在多台机器上进行加工，而不同机器上的加工时间存在差异。因此，相对于传统的作业车间调度问题（Job-Shop scheduling problem，JSP），FJSP更为复杂，更符合智能制造的实际应用场景。

目前，智能优化算法被广泛应用于FJSP的求解。例如，王凌等人［1］使用协同群智能优化解决考虑运输时间的分布式绿色柔性作业车间调度问题；潘全科等人［2］通过改进粒子群算法，使其能够适用于具有连续特性的调度问题；Devi等人［3］将萤火虫算法与动态自适应方法相结合，用于求解柔性作业车间调度。此外，研究人员还对花授粉算法［4］、果蝇算法［5］和教学优化算法［6］进行了改进，并将其应用于FJSP。尽管学者们已经提出了许多智能优化算法来处理FJSP，但目前尚未有一种算法能够在所有问题上获得最优解。因此，进一步的研究对于FJSP仍然是必要的，以获得更好的优化结果。

人工蜂群算法（artificial colony algorithm）是Karaboga等人［7］基于蜜蜂分工合作行为提出的一种优化算法。该算法在各种问题中得到了广泛应用。Cui等人［8］提出一种基于分数阶微积分的人工蜂群算法算法，用于解决机器人路径规划问题；Zhou等人［9］将人工蜂群算法与混沌系统相结合，作用于图像加密领域；Zhu等人［10］将人工蜂群算法应用于学校时间表问题的求解；Kaya等人［11］对人工蜂群算法在组合优化问题中的研究现状进行了综述。

此外，人工蜂群算法在柔性作业车间调度问题上也得到了越来越多的应用。郑小操等人［12］将混沌理论引入到初始化过程中，提出了一种基于邻域搜索的改进人工蜂群算法，用于解决柔性作业车间调度问题；裴小兵等人［13］将人工蜂群算法与博弈理论相结合，通过获得子博弈精炼纳什均衡的方式解决了多目标车间调度问题；另外，吴锐等人［14］设计了一种包含三维向量的编码方案，用于解决分布式柔性作业车间调度问题；Sassi等人［15］提出一种新型的基于分解的人工蜂群算法，用来求解多目标柔性作业车间调度。尽管智能优化算法在解决FJSP上取得了一定的进展，但在将人工蜂群算法运用到车间调度时仍存在一些问题亟待解决。首先，由于人工蜂群算法本身的特性，需要将其映射为离散编码才能应用于组合优化问题。其次，该算法在空间中进行随机寻优，无法充分利用到优质个体的特征，导致收敛速度较慢。最后，尽管算法具有参数较少、运行速度较快的优点，但其局部搜索能力仍然有待提高。

针对以上问题，本研究提出了一种改进算法，并将其应用于柔性作业车间调度问题。首先，针对离散型问题，采用两段式编码策略，将连续型编码转换为离散型编码，以便更好地处理离散型调度问题。此外，针对算法初始化解的质量问题，提出了一种基于反向学习的初始化方法，以提高初始解的质量。为了克服传统人工蜂群算法无法直接作用于离散问题的缺陷，本研究引入了遗传算法中的交叉和变异操作，取代原算法中的位置更迭操作。同时，提出一种基于特征的邻居定义方式，进一步增强算法的全局搜索能力和优质个体利用能力。为了进一步提高算法的搜索能力，本研究设计了六种邻域搜索方式，用于在搜索过程中扩大解空间。这些邻域搜索方式能够更充分地探索解空间，从而寻找潜在的更优解。最后，使用更合理的蜜源潜力值定义方式，剔除了陷入局部最优的个体，以保证算法的继续推进能力，防止陷入局部最优。通过对基准算例进行的大量仿真实验，本研究验证了改进算法在解决柔性作业车间调度问题上的有效性。

1  柔性作业车间调度问题

在当今实际生产和制造领域，智能调度决策的优劣直接关系到企业的实际生产效益和竞争力。作为一个重要的调度问题，柔性作业车间调度问题一直备受关注。在FJSP中，有n个工件，每个工件由一道或多道工序组成。每个工序可以从一组候选机器中选择一台机器进行加工。不同的机器具有不同的加工时间，而总共有m台可用机器。本研究的目标是为每个工序安排适当的加工顺序，并为每个工序选择适合的加工机器，以使最大完工时间最小化。FJSP需要满足以下约束条件：

a）准备就绪状态：所有工件和机器在开始时处于准备就绪状态，即可以立即进行加工。

b）机器限制：一台机器在同一时间只能加工一道工序，即同一时间只能有一项加工任务进行。

c）工序加工选择：每道工序可能有多台机器可供加工选择，但同一时间只能选择一台机器进行加工。

d）加工中断：一旦开始加工，就不能中断，即加工过程必须连续进行，不允许中途暂停或中断。

e）工序顺序：每个工件必须按照指定的顺序进行工序加工，即前一道工序完成后才能开始下一道工序。

f）工件优先级：每个工件加工的优先级相同，即所有工件的加工时间都应得到合理安排，不出现某个工件长时间等待的情况。

针对上述约束条件和目标函数，本研究旨在开发出一种有效的调度策略，以解决FJSP。通过优化工序的加工顺序和机器的选择，以及合理分配工件的加工时间，最大完工时间可以被最小化，从而提高生产效率和资源利用率。令C表示最大完工时间，Cj表示第j个工件的完工时间，n为工件总数，则目标函数可表示为

C=min（max（Cj））  1≤j≤n（1）

2  人工蜂群算法

2.1  基本人工蜂群算法

人工蜂群算法是一种元启发式算法，模仿蜂群的觅食行为，算法共分成四个阶段，包括初始化阶段、引领蜂阶段、观察蜂阶段和侦查蜂阶段。详细步骤如下：

a）算法初始化。算法初始化分为两个主要部分。首先，需要设置人工蜂群算法的参数。这些参数包括蜜源数量、控制次数、蜂群数量以及迭代次数。蜜源数量等同于引领蜂的数量，也等同于跟随蜂的数量。通过设置合适的参数，可以调整算法的收敛速度和搜索能力。其次，需要生成初始种群。在基本的ABC算法中，人工蜂群由引领蜂、跟随蜂和侦查蜂组成。每个引领蜂对应一个蜜源，而每个蜜源代表一个可行解。蜜源的质量决定了可行解的适应度。在算法初始化階段，需要生成初始的蜜源。蜜源的产生如式（2）所示。

Xi，j=Xminj+r×（Xmaxj-Xminj）（2）

其中：j∈{1，2，…，n}，i∈{1，2，…，SN}；r是一个0～1的随机数；Xi，j表示第i个蜜源第j维的变量；Xmaxj表示第j维的上界；Xminj表示第j维的下界。

b）引领蜂阶段。引领蜂对当前蜜源附近进行搜索，更新方式如式（3）所示。

Vi，j=Xi，j+φi，j×（Xi，j-Xk，j）（3）

其中：k≠i，Φ为［-1，1］的随机数。通过上式计算新蜜源的适应度并与原蜜源进行比较，如果新蜜源比原蜜源更优，则将新蜜源取代原蜜源，否则保留原蜜源。

c）观察蜂阶段。观察蜂根据引领蜂带来的信息飞到蜜源所在的位置，并围绕蜜源进行搜索。较优的蜜源具有更高的吸引力，因此会吸引更多的观察蜂。选择蜜源的概率可通过式（4）计算：

Pi=fiti/∑SNj=1fitj（4）

d）侦查蜂阶段。当一个蜜源在连续limit次的搜索中没有找到更好的解时，对应的引领蜂将被转换为侦查蜂。侦查蜂通过随机寻找新的蜜源来进行搜索，新蜜源位置如式（2）所示。

2.2  编码与解码

本文采用了一种两段式编码方式，分别对工序排序和机器选择这两个子问题进行编码。在工序编码中，使用位次来表示每道工序的顺序。而在机器编码中，表示每道工序选择的机器。工序编码的长度与机器编码的长度相等。

图1左半部分展示了机器编码的示例。机器编码表示当前工序在可选机器集中选择第几台机器。例如，图1中机器编码第三个数字2表示工序O21选择了可选机器集中的第二台机器M3进行加工。第六个数字1表示工序O32选择了可选机器集中的第一个机器M2进行加工；图1右边部分展现了工序编码的形态，工序编码层中的数字表示当前工序的排序位次。对于同一个工件来说，可能有几道工序需要加工。对于重复出现的工件编号，该编号第几次出现则表示为该工件的第几道工序。例如，图1中工序编码部分的第二个数字1为第一次出现，表示为工序O11，是所有加工工序中第二道執行的工序；最后一个数字1表示工件1的第二道工序，同时，工序O12也是最后进行加工的工序。

在解码过程中，采用了贪婪解码方法。通过工序编码，可以确定所有工序的加工顺序。然后根据机器编码，确定每道工序在哪台机器上进行加工，并确定相应的加工时间。对于每个工序，按照从前往后的顺序遍历可选机器，找到最早可进行加工的时间。通过按照上述方式安排所有工序，可以得到最终的调度解，并绘制甘特图。

2.3  种群初始化

在元启发式算法中，初始种群的质量对算法的收敛速度产生重要影响。本节提出了一种集成了四条规则的初始策略，旨在提高初始种群的质量。针对机器编码，本文采用了随机规则和全局最小加工时间的方式进行初始化，比例为1：1。对于工序编码，采用了随机和反向学习的策略，以增加初始种群的多样性和均匀性，比例同样为1：1。通过将这四种策略结合起来，可以获得高质量的初始解。四条规则如下：

a）随机工序规则。生成长度等于工序数的工序编码，并将编码随机打乱，产生多种不同的工序排列。共SN/2条。SN为种群数。

b）反向学习规则。每次选择一条已生成的随机工序规则中的工序，并将其逆置。这样可以生成一部分与原规则相反的工序排列，增强初始种群的广泛性，避免种群过于集中。

c）随机机器规则。针对每一条工序，在可选机器集中随机选择一台机器进行加工。使每个工序具有随机的机器选择，增加了初始解的多样性。

d）全局最小加工时间规则。随机决定工件加工顺序，并每次选择使总加工时间最短的机器。这样可以保证初始种群中的解具有较优的加工时间，提高了解的质量。

为验证初始化方法的有效性，本章对提出的随机规则和反向学习规则进行消融实验。其中，random表示机器编码和工序编码都只采用随机规则；reverse表示机器编码采用随机规则，工序编码采用反向学习规则；random+reverse为本文提出的四条规则结合算法。算法分别运行10次，迭代100次，初始种群数量为100。在算例MK4上分别运行10次的平均结果的收敛图如图2所示。

图2显示了算例MK在不同初始化策略下的迭代值。从图中可以看出，在机器编码方面，仅仅采用随机规则难以得到较高质量的初始解，初始解的质量一定程度上会对收敛过程产生影响。而采用随机规则和全局最小加工时间的方式，意味着以相等的概率选择这两种方式来确定工序对应的机器。随机规则的目的是增加初始解的多样性，而全局最小加工时间的方式则有助于减少加工时间较长的机器的使用频率，以提高解的质量。

对于工序编码，随机策略的作用是增加初始解的多样性，而反向学习策略的目标是通过引入反向学习算子来提高初始种群的均匀性。从图中可以看出，仅使用反向学习规则会影响种群的多样性，导致收敛速度降低。而采用了随机和反向学习的策略，平衡多样性和均匀性之间的权衡，会使种群在收敛速度上得到提升的同时收敛到更好的结果。

通过综合考虑这四种策略，能够获得质量较高的初始解。这样的初始种群具有较好的多样性和均匀性，为后续的元启发式算法提供了更有潜力的搜索空间，从而提高算法的性能和收敛速度。

2.4  近邻交叉

本文提出了一种基于邻居的交叉变异方式，并设计了一种特征表示方式来表示引领蜂个体。在该特征表示方式中，使用矩阵M来表示引领蜂个体，其中，Mij表示工序编码中第i位和第j位之间的距离。与传统的海明距离只关注同一位置上的差异不同，本文提出的特征表示方式更加注重工序之间的相对顺序，更符合工序之间的实际特性。

举例来说，若一个工序OS1加工的先后顺序为［1，4，2，3］，则其对应的特征矩阵如图3所示。其中，M21=2表示工序O21在工序O11之后两个位置进行加工。通过将两个个体的特征矩阵相减，再将求得的结果矩阵中的元素取绝对值并求和，即可得到两个个体之间的距离。计算公式如式（5）所示。

Dx，y=∑pj=1  ∑pi=1|Mx，i，j-My，i，j|（5）

其中：Dx，y表示第x个个体与第y个个体的距离；Mx，i，j表示第x个个体的特征矩阵；p为工序数，也等于工序编码的长度。

每个引领蜂都对应着一个蜜源，并且与当前位置最近的T个引领蜂被定义为该引领蜂的邻居。在交叉变异过程中，随机选择一个邻居，并与当前引领蜂进行交叉变异操作。具体步骤如下：

a）距离计算和邻居选择：根据式（5），计算每个蜜源之间的距离，并选择离目标蜜源最近的T个邻居作为其邻居集合。

b）邻居选择和交叉操作：从邻居集合中随机选择一个邻居，然后使用部分映射交叉（POX）和均匀交叉（UX）两种交叉算子进行操作，以生成新的蜜源。

c）蜜源比较和更新：将新蜜源与原蜜源进行比较，保留适应度较好的蜜源作为下一代的解。

d）潜力值调整和状态转换：如果新蜜源未能改善原蜜源的适应度，降低原蜜源的潜力值；反之，恢复新蜜源的潜力值。当蜜源的潜力值降至零时，引领蜂将被转换为侦查蜂。

改进近邻人工蜂群算法通过引入近邻交叉策略，限制交叉操作的范围，并且近距离的个体往往具有相似的基因组合。这意味着优良个体的近邻个体很可能也是优良个体。因此，在近邻交叉过程中，两个优良个体之间的交叉有助于保留和传递优秀的基因信息。这样的邻域搜索策略有助于改进算法跳出局部极值，提高全局搜索能力。

在传统的交叉变异策略中，个体之间进行交叉和变异的概率是相等的，因此个体在交叉和变异后变得更优或更劣的可能性是完全随机的。然而，在近邻交叉策略中，优秀个体之间的交叉更有可能保留和传递优秀的基因信息。相比之下，传统的随机交叉变异策略缺乏对优秀个体的特殊保护，个体之间的交叉和变异是随机进行的，无法保证在新一代中保留优秀基因的概率。为验证近邻交叉策略的有效性，设计了如下对比实验：将本文提出的基于近邻交叉的改进算法，称为INABC。与之对比的是传统交叉变异策略的算法，称为IABC。这两个算法在交叉变异策略上存在差异，而其余的模塊保持相同。分别在MK4、MK7、MK10算例上运行10次，迭代100次，初始种群数量为100。实验结果如表1所示。将在MK10中运行10次的数据取平均值，记录的收敛对比如图4所示。

最优值（Best）、平均值（Avg）这两个指标在一定程度上可以说明算法的性能。通过对比表1实验结果，可以观察到INABC在性能指标上的优越性。其中， INABC在Best上均取得更优结果，说明INABC对解空间搜索能力更强，有更强的寻优能力；在Avg上结果更优，说明INABC数据波动较低，鲁棒性更强，综合效果更好。图4为两种交叉策略在算例MK10上运行十次的收敛效果图。可以观察到INABC不仅收敛速度更快，收敛结果也更强。综上所述，基于近邻的交叉变异策略性能显著强于传统的交叉变异策略。

2.5  强化领域搜索

在解决组合优化问题时，邻域搜索是一种简单而有效的方法，用于拓展搜索空间、挖掘潜在的优质解，并提升算法的局部搜索能力。然而，当采用集中式邻域搜索方式时，逐一执行的方式会造成大量时间的浪费；而如果选择随机执行，成功率则会显著降低。鉴于此，本文参考了RVNS［16］的思路，应用强化学习方法，以自适应地选择最有可能成功的邻域搜索策略。

2.5.1  邻域结构

本文提出了六种邻域结构。描述如下：

a）邻域结构N1：随机选择一道工序，将其选择的机器改为加工时间最少的机器。

b）邻域结构N2：随机选择一道工序，将其加工机器随机改为另一台机器。

c）邻域结构N3：通过计算每台机器的负载，随机选择一道工序，并将该工序当前选中的机器负载减去。然后在可选机器中选择能使机器总负载最小的一台机器进行加工。

d）邻域结构N4：随机交换两道工序的位置。

e）邻域结构N5：随机将一道工序插入到另一道工序之前。

f）邻域结构N6：找到最后完成的工序，并将其换到另一台机器进行加工。

2.5.2  算法步骤

通过引入强化学习，算法能够根据问题的特征和当前搜索状态，智能地选择邻域搜索策略。这种自适应选择策略使得算法更加高效，避免了无效的搜索步骤，从而提高了找到优质解的成功率。相较于传统的集中式邻域搜索方法，基于强化学习的自适应策略在时间和效果上都有显著的改进。

基于强化学习的自适应邻域搜索策略为解决组合优化问题提供了一种创新的方法，它能够根据具体问题和搜索状态动态调整，以充分利用搜索资源并提升算法的性能和效率。这一策略不仅在理论上具有潜力，在实际应用中也展现出了良好的应用前景。算法步骤如下：

a）评估每种邻域搜索方式的质量，每种邻域搜索方式的选择概率与其质量评估成正比。

b）根据质量，选择一个邻域搜索方式，生成一个新的蜜源。质量越高的邻域搜索方式被选中的概率越大。通过应用该邻域搜索方式对当前蜜源进行改变，产生一个新的解决方案。

c）比较新蜜源与原蜜源的质量，判断是否可以替代原蜜源。如果新蜜源优于原蜜源，则将新蜜源插入到成功矩阵SM（success matrix）和失败矩阵FM（failure matrix）的尾部。

d）如果CM和FM中的记录数超过了设定的限定数目L，按照先进先出的原则，删除CM和FM中的第一条记录。

e）基于更新后的CM和FM信息，重新计算每种邻域搜索方式被选中的概率。根据邻域搜索方式在CM和FM中的记录数目比例来确定其被选中的概率，记录数目比例越高，被选中的概率越大。

2.6  潜力值更新

为了避免算法陷入局部最优解，需要淘汰那些相似度接近且潜力值耗尽的个体。每个个体的初始潜力值设定为一个预定义的限制值。在搜索过程中，如果未能找到更优质的蜜源，将降低该蜜源的潜力值，否则恢复该蜜源的潜力值。潜力值的更新公式如下：

Pi=Pi-fi/z（6）

其中：Pi表示第i个蜜源的潜力值；fi表示第i个蜜源的目标函数值；z表示当前迭代下的最优目标函数值。当前蜜源离最优结果越接近，则下降的值越小；离最优结果越远，则下降的值越大。这种潜力值更新策略在一定程度上加快了算法的收敛速度，同时保留了对更优解的探索能力。当蜜源的潜力值耗尽时，需要将该蜜源抛弃，并重新寻找新的蜜源。为此，提出了三种寻找新蜜源的策略，如图5所示。

a）循环移位：生成一个区间在［1，SN/2］的随机数r，将工序编码循环左移r位，并对每个工序随机选择一台新的机器。SN为工序编码长度。

b）反向循环：首先将工序编码反向，然后按照上述循环移位策略进行左移操作。

c）随机选择：利用初始化阶段中的随机规则重新生成一个新的蜜源。

在传统人工蜂群算法的侦察蜂阶段，如果个体在连续探索一定次数后仍未发现优质蜜源，传统方法会采取重新生成个体的初始化策略。然而，这种思路导致个体在停滞后需要一定的探索次数才能被替换，使得个體更新速度较慢，并且会导致对陷入局部最优个体的算力消耗过多。为了克服这一问题，改进后的潜力值更新算法引入了一种新的策略。该算法对离最优值较远的个体施加较大的惩罚力度，从而极大地加快了算法的收敛速度。相比传统方法，改进算法能够更快地发现并替换掉表现较差的个体。另外，原有的个体更换策略在传统方法中是通过使用初始化方式重新生成个体。然而，这种方式可能导致新个体与原有个体类似，从而使种群的多样性受到限制。为了增加种群的多样性，改进算法采用了三种策略重新生成个体，如图5所示。这些策略可以产生与原有个体基因距离较远的新基因，从而大大丰富了种群的基因库，提高了种群的多样性。其中，循环移位策略保留了原蜜源的某些特征，增强了算法的探索能力；反向循环策略扩大了搜索范围，提升了算法的广度；随机选择策略有助于跳出局部最优解，增加了算法的多样性。改进后的潜力值更新算法能更快地收敛到最优值，也使得种群更易跳出局部最优，并且保持了种群的多样性。

2.7  算法流程

改进的ABC算法用于解决FJSP时，首先采用四种混合规则的初始化方法生成高质量的初始蜜源。蜜源的编码采用基于工序的编码方式，而解码过程则采用贪婪解码方法以获得最优解。为了增强算法的局部搜索能力，使用六种邻域操作与近邻进行交叉变异，以发现周围的优质蜜源，提高蜜源的质量并加快种群的收敛速度。为了避免陷入局部最优解，对潜力值耗尽的蜜源采取三种方式进行重新选择。算法的基本流程如下：

a）初始化参数，包括蜜源数量、引领蜂和侦查蜂的数量，以及初始潜力值（limit）。

b）使用2.3节中的初始化方法初始化蜜源，并计算蜜源的邻居和适应度值。

c）引领蜂阶段，对于每个蜜源，采用2.4节中的近邻方法寻找一个邻居，并与之进行交叉变异，保留优质解，弃置劣质解。

d）跟随蜂阶段，根据适应度值采用轮盘赌方式选择一个蜜源，使用2.5节中的邻域搜索方法探索周围的优质蜜源。

e）侦查蜂阶段，对于潜力值耗尽的个体，采用2.6节中的选择方式初始化一个新的蜜源，并将潜力值重置为初始值。

f）如果达到最大迭代次数，则算法结束；否则返回步骤c）。

在本文中算法复杂度主要来源于解码，用P代表种群数量，T代表邻居大小，It代表迭代次数，k表示潜力值耗尽的个体比例。用解码次数表达复杂性如下：

初始化阶段：O（P）；

引领蜂阶段：O（T×It×P）；

跟随蜂阶段：O（It×P）；

侦察峰阶段：O（k×P）；

综上所述，INABC的复杂度上界为O（T×It×P）。

3  仿真实验与测试

本研究算法在一台配置Intel i5-6300HQ处理器、16 GB内存、64位Windows操作系统的计算机上运行处理，使用PyCharm 2022编程环境进行实现。为了验证算法的有效性，在大量的测试中，设置以下参数来进行算法的运行：种群规模为100，迭代次数为100，引领蜂的数量、跟随蜂的数量以及侦查蜂的数量都等于种群规模，选择邻居的个数为5，交叉概率为0.8，变异概率为0.1。

3.1  基准算例仿真实验

表2的记录对应于文献［17～20］中针对各个算例进行了十次运行的实验结果，其中，Best代表算法在算例上运行十次得到的最优结果，Avg为十次结果的平均值，PRD代表相对百分比差异，用于评估当前算法与最优算法之间的差距。在本文中，PRD的计算公式简化为：（R2-R1）/（R1+R2）×100。其中，R1表示当前算法的最优值，R2表示所有算法中的最优值。PRD越小，算法越优。Mean列表示PRD的平均值。标粗数字为所有算法中的最优值。

为了验证改进方法的有效性，本文对算法中提到的几种改善机制进行验证。在表2中，列出了几种不同算法及其相应的结果。其中，ABC表示基本的人工蜂群算法，不包含任何改善机制。ABCin表示在ABC算法中加入了初始化方法。ABCN表示在ABCin算法的基础上加入了近邻交叉方法。ABCVns表示在ABCN算法的基础上加入了变邻域搜索方法。INABC则指的是本文提出的改进算法。

从表2的数据中可以看出，加入初始化方法后，无论是在最优值的探索能力还是整体稳定性方面，算法都取得了显著的提升。在加入近邻交叉方法后，算法对最优值的探索能力作进一步提升。加入变邻域搜索方法后，虽然算法的整体稳定性不如ABCN算法，容易陷入局部最优，但在最优值的探索能力方面更加强大。最后，加入潜力值更新策略后，算法在探索能力和稳定性之间达到了一个平衡。可以观察到，INABC算法在几种算法中几乎总是能达到最优值，而且其平均RPD值也是最低的。实验结果表明，几种改进方法在不同方面都有一定的改善效果，综合运用可以得到较优的结果，整体算法有一定的有效性。

3.2  改进方法有效性实验

表3记录了本文算法与文献［17～20］在Kacem数据集上的比较。可以看出，在小数据集上，INABC皆能取得最优结果。

表4展示了五个算法在Brandimate数据上的运行结果。其中，INABC除了在MK10数据集上略逊于文献［19］，在其他所有算例中皆取得最优结果，可以证明INABC的有效性和优越性。

4  结束语

针对柔性作业车间调度的特点，提出了一种改进的人工蜂群算法。首先，提出了一种采用随机规则和反向学习规则的初始化方法，在提高初始种群多样性的同时兼顾了质量；为实现个体间的信息交互，设计了一种以相似度为评判标准的近邻交叉方式；提出了六种邻域搜索方式，增强算法的局部搜索能力。为避免算法陷入布局最优，设计了基于潜力值的更新策略。通过在多个算例上运行实验，INABC在求解FJSP上相较其他算法更具有效性。

后续工作将深入研究多目标的柔性作业车间调度问题，同時针对车间调度问题中的约束问题进行深入探索，结合强化学习方法挖掘算法性能，使算法更贴近实际生产场景。

参考文献：

［1］王凌，王晶晶.考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化［J］.中国科学：技术科学，2023，53（2）：243-257.（Wang Ling，Wang Jingjing.A cooperative memetic algorithm for the distributed green flexible Job-Shop with transportation time［J］.Sci Sin Tech，2023，53（2）：243-257.）

［2］潘全科，王凌，高亮.离散微粒群优化算法的研究进展［J］.控制与决策，2009，24（10）：1441-1449.（Pan Quanke，Wang Ling，Gao Liang.The-state-of-art discrete particle swarm optimization algorithms［J］.Control and Decision，2009，24（10）：1441-1449.）

［3］Devi K G，Mishra R S，Madan A K.A dynamic adaptive firefly algorithm for flexible Job-Shop scheduling［J］.Intelligent Automation & Soft Computing，2022，31（1）：243-257.

［4］刘二辉，姚锡凡，陶韬，等.基于改进花授粉算法的共融AGV作业车间调度［J］.计算机集成制造系统，2019，25（9）：2219-2236.（Liu Erhui，Yao Xifan，Tao Tao，et al.Improved flower pollinaton algorithm for Job-Shop scheduling problem integrated with AGVs［J］.Computer Integrated Manufacturing Systems，2019，25（9）：2219-2236.）

［5］周永强，王翠雨，李颖俐，等.改进果蝇算法求解混合流水车间调度问题［J］.控制理论与应用，2023，40（4）：597-606.（Zhou Yongqiang，Wang Cuiyu，Li Yingli，et al.Improved fruit fly optimization algorithm for solving & the hybrid flow shop scheduling problem［J］.Control Theory & Applcations，2023，40（4）：597-606.）

［6］Lei Deming，Su Bin，Li Ming.Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling［J］.International Journal of Production Research，2021，59（23）：7232-7245.

［7］Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC） algorithm［J］.Journal of Global Optimization，2007，29（3）：459-471.

［8］Cui Yibing，Hu Wei，Ahmed R.Fractional-order artificial bee colony algorithm with application in robot path planning［J］.European Journal of Operational Research，2023，306（1）：47-64.

［9］Zhou Yanqi，Wang Erfu，Song Xiaomeng，et al.Image encryption algorithm based on artificial bee colony algorithm and chaotic system［J］.Security and Communication Networks，2022，2022：1444676.

［10］Zhu Kaixiang，Li L D，Li M.School timetabling optimisation using artificial bee colony algorithm based on a virtual searching space method［J］.Mathematics，2021，10（1）：73-73.

［11］Kaya E，Gorkemli B，Akay B，et al.A review on the studies employing artificial bee colony algorithm to solve combinatorial optimization problems［J］.Engineering Applications of Artificial Intelligence，2022，115.

［12］郑小操，龚文引.改进人工蜂群算法求解模糊柔性作业车间调度问题［J］.控制理论与应用，2020，37（6）：1284-1292.（Zheng Xiaocao，Gong Wenyin.An improved artificial bee colony algorithm for fuzzy flexible Job-Shop scheduling problem［J］.Control Theory & Applications，2020，37（6）：1284-1292.）

［13］裴小兵，王诗慧.基于博弈人工蜂群算法的多目标车间调度研究［J］.武汉大学学报，2023，56（3）：362-370.（Pei Xiaobing，Wang Shihui.Research on multi-objective shop scheduling based on game artificial bee colony algorithm［J］.Engineering Journal of Wuhan University，2023，56（3）：362-370.）

［14］吴锐，郭顺生，李益兵，等.改进人工蜂群算法求解分布式柔性作业车间调度问题［J］.控制与决策，2019，34（12）：2527-2536.（Wu Rui，Guo Shunsheng，Li Yibing，et al.Improved artificial bee colony algorithm for distributed and flexible Job-Shop scheduling problem［J］.Control and Decision，2019，34（12）：2527-2536.）

［15］Sassi J，Alaya I，Borne P，et al.A decomposition-based artificial bee colony algorithm for the multi-objective flexible Job-Shop scheduling problem［J］.Engineering Optimization，2022，54（3）：524-538.

［16］Li Rui，Gong Wenyin，Lu Chao.A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible Job-Shop scheduling［J］.Expert System With Applications，2022，203：117380.

［17］杜凌浩，向鳳红.改进多邻域候鸟优化算法那的柔性作业车间调度研究［J］.兵器装备工程学报，2022，43（12）：299-206.（Du Linghao，Xiang Fenghong.Research on flexible Job-Shop scheduling based on improved multi-neighborhood migratory bird optimization algorithm［J］.Journal of Ordnance Equipment Engineering，2022，43（12）：299-306.）

［18］姜天华.混合灰狼优化算法那求解柔性作业车间调度问题［J］.控制与决策，2018，33（3）：503-508.（Jiang Tianhua.Flexible Job-Shop scheduling problem with hybrid grey wolf optimization algorithm［J］.Control and Decision，2018，33（3）：503-508.）

［19］栾飞，吴书强，李富强，等.一种求解柔性作业车间调度问题的鲸鱼群优化算法［J］.机械科学与技术，2020，39（2）：241-246.（Luan Fei，Wu Shuqiang，Li Fuqiang，et al.A whale swarm optimization algorithm for solving flexible Job-Shop scheduling problem［J］.Mechanical Science and Technology for Aerospace Engineering，2020，39（2）：241-246.）

［20］姜天华.猫群优化算法求解柔性作业车间调度问题［J］.计算机工程与应用，2018，54（23）：259-263.（Jiang Tianhua.Cat swarm optimization for solving flexible Job-Shop scheduling problem［J］.Computer Engineering and Applications，2018，54（23）：259-263.）