郭佳麗，王秋萍，王曉峰

西安理工大學(xué) 理學(xué)院，西安710054

隨著全球經(jīng)濟(jì)一體化和信息技術(shù)的發(fā)展，制造企業(yè)面臨的困難越來越艱巨，如全球經(jīng)濟(jì)放緩、生產(chǎn)成本上升、資源環(huán)境約束等。生產(chǎn)調(diào)度問題作為制造系統(tǒng)的一個核心問題，主要研究資源的分配問題，針對不同的任務(wù)，制定相應(yīng)的優(yōu)化目標(biāo)，最后找到最優(yōu)或者近似最優(yōu)的解決方案。合理的智能調(diào)度策略可以優(yōu)化協(xié)調(diào)企業(yè)整體的生產(chǎn)、運輸和管理，提高企業(yè)的生產(chǎn)效率并節(jié)約生產(chǎn)成本，推動智能制造的進(jìn)一步發(fā)展，因此對調(diào)度問題的研究具有重要意義。作業(yè)車間調(diào)度問題（Job Shop Scheduling Problem，JSSP）作為最基礎(chǔ)、最廣泛的組合優(yōu)化調(diào)度問題，具有NP難性[1]。傳統(tǒng)的用于解決JSSP的確定性算法如列舉法、整數(shù)規(guī)劃、拉格朗日松弛法和分支定界法通常被用來解決小規(guī)模調(diào)度問題，當(dāng)問題規(guī)模增大時，由于確定性計算方法的局限性，因此在有限的時間內(nèi)很難得到最優(yōu)解。在過去的二十多年，以模擬生物行為為基礎(chǔ)的群智能優(yōu)化算法如粒子群算法[2]、蟻群算法[3]、螢火蟲算法[4]等，創(chuàng)造了一種稱為“種群”的潛在解，通過種群內(nèi)個體之間的相互合作與競爭所產(chǎn)生的群體智能來尋優(yōu)，在最優(yōu)化領(lǐng)域得到廣泛的關(guān)注和迅速的發(fā)展，為人們解決實際的優(yōu)化問題提供了新的思路和手段。諸多學(xué)者使用群智能優(yōu)化算法以及它們的改進(jìn)算法求解作業(yè)車間調(diào)度問題，并驗證了這些方法的有效性。如Adil等[5]測試了教學(xué)算法在組合優(yōu)化問題上的性能。采用一種基于最大位置值規(guī)則的隨機(jī)密鑰方法獲得JSSP的工件排列。利用Giffler和Thompson算法構(gòu)造調(diào)度表，有效地解決了作業(yè)車間調(diào)度和流水車間調(diào)度問題。張梅等[6]針對教學(xué)算法局部搜索能力不足的缺陷，提出基于個體差異化自學(xué)習(xí)的改進(jìn)教學(xué)算法，使學(xué)習(xí)過程不僅考慮個體間的相互學(xué)習(xí)，還應(yīng)考慮個體的自我學(xué)習(xí)能力，并將改進(jìn)的教學(xué)算法用于求解作業(yè)車間調(diào)度問題。Asadzadeh[7]提出具有動態(tài)遷移策略的并行人工蜂群算法來求解作業(yè)車間調(diào)度問題。在該方法中，人工蜂群算法由位于網(wǎng)絡(luò)不同主機(jī)上的多個蜂群組成，不同的蜂群以并行方式更新。動態(tài)遷移策略用于確定蜂群何時與其鄰域個體進(jìn)行信息交流。Zhao等[8]考慮到Shuffled Complex Evolution算法存在求解精度低、收斂速度慢等缺點，提出一種新的策略改變個體的進(jìn)化，使產(chǎn)生的新解更接近全局最優(yōu)解，并將改進(jìn)的算法用于求解作業(yè)車間調(diào)度問題。Wang等[9]將混沌理論和“圍繞最優(yōu)搜索”策略與基本生物地理學(xué)優(yōu)化算法相結(jié)合，使其更快、更穩(wěn)定地收斂到作業(yè)車間調(diào)度問題的全局最優(yōu)解。對于作業(yè)車間調(diào)度問題的求解，這些方法雖然彌補(bǔ)了確定性方法尋找全局最優(yōu)解的缺陷，但在求解某些調(diào)度問題時仍存在易陷入局部最優(yōu)，無法獲得全局最優(yōu)的問題，因此開展作業(yè)車間調(diào)度問題與群智能優(yōu)化算法的研究仍然是生產(chǎn)調(diào)度領(lǐng)域的重要問題。

