基于改進灰狼算法求解柔性車間調(diào)度問題

吳繼浩，楊 濤

（西南科技大學(xué) 信息工程學(xué)院，綿陽 621010）

0 引言

柔性車間作業(yè)調(diào)度（Flexible Jobshop Scheduling Problem，簡稱FJSP），屬于一個典型的NP難問題。解決作業(yè)車間調(diào)度問題的方法主要有以下四類：1）運籌學(xué)方法，包括整數(shù)規(guī)劃，分支定界方法等；2）啟發(fā)式規(guī)則；3）神經(jīng)網(wǎng)絡(luò)方法；4）元啟發(fā)式算法。有很多知名的智能優(yōu)化算法都已經(jīng)成功應(yīng)用FJSP領(lǐng)域，如蟻群算法、遺傳算法、模擬退火算法和粒子群算法等。由NFL[1]定理可知，這個定理在邏輯上證明了沒有哪種元啟發(fā)式最適合解決所有的優(yōu)化問題。這個領(lǐng)域每年都會提出新的元啟發(fā)式算法。針對連續(xù)函數(shù)優(yōu)化問題，Mirjalili等[2]在2014年模仿了一群狼的生活和捕食方式的行為提出了一種新的啟發(fā)式算法，即灰狼算法（GWO）。

GWO是一種基于群體的元啟發(fā)式算法，它設(shè)定每個狼群都有層次結(jié)構(gòu)，狼群中的每只狼都有特定的角色。Mirjalili在文獻[2]中，通過對29個連續(xù)函數(shù)優(yōu)化問題的測試，結(jié)果表明GWO在求解精度和穩(wěn)定性上要明顯優(yōu)于PSO、DE和GSA等算法。GWO中所有候選狼（解決方案）都被最好的三只狼所吸引，從而更快地聚集到這些好狼位置周圍。但是這樣也很容易造成GWO算法容易陷入局部收斂。由于上述原因，GWO的收斂性能有待提高。Zhang等[3]提出了基于Powell局部優(yōu)化方法的PGWO算法，用于解決集群問題。龍文等[4]提出一種改進灰狼優(yōu)化（IGWO）算法用于求解約束優(yōu)化問題。

灰狼算法多用于解決連續(xù)函數(shù)問題的研究，在FJSP這類非常復(fù)雜的離散組合優(yōu)化問題應(yīng)用還比較少，本文針對經(jīng)典的FJSP的特點，通過優(yōu)化初始種群，采用新的解碼機制，在迭代后期結(jié)合遺傳算法的交叉變異和模擬退火的Metropolis準則提出一種新的“哨兵”機制，隨機的向各個新的位置隨機探索，有效的防止了GWO的局部收斂。經(jīng)過實驗對比，證實所提出的算法有效提高了GWO求解FJSP問題的能力。

1 問題建模及約束

對柔性車間（FJSP）問題[5]描述如下：車間中有M類設(shè)備，將一批訂單分解為在一段時間內(nèi)要求加工N個工件。每個工件由一系列工序組成，允許在一組可用的機器中加工它們。所有的作業(yè)和機器都在0時刻可用，而機器只能在給定的時間執(zhí)行一個工序。不允許機器搶占加工。在本文中的FJSP問題設(shè)置機器的運行時間和運行時間之間的運輸時間忽略不計。以最大完工時間最小為目標函數(shù)。

具體的建模和約束如文獻[5]中Model M2，文獻[5]中約束(2.1)定義了最大完工時間，約束(2.2)定義了工件的完工時間。如果沒有Oij分配到機器M，約束(2.3)將M的起始和完成時間設(shè)置為零。約束(2.4)保證機器加工過程不能被打斷且加工同一個操作時間相等。約束(2.7)保證了每道工序必須按照工藝順序依次在指定的設(shè)備上加工，且必須在前一道工序i（如果存在）加工完成后才開始后工序j加工。約束(2.8)保證機器只能加工一個工件。

