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

吳繼浩，楊 濤

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

0 引言

柔性車間作業(yè)調(diào)度（Flexible Jobshop Scheduling Problem，簡稱FJSP），屬于一個(gè)典型的NP難問題。解決作業(yè)車間調(diào)度問題的方法主要有以下四類：1）運(yùn)籌學(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]定理可知，這個(gè)定理在邏輯上證明了沒有哪種元啟發(fā)式最適合解決所有的優(yōu)化問題。這個(gè)領(lǐng)域每年都會提出新的元啟發(fā)式算法。針對連續(xù)函數(shù)優(yōu)化問題，Mirjalili等[2]在2014年模仿了一群狼的生活和捕食方式的行為提出了一種新的啟發(fā)式算法，即灰狼算法（GWO）。

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

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

1 問題建模及約束

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

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

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

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

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

3.1 編碼及解碼

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

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

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

圖2 工序圖

編碼時(shí)，首先隨機(jī)生成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]表示工件加工的順序，第一個(gè)1表示工件1的第一道工序，第二個(gè)2表示工件1的第二道工序，轉(zhuǎn)換成如T=[101，201，102，202]中間序列，解碼安排機(jī)器，按照如下所示的步驟安排：

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

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

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

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

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

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

3.2 種群初始化

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

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

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

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

3.3 個(gè)體位置更新方法

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

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

根據(jù)alpha，beta，delta結(jié)構(gòu)體的seq序列，采用文獻(xiàn)[9,10]的交叉、變異操作，得到3個(gè)哨兵灰狼。通過哨兵和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準(zhǔn)則接收哨兵狼，在迭代后期替換種群中最差的3個(gè)灰狼個(gè)體。其中關(guān)鍵參數(shù)由如下公式確定：

初始溫度：

Metropolis準(zhǔn)則：

退溫函數(shù)：

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

具體操作如下：

Step1：LOOPNew＞=LOOP*0.63時(shí)進(jìn)入；

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

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

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

圖3 算法流程圖

4 仿真及實(shí)驗(yàn)

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

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

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

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

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

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

表2 BRdata的結(jié)果

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

5 結(jié)束語

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