基于上述文獻(xiàn)，為獲得更精確和有效的結(jié)果，本文對基本飛蛾火焰算法進(jìn)行改進(jìn)并用于作業(yè)車間調(diào)度問題。飛蛾火焰優(yōu)化算法（Moth Flame Optimization algorithm，MFO）[10]是Mirjalili受飛蛾在夜間使用橫向定位飛行這一生物行為的啟發(fā)，于2015年提出的一種元啟發(fā)式算法。一個飛蛾的位置對應(yīng)于求解問題的一個解，火焰儲存了到目前為止飛蛾群體能夠找到的最優(yōu)解。MFO算法選用對數(shù)螺旋更新機(jī)制，螺旋的起點是飛蛾，終點為火焰的位置。飛蛾可以收斂到火焰周圍的任意一個位置，保證了火焰周圍的開發(fā)。給每一個飛蛾分配火焰列表中的一個火焰，每次迭代基于最好位置更新火焰列表，增加了對搜索空間的探索，降低了算法陷入局部最優(yōu)的可能性。在迭代過程中，自適應(yīng)減少火焰數(shù)量平衡了算法的探索與開發(fā)能力。

目前MFO算法已成功用于求解最優(yōu)潮流計算[11]、解決最優(yōu)無功調(diào)度[12]和多級閾值圖像分割[13]等實際優(yōu)化問題。與其他群智能算法一樣，基本飛蛾火焰算法也存在后期種群多樣性不足，火焰數(shù)量的減少可能使算法陷入局部最優(yōu)等缺點。為解決這些問題，對基本飛蛾火焰算法做以下方面改進(jìn)：（1）將擬反向?qū)W習(xí)策略引入到火焰更新過程，增加火焰種群的多樣性，提高了算法的全局探索能力。在迭代后期，有助于火焰從局部最優(yōu)中跳出。（2）對飛蛾種群基于適應(yīng)度值排序并分為兩組，其中一組使用排序配對學(xué)習(xí)策略增加飛蛾個體間的信息交流，產(chǎn)生新的飛蛾個體解。另一組使用交換、插入、反轉(zhuǎn)三種鄰域算子產(chǎn)生鄰域解，以增加飛蛾種群的多樣性，提高算法的局部開發(fā)能力。本文提出了一種融合學(xué)習(xí)策略和鄰域搜索的飛蛾火焰算法（Hybrid Moth Flame Algorithm with Learning Strategy and Neighborhood Search，LNHMFO）。選取30個CEC 2017測試函數(shù)進(jìn)行實驗，測試結(jié)果和統(tǒng)計分析表明了所提算法的求解精度和穩(wěn)定性得到了改善。此外，通過對ORLibrary中的案例進(jìn)行測試，實驗結(jié)果表明，所提算法與文獻(xiàn)中的方法相比，在解決作業(yè)車間調(diào)度問題上更有效、更魯棒。

1 作業(yè)車間調(diào)度問題描述

JSSP可描述為：車間內(nèi)n個工件要在m臺機(jī)器上進(jìn)行加工，每個工件有m道工序，每道工序在不同的機(jī)器上進(jìn)行加工。各個工件在m臺機(jī)器上均有其自身固定的加工順序，并且各道工序的加工時間是確定的。每臺機(jī)器在同一時刻最多只能加工一個工件，每道工序必須等到其所有前繼工序加工完畢后才能開始加工，每個工序的加工過程不能中斷。JSSP的目標(biāo)是在現(xiàn)有的約束條件下合理安排每臺機(jī)器上工件的加工順序，使某些調(diào)度指標(biāo)達(dá)到最優(yōu)。本文選用的調(diào)度指標(biāo)為完成所有工件所需的加工時間（makespan）最短。

用整數(shù)規(guī)劃模型表示作業(yè)車間調(diào)度問題[6]：假設(shè)J=1,2,…,n為工件集合，M=1,2,…,m為機(jī)器集合，其目標(biāo)函數(shù)和約束條件為：

其中，i,j=1,2,…,n，h,k=1,2,…,m，R為一個足夠大的正數(shù)，cik為第i個工件在第k臺機(jī)器上的完工時間，t ik為第i個工件在第k臺機(jī)器上的加工時間。

2 基本的飛蛾火焰優(yōu)化算法

