g支配策略的MOEA/D算法求解多目標(biāo)流水車間調(diào)度問題

陳世翔，朱光宇，徐文婕

(福州大學(xué)機(jī)械工程及自動化學(xué)院，福建 福州 350108)

0 引言

流水車間調(diào)度問題(flow-shop scheduling problem，F(xiàn)SP)是一類重要的生產(chǎn)調(diào)度問題，有廣泛的工程應(yīng)用背景[1].調(diào)度優(yōu)化算法可分為數(shù)學(xué)規(guī)劃方法、規(guī)則調(diào)度方法、仿真調(diào)度方法、啟發(fā)式方法和智能優(yōu)化方法等[2].智能優(yōu)化方法包含遺傳算法、禁忌搜索算法、模擬退火算法、蟻群算法和粒子群算法等.如： 文[3]提出變鄰域改進(jìn)遺傳算法求解混合流水車間調(diào)度問題.文[4]應(yīng)用并行禁忌搜索算法來解決混合流水車間調(diào)度問題.文[5]應(yīng)用改進(jìn)的免疫模擬退火算法求解混合流水車間調(diào)度問題.文[6]改進(jìn)離散粒子群算法求解柔性流水車間調(diào)度問題.該類智能優(yōu)化方法無需問題的特殊信息，可以很快收斂到局部最優(yōu)并獲得近似最優(yōu)解.

基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition，MOEA/D)是一種將傳統(tǒng)的數(shù)學(xué)規(guī)劃方法與進(jìn)化算法相結(jié)合求解多目標(biāo)優(yōu)化問題的算法[7].由于其簡單性和優(yōu)越的性能得到了學(xué)者廣泛的關(guān)注.Zhang等[8]在MOEA/D中引入DE算子，有效地解決了Pareto前沿問題.Ishibuchi等[9]針對MOEA/D中采用兩種不同聚合函數(shù)，降低了選擇聚合函數(shù)的難度.鄭金華等[10]提出了一種基于權(quán)重迭代的偏好多目標(biāo)分解算法來解決參考點(diǎn)的位置信息對算法的影響.模糊Pareto支配概念的引入提高了算法的收斂速度[11].Chang等[12]提出MOEA/D算法在流水車間調(diào)度問題中的應(yīng)用，并討論了MOEA/D算法在本問題中所采用的分解方法，通過實(shí)驗(yàn)證明，MOEA/D算法在二維或三維流水車間調(diào)度問題上比NSGA II和SPEA 2效果更優(yōu).MOEA/D將一個(gè)多目標(biāo)問題(MOP)按照一定的權(quán)重分解為若干個(gè)單目標(biāo)優(yōu)化子問題，然后優(yōu)化這些單目標(biāo)子問題，具有收斂速度快，效率高等特點(diǎn)，但是在求解流水車間調(diào)度非凸MOP時(shí)會面臨解的質(zhì)量不夠高、分布性差等問題[13].

本研究將g支配思想[14]引入MOEA/D算法中，結(jié)合基于二范數(shù)權(quán)重向量，提出g支配策略的MOEA/D算法(g-MOEA/D算法).g支配把傳統(tǒng)Pareto前沿與參考點(diǎn)的使用相結(jié)合，使基于分解的多目標(biāo)進(jìn)化算法生成適應(yīng)決策者偏好的有效解的集合，來代替整個(gè)Pareto解集或單個(gè)有效解，從而提高M(jìn)OEA/D的擇優(yōu)效果及收斂性.實(shí)驗(yàn)表明，g支配可以與 MOEA/D算法有效結(jié)合，獲得很好的多目標(biāo)優(yōu)化解，算法在各性能指標(biāo)上也能達(dá)到令人滿意的結(jié)果，可有效解決流水車間調(diào)度問題.

1 流水車間調(diào)度模型的構(gòu)建

1.1 問題描述

FSP作為典型的工業(yè)生產(chǎn)規(guī)劃問題是當(dāng)前學(xué)術(shù)界的熱點(diǎn)問題之一.FSP從數(shù)學(xué)上可以描述為：n個(gè)不同的工件在m臺不同的機(jī)床上加工，每個(gè)工件都以固定的順序依次訪問所有的機(jī)器，每個(gè)工件在不同機(jī)器上的加工時(shí)間都是固定的[15].這里使用時(shí)間矩陣T來表示使用機(jī)器加工零件的時(shí)間，其中：tij∈T，表示第i個(gè)工件使用第j個(gè)機(jī)器的加工時(shí)間[16].

