一種求解多目標(biāo)FJSP的自學(xué)習(xí)遺傳算法

常鏡洳，于 東

1(中國(guó)科學(xué)院大學(xué)，北京 100049)

2(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所，沈陽(yáng) 110168)

3(大連東軟信息學(xué)院，遼寧 大連 116023)

1 引 言

FJSP(flexible job-shop scheduling problem)已被證明為一種強(qiáng)NP難問(wèn)題[1]，作為智能化生產(chǎn)制造[2，3]中經(jīng)典決策活動(dòng)，在生產(chǎn)管理系統(tǒng)中占據(jù)核心和關(guān)鍵位置，其生產(chǎn)決策方案的精準(zhǔn)度、可靠性、時(shí)效性很大程度上體現(xiàn)企業(yè)的智能化水平.由于全局搜索和并行搜索的優(yōu)越性，遺傳算法(GA)是解決多目標(biāo)FJSP問(wèn)題的最廣泛群智能優(yōu)化算法之一[4].

Gu等針對(duì)復(fù)雜柔性生產(chǎn)調(diào)度問(wèn)題，提出了一種改進(jìn)的自適應(yīng)變鄰域搜索遺傳算法[5].Zeng等針對(duì)混合工作日歷下的多目標(biāo)FJSP問(wèn)題，設(shè)計(jì)了一種基于精英策略的非支配排序遺傳算法[6].Rooyani D等對(duì)大規(guī)模工件生產(chǎn)問(wèn)題，提出了一種高效的兩階段遺傳算法[7].Shi等利用模糊學(xué)和IGA算法求解能源消耗最小、最大完工時(shí)間和消費(fèi)者滿意度最大等不確定多重目標(biāo)的FJSP問(wèn)題[8].朱等基于直覺(jué)模糊集相似度改進(jìn)遺傳算法，求解空閑時(shí)間、機(jī)器能耗為目標(biāo)的多目標(biāo)FJSP問(wèn)題[9].Wang等設(shè)計(jì)并行雙鏈?zhǔn)骄幋a，結(jié)合變鄰域搜索強(qiáng)化遺傳算法的局部搜索能力，解決多目標(biāo)的柔性生產(chǎn)調(diào)度問(wèn)題[10].

GA的性能與交叉概率(Pc)和變異概率(Pm)緊密相關(guān).如果Pc和Pm太大，較優(yōu)解易丟失;如果Pc和Pm太小，則很難生成新染色體[11，12].因此，采用遺傳算法作為多目標(biāo)FJSP基本優(yōu)化方法，并基于增強(qiáng)學(xué)習(xí)(RL)對(duì)Pc和Pm進(jìn)行種群迭代間智能調(diào)整.本文結(jié)構(gòu)如下：第2章節(jié)FJSP問(wèn)題描述及數(shù)學(xué)建模；第3章節(jié)介紹基于非支配排序的GA算法和增強(qiáng)學(xué)習(xí)算法；第4章節(jié)介紹融合算法模型及增強(qiáng)學(xué)習(xí)設(shè)計(jì)要素；實(shí)驗(yàn)驗(yàn)證在第5章節(jié)展示；最后結(jié)論部分進(jìn)行總結(jié)及下一步研究工作介紹.

2 問(wèn)題定義

n×m的FJSP問(wèn)題描述如下：車(chē)間n種獨(dú)立工件J={J1，J2，J3，…，Jn}在m臺(tái)獨(dú)立機(jī)器M={M1，M2，M3，…，Mm}上加工；每個(gè)工件Ji有多道加工工序Oij(第i個(gè)工件Ji的第j個(gè)工序，j=1，2，3，…，hi)，并按照一定先后工藝次序進(jìn)行加工，且每道工序Oij可被多臺(tái)機(jī)器進(jìn)行加工，Oij在機(jī)器Mk(k=1，2，3，…，m)上的加工時(shí)間tijk固定且已知.

