改進近鄰人工蜂群算法求解柔性作業車間調度問題

李瑞 徐華 楊金峰 顧一帆

收稿日期：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.）