2 基本灰狼優(yōu)化算法

Mirjalili在文獻[2]中指出，GWO算法模擬了灰狼在自然界中的領(lǐng)導(dǎo)層次和狩獵機制。四種類型的灰狼，如alpha，beta，delta和omega，用于模擬領(lǐng)導(dǎo)層次結(jié)構(gòu)。此外，還實施了狩獵、尋找獵物、環(huán)繞獵物和攻擊獵物這三個主要步驟。算法進化過程中，alpha、beta和delta負責(zé)定位獵物的位置，并引導(dǎo)omega個體完成靠近、包圍和攻擊等行為，最終達到捕食獵物的目的。具體的過程及建?？梢詤㈤單墨I[2]。

3 改進灰狼優(yōu)化算法

3.1 編碼及解碼

對于GWO算法而言，如何將一個可行的工件加工序列轉(zhuǎn)換為一個灰狼個體的位置向量是一個最為關(guān)鍵的問題。標準的GWO算法是主要是用于求解連續(xù)變量優(yōu)化問題而提出的，F(xiàn)JSP是一個離散優(yōu)化問題，如何設(shè)計有效的編碼規(guī)則是問題解決的關(guān)鍵。文獻[6]利用基于隨機鍵編碼的LOV規(guī)則，文獻[7]采用了ROV規(guī)則。經(jīng)筆者實際的多次實驗仿真，得知LOV規(guī)則的編碼更適用于灰狼算法解決FJSP問題。根據(jù)LOV規(guī)則設(shè)計如圖1基于結(jié)構(gòu)體的數(shù)據(jù)結(jié)構(gòu)：

圖1 灰狼個體數(shù)據(jù)結(jié)構(gòu)

假設(shè)有兩個工件，每個工件的工序數(shù)和可使用的機器如圖2所示。

圖2 工序圖

編碼時，首先隨機生成WolStruct.poisition=[0.6，0.5，0.9，0.2]，根據(jù)LOV規(guī)則，對WolStruct.poisition變量做降序排列得到中間序列WolStruct.alp=[2，3，1，4]，然后按照公式獲得加工順序序列WolStruct.bta=[3，1，2，4]，其中φi為上述中間序列WolStruct.alp。最終得到加工序列WolStruct.seq=[1，2，1，2]。

經(jīng)上述編碼算法生成工序序列：C=[1，2，1，2]表示工件加工的順序，第一個1表示工件1的第一道工序，第二個2表示工件1的第二道工序，轉(zhuǎn)換成如T=[101，201，102，202]中間序列，解碼安排機器，按照如下所示的步驟安排：

Step1：讀入WolStruct.alp序列，解碼得到T中間序列。

Step2：識別機器最早的停止時間Te及最后加工的工序Oi,j。

Step3：識別能夠加工工序Oi,j+1:P(Oi,j+1)的所有可用機器。

Step4：計算每臺機器的等待時間Mk∈P(Oi,j+1)：如果Mk在時間t沒有加工任何工序，則等于Oi,j+1在機器Mk上的加工時間。如果Mk在t時刻正在處理工序Oz,y，則等待時間等于機器Mk等待操作的總處理時間+（Oz,y在Mk上剩余的加工時間）+Oi,j+1在Mk上加工時間。

Step5：選擇等待時間最短的機器來處理Oi,j+1。如果Mk在時間t沒有加工任何工序，則直接處理Oi,j+1，否則將Oi,j+1加入Mk的等待加工工序名單。

Step6：從Step2中得到Te及Oi,j，接著安排Oi,j+1到一個合適的機器。如果有很多等待名單，按照Cmax最小為規(guī)則選擇一個加工序列。

3.2 種群初始化

初始狼群的好壞直接將決定后期狩獵過程的優(yōu)劣，好的狼群將提高算法的運行效率。狼群G，個體S的位置可以表示如下：

