姜強(qiáng)強(qiáng)，張其亮

(1.浙江大學(xué) 軟件學(xué)院，浙江 寧波 315048；2.江蘇科技大學(xué) 電氣與信息工程學(xué)院，江蘇 張家港 215600)

0 引 言

置換流水車間調(diào)度問題(permutation flow-shop scheduling problem，PFSP)是一類典型的組合優(yōu)化問題，并已證明是NP難題[1]。PFSP有大批量生產(chǎn)加工的應(yīng)用背景，對PFSP的優(yōu)化調(diào)度不僅可以提高生產(chǎn)效率，還可以提高資源的利用率，多年來已經(jīng)得到廣泛而深入的研究并取得了較好的成果。

如今，混合群體優(yōu)化算法成為一個(gè)關(guān)注較高的研究方向，這些研究促使求解PFSP問題進(jìn)入新的階段。文獻(xiàn)[2]針對粒子群早熟的缺點(diǎn)，提出了一種結(jié)合迭代貪婪算法的混合粒子群算法，使用迭代貪婪算法對停滯的粒子和全局最優(yōu)粒子進(jìn)行變異，然后利用模擬退火思想概率接受新值，跳出局部極值。文獻(xiàn)[3]基于模糊化處理和蜂群尋優(yōu)的特點(diǎn)，提出模糊人工蜂群算法，將模糊輸入輸出機(jī)制引入算法保持蜜源訪問概率的動(dòng)態(tài)更新，避免陷入局部極值。文獻(xiàn)[4]提出混合離散人工蜂群算法，加入離散差分進(jìn)化與變鄰域搜索策略，雇傭蜂階段接受新個(gè)體采用模擬退火的概率突跳機(jī)制，使用錦標(biāo)賽方法進(jìn)行選擇，在偵察蜂階段對錦標(biāo)賽選擇的個(gè)體執(zhí)行破壞重建操作。文獻(xiàn)[5]提出一種混合的迭代局部搜索算法，將基于超啟發(fā)式的變鄰域下降算法嵌入迭代局部搜索算法中。文獻(xiàn)[6]提出一種結(jié)合集束搜索的迭代貪婪算法，首先利用基于構(gòu)建啟發(fā)式的快速集束搜索來評估部分工件序列，然后將構(gòu)建啟發(fā)式算法用于產(chǎn)生初始解。文獻(xiàn)[7]結(jié)合NEH啟發(fā)式構(gòu)造初始解的策略提出一種混合的猴群算法，初始種群的生成采用隨機(jī)方式和基于NEH的方式，同時(shí)利用SPV規(guī)則完成工件編碼。

上述研究通過實(shí)驗(yàn)證明了群體優(yōu)化算法對于求解PFSP問題的有效性。為了進(jìn)一步提高求解質(zhì)量，文中研究了新興的化學(xué)反應(yīng)優(yōu)化(chemical-reaction optimization，CRO)與水波優(yōu)化(water wave optimization，WWO)，提出一種混合的水波化學(xué)反應(yīng)優(yōu)化(wave chemical reaction optimization，WCRO)算法，同時(shí)引入迭代貪婪、路徑重連等策略，力求混合算法在局部搜索、全局搜索以及收斂速度上均具有良好的表現(xiàn)，最后通過與其他算法進(jìn)行實(shí)驗(yàn)測試對比證明該算法的可行性。

1 PFSP問題的數(shù)學(xué)描述

PFSP問題一般描述為n個(gè)工件需要在m臺機(jī)器上加工，每個(gè)工件需要經(jīng)過m道工序；每道工序要求不同的機(jī)器；n個(gè)工件在m臺機(jī)器上的加工順序相同；每個(gè)工件在每臺機(jī)器上的加工時(shí)間表示為pij(i為第i個(gè)工件，j為第j臺加工機(jī)器)。記π={π1,π2,…,πn}為所有工件的一個(gè)排列，C(πi,j)為工件πi在機(jī)器j的加工完成時(shí)間，則各工件在每臺機(jī)器上的加工完成時(shí)間的數(shù)學(xué)模型如下：

