應(yīng)用強化學(xué)習(xí)算法求解置換流水車間調(diào)度問題①

張東陽,葉春明

(上海理工大學(xué) 管理學(xué)院,上海 200093)

1 引言

排序問題是生產(chǎn)系統(tǒng)和服務(wù)系統(tǒng)中的一類典型問題,它作為傳統(tǒng)問題和熱點問題,至今一直有眾多學(xué)者研究.根據(jù)工件的不同加工特點,排序問題可分為流水作業(yè)排序(flow-shop scheduling)、自由作業(yè)排序(openshop scheduling)和異序作業(yè)排序(job-shop scheduling)[1],其中Flow-shop排序又可分為同順序和任意序兩大類,同順序Flow-shop排序問題又稱置換流水車間調(diào)度問題(Permutation Flow Shop Problem,PFSP).相關(guān)理論證明,3臺機器以上的PFSP即為NP難題[2],至今還未發(fā)現(xiàn)具有多項式時間的優(yōu)化算法.

目前,解決這類問題有效方法主要包括：精確算法,啟發(fā)式算法,智能優(yōu)化算法.如枚舉法、分支定界法等精確算法只對小規(guī)模問題的求解有著很好的效果.如Gupta法、RA法和NEH法等啟發(fā)式算法可以求解快速構(gòu)造問題的解,但是解的質(zhì)量較差[3].近年來,遺傳算法[4]、人工神經(jīng)網(wǎng)絡(luò)[5]、蟻群算法[6]、粒子群算法[7],煙花算法[8]、進化算法[9]等智能優(yōu)化算法因能在合理的時間內(nèi)獲得較優(yōu)解,受到了眾多學(xué)者的廣泛研究,并已經(jīng)成為解決該類問題的重要方法.

近年來,隨著技術(shù)的進步,機器學(xué)習(xí)領(lǐng)域里一個古老又嶄新的理論——強化學(xué)習(xí)[10,11],又得到了科研人員的廣泛重視.但目前強化學(xué)習(xí)主要應(yīng)用在游戲比賽、控制系統(tǒng)和機器人等領(lǐng)域[12-14],應(yīng)用在生產(chǎn)調(diào)度中的并不多.Wang等學(xué)者將Q-學(xué)習(xí)算法應(yīng)用到單機作業(yè)排序問題上,發(fā)現(xiàn)智能體經(jīng)過學(xué)習(xí)能夠從給定的規(guī)則中選出較好的規(guī)則,證明了將強化學(xué)習(xí)應(yīng)用到生產(chǎn)調(diào)度的可能性和有效性[15,16].Zhang等學(xué)者利用多智能協(xié)作機制解決了非置換流水車間調(diào)度問題[17],國內(nèi)的潘燕春等學(xué)者將Q-學(xué)習(xí)算法與遺傳算法有機的結(jié)合起來,在作業(yè)車間調(diào)度取得較好的效果[18,19].王超等學(xué)者提出了改進的Q-學(xué)習(xí)算法運用于動態(tài)車間調(diào)度,構(gòu)建了一系列符合強化學(xué)習(xí)標(biāo)準(zhǔn)的規(guī)則[20].可以看到,過往的文獻(xiàn)里面強化學(xué)習(xí)應(yīng)用在調(diào)度上大部分是多智能體協(xié)作,或者與其它算法結(jié)合去解決調(diào)度問題.因此,本文用單智能體的強化學(xué)習(xí)來解決置換流水車間調(diào)度問題,合理的將狀態(tài)定義為作業(yè)序列,將動作定義為機器前可選加工的工件,來適應(yīng)強化學(xué)習(xí)方法.智能體通過與環(huán)境不斷交互,學(xué)習(xí)一個動作值函數(shù),該函數(shù)給出智能體在每個狀態(tài)下執(zhí)行不同動作帶來的獎賞,伴隨函數(shù)值更新,進而影響到行為選擇策略,從而找到最小化最大完工時的狀態(tài)序列.最后用該算法對OR-Library提供Flow-shop國際標(biāo)準(zhǔn)算例進行仿真實驗分析,最終的實驗結(jié)果驗證了算法的有效性.

2 置換流水車間調(diào)度問題描述

置換流水車間調(diào)度可以描述為[21,22]：n個工件要在m個機器上加工,每個工件的加工順序相同,每一臺機器加工的工件的順序也相同,各工件在各機器上的加工時間已知,要求找到一個加工方案使得調(diào)度的目標(biāo)最優(yōu).本文選取最小化最大加工時間為目標(biāo)的調(diào)度問題.對該問題常作出以下假設(shè)：

1)一個工件在同一時刻只能在一臺機器上工；

2)一臺機器在同一時刻智能加工一個工件；

3)工件一旦在機器上加工就不能停止；