其中ub=100，lb=-100，W為群體G的灰狼總個數(shù)，n為工件工序的總個數(shù)，即灰狼的位置維度，這樣每個位置分量取值范圍在[-100,100]。

為了有效解決初始解的質(zhì)量，保證初始化種群的多樣性，提高初始解的質(zhì)量。根據(jù)它們的處理工序差異性來定義兩個位置之間的聚集性。隨機生成后，經(jīng)過LOV規(guī)則轉(zhuǎn)換成加工序列WolStruct.bta?；依莻€體位置的聚集性由如下公式計算：

Chm1,Chm2是兩個經(jīng)過LOV規(guī)則轉(zhuǎn)換后的工序加工序列WolStruct.bta。Opt1(i)，Opt2(i)和n代表WolStruct.bta的位置i上的值。當(dāng)兩個工序i位置上值相同時，操作返回0，如果不相等，則返回1。S的值被稱為漢明距離，當(dāng)S值非常小時，表示種群中兩個灰狼的位置距離很近。定義聚集率：P=S/n。生成種群個體時，保證每個灰狼的位置PS＞Pcmax=0.5，可以有效保證生成狼群個體的多樣性以提高解的質(zhì)量。

3.3 個體位置更新方法

由于灰狼算法的設(shè)計原理，在GWO算法進化后期，群體中所有灰狼個體均向最好的三個灰狼個體區(qū)域靠近，從而導(dǎo)致了種群喪失了群體多樣性，GWO容易出現(xiàn)早熟現(xiàn)象。文獻[8]針對不同的應(yīng)用領(lǐng)域都做出了一定有優(yōu)化，有效地降低了GWO出現(xiàn)早熟現(xiàn)象和陷入局部最優(yōu)的概率。本文提出“哨兵”機制。在種群中通過對最優(yōu)灰狼個體進行GA算法的遺傳變異操作，然后引入模擬退火算法Metropolis接收準則，生成種群的哨兵灰狼，在alpha，beta狼周圍，不斷的巡邏，降低狼群陷入局部最優(yōu)解的概率。

初始化種群后，通過編碼、解碼操作，根據(jù)最大化完工時間得出每個灰狼的適應(yīng)度，從小到大排序，最優(yōu)的GN個灰狼個體保存為新的種群，并且確定alpha，beta，delta的值。

根據(jù)alpha，beta，delta結(jié)構(gòu)體的seq序列，采用文獻[9,10]的交叉、變異操作，得到3個哨兵灰狼。通過哨兵和alpha狼漢明距離來賦予其狼群等級，以確保哨兵狼的權(quán)限。根據(jù)3.2節(jié)定義的聚集率P，按照如下公式確定哨兵狼的合理性。當(dāng)生成的哨兵狼聚集率PS∈{Pcmin，PC}就合格，否則一直重新交叉、變異直至合格。

式中：M為狼群最大迭代次數(shù)，m為當(dāng)前迭代次數(shù)，PC為自適應(yīng)聚集率，Pcmax為最大可接受聚集率，Pcmin為最小可接受聚集率。本文Pcmax=0.5，Pcmin=0.2。

采用Metropolis準則接收哨兵狼，在迭代后期替換種群中最差的3個灰狼個體。其中關(guān)鍵參數(shù)由如下公式確定：

初始溫度：

Metropolis準則：

退溫函數(shù)：

式中fmax和fmin分別為種群中最優(yōu)和最差個體的適應(yīng)度值。k為降溫的次數(shù)，ω是一個常數(shù)。其中df為新產(chǎn)生個體適應(yīng)度和要替換個體適應(yīng)度的差，pr取值范圍是(0,1)。

具體操作如下：

Step1：LOOPNew＞=LOOP*0.63時進入；

Step2：生成哨兵狼，計算適應(yīng)度函數(shù)，如果df＞f max或df＜fmin就替換舊個體，否則按照（rand是介于0和1之間的隨機數(shù)）概率接收新個體。