1.2 多目標(biāo)流水車間調(diào)度模型構(gòu)建

本FSP調(diào)度任務(wù)是確定各個(gè)工件的加工次序，即以工件的加工順序代表種群個(gè)體，其目的是同時(shí)優(yōu)化最大完工時(shí)間、最大延遲時(shí)間及庫存成本三個(gè)目標(biāo)[17]，該問題優(yōu)化后得到一組解集而不是一個(gè)最優(yōu)解，即得到Pareto最優(yōu)解集.針對本問題，構(gòu)建目標(biāo)函數(shù)：

minY=(f1,f2,f3)

(1)

FSP問題約束條件如下： ① 每個(gè)工件加工路徑相同，不允許改變(依序從機(jī)器1到機(jī)器m加工)； ② 每個(gè)時(shí)刻，每臺機(jī)床只能加工一道工序, 工序不允許中斷； ③ 一個(gè)工件不能同時(shí)在不同機(jī)床上加工； ④ 工序的準(zhǔn)備時(shí)間忽略不計(jì)，或者包含在加工時(shí)間中.構(gòu)建時(shí)間約束條件：

C11>t11

(2)

Cik≥max{Ci(k-1),C(i-1)k}+Tik(i=2, …,n；k=2, …,m)

(5)

式(2)表示工件1第一道工序的加工時(shí)間大于在第一臺機(jī)器加工時(shí)間，式(3)～(5)表示對任何工件，其完成時(shí)間取決于其在某機(jī)器上的加工時(shí)間和開始時(shí)間.其中：Tik表示第i個(gè)工件使用第k臺機(jī)器的加工時(shí)間；Cik為工件i的第k道工序的完工時(shí)間.

2 MOEA/D算法描述

多目標(biāo)優(yōu)化問題數(shù)學(xué)模型描述如下：

minF(x)={f1(x),f2(x), …,fi(x), …,fm(x)}T, subject tox∈Ω

(6)

其中：x是決策變量；Ω是決策空間；F:Ω→Rm為m維目標(biāo)向量；Rm表示目標(biāo)空間；fi(x)是第i個(gè)待優(yōu)化的目標(biāo)函數(shù)；F(x)為所得目標(biāo)函數(shù)值.

MOEA/D算法實(shí)現(xiàn)方式是將多目標(biāo)優(yōu)化數(shù)學(xué)模型(式(6))通過聚合函數(shù)分解成一系列單目標(biāo)子問題, 利用子問題的函數(shù)值，在種群更新過程中通過對比父代、子代所得子問題函數(shù)值的大小，保留子問題函數(shù)值較小的種群，實(shí)現(xiàn)對種群的更新，最終獲得一組Pareto最優(yōu)解.算法主要涉及分解策略、父代個(gè)體選擇策略和外部存檔更新策略.

2.1 分解策略

MOEA/D聚合函數(shù)的分解策略主要有三種[18]: 加權(quán)求和聚合法(weighted sum approach), 切比雪夫聚合法(Tchebycheff approach)以及邊界交叉聚合法(boundary intersection approach).切比雪夫聚合法在求解二維或三維目標(biāo)優(yōu)化問題上具較好的優(yōu)化能力，因此主要討論切比雪夫聚合法，應(yīng)用切比雪夫聚合函數(shù)將多目標(biāo)模型(式(6))轉(zhuǎn)化為單目標(biāo)子問題的形式如下：

(7)

2.1.1 權(quán)重向量產(chǎn)生方法

MOEA/D通過權(quán)重向量的選取對種群中的個(gè)體運(yùn)動軌跡和搜索方向進(jìn)行控制.能夠自適應(yīng)地調(diào)整對Pareto前沿不同部分的搜索.MOEA/D使用NBI(normal boundary intersection)法在超平面上產(chǎn)生均勻分布的權(quán)重向量[22].NBI法在種群規(guī)模大、目標(biāo)多時(shí)，存在權(quán)重向量分布不均勻的問題.為改善MOEA/D在FSP問題上的應(yīng)用，提高M(jìn)OEA/D的性能，采用基于二范數(shù)的方法生成權(quán)重向量：