3個(gè)調(diào)度目標(biāo)：最大完工時(shí)間最小Cmax、最大負(fù)荷機(jī)器最小Wm、總機(jī)器負(fù)荷最小Wt，其目標(biāo)函數(shù)如式(1)～式(3)所示：

(1)

(2)

(3)

問(wèn)題約束函數(shù)如下：

tij≥0，sij≥0i=1，2，3，…，n;j=1，2，3，…，hi;

(a)

sij+tij≤si(j+1)i=1，2，3，…，n;j=1，2，3，…，hi;

(b)

sij+tijk≤srt+Z×(1-yijrtk)i=1，2，3，…，n;r=1，2，3，…，n;j=1，2，3，…，hi;t=1，2，3，…，hr;k=1，2，3，…，m;

(c)

(d)

(e)

(f)

其中sij表示工序Oij在加工開(kāi)始時(shí)間，hi表示工件Ji的工序總數(shù)，Z表示一個(gè)足夠大的正數(shù)，mij表示工序Oij的可選加工機(jī)器數(shù).約束式(a)表示工序的加工時(shí)間必須大于0；約束式(b)表示每一個(gè)工件的工序間先后順序；約束式(c)表示同一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；約束式(d)表示同一工件在同一時(shí)刻只能被一臺(tái)機(jī)器加工.

表1為一個(gè)2×4的FJSP實(shí)例，表中數(shù)字表示加工時(shí)間tijk，‘-’表示工序在對(duì)應(yīng)機(jī)器上不能被加工.

3 基礎(chǔ)算法

3.1 遺傳算法

3.1.1 編碼

染色體采用A/B分段編碼，將FJSP的工序排序(OS)和機(jī)器選擇(MS)兩個(gè)子問(wèn)題分開(kāi)表示，OS部分基因位長(zhǎng)度和MS部分基因位長(zhǎng)度都等于所有工件工序數(shù)總和T0，以表1的P-FJSP為例，一個(gè)染色體編碼如圖1所示.

表1 P-FJSP實(shí)例

圖1從左至右，OS部分從左至右的先后順序表示工序Oij間的先后加工順序，第1個(gè)2′代表工件J2，J2第1次出現(xiàn)表示工序O21.MS部分整數(shù)基因位依次對(duì)應(yīng)OS部分工序Oij選擇的機(jī)器，左邊第1個(gè)1′代表工序O21在可加工機(jī)器集{M1，M2，M4}中選擇M1.

圖1 一條染色體表示

3.1.2 種群初始化

為提高初始種群解的質(zhì)量，本算法的工序排序OS部分采用隨機(jī)方法生成，而機(jī)器選擇MS部分采用全局選擇GS、局部選擇LS和隨機(jī)選擇RS相結(jié)合的方式生成.

全局選擇機(jī)器是以所有機(jī)器負(fù)荷均衡化的角度，使用貪心算法設(shè)計(jì)策略為每個(gè)工序選擇當(dāng)前可加工機(jī)器中負(fù)荷最小的機(jī)器；局部選擇機(jī)器在每個(gè)工件內(nèi)部使用貪心設(shè)計(jì)策略，在每個(gè)工件Ji內(nèi)，其每個(gè)工序Oij選擇機(jī)器時(shí)，考慮所有機(jī)器負(fù)荷均衡化的角度；下一個(gè)工件Ji+1的第一個(gè)工序選擇機(jī)器時(shí)，每臺(tái)機(jī)器負(fù)荷重新設(shè)置為0.

3.1.3 快速非支配排序和適應(yīng)度值分配

依據(jù)NSGA-II[13]中快速非支配排序，將種群P劃分成互不相交的且具有支配關(guān)系的子群體P1P2…Pn，對(duì)染色體支配關(guān)系進(jìn)行分類(lèi)劃定對(duì)應(yīng)帕累托階層prank=1，2，3，…，n.

為保證種群分布多樣性，采用小生境技術(shù)中的擁擠距離.Dij表示同一帕累托階層Pi中染色體i、j之間的距離如見(jiàn)式(4)，則染色體i到同層染色體距離的最小值為i的擁擠距離Cd(i)如式(5)所示：