MFO算法是受飛蛾在夜間使用橫向定位飛行這一生物行為的啟發(fā)提出的一種新的元啟發(fā)式算法。其中飛蛾表示在搜索空間中移動的搜索個體，而火焰是到目前為止飛蛾獲得的最佳位置。每只飛蛾以所對應(yīng)的火焰作為尋優(yōu)指導(dǎo)，不斷調(diào)整自己的飛行軌跡向全局最優(yōu)解靠攏。MFO算法具體描述如下。

（1）種群初始化

在MFO算法中，假設(shè)飛蛾是候選解，問題的變量是飛蛾在搜索空間中的位置。飛蛾種群用矩陣表示如下：

其中，n表示飛蛾的個數(shù)，d表示變量的個數(shù)。

對于所有飛蛾，用一個數(shù)組OM來存儲相應(yīng)的適應(yīng)度值，如公式（7）所示：

在MFO算法中另一個關(guān)鍵的組成部分是火焰，火焰位置是與飛蛾位置相同維度的變量矩陣：

同樣對于所有火焰，用數(shù)組OF來存儲相應(yīng)的適應(yīng)度值，如公式（9）所示：

（2）位置更新過程

MFO算法給每只飛蛾分配一個特定的火焰，使用對數(shù)螺旋來更新飛蛾的位置，公式如下：

其中，D i=|F j-Mi|是飛蛾Mi與火焰F j之間的距離，b是與螺旋形狀相關(guān)的常數(shù)，隨機(jī)數(shù)t∈[-1,1],t=-1表示離火焰最近的位置，t=1表示離火焰最遠(yuǎn)的位置。在優(yōu)化過程中，為了進(jìn)一步增強(qiáng)開發(fā)能力，假定t是[r,1]中的隨機(jī)數(shù)，r從-1線性遞減到-2。

在迭代的初始階段有n個火焰，MFO算法自適應(yīng)減少火焰數(shù)量直到保留最后一個最優(yōu)火焰，如式（11）：

其中，l是當(dāng)前迭代次數(shù)，T是最大迭代次數(shù)，n是最大火焰數(shù)，flame_no是第l次迭代的火焰數(shù)。

迭代過程中火焰數(shù)量自適應(yīng)減少是為了平衡算法的探索與開發(fā)能力。隨著迭代的進(jìn)行，火焰的數(shù)量越來越少，飛蛾的數(shù)量相對會有“多余”，這時讓多余的飛蛾圍繞第flame_no個火焰更新位置。

3 融合學(xué)習(xí)策略和鄰域搜索的飛蛾火焰算法

MFO算法采用了一種基于火焰矩陣的位置更新機(jī)制，具有較好的搜索能力。然而，基于精英保留的貪婪策略可能會使得火焰喪失種群多樣性、過早陷入局部最優(yōu)而使得飛蛾無法跳出。此外，火焰數(shù)量自適應(yīng)減少使得迭代后期圍繞第flame_no個火焰的飛蛾數(shù)增加，就導(dǎo)致種群多樣性喪失[14]?；诖耍疚膶M反向?qū)W習(xí)策略、排序配對學(xué)習(xí)策略、鄰域搜索策略與基本的MFO算法結(jié)合以進(jìn)一步提高算法的搜索能力。

3.1 擬反向?qū)W習(xí)策略

2005年，Tizhoosh提出了反向?qū)W習(xí)的概念，主要思想是同時評估當(dāng)前解和其反向解，擇優(yōu)保留，以此來增強(qiáng)群智能算法的優(yōu)化性能。反向點的定義如下：

定義1[15]（反向點）若X=(x1,x2,…,x d)是d維空間的點，其中x i∈(a i,b i)，則反向點的定義如式（12）：

反向點采用固定最大最小邊界來計算給定點的中心對稱點，擬反向點是在反向點和搜索空間的中心點之間產(chǎn)生的隨機(jī)數(shù)，一維空間點x的反向點xo與擬反向點x qo的分布如圖1所示。

圖1 一維空間的點x、反向點xo與擬反向點x qo

與反向?qū)W習(xí)策略不同的是，擬反向?qū)W習(xí)策略同時評估當(dāng)前解和其擬反向解，擇優(yōu)保留，在處理黑箱優(yōu)化問題時有更高的機(jī)會接近問題的未知最優(yōu)解。擬反向點的定義如下：

定義2[16]（擬反向點）若X=(x1,x2,…,x d)是d維空間的點，其中x i∈(ai,b i)，則擬反向點的定義如式（13）：

將擬反向?qū)W習(xí)融入到基本的MFO算法中，計算每個火焰F j的擬反向點，然后，比較火焰F j與的適應(yīng)度值，保留具有更小適應(yīng)度值的火焰，并記為。