4)每臺機器上的工件加工順序相同.

問題的數(shù)學(xué)描述如下,假設(shè)各工件按機器1到m的順序加工,令 π ={π1,π2,···,πn}為所有工件的一個排序.pij為工件i在機器上j的加工時間,不考慮所有工件準(zhǔn)備時間,C(πi,j)為工件 πi在機器j上加工完成時間.

其中,式(1)中的i=2,···,n；j=2,···,n,式(2)為最大完工時間.

3 強化學(xué)習(xí)理論

強化學(xué)習(xí)是人工智能領(lǐng)域中機器學(xué)習(xí)的關(guān)鍵技術(shù),不同于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí),主要特點在于與環(huán)境交互,具有很強的自適應(yīng)能力,具有實時學(xué)習(xí)的能力.強化學(xué)習(xí)的目標(biāo)是在與環(huán)境的試探性交互中學(xué)習(xí)行為策略,來獲取最大的長期獎賞[23].圖1描述了強化學(xué)習(xí)的過程,強化學(xué)習(xí)最主要的是兩個主體,分別為智能體和智能體所處的環(huán)境,環(huán)境意味著多樣的復(fù)雜狀態(tài),所有的狀態(tài)可以看成一個集合S.當(dāng)智能體接受到t時刻的狀態(tài)st(st∈S)以及從上一個狀態(tài)st-1轉(zhuǎn)變成st所得到的瞬時獎勵rt,智能體從可選的行為集合A中選取一個動作at來執(zhí)行,這樣環(huán)境狀態(tài)就轉(zhuǎn)移為st+1,同時智能體接受來自于環(huán)境狀態(tài)改變瞬時獎勵rt+1和t+ 1時刻的狀態(tài)st+1,根據(jù)從中學(xué)習(xí)到的經(jīng)驗,來決策t+ 1時刻的動作at+1.按此循環(huán),智能通過不斷與環(huán)境交互,根據(jù)學(xué)習(xí)到的策略,不斷嘗試并調(diào)整自身的行為,來獲取最大的長期獎賞.

圖1 強化學(xué)習(xí)模型

強化學(xué)習(xí)的算法可以分為2類,一類是基于模型已知的動態(tài)規(guī)劃法,一類是基于模型未知的算法如蒙特卡洛算法、Q-Learning算法、TD算法等.本文采用的Q-Learning算法來解決問題.算法的核心是一個簡單的值迭代更新,每個狀態(tài)動作對都有一個Q值關(guān)聯(lián),當(dāng)智能體處在t時刻的狀態(tài)st選擇操作at時,該狀態(tài)動作對的Q值將根據(jù)選擇該操作時收到的獎勵和后續(xù)狀態(tài)的最佳Q值進行更新.狀態(tài)操作對的更新規(guī)則如下：

式(3)中,表示學(xué)習(xí)率,學(xué)習(xí)率越大,表明立即獎賞和未來獎賞對當(dāng)前的影響較大,智能體越能看到未來的結(jié)果,但收斂速度會比較慢,表示折扣因子,代表決策者對得到的獎賞的偏好,折扣因子越大,智能體越有遠(yuǎn)見,即考慮當(dāng)前的選擇對未來的結(jié)果造成的影響.已經(jīng)證明,在馬爾科夫決策過程中,在某些限制條件下,QL能夠收斂到最優(yōu)值[24].QL算法更新過程如算法1所示.

算法1.QL算法初始化Q值for each episode：初始化狀態(tài)s for each episode step：在t時刻下狀態(tài) 的所有可能行為中選取一個行為images/BZ_201_511_1487_536_1512.png images/BZ_201_1002_1487_1027_1512.png執(zhí)行動作,得到下一狀態(tài)images/BZ_201_660_1531_710_1565.png和獎賞值更新Q值：[()]images/BZ_201_418_1540_443_1565.png images/BZ_201_843_1540_864_1565.pngimages/BZ_201_366_1649_1108_1699.pngimages/BZ_201_285_1720_385_1745.pngend for end for

算法中的智能體有2種不同動作選擇策略：探索和利用,而 ε-貪心行動值法是智能體選擇動作的常用的策略,以較大概率(1 -ε)選擇完全貪婪行動,以較小概率(貪婪率)ε隨機選擇行動[10].ε越小越重于利用,即利用現(xiàn)有的學(xué)習(xí)成果來選取行動,ε越大越重于探索,即隨機選取行動.

4 Q-Learning在PFSP上的應(yīng)用

利用強化學(xué)習(xí)解決PFSP問題,最重要是如何將問題映射到強化學(xué)習(xí)模型中,并利用相關(guān)算法來得到優(yōu)化的策略結(jié)果.本文構(gòu)建了環(huán)境中的狀態(tài)集,動作和反饋函數(shù),并采用QL算法來進行優(yōu)化.

