面向多目標柔性作業(yè)車間調(diào)度的強化學習NSGA-II算法

尹愛軍，閆文濤，張厚望

(1.重慶大學 a.機械工程學院;b.機械傳動國家重點實驗室,重慶 400044; 2.中國石油西南油氣田分公司 重慶氣礦,重慶 400021)

作業(yè)車間調(diào)度問題(JSP, Job shop scheduling problem)是作業(yè)車間系統(tǒng)生產(chǎn)管理的核心部分，在實現(xiàn)制造過程智能化的過程中發(fā)揮著重要作用。多目標柔性作業(yè)車間調(diào)度問題(MO-FJSP, multi-objective flexible job-shop scheduling problem)同時對多個性能指標進行優(yōu)化，在解決工序排序問題時考慮了工序加工機器選擇問題，更加貼近于實際生產(chǎn)環(huán)境，因而受到了諸多學者的廣泛關注[1-4]。

MO-FJSP是更為復雜的NP-hard問題[5]。Deb等[6]引入快速非支配排序和擁擠距離計算提出了NSGA-II算法，被廣泛應用于多目標優(yōu)化問題求解，但也存在易于早熟和多樣性不足等問題，許多學者對該算法做出了改進。Seng等[7]通過計算擁擠度和非支配水平來優(yōu)化新的種群選擇，提出一種基于改進NSGA-II的柔性車間作業(yè)低碳調(diào)度方法。繆嘉成等[8]針對RV減速器結構優(yōu)化問題，提出一種離散變量的編碼方案改進NSGA-II。陳輔斌等[9]利用免疫平衡原理改進NSGA-II算法的選擇策略和精英保留策略，提高了算法的優(yōu)化性能。胡成玉等[10]提出一種改進擁擠距離和自適應交叉變異的NSGA-II算法求解分布式數(shù)據(jù)中心負載調(diào)度問題，提升了算法收斂速度和精度。以上研究對NSGA-II算法的改進大都采用單一種群的遺傳操作模式，進化過程中缺乏激烈競爭關系，難以進化出適應性較強的個體。多種群進化策略可以有效改善算法對解空間的探索能力和開發(fā)能力，提高解的多樣性和分布均勻性。程子安等[11]提出一種改進的雙種群混合遺傳算法求解柔性作業(yè)車間調(diào)度問題，兩個種群采用不同的交叉與變異算子以提高種群多樣性，然而種群比例參數(shù)由人為設定，降低了算法的靈活性。近年來，許多研究將強化學習與智能算法結合應用于實際問題求解，Chen等[12]利用強化學習技術保持遺傳算法中種群的多樣性，防止GA過早收斂，提出一種基于強化學習的最優(yōu)RS算法。王曉燕等[13]提出一種基于強化學習的多策略選擇遺傳算法將種群劃分為3個子種群分別進化，提高收斂速度的同時改善了全局收斂問題，但僅優(yōu)化單個目標。封碩等[14]將支持強化學習RNSGA-II算法應用于無人機多目標三維航跡規(guī)劃規(guī)劃問題，通過動態(tài)優(yōu)化種群間遷徙參數(shù)保持種群多樣性，提高了收斂速度和收斂精度，但遺傳操作方式單一減小了局部搜索空間。

根據(jù)上述研究內(nèi)容的優(yōu)勢與不足，提出一種基于強化學習的改進NSGA-II算法用于求解多目標柔性車間調(diào)度問題。首先，根據(jù)性別判定法和種群比例參數(shù)將種群劃分為兩個不同的種群，并為每個種群分配不同的進化目標與遺傳操作，增強算法全局與局部搜索能力。迭代過程中運用強化學習機制動態(tài)調(diào)整種群比例參數(shù)，自主保持種群多樣性及分布均勻性在合理范圍，有效改善了算法尋優(yōu)能力與收斂性能。通過對標準算例實驗仿真，驗證了RLNSGA-II在求解多目標柔性車間調(diào)度問題上可以獲得較優(yōu)的Petro解集。

1 多目標柔性作業(yè)車間調(diào)度模型

MO-FJSP需解決n個工件{J1,J2,…,Jn}的加工機器分配以及在m臺機器{M1,M2,…,Mk}(k∈{1,2,…,m})上的加工順序問題。其中，每個工件Ji(i∈{1,2,…,n})有pi道工序，工序Oij(j∈{1,2,…,pi})的加工時間由所選機器性能決定。調(diào)度的目標是在滿足加工約束條件下使所期望的多個性能指標得到優(yōu)化。