Rahnamayan等人在文獻(xiàn)[17]中證明了擬反向點比反向點有更高的概率接近問題的未知最優(yōu)解。擬反向?qū)W習(xí)策略用于火焰更新過程，在搜索空間的中心位置與火焰的反向位置之間隨機(jī)生成新的火焰，增加了火焰種群的多樣性，擇優(yōu)保留。飛蛾圍繞保留的火焰尋優(yōu)，提高了算法的全局搜索能力。MFO算法中火焰隨著迭代次數(shù)的增加自適應(yīng)減少，在迭代后期擬反向?qū)W習(xí)策略有助于火焰跳出局部最優(yōu)，避免算法早熟收斂。

3.2 排序配對學(xué)習(xí)策略

在一個學(xué)習(xí)小組中，實行成對輔導(dǎo)，較差的個體向比它優(yōu)秀的個體學(xué)習(xí)來提升自己，這種配對學(xué)習(xí)行為能夠提高整個團(tuán)體的質(zhì)量[18]。受這種配對學(xué)習(xí)行為的啟發(fā)，本文提出排序配對學(xué)習(xí)策略（RPL）來實現(xiàn)飛蛾個體間的信息交流，豐富種群多樣性，提升整個飛蛾種群的質(zhì)量。RPL學(xué)習(xí)框架如圖2所示。在標(biāo)準(zhǔn)MFO位置更新之后，對當(dāng)前飛蛾種群基于適應(yīng)度值排序，然后所有的飛蛾被劃分到兩個組中，其中，樣本組（GE）包含前一半具有較好適應(yīng)度值的飛蛾，學(xué)習(xí)組（GL）包含后一半具有較差適應(yīng)度值的飛蛾。分別表示GE與GL組中第i個飛蛾的位置，GE與GL組的飛蛾滿足以下條件：

圖2 排序配對學(xué)習(xí)過程

為擴(kuò)大樣本和學(xué)習(xí)者間適應(yīng)度值的差異，GL組的飛蛾采用如下的學(xué)習(xí)規(guī)則選擇學(xué)習(xí)樣本：

并基于文獻(xiàn)[19]提出的位置更新方法，對GL組的飛蛾個體根據(jù)其與學(xué)習(xí)樣本之間的差異采用式（15）、（16）進(jìn)行位置更新，如下式：

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

使用交換、插入這兩種鄰域搜索算子，對于大多數(shù)問題足以得到更好的解。根據(jù)實驗的經(jīng)驗，對于一些高維的困難問題，需要一個跳出局部最優(yōu)的策略[1]。本文將反轉(zhuǎn)算子與交換算子、插入算子結(jié)合并融入到基本的MFO算法中。對GE組的每個飛蛾，隨機(jī)選取兩個不同的維p與q，從以下三種鄰域結(jié)構(gòu)算子中依概率選擇一種算子產(chǎn)生飛蛾個體的鄰域解。即在[0，1]區(qū)間產(chǎn)生一個隨機(jī)數(shù)r,若0＜r≤0.2,則使用交換算子；若0.2＜r≤0.6，則使用插入算子；若0.6＜r≤1，則使用反轉(zhuǎn)算子。

（1）交換算子，交換飛蛾個體第p維與第q維的值，得到新的個體。交換算子的實例如圖3所示。

圖3 交換算子，p=2且q=7

（2）插入算子，將飛蛾個體第p維的值插入到第q維的位置上，得到新的個體。插入算子的實例如圖4所示。

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

（3）反轉(zhuǎn)算子，將飛蛾個體第p維與第q維之間的值進(jìn)行反轉(zhuǎn)，得到新的個體。反轉(zhuǎn)算子的實例如圖5所示。

圖5 反轉(zhuǎn)算子，p=2且q=7

產(chǎn)生飛蛾的鄰域個體后，通過評估兩者的適應(yīng)度值，選擇適應(yīng)度值更小的個體保留至下一代。這種貪婪選擇操作既增加了種群的多樣性，又保證了解的質(zhì)量。

3.4 算法描述

LNHMFO算法的步驟描述如下：

步驟1設(shè)置算法參數(shù)，包括種群規(guī)模n，維數(shù)d，最大迭代次數(shù)T。

步驟2令迭代次數(shù)l=0，在搜索空間內(nèi)隨機(jī)產(chǎn)生初始飛蛾種群M。