(8)

(9)

2.1.2 理想?yún)⒖键c(diǎn)選取方法

切比雪夫聚合函數(shù)中理想?yún)⒖键c(diǎn)的初值取初始種群中各個(gè)子問題目標(biāo)函數(shù)的最小值.表示為：zj=min{fj(x)|x∈Ω}，j=1, 2, …,M.在每次種群更新后，比較更新后的目標(biāo)函數(shù)值與上一代的理想?yún)⒖键c(diǎn)函數(shù)值，保留其較小值，完成對理想?yún)⒖键c(diǎn)的更新.具體步驟可表示為： 若zj>fj(y′), 則設(shè)zj=fj(y′),j=1, …,M.y′為更新后的個(gè)體，fj(y′)為第j個(gè)目標(biāo)的函數(shù)值.

2.2 父代個(gè)體選擇策略

MOEA/D算法中，從父代中選擇兩個(gè)個(gè)體進(jìn)行交叉從而對個(gè)體進(jìn)行更新.通過父代個(gè)體的鄰域關(guān)系選擇出兩個(gè)個(gè)體.計(jì)算個(gè)體權(quán)重向量之間的歐式距離，歐式距離越小，說明個(gè)體之間的函數(shù)值越接近.取函數(shù)值最接近的兩個(gè)個(gè)體進(jìn)行交叉，有利于對種群的進(jìn)化.其具體方法可表示為：

計(jì)算權(quán)重向量集{λ1,λ2, …,λi, …,λN}之間的歐式距離.其中，λi為個(gè)體i所對應(yīng)的權(quán)重向量；

選取與λi歐式距離最近的T條權(quán)重向量{λi1, …,λiT}，得到T條權(quán)重向量所對應(yīng)的個(gè)體，將其作為個(gè)體i的鄰域集B(i)={i1, …,iT}.其中，T是權(quán)重向量的領(lǐng)域個(gè)數(shù).依靠這種鄰域關(guān)系，選定父代個(gè)體進(jìn)行交叉、修正操作，繁殖出新后代，實(shí)現(xiàn)個(gè)體更新.

2.3 外部存檔更新策略

MOEA/D算法中使用聚合函數(shù)對種群進(jìn)行一次更新后，采用非支配關(guān)系篩選出Pareto最優(yōu)解作為外部存檔(EP).每次迭代后都對外部存檔進(jìn)行更新.具體方法為： 將EP中所有被F(x′)支配的向量移除, 將非支配F(x′)加入EP中，完成對EP的更新.其中，x′為更新后的新解.F(x′)為其對應(yīng)的目標(biāo)函數(shù)值.

3 g-MOEA/D算法及求解FSP

3.1 g-MOEA/D算法描述

經(jīng)仿真實(shí)驗(yàn)表明, MOEA/D算法的支配關(guān)系在求解流水車間調(diào)度MOP時(shí)，求解質(zhì)量難以保證，解集的均勻性和分布性相對較差.將g支配策略作為外部存檔更新策略引入MOEA/D算法，建立g-MOEA/D算法，新策略不但能與切比雪夫分解策略有效結(jié)合，而且能進(jìn)一步提升求解多目標(biāo)流水車間調(diào)度問題解的質(zhì)量，能有效提升種群的均勻性及分布性.g-MOEA/D算法的實(shí)現(xiàn)方法為：

1) 初始化及建立外部存檔EP.隨機(jī)生成初始種群，設(shè)置EP上限NA，計(jì)算初始種群中個(gè)體g支配數(shù)量并進(jìn)行降序排列，保留種群中前NA個(gè)個(gè)體，加入外部存檔EP.

2) 應(yīng)用切比雪夫聚合函數(shù)對多目標(biāo)模型進(jìn)行分解.

3) 利用權(quán)重向量從父代中選擇個(gè)體，進(jìn)行交叉、修正操作，繁殖出新后代，比較父代與新后代，實(shí)現(xiàn)個(gè)體更新.

4) 基于g支配的外部存檔更新.合并更新后種群與父代外部存檔EP，計(jì)算合并后種群中每個(gè)個(gè)體g支配數(shù)量并進(jìn)行降序排列，保留種群中前NA個(gè)個(gè)體，加入EP，實(shí)現(xiàn)更新.