Dij=|Cmax(i)-Cmax(j)|+|Wm(i)-Wm(j)|+|Wt(i)-Wt(j)|(i≠j)

(4)

Cd(i)=min{Di1，Di2，…，Dik，…，Din}(i≠k)

(5)

根據(jù)染色體i所在的帕累托階層prank和其擁擠距離Cd(i)，計(jì)算適應(yīng)度值分配；計(jì)算公式如式(6)所示：

(6)

3.1.4 遺傳算子

1)選 擇

本文采用輪盤(pán)賭和精英保留策略相結(jié)合的選擇方法，兩者相輔相成加快算法收斂速度.假設(shè)種群規(guī)模為popSize，前popSize-1個(gè)染色體通過(guò)輪盤(pán)賭方法選擇，第popSize個(gè)染色體設(shè)置為當(dāng)前種群中適應(yīng)度值最高的染色體.

2)交 叉

Price及Stephens等在1975年的Holland的模式理論基礎(chǔ)上做了相關(guān)研究表明[14]：進(jìn)化算法的多點(diǎn)交叉上，適應(yīng)度高的模式在子代中成指數(shù)階增長(zhǎng).因此本算法在MS部分采用均勻交叉方式，OS部分采用POX(基于工件優(yōu)先順序交叉)方式.

3)變 異

機(jī)器選擇部分采用多輪單點(diǎn)交換變異；為了提高GA的局部搜索能力且保證種群多樣性，OS部分采用鄰域搜索變異.

3.2 增強(qiáng)學(xué)習(xí)

增強(qiáng)學(xué)習(xí)[15，16]基礎(chǔ)模型包括環(huán)境、智能體、行動(dòng)策略、獎(jiǎng)勵(lì)、值函數(shù)，通常用馬爾科夫決策過(guò)程(Markov Decision Process)[17]描述學(xué)習(xí)過(guò)程.環(huán)境的狀態(tài)空間S，智能體采取的行動(dòng)空間A，智能體感知到環(huán)境當(dāng)前狀態(tài)st(st∈S)并對(duì)其實(shí)施行動(dòng)at(at∈A)，行動(dòng)at作用在狀態(tài)st上，環(huán)境狀態(tài)發(fā)生變化，轉(zhuǎn)移至狀態(tài)st+1，同時(shí)給予智能體獎(jiǎng)勵(lì)rt+1，智能體根據(jù)rt+1更新行動(dòng)選擇，并對(duì)環(huán)境實(shí)施下一個(gè)行動(dòng)at+1.

SARSA和Q-learning[18]是兩種典型的基于值的增強(qiáng)學(xué)習(xí)算法.Q值用于表征動(dòng)作選擇，SARSA和Q-learning的一步更新函數(shù)如式(7)和式(8)[19]所示：

Q(st，at)=(1-α)Q(st，at)+α(rt+1+γQ(st+1，at+1))

(7)

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

(8)

其中Q(st，at)為狀態(tài)st與動(dòng)作at的Q值函數(shù)，rt+1為動(dòng)作at執(zhí)行后獎(jiǎng)勵(lì)值，α為學(xué)習(xí)率，γ為學(xué)習(xí)折扣率.

本文將SARSA和Q-learning算法結(jié)合動(dòng)態(tài)調(diào)整Pc和Pm；種群迭代初期，GA與SARSA結(jié)合，通過(guò)公式(7)更新Q值；種群迭代次數(shù)滿足公式(9)轉(zhuǎn)換條件，GA與Q-learning結(jié)合，Q值通過(guò)公式(8)更新.

(9)

其中t表示當(dāng)前迭代次數(shù)，|S|表示環(huán)境狀態(tài)總數(shù)，|A|表示行動(dòng)總數(shù).

4 融合算法

4.1 融合算法模型

GA與RL融合算法模型如圖2所示，包括GA環(huán)境、增強(qiáng)學(xué)習(xí)模型和學(xué)習(xí)過(guò)程.學(xué)習(xí)過(guò)程如下：

