融合學習策略和鄰域搜索的飛蛾火焰算法

郭佳麗，王秋萍，王曉峰

西安理工大學 理學院，西安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 五種算法在標準測試案例上的結果比較