C(π1,1)=pπ1,1

(1)

C(πi,1)=C(πi-1,1)+pπi,1i=2,3,…,n

(2)

C(π1,j)=C(π1,j-1)+pπ1,jj=2,3,…,m

(3)

C(πi,j)=max{C(πi-1,j),C(πi,j-1)}+pπi,j

i=2,3,…,n；j=2,3,…,m

(4)

式1表示第1個(gè)工件在第1臺機(jī)器上的完工時(shí)間；式2表示第i個(gè)工件在第1臺機(jī)器上的完工時(shí)間；式3表示第1個(gè)工件在第j臺機(jī)器上的完工時(shí)間；式4表示第i個(gè)工件在第j臺機(jī)器上的完工時(shí)間。

加工的總完工時(shí)間Cmax(π)計(jì)算如下：

Cmax(π)=C(πn,m)

(5)

PFSP問題的目標(biāo)是尋找一個(gè)工件排列序列π*使得Cmax(π*)最小，如式6所示：

Cmax(π*)≤Cmax(πn,m)

(6)

2 求解PFSP問題的WCRO算法

2.1 PFSP問題編碼

文中PFSP問題的解采用離散編碼方式，每個(gè)工件用一個(gè)整數(shù)代表，工件從0開始標(biāo)記，{0,1,…,n-1}為n個(gè)工件標(biāo)記，如n=5的一種工件序列為{2,3,1,4,0}。

在WCRO算法中，每個(gè)工件序列對應(yīng)種群中個(gè)體的結(jié)構(gòu)，工件序列的完工時(shí)間對應(yīng)個(gè)體的適應(yīng)度值。

2.2 WCRO算法概述

文中將CRO算法與WWO算法混合，提出了一種新的混合水波化學(xué)反應(yīng)優(yōu)化算法(WCRO)，算法框架如圖1所示。

圖1 WCRO算法框架

WCRO算法首先初始化種群，然后進(jìn)入由CRO與WWO協(xié)作完成的迭代優(yōu)化階段，化學(xué)反應(yīng)優(yōu)化針對種群個(gè)體，即隨機(jī)選擇種群中的個(gè)體進(jìn)行化學(xué)反應(yīng)優(yōu)化操作，水波優(yōu)化則針對整個(gè)群體進(jìn)行優(yōu)化操作，迭代完成后輸出最優(yōu)解。

2.3 基于NEH_GRASP初始化種群

為了得到多個(gè)質(zhì)量較高且多樣性的初始解，采用文獻(xiàn)[8]提出的基于NEH的貪婪隨機(jī)自適應(yīng)搜索算法(NEH_GRASP)。NEH_GRASP算法在構(gòu)造解時(shí)，首先對每一個(gè)候選元素賦予一個(gè)貪婪函數(shù)值，將每個(gè)工件在所有機(jī)器上加工完成的時(shí)間作為貪婪函數(shù)值，并按照從大到小進(jìn)行排序；其次，將排在前面的候選元素選入到約束候選表中；然后，從約束候選表中隨機(jī)選擇一個(gè)元素構(gòu)造初始解；重復(fù)上述操作直至初始解中包含所有的工件。NEH_GRASP算法一次生成一個(gè)初始解，經(jīng)過多次執(zhí)行可獲得多個(gè)質(zhì)量較高且多樣性的初始解。

2.4 化學(xué)反應(yīng)優(yōu)化

