面向多目標(biāo)柔性作業(yè)車(chē)間調(diào)度的強(qiáng)化學(xué)習(xí)NSGA-II算法

尹愛(ài)軍，閆文濤，張厚望

(1.重慶大學(xué) a.機(jī)械工程學(xué)院;b.機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室,重慶 400044; 2.中國(guó)石油西南油氣田分公司 重慶氣礦,重慶 400021)

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

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

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

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

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

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

1)最大完工時(shí)間。

(1)

2)機(jī)器總負(fù)荷。

(2)

3)瓶頸機(jī)器負(fù)荷。

(3)

s.t.

(4)

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

(5)

(6)

(7)

Sij≥0,Cij≥0。

(8)

2 RNSGA-Ⅱ算法求解多目標(biāo)柔性車(chē)間調(diào)度問(wèn)題

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

圖1 NSGA-Ⅱ種群進(jìn)化過(guò)程Fig. 1 Population evolution process in NSGA-Ⅱ

2.1 雙種群進(jìn)化策略

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

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

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

3)計(jì)算染色體種群中個(gè)體的繁殖能力，具體過(guò)程如下。

Fori=1 To N do

Forj=1 To S do

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

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

End for

End for

4)評(píng)判染色體種群中個(gè)體的繁殖能力，具體過(guò)程如下。

Fori=1 To N do

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

個(gè)體i為繁殖個(gè)體；

Else

個(gè)體i為普通個(gè)體。

End for

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

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

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

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

2.2 多目標(biāo)問(wèn)題多樣性度量

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

2.2.1 解間距度量(spaceing metric)

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

(9)

其中

(10)

2.2.2 熵度量(Entropy)

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

(11)

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

(12)

當(dāng)熵值越大時(shí)，種群中個(gè)體分布得越離散、越均勻，種群的多樣性也越好。

2.3 基于強(qiáng)化學(xué)習(xí)的比例參數(shù)調(diào)整策略

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

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

(13)

式中：α稱(chēng)為學(xué)習(xí)因子；γ為折扣率；r為獲得的即時(shí)獎(jiǎng)勵(lì)。

將NSGA-Ⅱ中的種群視為Agent，最終目標(biāo)是比例參數(shù)學(xué)習(xí)，Agent通過(guò)感知種群多樣性變化來(lái)控制種群比例參數(shù)，進(jìn)而控制種群進(jìn)化方向，當(dāng)解間距較初始種群減小而熵度量值增加時(shí)，種群比例設(shè)置合理。強(qiáng)化學(xué)習(xí)的狀態(tài)劃分、動(dòng)作設(shè)計(jì)以及獎(jiǎng)賞機(jī)制如下。

2.3.1 狀態(tài)

表1 狀態(tài)集合

2.3.2 動(dòng)作

強(qiáng)化學(xué)習(xí)Agent的動(dòng)作是對(duì)種群比例參數(shù)的調(diào)整，包含增加、不變、減少3種。計(jì)算公式如式(14)所示。

(14)

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

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

R=Rd+Re

(15)

(16)

2.4 RNSGA-II算法求解MO-FJSP問(wèn)題流程

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

圖4 基于強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II算法流程圖Fig. 4 Flow chart of improved NSGA-II algorithm based on reinforcement learning

操作步驟如下：

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

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

Step3 對(duì)種群進(jìn)行快速非支配排序和擁擠度計(jì)算。

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

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

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

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

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

3 試驗(yàn)仿真與分析

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

3.1 算例測(cè)試

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

表2 Kacem算例結(jié)果對(duì)比

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

圖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 算法改進(jìn)性能分析

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

圖7 算法收斂性對(duì)比Fig.7 Algorithm convergence comparison

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

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

圖8 解間距值對(duì)比Fig. 8 Comparison of solution spacing values

圖9 熵度量值對(duì)比Fig. 9 Comparison of entropy measures

4 結(jié)束語(yǔ)

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