步驟3計算飛蛾種群的適應(yīng)度值OM。

步驟4根據(jù)式（11）計算火焰的數(shù)量flame_no。

步驟5若當(dāng)前迭代次數(shù)l=1,則根據(jù)OF=sort(OM),F=sort(M)更新火焰種群。否則根據(jù)OF=sort(OM l-1,OM l),F=sort(Ml-1,Ml)更新火焰種群，記錄第一個火焰為最好個體。

步驟6計算每個火焰的擬反向點。

步驟7根據(jù)式（14）更新飛蛾的位置。

步驟8基于適應(yīng)度值對當(dāng)前飛蛾種群按升序方式排序。前一半的飛蛾使用鄰域搜索策略更新位置，而后一半的飛蛾則使用式（15）～（16）更新位置。通過評估適應(yīng)度值，選擇最優(yōu)個體保留至下一代。

步驟9判斷算法是否達(dá)到最大迭代次數(shù)，若是，則算法結(jié)束，輸出最優(yōu)值。否則令l=l+1，返回步驟3。

以下綜合分析了本文算法全局尋優(yōu)與局部尋優(yōu)的平衡性。

本文在MFO算法中將擬反向?qū)W習(xí)策略引入到火焰更新過程，增加火焰種群的多樣性，提高了算法的全局探索能力。在迭代后期，有助于火焰從局部最優(yōu)中跳出。對飛蛾種群基于適應(yīng)度值排序并分為兩組，其中一組使用排序配對學(xué)習(xí)策略增加飛蛾個體間的信息交流，產(chǎn)生新的飛蛾個體解。另一組使用交換、插入、反轉(zhuǎn)三種鄰域算子產(chǎn)生鄰域解，以增加飛蛾種群的多樣性，提高算法的局部開發(fā)能力。三種策略的有效結(jié)合平衡了本文算法的探索與開發(fā)能力，使其具有更高的求解精度和更強(qiáng)的穩(wěn)定性。

與反向點相比，擬反向點有更高的概率接近問題的未知最優(yōu)解，Rahnamayan等人在文獻(xiàn)[17]中證明了如下定理：

定理1[17]假設(shè)x、xo和x qo分別是候選解及其反向解、擬反向解。x?是問題的未知最優(yōu)解，則

其中，d(?)是到x?的距離。

3.5 算法的復(fù)雜度分析

MFO算法的計算復(fù)雜度依賴于飛蛾的個數(shù)n、變量的個數(shù)d、最大迭代次數(shù)T和每次迭代火焰的排序機(jī)制。由于使用了快速排序，在最好和最壞情況下排序的計算復(fù)雜度分別是O(nlbn)和O(n2)。所以基本MFO算法的計算復(fù)雜度是：

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

LNHMFO在基本MFO算法中引入了擬反向?qū)W習(xí)策略、排序配對學(xué)習(xí)策略和鄰域搜索策略。其中，擬反向?qū)W習(xí)策略的計算復(fù)雜度為O(nd)，排序配對學(xué)習(xí)策略的計算復(fù)雜度為O((n/2)d)，鄰域搜索策略的計算復(fù)雜度為O((n/2)d)。因此，LNHMFO算法的計算復(fù)雜度是：

綜上，LNHMFO和基本MFO算法相比，運算量稍微增加了一點，計算復(fù)雜度是一樣的，但求解精度和穩(wěn)定性得到了改善。

3.6 數(shù)值實驗與結(jié)果分析

對于隨機(jī)優(yōu)化算法，選擇適當(dāng)?shù)臏y試集來測試其性能是非常有必要的。因此，本節(jié)使用具有挑戰(zhàn)性的IEEE CEC 2017測試函數(shù)來評估LNHMFO算法的尋優(yōu)性能[20]。測試函數(shù)的詳細(xì)信息見參考文獻(xiàn)。將LNHMFO與MFO、LMFO[21]、QOGWO[22]、AWOA[23]、OBSCA[24]算法的結(jié)果進(jìn)行比較。為體現(xiàn)比較公平性，將所有算法的初始化種群設(shè)定相同，實驗參數(shù)統(tǒng)一設(shè)置如下：種群規(guī)模為50，維數(shù)為50，最大迭代次數(shù)為1 000。為減少隨機(jī)性的影響，將所有算法在每個測試函數(shù)上獨立運行30次。