圖2 融合算法模型

1)RL獲取GA的狀態(tài)st；

2)RL根據(jù)行動(dòng)選擇策略確定行動(dòng)at：確定種群當(dāng)前迭代Pc、Pm值；

3)GA執(zhí)行at，即根據(jù)Pc、Pm值執(zhí)行遺傳算子，GA環(huán)境狀態(tài)轉(zhuǎn)移至st+1；

4)RL從GA獲取獎(jiǎng)勵(lì)值rt，更新行動(dòng)選擇以確定下一步行動(dòng)at+1，并計(jì)算Q值以更新Q值表.

4.2 學(xué)習(xí)模型設(shè)計(jì)要素

1)GA狀態(tài)集

多目標(biāo)FJSP的目標(biāo)包括最大完工時(shí)間最小Cmax、最大負(fù)荷機(jī)器最小Wm、總機(jī)器負(fù)荷最小Wt，因此非支配排序分配的適應(yīng)度作為GA環(huán)境狀態(tài)依據(jù)，GA算法狀態(tài)st計(jì)算公式如式(10)所示：

(10)

GA環(huán)境狀態(tài)集S={s1，s2，…，s19，s20}[20]，S取值范圍[0，1)，s的取值跨度為0.05.若st∈[0，0.05)，則s=s1；若st∈[0.05，0.1)，則s=s2；依此類(lèi)推，若st∈[0.95，1)，則s=s20.

2)行動(dòng)集

學(xué)習(xí)模型中行動(dòng)確定GA的交叉概率Pc和變異概率Pm，因此行動(dòng)集A={a1，a2，…，a9，a10}.Pc取值范圍[0.4，0.9]，因此每個(gè)交叉概率取值跨度為0.05；例如學(xué)習(xí)模型根據(jù)策略選擇行動(dòng)a1，那么Pc∈[0.4，0.45]，從[0.4，0.45]中選取一隨機(jī)數(shù)賦值給Pc.Pm取值范圍[0.01，0.21]，每個(gè)變異概率取值跨度為0.02，例如選擇行動(dòng)a2，那么Pm∈[0.04，0.06]，從[0.04，0.06]中選取一隨機(jī)數(shù)賦值給Pm.

3)獎(jiǎng)勵(lì)函數(shù)

交叉和變異算子分別體現(xiàn)GA的全局搜索和局部搜索能力，因此最優(yōu)染色體適應(yīng)度和平均染色體適應(yīng)度分別體現(xiàn)Pc和Pm的獎(jiǎng)勵(lì).如果第t代中最優(yōu)染色體適應(yīng)度值優(yōu)于第t-1代中最優(yōu)染色體適應(yīng)度值，說(shuō)明當(dāng)前Pc的有效性，因此GA給與智能體有效的獎(jiǎng)勵(lì)rc；如果第t代平均染色體適應(yīng)度值優(yōu)于第t-1代平均染色體適應(yīng)度值，說(shuō)明當(dāng)前Pm的有效性，因此GA給與智能體有效的獎(jiǎng)勵(lì)rm；rc和rm的計(jì)算公式如式(11)、式(12)所示：

(11)

(12)

其中Bestf(xit)表示第t代種群Population中最優(yōu)適應(yīng)度.

4)行動(dòng)策略

exploitation和exploration是矛盾體，若使得累計(jì)獎(jiǎng)勵(lì)最大，必須在兩者間達(dá)成折中.ε-greedy策略基于概率進(jìn)行折中，以ε概率進(jìn)行exploration，以1-ε概率進(jìn)行exploitation，其表達(dá)式如式(13)所示：

(13)

4.3 融合算法流程

融合算法流程圖如圖3所示，其具體實(shí)現(xiàn)步驟如下：

圖3 融合算法流程

Step1.初始化基本參數(shù)

1)GA基本參數(shù)：全局選擇比例Pgs、局部選擇比例Pls和隨機(jī)選擇比例Prs、種群規(guī)模Popsize和迭代上限Iteration等.