定義1.狀態(tài)集.將n×m的PFSP問題中m個機器中的第一個機器當(dāng)作智能體,將第一臺機器前的未加工的工件作為環(huán)(境狀)態(tài).根據(jù)文獻(xiàn)[25],智能體的狀態(tài)可以設(shè)定為Si=Ari,每個智能體(i)都有|Si|=2n(n表示工件數(shù))狀態(tài).在我們的案例中只有一個智能體,因此,所有狀態(tài)的集合為 |S|=2n,表示為S={s1,s2,···,sn2}.

定義2.動作集.將智能體前可以選擇加工的工件作為可選的動作.因此,在我們的案例中可選擇的動作集為A={a1,a2,···,an}.

定義3.反饋函數(shù).我們選取最小化最大完工時間作為獎勵信號,最小化最大完工時間越小,獎勵值越大,意味著選取的動作也好,函數(shù)表示如下：

根據(jù)上述的定義,將PFSP問題映射到QL算法中,具體描述如算法2所示.

算法2.QL解決PFSP問題算法初始化：Q(s,a)={}Best={}for each episode step：初始化狀態(tài)s={}while not finished(所有工件)：初始化所有動作值根據(jù)狀態(tài)s利用貪心行動值法來選擇動作執(zhí)行動作,得到下一個狀態(tài)st+1和獎賞值r(1/makespan)更新Q(s,a)[()]images/BZ_201_1439_1684_2180_1734.pngimages/BZ_201_1365_1755_1457_1780.pngimages/BZ_201_1357_1909_1457_1934.pngend while if makespan(s)< makespan(Best)：end for

5 實驗結(jié)果分析

為驗證QL算法解決置換流水車間問題的性能,選擇OR-Library中Carl類例題,21個Reeves例題來進行測試,將實驗結(jié)果與一些算法進行比較.算法程序用Python3.0編寫,運行環(huán)境為Windows 7 64位系統(tǒng),處理器為2.60 GHz,4 GB內(nèi)存.經(jīng)過初步實驗,分析了不同學(xué)習(xí)參數(shù)對學(xué)習(xí)的影響,最后確定了相關(guān)參數(shù),迭代次數(shù)為5000,學(xué)習(xí)率為0.1,折扣因子為0.8,貪婪率為0.2.以相對誤差率RE=(C-C*)/C*×100%,平均誤差率ARE=(Ca-C*)/C*×100%和最優(yōu)誤差率BRE=(Cbest-C*)/C*×100%為比較標(biāo)準(zhǔn),每個例題運行20次.其中C為算法運行的結(jié)果,C*為算列的最優(yōu)值.Ca,Cbest分別為所求解的平均值和最優(yōu)值.

選擇Car類例題與文獻(xiàn)[25]提到的螢火蟲算法(FA)、粒子群算法(PSO)、啟發(fā)式算法NEH來進行比較.從表1和圖2中我們可以看出,QL算法在Car類算例中基本能找到最優(yōu)值,與PSO,FA等智能算法尋優(yōu)效果上相差不大,而啟發(fā)式算法NEH求解算例最優(yōu)的效果一般,只適用于對精度要求不高的場合.在算例的平均誤差上,QL算法求解質(zhì)量優(yōu)于PSO算法,和FA算法不相上下,展現(xiàn)了QL算法的良好穩(wěn)定性.說明QL算法對置換流水車間調(diào)度問題有較好的尋優(yōu)能力.

表1 Car類問題測試結(jié)果

圖2 平均值比較

選取算例Car4算例來分析QL算法的收斂能力,從圖3中發(fā)現(xiàn)QL算法剛開始下降較快,在中間一段時間內(nèi)雖然兩次陷入了局部最優(yōu)值,但最后都成功跳出了局部最優(yōu),達(dá)到最優(yōu)值.

圖3 算例Car4最優(yōu)值下降曲線圖

表2給出了QL算法對Reeves例題(Rec37、Rec39、Rec41 3個算例的值不是最優(yōu)值,而是最優(yōu)上界).測試結(jié)果,并與PSO[25],GA[26]等知名算法比較,QL算法的平均最優(yōu)值最小,表明整體上QL算法的尋優(yōu)能力比GA和PSO算法都好.

表2 Reeves例題BRE測試結(jié)果

6 結(jié)束語

面對日益增長的大規(guī)模調(diào)度問題,開發(fā)新型算法越來越重要.本文提出了基于QL算法解決置換流水車間調(diào)度問題的算法,通過對Car算例和Reeves算例等基準(zhǔn)問題進行測試并與已有的算法進行比較,評價了該算法的有效性.結(jié)果表明,該方法是解決置換流水車間調(diào)度問題的一種有效的方法.