使用Wilcoxon秩和檢驗來檢驗對比算法與LNHMFO之間是否存在顯著性差異，取顯著性水平α=0.05。表1給出了六種算法在30個測試函數(shù)上獨立運行30次的實驗結(jié)果，其中包含平均誤差、標(biāo)準(zhǔn)差以及Wilcoxon檢驗的p-value，加粗?jǐn)?shù)據(jù)表示每個測試函數(shù)對應(yīng)的最佳結(jié)果，最后一行的“+/=/?”分別表示用Wilcoxon秩和檢驗時對比算法“優(yōu)于/無差異/劣于”LNHMFO算法函數(shù)的個數(shù)。

由表1可知，與MFO、AWOA和OBSCA算法的比較，在幾乎所有的函數(shù)上，LNHMFO算法明顯優(yōu)于這三種比較算法。LNHMFO優(yōu)于、劣于和等于LMFO算法的函數(shù)個數(shù)分別是29、0和1，說明LNHMFO在29個函數(shù)上的結(jié)果顯著優(yōu)于LMFO算法，在函數(shù)F3上的結(jié)果與LMFO算法無差異。LNHMFO優(yōu)于、劣于和等于QOGWO算法的函數(shù)個數(shù)分別是18、3和9，說明LNHMFO在18個函數(shù)上的結(jié)果顯著優(yōu)于QOGWO算法，在函數(shù)F3、F16、F21上的結(jié)果沒有QOGWO算法的結(jié)果好，在函數(shù)F5、F6、F7、F10、F17、F18、F20、F22、F26上的結(jié)果與QOGWO算法無差異。在多數(shù)情況下LNHMFO是六個算法中標(biāo)準(zhǔn)差最小的，說明其具有較好的穩(wěn)定性。

圖6給出六種算法在部分測試函數(shù)上的收斂曲線圖。由圖可以看出，LNHMFO算法隨著迭代次數(shù)的增加持續(xù)尋優(yōu)，未出現(xiàn)停止?fàn)顩r，且尋優(yōu)精度較高。而其他比較算法的曲線下降平緩，在迭代后期出現(xiàn)不同程度的停滯，且尋優(yōu)精度較低。綜上可知，LNHMFO算法具有較快的收斂速度和較高的尋優(yōu)精度。

表1 6種算法在CEC 2017測試函數(shù)上的實驗結(jié)果

圖6 LNHMFO與對比算法的收斂曲線圖

在元啟發(fā)式算法中，多樣性可以反映出種群的分布情況，即分散和收斂情況。增加或保持算法的種群多樣性，可以相應(yīng)地提高算法的性能。為比較MFO與LNHMFO算法的種群多樣性，本文采用種群中所有個體的距離之和來度量種群的多樣性，第l次迭代種群多樣性的計算公式如下：其中，n表示種群規(guī)模，d表示維數(shù)，Mij(l)表示第i個飛蛾在第j維的位置，如果D(l)越大，表明種群多樣性越好。圖7給出MFO與LNHMFO算法在部分測試函數(shù)（F2、F3、F8、F10、F22、F28）上的多樣性變化曲線圖。由圖7可以看出，MFO算法在迭代初期種群多樣性快速下降，之后多樣性曲線保持平緩下降。相比于MFO算法，LNHMFO在整個迭代過程中保持了較高的多樣性，由此說明排序配對學(xué)習(xí)和鄰域搜索策略有利于維持種群多樣性。

圖7 LNHMFO與MFO算法的多樣性變化圖

為驗證“擬反向?qū)W習(xí)策略、排序配對學(xué)習(xí)策略、鄰域搜索策略”的有效性，本文選用單峰函數(shù)F1、F2，多峰函數(shù)F4、F9，混合函數(shù)F12、F13，組合函數(shù)F28、F30進(jìn)行測試實驗。將LNHMFO算法與僅使用擬反向?qū)W習(xí)的飛蛾火焰優(yōu)化算法（記為QMFO）、僅使用排序配對學(xué)習(xí)策略的飛蛾火焰優(yōu)化算法（記為RMFO）、僅使用鄰域搜索策略的飛蛾火焰優(yōu)化算法（記為NMFO）、基本的MFO算法的實驗結(jié)果進(jìn)行比較。為體現(xiàn)比較公平性，所有算法采用相同的初始種群，設(shè)置統(tǒng)一的參數(shù)值，即種群規(guī)模為50，維數(shù)為50，最大迭代次數(shù)為1 000，并將五種算法在每個測試函數(shù)上獨立運行30次。表2給出了MFO、QMFO、RMFO、NMFO與LNHMFO這五種算法在8個測試函數(shù)上的平均誤差值和標(biāo)準(zhǔn)差，并將最好的結(jié)果標(biāo)記為黑體。