Step3：最差的第三個個體已經(jīng)替換完畢，即保存當(dāng)前種群進入下一次迭代。

本文將改進后的灰狼算法簡稱為GSGWO算法，流程圖如圖3所示。

圖3 算法流程圖

4 仿真及實驗

選擇7個比較經(jīng)典的測試集來驗證提出的GSGWO算法，包括5個小規(guī)模Kacem實例[11]和2個大型的BRdata實例[12]。實例m×n，其中m是作業(yè)數(shù)，n是機器數(shù)。實驗仿真環(huán)境為Windows10、處理器 Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz、內(nèi)存8.00G，MATLABR2016a實現(xiàn)算法編程。

為了驗證改進GSGWO算法的尋優(yōu)性能，與文獻[6]中GWO+鄰域局部搜索（HGWO），文獻[8]中改進GA算法（GA），文獻[9]中遺傳算法+模擬退火算法（GASA），文獻[2]中GWO，分別對上述7個實例進行求解，求解結(jié)果如表1，表2所示。GWO，HGWO，GA，GASA種群大小均取60，迭代次數(shù)均為5000次，其中GA，GASA交叉概率和變異概率為0.8、0.2，運行60次。

表1結(jié)果表明，在5個小規(guī)模Kacem實例問題，對于機器數(shù)較少的簡單問題如4×5，8×8，GSGWO均可以給出比較滿意的解，GWO，HGWO，GA，GASA，GSGWO均能找到最優(yōu)解，對應(yīng)8×8實例文中五種算法最優(yōu)解甘特圖如圖4所示。當(dāng)調(diào)度復(fù)雜度提高時，GWO尋找最優(yōu)解的能力明顯低于GA。表1中數(shù)據(jù)Δavg和m*的值可以看出，GWO算法雖然可以快速接最優(yōu)解的周圍，但是容易被頭狼帶到局部最優(yōu)。GSGWO雖然從Δavg這個參數(shù)來對比，沒有對GWO形成絕對優(yōu)勢，但是GSGWO由于有哨兵狼這個小分隊，在后期接近最優(yōu)解的范圍，能夠有一定的概率捕捉到最優(yōu)解的位置。

圖4 8×8實例最優(yōu)解的甘特圖

通過表2結(jié)果表明，BRdata數(shù)據(jù)集中MK09為20×10，MK10為20×15。問題規(guī)模明顯大于表1。對應(yīng)20×15實例文中五種算法最優(yōu)解甘特圖如圖5所示。GWO，HGWO算法都難以找到問題的最優(yōu)解，尋優(yōu)率都為0，但從Δavg這個參數(shù)可以得出，HGWO算法明顯要優(yōu)于GWO，更靠近最優(yōu)解，HGWO加入的鄰域搜索對算法陷入局部最優(yōu)解有一定的抑制作用。標準GA算法的對FJSP問題的求解能力要優(yōu)于標準GWO，GASA算法對FJSP問題的求解效率要高于GA算法，本文提出的GSGWO更容易找出最優(yōu)值，雖然尋優(yōu)率并不高，但是相對于標準的GWO和HGWO算法，GSGWO算法的優(yōu)化性能已經(jīng)有了很大的改善。GSGWO相對于GA，GASA表現(xiàn)出了對于解決FJSP問題的優(yōu)勢。

表1 Kacem實例的結(jié)果

表2 BRdata的結(jié)果

圖5 20×15實例最優(yōu)解的甘特圖

5 結(jié)束語

本文針對的是單目標優(yōu)化，F(xiàn)JSP問題大多都是多目標優(yōu)化，工件優(yōu)先級也未成考慮，滾動插單這些約束都未考慮，下一步研究工作方向，向著多目標，優(yōu)先級，動態(tài)插單方向研究灰狼算法的有效性。車間調(diào)度問題還有很多分支，如流水車間、作業(yè)車間和開放式車間等。這些領(lǐng)域的灰狼優(yōu)化算法的研究也是下一步的研究方向。