CRO算法是一種模擬化學(xué)反應(yīng)變化的群體優(yōu)化算法[9]。反應(yīng)中的分子通過不斷進(jìn)行撞墻、分解、互撞以及合成四種反應(yīng)實(shí)現(xiàn)能量的轉(zhuǎn)化以尋求更低的勢能。CRO算法具有保持種群多樣性、全局搜索能力好的優(yōu)點(diǎn)，而分解與合成反應(yīng)在整個(gè)算法中的作用不明顯[10-11]，因此只保留撞墻和互撞反應(yīng)。分子動(dòng)能隨反應(yīng)的進(jìn)行逐漸降低，則反應(yīng)所需條件也愈加難以滿足，為了使反應(yīng)持續(xù)進(jìn)行，在反應(yīng)前加入分子動(dòng)能是否過低的判斷，當(dāng)KE

2.4.1 撞 墻

撞墻反應(yīng)指單個(gè)分子與容器壁碰撞后分子結(jié)構(gòu)發(fā)生改變的過程，使得分子對應(yīng)的解突變，防止算法陷入局部最優(yōu)，文中采用基于隨機(jī)互換方式實(shí)現(xiàn)撞墻操作。首先隨機(jī)選擇一個(gè)分子，然后針對分子的結(jié)構(gòu)即工件序列，隨機(jī)選擇兩個(gè)不同的位置工件進(jìn)行交換，如圖2所示。

圖2 撞墻反應(yīng)的分子結(jié)構(gòu)變化

2.4.2 互 撞

互撞反應(yīng)是指兩個(gè)分子間發(fā)生碰撞后分子結(jié)構(gòu)發(fā)生變化，發(fā)生碰撞的兩個(gè)分子間進(jìn)行信息交換，文中采用基于位置的交叉操作(position-based crossover，PBX)。隨機(jī)選擇兩個(gè)分子，記互撞前后分子對應(yīng)的工件序列分別為A、B和A'、B'。首先，確定保留信息的長度d且d∈[1,n]；其次，隨機(jī)選擇A中的幾個(gè)位置，將選中位置的工件直接保留到A'序列中對應(yīng)的位置；最后，先在B中找出第一步選中的工件在本序列中的位置，再將其余工件按順序放入A'中的空缺位置，如圖3所示。

圖3 分子碰撞反應(yīng)的結(jié)構(gòu)變化

B'生成的規(guī)則與A'相同，先從B中隨機(jī)選擇保留的工件，再從A中選擇剩余工件補(bǔ)充空缺位置。

2.5 水波優(yōu)化

WWO算法是一種以淺水波理論為基礎(chǔ)，通過模擬水波的傳播、碎浪、折射操作在搜索空間中進(jìn)行尋優(yōu)的新興元啟發(fā)式優(yōu)化算法[12-13]。

WWO算法用于求解連續(xù)優(yōu)化問題，而文中求解PFSP問題采用了離散的編碼方式，因此，需要設(shè)計(jì)離散的水波優(yōu)化算法的求解問題，同時(shí)引入迭代貪婪、路徑重連、淘汰機(jī)制來改善算法的局部搜索能力和收斂的速度。

離散WWO算法包括四個(gè)階段：傳播、折射、碎浪以及淘汰劣解。算法對每個(gè)水波執(zhí)行傳播操作，傳播后的水波適應(yīng)度值、波長、波高發(fā)生改變。適應(yīng)度值的變化情況決定是否執(zhí)行碎浪操作，波高的變化情況決定是否行進(jìn)行折射或淘汰劣解操作。記工件序列πi為第i個(gè)水波，λi為波長，hi為波高。

2.5.1 傳 播

水波的波長決定傳播范圍，適應(yīng)度越好其波長越小，傳播操作的搜索空間也越小。迭代貪婪(iterated greedy，IG)算法[14]通過在原始解上進(jìn)行破環(huán)、構(gòu)造操作來獲得一個(gè)更優(yōu)質(zhì)的解，以該算法作為傳播操作算子。

破壞操作選擇d個(gè)工件并從原始序列π中移除，π被分成兩部分：πd包含d個(gè)工件，πr包含n-d個(gè)工件。構(gòu)造操作從πd中依次選擇工件嘗試插入πr中所有可能位置，選擇一個(gè)使πr適應(yīng)度最好的位置。