3.2 g支配策略

g支配(g-dominance)是對Pareto支配概念的改進(jìn)，這種支配方法可在不使用任何標(biāo)量函數(shù)的情況下，縮小已得到的Pareto解集范圍，從而得到更為有效的解集.g支配的數(shù)學(xué)模型如下:

(10)

圖1 基于參考點(diǎn)g的Flags值Fig.1 Flags based on reference point g

1) Flagg(fl)>Flagg(fn)；

通過上述g支配的條件，可得知在Flagg(fi)=0區(qū)域的個(gè)體定由Flagg(fi)=1區(qū)域的個(gè)體所支配.因此g支配數(shù)量較多的個(gè)體主要分布在區(qū)域二及區(qū)域四中.在經(jīng)過MOEA/D算法得到一組Pareto前沿后，結(jié)合g支配的條件，將進(jìn)一步縮小Pareto前沿的有效解范圍.在這兩個(gè)區(qū)域中有效解集的分布(圖2、圖3中紅色部分)主要分為兩種情況.

由圖2可以看出，參考點(diǎn)g并不是最優(yōu)解.存在Pareto前沿上個(gè)體都比參考點(diǎn)g小的情況.因此有效的最優(yōu)解集主要分布在區(qū)域四； 由圖3可以看出，參考點(diǎn)g是理想的最優(yōu)解.因此尋找區(qū)域二中與參考點(diǎn)最接近的個(gè)體作為更有效的最優(yōu)解集.無論給定的參考點(diǎn)g是否比Pareto前沿更好，都能夠通過g支配策略得出更為有效的最優(yōu)解集.

圖2 不可行的參考點(diǎn) 圖3 可行的參考點(diǎn)

3.3 g-MOEA/D算法求解FSP的具體步驟

步驟1 設(shè)置參數(shù)，包括種群大小N； 鄰域數(shù)量T； 目標(biāo)個(gè)數(shù)M； 最大迭代次數(shù)maxgen； 外部檔案上限NA.

步驟 2 利用式(12)產(chǎn)生N條權(quán)重向量λ1,λ2, …,λN.計(jì)算任意兩權(quán)重向量的歐式距離，為每個(gè)向量選出與其距離最近的T個(gè)向量作為其鄰域向量.對每個(gè)個(gè)體i=1, …,N，設(shè)置i的T條鄰域B(i)={i1, …,iT}，其中{λi1, …,λiT}是個(gè)體權(quán)重λi的T條最小距離權(quán)重.

步驟4 對種群進(jìn)行更新操作：

步驟4.1 交叉.從個(gè)體鄰域B(i)中隨機(jī)選擇2個(gè)個(gè)體進(jìn)行二進(jìn)制交叉, 生成新個(gè)體y.

步驟4.2 修正.通過ROV將新個(gè)體y轉(zhuǎn)化為整數(shù)型個(gè)體y′.

步驟4.3 更新理想?yún)⒖键c(diǎn)z.若zj>fj(y′), 則設(shè)zj=fj(y′),j=1, …,M.

步驟5 外部存檔維護(hù)和更新.采用g支配方法將EP中所有被F(y′)支配的解從EP中移除； 若F(y′) 不被EP中的任意解支配，則將非支配F(y′) 加入EP.

步驟6 如果滿足停止條件(迭代次數(shù)大于maxgen), 則停止迭代, 并輸出EP.否則, 返回步驟4.

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

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證g-MOEA/D算法的有效性及其優(yōu)越性，采用文[19]的方法建立10個(gè)不同規(guī)模的流水車間調(diào)度實(shí)例.對g-MOEA/D算法與文[6]中MOEA/D算法在理想解、性能指標(biāo)等方面進(jìn)行比較.兩算法對每一實(shí)例獨(dú)立運(yùn)行10次，采用當(dāng)代距離GD[24]、間隔距離SP[25]來比較解集的收斂性和分布性.

4.2 進(jìn)化算法的性能評價(jià)指標(biāo)

1) GD指標(biāo).GD指標(biāo)用于度量兩種比較算法得到的近似Pareto前沿和真實(shí)Pareto前沿之間的距離，是算法收斂性的度量指標(biāo).GD指標(biāo)定義為：

(11)