從表2的比較結(jié)果可知，采用單一改進(jìn)策略的QMFO、RMFO和NMFO算法在8個測試函數(shù)上的求解精度和穩(wěn)定性都優(yōu)于基本的MFO算法，且三種策略的有效結(jié)合使得基本算法的求解精度和穩(wěn)定性得到更進(jìn)一步的提高。由此可知，本文提出的改進(jìn)策略是有效的。

4 LNHMFO算法優(yōu)化調(diào)度方案

4.1 編碼方式

編碼方式即為調(diào)度方案解的構(gòu)造，在飛蛾火焰算法中，每一個飛蛾對應(yīng)于該問題的一個解。飛蛾位置的每一維對應(yīng)于一個工件的一個操作。對于n個工件m個機(jī)器的作業(yè)車間調(diào)度問題，每個飛蛾的位置表示為由實數(shù)組成的大小為m×n的行向量。針對要解決的JSSP離散調(diào)度優(yōu)化問題，采用基于工序的編碼方式對問題進(jìn)行編碼?？蛇M(jìn)行舉例說明：對于3個工件在3個機(jī)器上加工的JSSP問題，搜索空間的維數(shù)是3×3維，構(gòu)造一個調(diào)度解（1，2，2，3，1，3，1，2，3），其中，1，2，3為工件編號，第一次出現(xiàn)的“1”表示工件1的第1個工序，第二次出現(xiàn)“1”表示工件1的第2個工序，以此類推，這樣編碼可使調(diào)度解自動滿足鏈?zhǔn)郊s束。

基本的MFO算法用于求解連續(xù)變量的優(yōu)化問題，而JSSP是一個典型的組合優(yōu)化問題，其解空間是離散的。因此，設(shè)計合適的表示方式實現(xiàn)連續(xù)值到離散值的轉(zhuǎn)換，對于解決JSSP是至關(guān)重要的。本文通過使用Random-key（RK）編碼方法[1]將連續(xù)型飛蛾位置向量轉(zhuǎn)換為離散型工件加工序列，這樣飛蛾的性能能夠被評估。以3×3的JSSP為例解釋RK，假設(shè)搜索空間中某個飛蛾的位置是[0.3，0.8，1.9，1.3，2.6，1.5，3.2，2.7，0.7]，通過升序的方式對這9個數(shù)排序，得到整數(shù)序列[1，3，6，4，7，5，9，8，2]，（例如，0.3是最小的數(shù)，它排名為1）。在這個整數(shù)序列中，整數(shù)3、6、9表示操作屬于工件1。因為（3 mod 3）+1=1，（6 mod 3）+1=1，（9 mod 3）+1=1。整數(shù)1、4、7表示操作屬于工件2。因為（1 mod 3）+1=2，（4 mod 3）+1=2，（7 mod 3）+1=2。整數(shù)2、5、8表示操作屬于工件3。因為（2 mod 3）+1=3，（5 mod 3）+1=3，（8 mod 3）+1=3。這樣就得到一個對應(yīng)于工件的操作排列（2，1，1，2，2，3，1，3，3）。

4.2 解碼方式

對調(diào)度解的解碼過程如下[8]：

步驟1首先將編碼的序列轉(zhuǎn)化為工序表。

步驟2基于工序表和工件加工的約束條件對各操作以最早允許加工時間逐一進(jìn)行加工。

步驟3產(chǎn)生調(diào)度方案。

對于一個3×3的JSSP問題，其加工時間和加工的機(jī)器如表3所示，假設(shè)有一個編碼序列為（1，2，3，2，2，3，1，3，1），對應(yīng)的工序加工序列為（J1，1，J2，1，J3，1，J2，2，J2，3，J3，2，J1，2，J3，3，J1，3），它表示先加工第1工件的第1道工序，再加工第2工件的第1道工序，依次類推，最后加工第1工件的第3道工序，對照機(jī)器和工件的工藝約束條件，產(chǎn)生相應(yīng)的調(diào)度方案如下：

（1）在機(jī)器2上加工第1個工件的第1道工序，用時10 s。

（2）在機(jī)器2上加工第2個工件的第1道工序，用時5 s。

（3）在機(jī)器3上加工第3個工件的第1道工序，用時9 s。

表2 五種算法在部分測試函數(shù)上的結(jié)果比較

（4）在機(jī)器3上加工第2個工件的第2道工序，用時7 s。