記操作完成后的水波為π'，如果π'適應(yīng)度更好，替換原來的π，否則原水波波高減1。DWWO算法中波長決定IG算法中破壞長度d，即d=λi，每次迭代波長發(fā)生如下改變：

(7)

c2=Cworst-Cbest

(8)

λi=λmax-λmin·e-c1/(c2+ε)

(9)

其中，λmax、λmin分別為最長波長與最短波長；Cmax(πi)為當(dāng)前水波的適應(yīng)度；Cworst、Cbest分別為當(dāng)前最優(yōu)解與最差解的適應(yīng)度；ε=0.001避免出現(xiàn)除數(shù)為0的情況。

2.5.2 折 射

當(dāng)水波經(jīng)過傳播后波高減小為0時(shí)，進(jìn)行折射。利用路徑重連(path relinking，PR)完成折射使當(dāng)前水波πi保持向最優(yōu)水波π*的學(xué)習(xí)性。文中采用基于交換的PR算法，通過交換工件位使起始解向目標(biāo)解靠攏，此過程會(huì)產(chǎn)生部分中間解，選擇適應(yīng)度最好的中間解作為PR算法的結(jié)果。

2.5.3 碎 浪

如果傳播后的水波的適應(yīng)度比當(dāng)前最優(yōu)解更好，對水波πi執(zhí)行碎浪操作，此操作能進(jìn)一步對最優(yōu)解的附近范圍搜索。以基于插入的局部搜索算法完成碎浪操作，首先，隨機(jī)生成一個(gè)具有n個(gè)工件的序列π'，令π作為每次操作的結(jié)果；其次，依次遍歷π'中的工件，并在當(dāng)前水波πi中找到對應(yīng)的工件并插入所有可能插入的位置，找到一個(gè)適應(yīng)度最好的工件序π''；然后將π''與當(dāng)前解π進(jìn)行比較，如果更優(yōu)則用π''替換π。

2.5.4 淘汰劣解

淘汰劣解是一種概率性的接受較差解的操作，引入此操作有助于加快收斂速度。如果當(dāng)前水波πi傳播后得到的工件序列π'比原來更差，水波高度減1后高度變?yōu)?時(shí)，根據(jù)rand<α(α為算法參數(shù)，rand是0到1之間的隨機(jī)數(shù))條件決定是否淘汰群體中適應(yīng)度最差的水波，如果滿足淘汰條件，將π'替換群體中最差水波，否則舍棄π'。

2.6 WCRO算法設(shè)計(jì)

基于上述WCRO算法的框架設(shè)計(jì)，并且針對化學(xué)反應(yīng)算法和離散水波優(yōu)化算法給出的具體實(shí)現(xiàn)，WCRO具體程序流程設(shè)計(jì)如下：初始階段以NEH_GRASP算法生成高質(zhì)量、多樣性的種群，然后進(jìn)入迭代優(yōu)化階段，包括執(zhí)行兩種分子碰撞的化學(xué)反應(yīng)優(yōu)化和混合搜索策略的離散水波優(yōu)化，在水波優(yōu)化進(jìn)行深度局部尋優(yōu)前先以化學(xué)反應(yīng)優(yōu)化執(zhí)行全局搜索，防止陷入局部最優(yōu)。

偽代碼如下：

1：基于NEH_GRASP算法初始化種群

2：While (迭代停止條件未滿足)

3：If(rand(0,1)≥MoleColl)

4：隨機(jī)選擇一個(gè)分子m執(zhí)行撞墻反應(yīng)

5：Else

6：隨機(jī)選擇兩個(gè)分子m1、m2執(zhí)行互撞反應(yīng)

7：End if

8：Fori=1:PopSize

12：End if

14：Else

15：hi=hi-1

16：If(hi==0)

17：對πi執(zhí)行折射操作

18：hi=hmax

19：Else