其中：P*為均勻分布的真實(shí)Pareto前沿；A是通過算法得到的近似Pareto前沿;v為從A中取任一近似Pareto前沿;d(v,P*)是v與P*的歐式距離的最小值; |A|是A中所有元素的總數(shù).GD值越小，算法所求得的近似Pareto前沿與真實(shí)Pareto前沿更近，收斂性更好.

2) SP指標(biāo).SP指標(biāo)用于評價(jià)算法的分布性，表示為：

(12)

其中：A是通過算法得到的近似Pareto前沿，|A|是A中所有元素的總數(shù).該指標(biāo)越小，所求的Pareto前沿的分布性越均勻.

4.3 結(jié)果對比及分析

以兩種算法計(jì)算每個(gè)實(shí)例，并獨(dú)立運(yùn)行10次后得到多目標(biāo)Pareto最優(yōu)解的平均值、GD指標(biāo)和SP指標(biāo)的平均值，結(jié)果列于表1.

表1 多目標(biāo)流水車間調(diào)度問題的仿真實(shí)驗(yàn)結(jié)果及其評價(jià)指標(biāo)

兩個(gè)算法的理想解為在各自的選擇交叉過程中所得到的不同理想?yún)⒖键c(diǎn).從表1可見： 在實(shí)例1, 2, 3, 4, 5, 6, 10中，g-MOEA/D算法的Pareto最優(yōu)解在三個(gè)目標(biāo)上全優(yōu)于MOEA/D算法； 在實(shí)例7, 8, 9中，g-MOEA/D算法的Pareto最優(yōu)解有兩個(gè)目標(biāo)優(yōu)于MOEA/D算法.結(jié)果表明，g-MOEA/D算法所得的Pareto最優(yōu)解總體上優(yōu)于MOEA/D算法.

從表1的評價(jià)指標(biāo)還可以看出： 其當(dāng)代距離(GD)及間隔距離(SP)方面g-MOEA/D都小于MOEA/D算法，可見g-MOEA/D其解的收斂性和分布均勻性均要優(yōu)于MOEA/D算法.

兩種算法的GD指標(biāo)及SP指標(biāo)盒圖如圖4所示，用于分析算法的顯著性差異，由于論文長度限制，圖4僅給出了代表種群規(guī)模小中大的三個(gè)實(shí)例.盒圖中間的紅色橫線代表中位數(shù)，紅色“+”為異常點(diǎn)，盒圖形狀越扁表示方差越小，穩(wěn)定性越高.從圖4可見：g-MOEA/D算法所得盒圖的中位線及上下兩條橫線的位置明顯低于MOEA/D算法，說明g-MOEA/D算法其GD指標(biāo)及SP明顯低于原MOEA/D算法，所得解集質(zhì)量更優(yōu).實(shí)驗(yàn)表明，基于g支配策略的MOEA/D算法可以有效解決多目標(biāo)流水車間調(diào)度問題.

圖4 兩種算法在3種不同種群規(guī)模上運(yùn)行10次的GD及SP指標(biāo)盒圖Fig.4 Boxplot of two algorithms for GD and SP running 10 times on 3 different population sizes

5 結(jié)語

為改善MOEA/D算法種群的收斂性與多樣性，提高多維目標(biāo)流水車間調(diào)度問題中解集的整體質(zhì)量，對MOEA/D算法進(jìn)行改進(jìn)，提出一種g支配策略的MOEA/D算法.該算法采用基于二范數(shù)權(quán)重向量，并將g支配方法引入到MOEA/D算法中用以求解三維多目標(biāo)流水車間調(diào)度問題.應(yīng)用g支配方法可以提高外部檔案擇優(yōu)的效率，進(jìn)而提高解集的收斂性與均勻性, 得到較高質(zhì)量的多目標(biāo)優(yōu)化解.通過仿真實(shí)驗(yàn)證明: 改進(jìn)后的g-MOEA/D算法對FSP問題具有更強(qiáng)的求解效果.本算法僅針對流水車間調(diào)度問題進(jìn)行求解，下一步將嘗試考慮更高維度的多目標(biāo)調(diào)度問題以及與其他類型的組合進(jìn)行問題研究，如柔性作業(yè)車間調(diào)度問題、零空閑流水車間調(diào)度問題、無等待流水車間調(diào)度等.