調(diào)度模型考慮生產(chǎn)效率和設備利用率兩個方面，針對最大完工時間(Cm)、機器總負荷(Wt)以及瓶頸機器負荷(Wm)3個指標同時進行優(yōu)化，調(diào)度優(yōu)化目標集可以表示為min(Cm,Wt,Wm)，其中最小化最大完工時間是為了提高生產(chǎn)效率，而降低機器負荷可以提高機器利用率及機器壽命。目標函數(shù)的計算公式如下。

1)最大完工時間。

(1)

2)機器總負荷。

(2)

3)瓶頸機器負荷。

(3)

s.t.

(4)

Cij≤Si(j+1),?i,j。

(5)

(6)

(7)

Sij≥0,Cij≥0。

(8)

2 RNSGA-Ⅱ算法求解多目標柔性車間調(diào)度問題

NSGA-Ⅱ種群進化過程如圖1所示。首先對種群Pt執(zhí)行選擇、交叉、變異操作形成種群Qt，并將2個種群合并為種群Rt，然后對種群Rt進行非支配排序形成多個前列面Fi，并從低到高依次加入新一代種群Pt+1，當Fi加入使得種群超出規(guī)模大小時，依據(jù)擁擠距離從大到小將個體加入新一代種群Pt+1。由于降低了計算復雜度，NSGA-Ⅱ被廣泛應用于多目標優(yōu)化問題。但求解多目標柔性作業(yè)車間調(diào)度問題時，存在精英選擇策略導致種群多樣性不足使得算法陷入局部最優(yōu)解、早熟收斂的問題。因此，筆者通過融合多個多樣性度量指標，采用雙種群進化策略和強化學習改進NSGA-Ⅱ求解多目標柔性作業(yè)車間調(diào)度問題。

圖1 NSGA-Ⅱ種群進化過程Fig. 1 Population evolution process in NSGA-Ⅱ

2.1 雙種群進化策略

多目標進化算法大都采用單一進化策略，在一定程度上降低了算法的搜索能力和收斂速度，增加了算法的隨機性。采用雙種群進化思想可以提高NSGA-Ⅱ進化的方向性和適應性，擴大搜索空間，避免算法陷入局部最優(yōu)的問題。在進化過程中，根據(jù)種群比例參數(shù)和性別判定法[15]將種群拆分為兩個種群，并對兩個種群采用不同的遺傳操作。針對多目標優(yōu)化問題，采用性別判定法拆分種群的流程如下。

1)確定染色體種群規(guī)模N、測試種群規(guī)模S、種群分割比例參數(shù)β。

2)隨機生成數(shù)量為S的測試種群。

3)計算染色體種群中個體的繁殖能力，具體過程如下。

Fori=1 To N do

Forj=1 To S do

a)個體i與個體j進行交叉操作后產(chǎn)生后代個體；

b)如果后代個體支配個體i，則后代個體替換個體i并將個體i的繁殖能力加1；

End for

End for

4)評判染色體種群中個體的繁殖能力，具體過程如下。

Fori=1 To N do

If(個體i的繁殖能力大于平均繁殖能力)

個體i為繁殖個體；

Else

個體i為普通個體。

End for

5)種群分割。選擇繁殖個體中繁殖能力較強的N×β個個體形成子種群1，若數(shù)量不夠，則挑選普通個體中繁殖能力較強的個體補充；剩余個體形成子種群2。

種群1中的個體由于繁殖能力較強，因此對工序排序部分采用普通的POX交叉和插入變異[16]方式，機器選擇部分采用單點交叉和單點變異，從而保持種群的全局優(yōu)勢。而對于種群2，利用普通的遺傳操作難以產(chǎn)生新的個體，降低了算法的局部搜索能力，因此對工序排序部分采用改進的POX交叉方式和基因串逆序變異方式，如圖2(a)和(b);機器選擇部分選擇均勻交叉和定向變異方式，以提高算法的收斂能力，如圖3(a)和(b)所示。

圖2 種群2染色體工序部分交叉變異操作Fig. 2 Population 2 chromosome process partial crossover mutation operation

圖3 種群2染色體機器部分交叉變異操作Fig. 3 Population 2 chromosome machine partial crossover mutation operation

2.2 多目標問題多樣性度量