20：If(rand(0,1)<α)淘汰劣解

21：End if

22：End if

23：End if

24：根據(jù)式7～9更新波長λi

25：End for

26：End while

3 實(shí)驗(yàn)結(jié)果與分析

借助Eclipse開發(fā)平臺，使用Java語言實(shí)現(xiàn)求解PFSP問題的WCRO算法，程序運(yùn)行環(huán)境為Windows 10 64位操作系統(tǒng)、主頻3.4 G的Intel Core i3系列CPU、4G DDR3內(nèi)存。實(shí)驗(yàn)測試采用Taillard[15]提出的120組基準(zhǔn)測試案列。

3.1 參數(shù)設(shè)置

WCRO算法涉及如下幾個(gè)重要參數(shù)：最大迭代次數(shù)MaxIteration、群體規(guī)模PopSize、初始動(dòng)能InitialKE、動(dòng)能損失率KELossRate、單雙分子反應(yīng)決定因子MoleColl、低動(dòng)能閾值LowKE、初始波高h(yuǎn)max、最大波長λmax、最小波長λmin、淘汰劣解決定因子α。參考肖華軍等[16]有關(guān)CRO算法的研究以及Zhao[17]等有關(guān)DWWO算法的研究，對WCRO算法的參數(shù)設(shè)置如表1所示。

表1 WCRO算法參數(shù)取值

需要注意的是，在500×20的數(shù)據(jù)規(guī)模中，存在不同的解的完工時(shí)間差距較大的情況，太小的分子動(dòng)能大規(guī)模問題中難以保證化學(xué)反應(yīng)成功進(jìn)行，因此在500×20規(guī)模的案例中，將參數(shù)InitialKE和LowKE分別設(shè)置為2 000和200，以此保證算法能夠在所有測試案例中發(fā)揮作用。

3.2 基準(zhǔn)實(shí)例測試

實(shí)驗(yàn)結(jié)果的對比以兩種比較標(biāo)準(zhǔn)為例：平均誤差率(average error rate，ARE)和平均相對百分偏差(average relative percentage deviation，ARPD)，算法針對每個(gè)案例獨(dú)立運(yùn)行10次。

公式如下：

(10)

(11)

其中，mean、best分別表示算法所求得的平均值和最優(yōu)值；opt為目前已知該案例的最優(yōu)值。

為了完成性能測試，選取近些年較新的算法：新布谷鳥算法(NCS)[18]、免疫遺傳算法(VacGA)[19]、改進(jìn)NEH算法(NEHLJP1)[20]與文中算法進(jìn)行對比。對比結(jié)果如表2和表3所示。

表2 WCRO、NCS算法的ARE結(jié)果對比

表3 WCRO、VacGA、NEHLJP1算法的ARPD結(jié)果對比

由表2可知，文中算法除了問題Ta100的求解結(jié)果比NCS算法稍有不足外，對其余問題的求解結(jié)果均優(yōu)于NCS算法。從表3中數(shù)據(jù)可以看出，文中算法對于求解Taillard所有問題得到的結(jié)果與最優(yōu)解的誤差最小，與VacGA算法和NEHLJP1算法相比尋優(yōu)性能更好。

4 結(jié)束語

基于CRO與WWO算法提出一種新的WCRO算法。使用NEH_GRASP算法生成高質(zhì)量、多樣性的種群，保留CRO中兩種分子碰撞完成化學(xué)反應(yīng)優(yōu)化，設(shè)計(jì)離散型WWO算法并引入迭代貪婪、路徑重連、淘汰機(jī)制，以CRO與DWWO協(xié)作完成算法的主要優(yōu)化過程。

通過實(shí)驗(yàn)對比證明WCRO算法求解PFSP問題的可行性。未來可以將WCRO算法應(yīng)用于TSP、作業(yè)車間調(diào)度、混合流水車間調(diào)度等其他組合優(yōu)化問題中，以進(jìn)一步證明該算法的有效性。