2)初始化RL基本參數(shù)：狀態(tài)集S、行為集A、學(xué)習(xí)率α、學(xué)習(xí)折扣率γ、獎(jiǎng)勵(lì)值r、Q值表等.

Step2.根GA中種群初始化策略和染色體編碼規(guī)則生成初始種群Population;并設(shè)置當(dāng)前迭代次數(shù)t←0.

Step3.為初始種群中每個(gè)染色體劃定帕累托階層、計(jì)算擁擠距離、基于階層和距離分配適應(yīng)度.

Step4.從行動(dòng)集中隨機(jī)選擇一個(gè)行動(dòng)at，令a←at;根據(jù)公式(10)計(jì)算GA算法的狀態(tài)st，令當(dāng)前狀態(tài)s←st.

Step5.判斷迭代次數(shù)t是否達(dá)到上限，如果達(dá)到，輸出最優(yōu)解集；否則轉(zhuǎn)入步驟6.

Step6.根據(jù)公式(11)和(12)計(jì)算獎(jiǎng)勵(lì)函數(shù)rc和rm.

Step7.判斷轉(zhuǎn)換條件式(9)是否達(dá)到，若未達(dá)到，轉(zhuǎn)至Step8；否則轉(zhuǎn)至Step 9.

Step8.根據(jù)ε-greedy策略選擇行動(dòng)at+1，并根據(jù)公式(7)更新Q值表.

Step9.根據(jù)貪心策略選擇行動(dòng)at+1，并根據(jù)公式(8)更新Q值表，根據(jù)ε-greedy策略更新行動(dòng)at+1.

Step10.根據(jù)公式(10)計(jì)算GA算法的狀態(tài)st+1，更新當(dāng)前狀態(tài)s←st+1；更新當(dāng)前行動(dòng)a←at+1;

Step11.根據(jù)a中Pc和Pm執(zhí)行遺傳算子，生成新的種群Population，迭代次數(shù)t←t+1.

Step12.解碼活動(dòng)調(diào)度：種群Population中每個(gè)染色體劃定帕累托階層、計(jì)算擁擠距離、基于階層和距離分配適應(yīng)度.

Step13.轉(zhuǎn)至步驟5.

5 實(shí)驗(yàn)測(cè)試

上述融合算法在Matlab 2018a上采用matlab語(yǔ)言實(shí)現(xiàn)，程序在處理器Intel CoreIi5-5200U，主頻2.2GHz，內(nèi)存8G的PC機(jī)上運(yùn)行.為證明該融合算法求多目標(biāo)FJSP最優(yōu)解集的準(zhǔn)確性和高效性，實(shí)驗(yàn)測(cè)試包含：

實(shí)驗(yàn)1.選用Kacem et al.設(shè)計(jì)的8×8、10×10、15×10實(shí)例[21]測(cè)試Pareto最優(yōu)解集準(zhǔn)確性；

實(shí)驗(yàn)2.選取Brandimarte的標(biāo)準(zhǔn)實(shí)例mk01-mk10[22]進(jìn)行算法時(shí)間效率測(cè)試.

算法其他參數(shù)設(shè)置：種群規(guī)模Popsize為100，最大迭代次數(shù)Iteration為100，全局機(jī)器選擇概率Pgs=0.6，局部機(jī)器選擇概率Pls=0.3，隨機(jī)選擇機(jī)器概率Prs=0.1；初始Q值表：一個(gè)20行10列的0值矩陣，初始化隨機(jī)選取行動(dòng)a，獎(jiǎng)勵(lì)函數(shù)r=1，策略貪心率ε=0.85，學(xué)習(xí)率α=0.75，學(xué)習(xí)折扣率γ=0.2.

5.1 實(shí)驗(yàn)1

以Kacem設(shè)計(jì)8×8、10×10、15×10問(wèn)題數(shù)據(jù)進(jìn)行測(cè)試，每個(gè)問(wèn)題仿真實(shí)驗(yàn)運(yùn)行30次.為驗(yàn)證算法有效性，將測(cè)試結(jié)果和EDA[23]、DCRO[24]、GSA-M[25]算法進(jìn)行比較，測(cè)試結(jié)果如表2所示.