多目標問題中非劣解集在近似Pareto前沿上分布得越均勻、越離散則表明多樣性更好。常用的指標包括[17]Sigma度量、解間距度量、網(wǎng)格度量、熵度量和個體空間度量等。然而，單一評價指標會導致一定程度的偏差。因此考慮解間距和熵度量值兩個指標對多樣性進行度量，并結合強化學習動態(tài)控制種群比例參數(shù)，實現(xiàn)多目標柔性車間調(diào)度問題優(yōu)化求解。

2.2.1 解間距度量(spaceing metric)

設算法搜索到的具有Pareto性的前沿解的個數(shù)為|A|，則解間距指標Sp定義為：

(9)

其中

(10)

2.2.2 熵度量(Entropy)

設種群X有劃分X={X1,X2,…,XQ},其中1≤i≤Q,Q為劃分數(shù)，則

(11)

式中：Pi表示個體i落入第i個劃分的概率;|Xi|表示第i個劃分的個體數(shù)目;N表示整個種群的規(guī)模。種群多樣性熵的計算公式為

(12)

當熵值越大時，種群中個體分布得越離散、越均勻，種群的多樣性也越好。

2.3 基于強化學習的比例參數(shù)調(diào)整策略

強化學習是一種目標驅(qū)動的自適應優(yōu)化控制方法，智能體Agent通過與環(huán)境進行交互來調(diào)整自己的行動策略。其最終目標是獲得最優(yōu)策略π*，使得期望累積回報E=[Rs|st=s]最大。強化學習的迭代計算公式為

Q(st,at)=Q(st,at)+α[rt+1+γmaxQ(st+1,at)-Q(st,at)]，

(13)

式中：α稱為學習因子；γ為折扣率；r為獲得的即時獎勵。

將NSGA-Ⅱ中的種群視為Agent，最終目標是比例參數(shù)學習，Agent通過感知種群多樣性變化來控制種群比例參數(shù)，進而控制種群進化方向，當解間距較初始種群減小而熵度量值增加時，種群比例設置合理。強化學習的狀態(tài)劃分、動作設計以及獎賞機制如下。

2.3.1 狀態(tài)

表1 狀態(tài)集合

2.3.2 動作

強化學習Agent的動作是對種群比例參數(shù)的調(diào)整，包含增加、不變、減少3種。計算公式如式(14)所示。

(14)

式中β(t)、β(t-1)分別為第t和t-1代種群的分割比例參數(shù)。

依據(jù)解間距與熵度量值的變化決定Agent的獎賞，目標是學習最優(yōu)的比例參數(shù)β(t)。具體計算公式為

R=Rd+Re

(15)

(16)

2.4 RNSGA-II算法求解MO-FJSP問題流程

RLNSGA-II算法求解MO-FJSP的流程如圖4所示。

圖4 基于強化學習的改進NSGA-II算法流程圖Fig. 4 Flow chart of improved NSGA-II algorithm based on reinforcement learning

操作步驟如下：

Step1 輸入工件信息，設置算法參數(shù)：迭代次數(shù)G，初始種群比例參數(shù)β，種群規(guī)模N，交叉概率Pc，變異概率Pm，強化學習Q值表，學習率α以及折扣率γ。

Step2 產(chǎn)生初始種群，計算初始種群解間距值和熵度量值。染色體編碼采用基于工序的實數(shù)編碼方式，分為工序調(diào)度與機器選擇兩部分。

Step3 對種群進行快速非支配排序和擁擠度計算。

Step4 采用性別判定法按照比例參數(shù)β拆分種群，通過雙種群進化策略獲得新一代種群。

Step5 判斷是否達到最大迭代次數(shù)，如果是，則結束迭代；否則，執(zhí)行Step6。

Step6 計算種群的解間距和熵值，獲得狀態(tài)st。

Step7 計算獎勵值R，根據(jù)公式(14)更新Q值表。

Step8 采用ε-貪心策略選擇動作at，更新種群比例參數(shù),轉(zhuǎn)到Step3。

3 試驗仿真與分析

算法采用C#程序語言在Visual Studio2017軟件實現(xiàn)，運行環(huán)境為Intel?CoreTMi5-4430 CPU@3.00 GHz。RLNSGA-II算法的參數(shù)設置如下：種群規(guī)模N=100，最大迭代次數(shù)G=200,初始種群比例參數(shù)β=0.5,交叉概率Pc=0.8，變異概率Pm=0.1，強化學習的學習率α=0.9,折扣因子γ=0.9。

3.1 算例測試