（5）在機(jī)器1上加工第2個工件的第3道工序，用時4 s。

（6）在機(jī)器2上加工第3個工件的第2道工序，用時13 s。

（7）在機(jī)器1上加工第1個工件的第2道工序，用時6 s。

（8）在機(jī)器1上加工第3個工件的第3道工序，用時8 s。

（9）在機(jī)器3上加工第1個工件的第3道工序，用時3 s。

表3 3×3 JSSP的機(jī)器序列與工件加工時間

4.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是對調(diào)度解進(jìn)行衡量的重要指標(biāo)。在利用LNHMFO算法尋找最佳調(diào)度方案時，采用所有工件加工的完成時間最短為衡量指標(biāo)。因此定義的適應(yīng)度函數(shù)為：

其中，cik為第i個工件在第k臺機(jī)器上的完工時間。

4.4 數(shù)值實驗與分析

為驗證LNHMFO算法求解作業(yè)車間調(diào)度問題的可行性與有效性，選取OR-Library中具有代表性的15個標(biāo)準(zhǔn)問題進(jìn)行測試（http：//people.brunel.ac.uk/mastjjb/jeb/orlib/），其大小規(guī)模包括6×6、10×5、15×5、10×10、20×5。將LNHMFO算法與MFO算法的數(shù)據(jù)進(jìn)行比較以驗證LNHMFO算法的改進(jìn)效果。將LNHMFO算法與PaGA算法[25]、GWO算法[26]、aLSGA算法[27]的結(jié)果進(jìn)行比較以進(jìn)一步表明NLSMFO算法的尋優(yōu)精度。比較算法的結(jié)果直接取自文獻(xiàn)[28]。為體現(xiàn)比較公平性，LNHMFO與MFO算法的參數(shù)統(tǒng)一設(shè)置如下：種群規(guī)模為40，最大迭代次數(shù)為500，將兩種算法在每個標(biāo)準(zhǔn)問題上分別獨立運行20次，運行結(jié)果如表4所示。在實驗結(jié)果中，instance是測試問題的名稱，size表示測試問題的規(guī)模n×m（n表示工件的個數(shù)，m表示機(jī)器的個數(shù)），BKS表示已知的最優(yōu)解，EBS表示算法重復(fù)運行所求得最優(yōu)解的平均值，R PD表示相對百分比誤差，計算公式如下：

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

由表4可知，對于15個不同規(guī)模的JSSP問題，基本的MFO算法僅找到6個最優(yōu)解，而LNHMFO算法找到了13個最優(yōu)解。說明改進(jìn)算法具有更強(qiáng)的搜索能力，在有限的時間內(nèi)能找到更多調(diào)度問題的最優(yōu)解。與PaGA、GWO和aLSGA算法的比較進(jìn)一步說明本文提出的LNHMFO算法在作業(yè)車間調(diào)度問題的求解上具有一定的有效性。

5 結(jié)束語

作業(yè)車間調(diào)度作為經(jīng)典的組合優(yōu)化難題，一直受到學(xué)術(shù)界的廣泛關(guān)注。本文針對以最小化最大完工時間為目標(biāo)的作業(yè)車間調(diào)度問題，提出一種融合學(xué)習(xí)策略和鄰域搜索的飛蛾火焰算法以降低局部最優(yōu)停滯的可能性并提高種群的多樣性。對基本的飛蛾火焰算法做了以下改進(jìn)：（1）將擬反向?qū)W習(xí)策略嵌入到火焰更新過程，有助于火焰從局部最優(yōu)中跳出，并且提供了更高的機(jī)會接近問題的未知最優(yōu)解。（2）對飛蛾種群基于適應(yīng)度值分群，其中一個群采用排序配對學(xué)習(xí)策略以實現(xiàn)個體間的信息交流，另一個群采用鄰域搜索策略以增加種群多樣性，這種并行計算能更快地提升整個種群的質(zhì)量。選取最新的IEEE CEC 2017測試函數(shù)進(jìn)行數(shù)值實驗，并與元啟發(fā)式算法的改進(jìn)版本進(jìn)行比較，測試結(jié)果和統(tǒng)計分析驗證了所提算法具有更高的求解精度和穩(wěn)定性。將所提出的算法用于OR-Library中標(biāo)準(zhǔn)實例的求解，測試結(jié)果表明新提出的算法對作業(yè)車間調(diào)度問題是有效的。

表4 五種算法在標(biāo)準(zhǔn)測試案例上的結(jié)果比較