表2 Kacem的3個(gè)算例數(shù)據(jù)對(duì)比

8×8問(wèn)題本算法和其他算法相比，最優(yōu)解都找到了，且最優(yōu)解(16，13，73)找到的頻率最高，其調(diào)度方案如圖4所示.10×10的問(wèn)題本算法和其他算法相比，最優(yōu)解都找到了，且最優(yōu)解(7，5，43)找到的頻率最高，其調(diào)度方案如圖5所示.15×10的問(wèn)題本算法和其他算法相比，兩個(gè)最優(yōu)解都找到了，且最優(yōu)解(11，10，93)找到的頻率最高，其調(diào)度方案如圖6所示.

圖4 8×8問(wèn)題實(shí)例解(Cmax=16，Wm=13，Wt=73)

圖5 10×10問(wèn)題實(shí)例解(Cmax=7，Wm=5，Wt=43)

圖6 15×10問(wèn)題實(shí)例解(Cmax=11，Wm=10，Wt=93)

5.2 實(shí)驗(yàn)2

為證明該多目標(biāo)融合算法的時(shí)間有效性，測(cè)試算例選取Brandimarte設(shè)計(jì)的mk01-mk10數(shù)據(jù)；在改進(jìn)的快速非支配排序GA算法基礎(chǔ)上，對(duì)GA、GA+SARSA、GA+Q-Learning和本文中融合算法進(jìn)行執(zhí)行時(shí)間對(duì)比，以及mk06算例交叉和變異數(shù)量對(duì)比.

每組算例均仿真實(shí)驗(yàn)運(yùn)行30次，執(zhí)行時(shí)間取平均值，測(cè)試結(jié)果如表3所示，在每組算例上提出的融合算法的執(zhí)行平均時(shí)間都最小.mk06算例仿真實(shí)驗(yàn)運(yùn)行30次，交叉數(shù)量和變異數(shù)量取平均值，測(cè)試結(jié)果如表4所示；第2行和第3行中所提融合算法的交叉數(shù)和變異數(shù)均最少；第4行和第5行表示所提算法相對(duì)于其他3種算法的縮減百分比.

表3 Brandimarte的10個(gè)算例執(zhí)行時(shí)間對(duì)比

表4 交叉和變異平均數(shù)量對(duì)比

所提融合算法保證解的質(zhì)量的同時(shí)，通過(guò)增強(qiáng)學(xué)習(xí)，GA減少了冗余的交叉和變異操作；通過(guò)統(tǒng)計(jì)分析驗(yàn)證了該融合算法的時(shí)間有效性.

6 結(jié) 論

實(shí)驗(yàn)1證明融合算法尋找多目標(biāo)最優(yōu)解的準(zhǔn)確性，實(shí)驗(yàn)2證明融合算法求解多目標(biāo)FJSP問(wèn)題的時(shí)間高效性，為求解多目標(biāo)柔性車(chē)間調(diào)度問(wèn)題提供一條有效途徑.

在實(shí)際車(chē)間生產(chǎn)復(fù)雜場(chǎng)景下解決FJSP問(wèn)題，GA算法的Pc和Pm直接影響算法效率，如果值太大，較優(yōu)解容易丟失，如果它們值太小，影響種群多樣性.本文提出的融合調(diào)度算法，提升智能生產(chǎn)中決策活動(dòng)的自適應(yīng)性、動(dòng)態(tài)調(diào)度的可操作性.

針對(duì)碳中和節(jié)能為目標(biāo)的柔性作業(yè)車(chē)間調(diào)度實(shí)際生產(chǎn)環(huán)境中，單純依靠智能算法并不能有效、快速解決所有機(jī)器故障柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題[26].下一步研究重點(diǎn)：在本融合算法基礎(chǔ)上研究基于人機(jī)協(xié)同的多目標(biāo)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題.