為驗證RLNSGA-II算法求解的有效性，選取Kacem[18]等提出的不同規(guī)模的標準算例進行測試，用n×m表示一組n個工件與m臺機器的算例，每組算例均獨立運行10次，并將運行結果與多策略融合的Pareto人工蜂群算法[19]、改進粒子群算法[20]、混合人工蜂群算法[21]、自適應Jaya算法[22]及基于正態(tài)云的狀態(tài)轉(zhuǎn)移算法[23]的仿真結果進行對比，比較結果如表2所示。

表2 Kacem算例結果對比

通過表2可知，運用RLNSGA-II求解多目標FJSP均可以得到最優(yōu)組合解，且在總體運行結果和解的多樣性上與所提文獻中算法的結果基本一致。根據(jù)表格中的運算結果， RLNSGA-II算法在求解算例4×4和算例10×7時與MSIPABC算法的結果相同，相比于其他幾種優(yōu)化算法Pareto解更多樣且在單個目標值上有所突破；而對于算例8×8和算例10×10，RLNSGA-II的運行結果與MSIPABC、SAMO-Jaya和CSTA相近，但獲得Pareto解的個數(shù)多于TL-HGAPOS和HTABC算法,且與其相比在Wm優(yōu)化目標上更優(yōu)，圖5和圖6分別展示了RLNSGA-II求解算例8×8和算例10×10運算結果的甘特圖；對于算例15×15，RLNSGA-II的運算結果接近于其他幾種算法求得的最優(yōu)解，但解的多樣性優(yōu)于MSIPABC、TL-HGAPOS、HTABC和SAMO-Jaya 4種算法的仿真結果。綜合上述分析可知，RLNSGA-II可有效求解柔性作業(yè)車間多目標優(yōu)化調(diào)度問題。

圖5 8×8算例甘特圖Fig.5 Gantt chart of 8×8 calculation example

圖6 10×10算例甘特圖Fig.6 Gantt chart of 10×10 calculation example

3.2 算法改進性能分析

為了驗證各改進部分對NSGA-II影響， 針對Kacem 8×8算例進行收斂性能及多樣性度量指標對比分析。以3個目標函數(shù)之和作為適應度值，分別采用NSGA-II、只加入雙種群進化策略的改進NSGA-II及RLNSGA-II進行求解，得到收斂性能對比圖及多樣性度量指標圖(如圖7所示)。

圖7 算法收斂性對比Fig.7 Algorithm convergence comparison

由圖7中收斂曲線對比分析可知，采用雙種群進化策略改進NSGA-II后，可以明顯提升算法的收斂速度，克服NSGA-II易于局部收斂問題。而RLNSGA-II同時引入雙種群進化策略和強化學習機制，收斂速度更快，種群適應度值更優(yōu)。驗證了RLNSGA-II算法能夠有效改善NSGA-II的收斂性能。

圖8和圖9分別為算法求解過程中兩個多樣性度量指標的變化曲線。由圖8可知，采用強化學習對NSGA-II改進后，種群的解間距能夠快速地降低并保持在較小的范圍內(nèi)，說明RLNSGA-II得到的解更加均勻。圖9為熵度量值對比圖，相比于NSGA-II和改進NSGA-II，RLNSGA-II在前100次迭代過程中可以更好地保持種群熵度量值在較大的范圍；而在后100次迭代過程中，RLNSGA-II相比于改進NSGA-II在加快收斂的同時仍能有效保持熵度量值，增加解的離散性，驗證了RLNSGA-II能夠較好保持種群的多樣性。

圖8 解間距值對比Fig. 8 Comparison of solution spacing values

圖9 熵度量值對比Fig. 9 Comparison of entropy measures

4 結束語

針對完工時間、機器總負荷和瓶頸機器負荷3個調(diào)度目標，提出了一種基于強化學習的改進NSGA-II算法求解MO-FJSP問題。運用性別判定法對種群進行拆分，并采用雙種群進化策略改進NSGA-II的進化過程，增加算法局部搜索空間和全局搜索能力，改善收斂性能；根據(jù)種群解間距和熵值兩個度量指標建立狀態(tài)空間，通過強化學習機制調(diào)整種群比例參數(shù)，間接調(diào)整種群的進化方向，將種群多樣性保持在合理范圍內(nèi)，避免了NSGA-II易于收斂至第一等級非支配曲面的缺陷。最后，通過仿真基準算例驗證了算法求解的有效性和對NSGA-II改進的優(yōu)越性。未來將繼續(xù)對算法進行優(yōu)化，進一步研究RLNSGA-II用于柔性作業(yè)車間多目標動態(tài)調(diào)度等復雜問題。