程 瑋,張亞輝,曹先鋒,金增志,胡小鋒+

(1.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院,上海 200240;2.上海交通大學(xué) 海洋裝備研究院,上海 200240;3.中國(guó)重汽集團(tuán) 工藝研究院,山東 濟(jì)南 250100)

0 引言

裝配線是車間流水生產(chǎn)的一種常見(jiàn)方式,常用于汽車、家電等大批量生產(chǎn)[1]。雙邊裝配線相對(duì)于傳統(tǒng)單邊作業(yè)的裝配線,擁有長(zhǎng)度短、設(shè)備利用率高、物料搬運(yùn)成本低等一系列優(yōu)點(diǎn),在裝載機(jī)、卡車、汽車等較大型機(jī)械產(chǎn)品裝配車間得到了廣泛應(yīng)用[1]。

裝配線平衡問(wèn)題即在滿足一定約束條件下(生產(chǎn)工藝約束和節(jié)拍時(shí)間約束等),將一組裝配任務(wù)盡可能均勻地分配到各個(gè)工位上,其追求一個(gè)或多個(gè)目標(biāo)優(yōu)化,屬于NP hard組合優(yōu)化問(wèn)題,同樣雙邊裝配線平衡問(wèn)題也屬于NP hard組合優(yōu)化問(wèn)題[1]。通常,根據(jù)優(yōu)化目標(biāo)的不同,雙邊裝配線平衡問(wèn)題分為兩類,第一類問(wèn)題為給定節(jié)拍,最小化工作站數(shù)量,第二類問(wèn)題為給定工作站數(shù)量,最小化節(jié)拍[2]。

自BARTHOLD[3]首次提出雙邊裝配線平衡問(wèn)題以來(lái),眾多研究人員對(duì)該問(wèn)題展開了深入研究。針對(duì)第一類問(wèn)題,KIM等[4]提出一種基于“工位”編碼方式的遺傳算法;LEE等[5]提出一種基于最大集規(guī)則的任務(wù)歸組分配法,提高了裝配任務(wù)之間的操作連續(xù)性;BAYKASOGLU等[6]設(shè)計(jì)了一種蟻群算法求解考慮區(qū)域約束的第一類問(wèn)題;?ZCAN等[7]采用禁忌搜索算法求解,同時(shí)考慮裝配線效率和平滑度兩個(gè)優(yōu)化目標(biāo),并通過(guò)非線性組合將其轉(zhuǎn)換為易于求解的單目標(biāo)問(wèn)題;KHORASANIAN等[8]采用模擬退火算法求解,得到了較好的解;YUAN等[9]設(shè)計(jì)了一種延遲接受爬山算法,考慮雙邊裝配線問(wèn)題額外約束,并與常見(jiàn)算法進(jìn)行比較,驗(yàn)證其有效性;李大雙等[10]將殖民競(jìng)爭(zhēng)算法與延遲接受爬山算法結(jié)合,提出一種新型混合殖民競(jìng)爭(zhēng)算法,通過(guò)多個(gè)算例測(cè)試驗(yàn)證了算法的合理性;LI等[11]基于改進(jìn)的NEH(Nawaz-Enscore-Ham)啟發(fā)式規(guī)則獲得高質(zhì)量的初始解,設(shè)計(jì)了一種改進(jìn)的迭代貪婪算法,并與多種元啟發(fā)式算法比較證明其優(yōu)越性;LI等[12]提出一種分支界定記憶算法,將通過(guò)改進(jìn)霍夫曼啟發(fā)式規(guī)則獲得高質(zhì)量的初始解作為上界,并在標(biāo)準(zhǔn)案列上測(cè)試其有效性。

綜上所述,第一類平衡問(wèn)題的求解算法主要有啟發(fā)式算法、精確算法和元啟發(fā)式算法三大類。啟發(fā)式算法雖然求解速度快、簡(jiǎn)潔高效,但是求解結(jié)果不能達(dá)到全局最優(yōu);精確算法能夠得到最優(yōu)解,但是求解速度慢;元啟發(fā)式算法的迭代搜索過(guò)程通常比較耗時(shí),每個(gè)問(wèn)題案例需要重新迭代求解。這些傳統(tǒng)優(yōu)化算法很少利用歷史信息來(lái)調(diào)整行為,不能有效利用歷史求解經(jīng)驗(yàn)進(jìn)行學(xué)習(xí),許多算法在大規(guī)模問(wèn)題上仍有很大提升空間。

目前,利用深度強(qiáng)化學(xué)習(xí)算法求解組合優(yōu)化問(wèn)題已有一些初步的成果,包括旅行商問(wèn)題、凸包問(wèn)題、最大割問(wèn)題、點(diǎn)集匹配、車間調(diào)度問(wèn)題等[13],這些研究通常將求解組合優(yōu)化問(wèn)題轉(zhuǎn)化為馬爾科夫決策過(guò)程(Markov Decision Process,MDP),狀態(tài)s描述問(wèn)題狀態(tài),強(qiáng)化學(xué)習(xí)智能體(Agent)觀察狀態(tài)s,并做出決策a,環(huán)境采用決策a更新狀態(tài),并再將獎(jiǎng)勵(lì)r反饋給智能體,通過(guò)與環(huán)境交互獲取決策經(jīng)驗(yàn)來(lái)更新模型,在最大化獎(jiǎng)勵(lì)的同時(shí)最優(yōu)化決策策略。

本文提出一種基于近端策略優(yōu)化(Proximal Policy Optimization,PPO)的深度強(qiáng)化學(xué)習(xí)算法求解雙邊裝配線第一類平衡問(wèn)題,該算法充分利用深度強(qiáng)化學(xué)習(xí)從歷史求解經(jīng)驗(yàn)中進(jìn)行學(xué)習(xí),不斷更新任務(wù)分配策略的特性,訓(xùn)練得到的模型可以直接用于求解其他具有相似組合優(yōu)化結(jié)構(gòu)的問(wèn)題。PPO算法[14]是OpenAI在2017年提出的一種基于策略的深度強(qiáng)化學(xué)習(xí)算法,其獨(dú)有的損失函數(shù)裁剪機(jī)制使得該算法學(xué)習(xí)穩(wěn)定性更強(qiáng),在交通、機(jī)器人、車間調(diào)度等智能控制領(lǐng)域得到應(yīng)用,且明顯優(yōu)于策略梯度(Policy Gradient,PG)[15]、信任區(qū)域策略優(yōu)化(Trust Region Policy Optimization,TRPO)[16]、優(yōu)勢(shì)動(dòng)作評(píng)論(Advantage Actor Critic,A2C)[17]等深度強(qiáng)化學(xué)習(xí)算法。同時(shí),考慮到雙邊裝配線第一類平衡問(wèn)題求解過(guò)程中狀態(tài)的復(fù)雜性和多變性,采用獨(dú)熱編碼將其轉(zhuǎn)換為狀態(tài)矩陣并引入卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks, CNN),構(gòu)建了高效的CNN-PPO(proximal policy optimization with convolutional neural networks)算法求解雙邊裝配線第一類平衡問(wèn)題。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

雙邊裝配線的構(gòu)造如圖1所示,其具有左右兩條裝配線,能在兩側(cè)并行完成同一產(chǎn)品的不同工藝,裝配線每個(gè)工作站又分為左右兩個(gè)相互獨(dú)立的工作區(qū),即左右兩個(gè)工位,例如圖中工作站2包括工位3和工位4,這兩個(gè)左右對(duì)稱的工位稱作伴隨工位,又稱作配對(duì)工位[9]。

雙邊裝配線的任務(wù)操作方位有左邊(L)、右邊(R)和雙邊(E)3種。圖2a所示為P16問(wèn)題的任務(wù)先序圖,圖中圓圈內(nèi)的數(shù)字表示任務(wù)的序列號(hào),括號(hào)中的數(shù)字表示該任務(wù)的作業(yè)時(shí)間,字母表示該任務(wù)的操作方位,箭頭表示任務(wù)之間的執(zhí)行順序關(guān)系。

雙邊裝配線任務(wù)分配需要考慮如下約束:

(1)先序約束 任務(wù)分配必須遵守任務(wù)之間的執(zhí)行順序關(guān)系。

(2)節(jié)拍約束 一個(gè)工位內(nèi)所有任務(wù)的作業(yè)時(shí)間之和應(yīng)該小于等于該工位的節(jié)拍時(shí)間。

(3)操作方位約束 任務(wù)只能分配到對(duì)應(yīng)的操作邊。

(4)序列相關(guān)約束 雙邊裝配線上的任務(wù)可以同時(shí)串行、并行作業(yè),導(dǎo)致任務(wù)在分配過(guò)程中除了考慮在其所分配工位上前一個(gè)任務(wù)的影響,還要考慮分配在伴隨工位上的先、后序任務(wù)的影響。

圖2b中,工作站1～工作站3表示該方案共開啟3個(gè)工作站,L和R分別表示左工位和右工位;矩形內(nèi)的數(shù)字表示任務(wù)的序列號(hào),數(shù)字的先后順序表示任務(wù)在該工位的執(zhí)行順序;矩形上的數(shù)字表示任務(wù)在該工位的開始和結(jié)束作業(yè)時(shí)間,數(shù)字的最大值表示該工位的作業(yè)完工時(shí)間;矩形內(nèi)的黑色區(qū)域表示無(wú)任務(wù)分配。例如,工作站1的左工位分配任務(wù)為1,3,4,任務(wù)1的開始作業(yè)時(shí)間為0,結(jié)束作業(yè)時(shí)間為6,任務(wù)4的開始作業(yè)時(shí)間為6,結(jié)束作業(yè)時(shí)間為15,任務(wù)3的開始作業(yè)時(shí)間為15,結(jié)束作業(yè)時(shí)間為17,滿足先序約束,而且該工位作業(yè)完工時(shí)間為17,小于節(jié)拍18,滿足節(jié)拍約束。根據(jù)圖2a,任務(wù)7可以分配在左工位或右工位,任務(wù)9只能分配在右工位,且執(zhí)行順序位于任務(wù)7之后;圖2b中,任務(wù)7分配在工作站2左工位,任務(wù)9分配在工作站2右工位,滿足操作方位約束,而且任務(wù)9的開始作業(yè)時(shí)間等于任務(wù)7的結(jié)束作業(yè)時(shí)間,同時(shí)滿足先序約束和序列相關(guān)約束。

1.2 數(shù)學(xué)模型

本文涉及的參數(shù)說(shuō)明如下:

(1)基本參數(shù)

Ns為雙邊裝配線工作站數(shù)量;

I為任務(wù)集,I={1,2,…,i,…,m};

J為工作站集,J={1,2,…,j,…,n};

(j,k)表示工作站j上方位指示為k的工位,k=1表示工作站的左工位,k=2表示工作站的右工位;

AL為只能在左工位執(zhí)行的任務(wù)集,AL?I;

AR為只能在右工位執(zhí)行的任務(wù)集,AR?I;

AE表示在左或右工位均可執(zhí)行的任務(wù)集,AE?I;

P(i)為任務(wù)i的緊鄰先序任務(wù)集;

Pa(i)為任務(wù)i的先序任務(wù)集;

S(i)為任務(wù)i的緊鄰后續(xù)任務(wù)集;

Sa(i)為任務(wù)i的后序任務(wù)集;

Pc為沒(méi)有緊鄰先序約束關(guān)系的任務(wù)集;

ct表示節(jié)拍;

μ為一個(gè)較大的常數(shù)。

C(i)為與任務(wù)i操作方位相反的任務(wù)集,其中C(i)=AL,i∈AR,C(i)=AR,i∈AL,C(i)=Φ,i∈AE;

K(i)為任務(wù)i操作方位指示符號(hào)集,其中K(i)={1},i∈AL,K(i)={2},i∈AR,K(i)={1,2},i∈AE。

(2)決策變量

xijk={0,1},如果任務(wù)i分配到工作站(j,k),則xijk=1,否則xijk=0。

(3)指示變量

zip={0,1},在同工作站上,如果任務(wù)i在任務(wù)p前,則zip=1,否則zip=0。

本文研究雙邊裝配線第一類平衡問(wèn)題,參考張亞輝[2]、李大雙[10]等的研究成果,數(shù)學(xué)模型如下:

minns。

(1)

(2)

(3)

tf≥ti,?i∈I;

(4)

(5)

(6)

(7)

(8)

xij1={0,1},i∈AL,j∈J;

(9)

xij2={0,1},i∈AR,j∈J;

(10)

xijk={0,1},i∈AE,j∈J;

(11)

zip=0或1,?i∈I,
p∈{r|r∈I-(Pa(i)∪Sa(i)∪C(i)),ir}。

(12)

其中:式(1)表示優(yōu)化目標(biāo),即最小化工作站數(shù)量;式(2)表示每一個(gè)任務(wù)只能分配到一個(gè)工位;式(3)和式(4)表示每個(gè)任務(wù)的完工時(shí)間必須小于節(jié)拍,確保節(jié)拍約束;式(5)對(duì)應(yīng)先序約束;式(6)～式(8)表示序列相關(guān)約束;式(9)～式(12)定義各個(gè)變量。

2 CNN-PPO算法求解雙邊裝配線第一類平衡問(wèn)題

CNN-PPO算法求解雙邊裝配線第一類平衡問(wèn)題的過(guò)程如圖3所示。CNN-PPO強(qiáng)化學(xué)習(xí)智能體觀察雙邊裝配線環(huán)境狀態(tài)st,采取任務(wù)分配決策at,環(huán)境完成任務(wù)at分配,并將獎(jiǎng)勵(lì)rt反饋給智能體,智能體通過(guò)與環(huán)境不斷交互求解第一類平衡問(wèn)題,同時(shí)獲取任務(wù)分配求解經(jīng)驗(yàn),以數(shù)據(jù)驅(qū)動(dòng)的方法學(xué)習(xí)經(jīng)驗(yàn),更新模型,通過(guò)反復(fù)試錯(cuò)獲取更高的獎(jiǎng)勵(lì)值,在最大化累積獎(jiǎng)勵(lì)的同時(shí)最優(yōu)化任務(wù)分配策略。

2.1 CNN-PPO強(qiáng)化學(xué)習(xí)智能體

CNN-PPO強(qiáng)化學(xué)習(xí)智能體采用類似PPO的執(zhí)行—評(píng)價(jià)(Actor-Critic)結(jié)構(gòu)類型。其中Actor策略網(wǎng)絡(luò)根據(jù)雙邊裝配線環(huán)境狀態(tài)st做出任務(wù)分配決策at,Critic評(píng)價(jià)網(wǎng)絡(luò)對(duì)任務(wù)分配決策at的優(yōu)劣進(jìn)行評(píng)價(jià)。

Actor策略網(wǎng)絡(luò)用參數(shù)為θ的CNN逼近最優(yōu)的任務(wù)分配策略pθ(at|st),網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示,包括兩層卷積網(wǎng)絡(luò)、三層全連接網(wǎng)絡(luò)。圖中,維度M×N的狀態(tài)矩陣是網(wǎng)絡(luò)在時(shí)刻t的輸入,對(duì)應(yīng)雙邊裝配線環(huán)境狀態(tài)st,M為狀態(tài)特征數(shù)量,N為任務(wù)數(shù)量;pθ(at|st)為時(shí)刻tActor策略網(wǎng)絡(luò)的輸出,指Actor策略網(wǎng)絡(luò)在雙邊裝配線環(huán)境狀態(tài)st下輸出任務(wù)分配決策at的概率。

Critic評(píng)價(jià)網(wǎng)絡(luò)用參數(shù)為ψ的CNN逼近最優(yōu)的策略評(píng)價(jià)值vψ(st|at)。本文Critic策略網(wǎng)絡(luò)結(jié)構(gòu)前幾層和Actor網(wǎng)絡(luò)結(jié)構(gòu)相同,只是最后一層為線性回歸層,即vψ(st|at)=f(h(t);ψ)=ω×h(t)+b替代Actor網(wǎng)絡(luò)中的SoftMax層,其中vψ(st|at)為t時(shí)刻Critic評(píng)價(jià)網(wǎng)絡(luò)輸出的策略評(píng)價(jià)值,h(t)為上一層的輸出,ψ為網(wǎng)絡(luò)內(nèi)部單元節(jié)點(diǎn)的參數(shù),包括權(quán)重ω和偏置項(xiàng)b。

2.2 雙邊裝配線狀態(tài)

狀態(tài)的定義應(yīng)與雙邊裝配線平衡問(wèn)題特征緊密相關(guān)。2016年,張智聰?shù)萚18]對(duì)強(qiáng)化學(xué)習(xí)在調(diào)度問(wèn)題的狀態(tài)選擇提出以下準(zhǔn)則:

(1)調(diào)度環(huán)境的主要特點(diǎn)和變化能夠通過(guò)狀態(tài)特征描述,包括調(diào)度系統(tǒng)的全局特征和局部特征。

(2)可以通過(guò)一個(gè)通用特征集表示所有問(wèn)題的所有狀態(tài)。

(3)狀態(tài)特征可以用來(lái)表示和概括各種不同調(diào)度問(wèn)題的狀態(tài)。

(4)狀態(tài)特征是調(diào)度問(wèn)題狀態(tài)變量的數(shù)值表征。

(5)狀態(tài)特征應(yīng)易于計(jì)算。

結(jié)合肖鵬飛對(duì)非置換流水車間調(diào)度問(wèn)題提出的狀態(tài)特征[19],本文針對(duì)雙邊裝配線平衡問(wèn)題提出雙邊裝配線狀態(tài)特征,如表1所示。

表1 雙邊裝配線狀態(tài)特征

續(xù)表1

其中,狀態(tài)特征1～5的特征值為相應(yīng)的任務(wù)序列號(hào),狀態(tài)特征6～14反映雙邊裝配線的整體特征,特別地,對(duì)狀態(tài)特征11～14進(jìn)行取整處理。假設(shè),某雙邊裝配線任務(wù)數(shù)量為N,對(duì)表1中的狀態(tài)特征進(jìn)行獨(dú)熱編碼處理,得到該雙邊裝配線環(huán)境狀態(tài)矩陣st,其維度為14×N。若序號(hào)為i的狀態(tài)特征的特征值j≠0,則矩陣st第i行第j列的值為1,第i行其他列的值均為0;若狀態(tài)特征i的特征值j大于矩陣列數(shù),則取j的值為矩陣列數(shù)。

以P16問(wèn)題為例,由圖2a可知,在求解初始,裝配線開啟左工位,可分配的無(wú)先序任務(wù)集合為{1,2},對(duì)應(yīng)的作業(yè)時(shí)間為{6,5},因此表1中,第1個(gè)狀態(tài)特征PTime的特征值為1,其他狀態(tài)特征可同理依次求得,如表2第3列所示,經(jīng)過(guò)獨(dú)熱編碼處理得到的狀態(tài)矩陣s1如圖5a所示。隨后,CNN-PPO強(qiáng)化學(xué)習(xí)智能體觀察狀態(tài)矩陣s1,做出任務(wù)分配決策,若輸出待分配任務(wù)1,并按下文裝配線環(huán)境任務(wù)分配邏輯分配任務(wù)1(詳見(jiàn)2.4節(jié)任務(wù)分配),則裝配線開啟右工位。考慮操作方位約束和序列相關(guān)約束,可分配的無(wú)先序任務(wù)集合變?yōu)閧2},對(duì)應(yīng)的作業(yè)時(shí)間為{5},因此PTime的狀態(tài)特征值變?yōu)?,其他狀態(tài)特征的參數(shù)相應(yīng)發(fā)生變化,如表2第4列所示,經(jīng)過(guò)獨(dú)熱編碼處理得到狀態(tài)矩陣s2如圖5b的狀態(tài)矩陣所示。

表2 P16問(wèn)題狀態(tài)特征值變化

2.3 任務(wù)決策

CNN-PPO強(qiáng)化學(xué)習(xí)智能體根據(jù)雙邊裝配線狀態(tài)矩陣st輸出pθ(at|st),并按概率分布采樣,獲得待分配任務(wù)at。然而,因?yàn)殡p邊裝配線第一類平衡問(wèn)題具有先序、操作方位、序列相關(guān)等約束,如果直接按概率分布采樣,獲得待分配任務(wù)at,則會(huì)出現(xiàn)算法難以收斂、陷入局部最優(yōu)等問(wèn)題,所以本文引入標(biāo)記層(mask)來(lái)保證滿足先序、操作方位、序列相關(guān)約束的任務(wù)能被采取,以充分利用智能體從經(jīng)驗(yàn)中進(jìn)行學(xué)習(xí)的能力。

以P16問(wèn)題為例,Actor策略網(wǎng)絡(luò)參數(shù)θ采用正交初始化,在雙邊裝配線環(huán)境初始狀態(tài)矩陣s1下,輸出的pθ(a1|s1)如圖6上所示,若按概率分布采樣,則獲得待分配任務(wù)a1為3,不滿足先序約束。經(jīng)mask層標(biāo)記后如圖6下所示,只能在滿足約束的任務(wù)1和任務(wù)2中選擇,若按概率分布采樣,則獲得待分配任務(wù)a1為1。

2.4 任務(wù)分配

雙邊裝配線環(huán)境任務(wù)分配流程如圖7所示。

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

CNN-PPO強(qiáng)化學(xué)習(xí)智能體通過(guò)最大化累積獎(jiǎng)勵(lì)rsum,實(shí)現(xiàn)最優(yōu)的任務(wù)分配策略pθ(at|st),繼而實(shí)現(xiàn)優(yōu)化目標(biāo)最優(yōu)化。本文采用稀疏獎(jiǎng)勵(lì),即智能體與環(huán)境交互過(guò)程中獎(jiǎng)勵(lì)r1,r2,…,rn-1均為0,當(dāng)環(huán)境分配完所有N個(gè)任務(wù)后,給智能體反饋獎(jiǎng)勵(lì)rn,則累積獎(jiǎng)勵(lì)rsum=rn。若直接定義累積獎(jiǎng)勵(lì)為優(yōu)化目標(biāo)的負(fù)值,即rsum=rn=-ns,則環(huán)境給智能體反饋的信息太少,不利于智能體學(xué)習(xí),因此本文累積獎(jiǎng)勵(lì)不僅包括優(yōu)化目標(biāo),還包括該問(wèn)題其他能輔助優(yōu)化目標(biāo)優(yōu)化的子目標(biāo)。

對(duì)于雙邊裝配線第一類平衡問(wèn)題,優(yōu)化目標(biāo)是工作站數(shù)量ns,通常優(yōu)化工位數(shù)量nw能夠幫助優(yōu)化工作站數(shù)量ns,而且雙邊裝配線效率LE、平滑系數(shù)SI、完工時(shí)間平滑度CSI[2]能夠反映任務(wù)分配方案的優(yōu)劣,也能輔助優(yōu)化工作站數(shù)量,計(jì)算公式分別為:

(13)

(14)

(15)

式中:STi為工位i上所有任務(wù)作業(yè)時(shí)間的總和,STmax=max(STi)為其最大值;Ct(j,k)為工位(j,k)的作業(yè)完工時(shí)間,Ctmax=max(Ct(j,k))為其最大值。

考慮優(yōu)化目標(biāo)ns和子優(yōu)化目標(biāo)nw,LE,SI,CSI間的關(guān)系,本文首先采用線性規(guī)劃法進(jìn)行目標(biāo)轉(zhuǎn)化,以便高效獲得較優(yōu)的任務(wù)分配方案。參考文獻(xiàn)[20],合并轉(zhuǎn)化的函數(shù)方程式為

(16)

式中:wns和wnw為工作站數(shù)量ns和工位數(shù)量nw對(duì)應(yīng)的參數(shù),在雙邊裝配線中,一個(gè)工作站包括兩個(gè)工位,因此設(shè)置wns=1,wnw=2[14],le=100,而si的設(shè)置針對(duì)雙邊裝配線問(wèn)題規(guī)模的不同略有調(diào)整,即si為1(P24),25(P65),40(P148),300(P205),P9,P12,P16的si同樣取1,csi取值同si。

因此,取rsum=rn=-f。

2.6 模型更新

CNN-PPO強(qiáng)化學(xué)習(xí)智能體通過(guò)與雙邊裝配線環(huán)境不斷交互完成第一類平衡問(wèn)題求解,當(dāng)雙邊裝配線所有N個(gè)任務(wù)均完成分配時(shí),定義τ={s1,a1,r1,s2,a2,r2,…,st,at,rt,…,sn,an,rn}為智能體與環(huán)境的交互軌跡,即智能體求解過(guò)程獲取的經(jīng)驗(yàn)。智能體與環(huán)境繼續(xù)交互獲取大量求解經(jīng)驗(yàn),并將其儲(chǔ)存在經(jīng)驗(yàn)池,當(dāng)經(jīng)驗(yàn)池的儲(chǔ)存數(shù)量達(dá)到容量上限時(shí),交互過(guò)程暫停,將經(jīng)驗(yàn)池中的歷史求解經(jīng)驗(yàn)作為智能體Actor-Critic網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù),采用梯度下降法對(duì)網(wǎng)絡(luò)參數(shù)進(jìn)行更新,通過(guò)不斷迭代對(duì)智能體任務(wù)分配策略進(jìn)行優(yōu)化。其中,Actor網(wǎng)絡(luò)和Critic網(wǎng)絡(luò)的損失函數(shù)同PPO[14]。

算法1基于CNN-PPO的雙邊裝配線第一類平衡算法。

1:初始化Actor-Critic網(wǎng)絡(luò)參數(shù)θ,φ,初始化迭代最大回合數(shù)episode、經(jīng)驗(yàn)池容量buffersize、經(jīng)驗(yàn)池最大容量max buffer size、批量樣本大小batchsize

2:for each episode do:

3: t=1

4: 初始化雙邊裝配線環(huán)境,生成狀態(tài)st,清空經(jīng)驗(yàn)池

5: While buffer size

6: while雙邊裝配線所有任務(wù)沒(méi)有被分配完do:

7: 智能體觀察環(huán)境狀態(tài)st,根據(jù)策略pθ(at|st)決定待分配任務(wù)at

8: 環(huán)境分配任務(wù)at,反饋獎(jiǎng)勵(lì)rt

9: t=t+1

10: 更新環(huán)境狀態(tài)st

11: end while

12: 智能體將交互軌跡τ(求解經(jīng)驗(yàn))存入經(jīng)驗(yàn)池

13: end while

14: for epochin{1,2,…,buffer size/batch size} do:

15: 計(jì)算Actor策略網(wǎng)絡(luò)損失函數(shù)actor loss,Critic評(píng)價(jià)網(wǎng)絡(luò)損失函數(shù)critic loss

16: 更新Actor策略網(wǎng)絡(luò)pθ(at|st)

17: 更新Critic評(píng)價(jià)網(wǎng)絡(luò)vΨ(st|at)

18: end for

19: θold,φold←θ,Ψ

20:end for

3 實(shí)驗(yàn)驗(yàn)證

采用Python語(yǔ)言編程,環(huán)境為Python 3.6,在操作系統(tǒng)為Ubuntu 20.04 LTS、CPU頻率為2.90 GHz、內(nèi)存為16 G的計(jì)算機(jī)上運(yùn)行。以面向?qū)ο蟮男问酱罱穗p邊裝配線環(huán)境類,包括狀態(tài)更新、任務(wù)分配、獎(jiǎng)勵(lì)生成,并用Pytorch框架和Python編程語(yǔ)言搭建了CNN-PPO強(qiáng)化學(xué)習(xí)智能體。

本文用基準(zhǔn)問(wèn)題進(jìn)行算法測(cè)試,包括P9,P12,P16,P24,P65,P148,P205共7個(gè)問(wèn)題,59個(gè)案例,問(wèn)題數(shù)據(jù)同文獻(xiàn)[6]。

3.1 模型訓(xùn)練

在模型訓(xùn)練開始之前,本文算法的參數(shù)主要根據(jù)經(jīng)驗(yàn)值和智能體交互過(guò)程的實(shí)際數(shù)據(jù)設(shè)置,具體如表3所示。

表3 算法參數(shù)

完成算法參數(shù)設(shè)定后開始訓(xùn)練,在迭代過(guò)程中記錄智能體獲得的累積獎(jiǎng)勵(lì)、Actor策略網(wǎng)絡(luò)損失函數(shù)、Critic評(píng)價(jià)網(wǎng)絡(luò)損失函數(shù)的變化情況,并與PPO算法對(duì)比。PPO算法為5層全連接網(wǎng)絡(luò),其輸入為14×1的一維向量,14為狀態(tài)特征個(gè)數(shù),其輸出和CNN-PPO一樣都有mask層處理。

圖8所示為改進(jìn)前后的算法在P65、節(jié)拍CT=381案例上迭代訓(xùn)練過(guò)程的對(duì)比。

對(duì)比圖8a和圖8b可見(jiàn),隨著訓(xùn)練回合數(shù)的增加,增加CNN的CNN-PPO算法的累積獎(jiǎng)勵(lì)逐漸上升,而PPO算法一直在振蕩,收斂困難,CNN-PPO算法的優(yōu)化過(guò)程明顯好于PPO算法,其收斂過(guò)程更穩(wěn)定,優(yōu)化結(jié)果更好。說(shuō)明CNN的數(shù)據(jù)表征學(xué)習(xí)能力能夠有效提取雙邊裝配線狀態(tài)矩陣的數(shù)據(jù)特征,并能更快更好地完成任務(wù)分配。圖8c中PPO算法的Actor網(wǎng)絡(luò)損失曲線振蕩很厲害,收斂困難,而CNN-PPO算法的Actor網(wǎng)絡(luò)損失曲線隨著迭代次數(shù)的增加趨于收斂,策略趨于穩(wěn)定。圖8d中PPO算法的Critic網(wǎng)絡(luò)損失曲線始終變化不大,即策略評(píng)價(jià)變化不大,表明Actor策略網(wǎng)絡(luò)沒(méi)有收斂,策略變化不大,而CNN-PPO算法的Critic網(wǎng)絡(luò)損失曲線收斂過(guò)程更穩(wěn)定,效果更好,說(shuō)明CNN-PPO算法的優(yōu)化過(guò)程更好。

綜上所述,訓(xùn)練過(guò)程整體表明,相對(duì)于PPO算法,CNN-PPO算法的訓(xùn)練過(guò)程穩(wěn)定,求解能力更強(qiáng),更能滿足雙邊裝配線第一類平衡問(wèn)題求解的需求,驗(yàn)證了算法改進(jìn)的有效性。

3.2 模型驗(yàn)證

保存訓(xùn)練后的CNN-PPO模型,在P9,P12,P16,P24,P65,P148,P205問(wèn)題上求解,并將求解結(jié)果和現(xiàn)有5種較好的算法進(jìn)行對(duì)比,對(duì)比算法為禁忌搜索(Tabu Search ,TS)算法[7]、模擬退火(Simulated Annealing, SA)算法[8]、延遲接受爬山(Late Acceptance Hill-Climbing,LAHC)算法[9]、迭代貪婪(Iterated Greedy,IG)算法[11]、改進(jìn)霍夫曼(Modified Hoffman Heuristic,MHH)算法[12]、分支定界記憶(Branch,Bound and Remember,BBR)算法[12]。其中,TS,SA,LAHC,IG為元啟發(fā)式算法,MHH為啟發(fā)式算法,BBR為精確算法。因?yàn)槲墨I(xiàn)[11]中,IG算法設(shè)定的優(yōu)化目標(biāo)為工位數(shù)量而非工作站數(shù)量,所以此處IG算法的求解結(jié)果取自文獻(xiàn)[12],而文獻(xiàn)[12]的IG算法同文獻(xiàn)[11],文獻(xiàn)[12]中已做說(shuō)明。本文算法在每個(gè)問(wèn)題案例上運(yùn)行20次,記錄最好的求解結(jié)果,對(duì)比算法的求解結(jié)果取自相應(yīng)文獻(xiàn)。求解結(jié)果對(duì)比如表4所示,各個(gè)算法求解問(wèn)題所能得到的下界個(gè)數(shù)對(duì)比如表5所示。

表4 求解結(jié)果對(duì)比

P2051 133111211—111111111111.250.191 27510———101010101010.050.051 32291110—9910999.100.091 4559———99999901 510898—889888.250.191 6508———88888801 699797—778777.250.191 888787877777701 9207———77777702 077676—66666602 1006———66666602 266676766666602 3006———66666602 4545656555555.600.242 5005———555555.050.052 643565655555502 8005———55555502 83255565555550

表5 求解結(jié)果達(dá)到下界的個(gè)數(shù)對(duì)比

由于本文算法采用Pytorch框架和Python編寫,IG和BBR算法采用C++編程語(yǔ)言,考慮編程語(yǔ)言以及個(gè)人計(jì)算機(jī)性能的差異,此處沒(méi)有比較CNN-PPO和IG,BBR算法的求解速度,但從求解結(jié)果上看,CNN-PPO算法求解性能優(yōu)異,能有效求解雙邊裝配線第一類平衡問(wèn)題。

由表5可知,CNN-PPO算法在全部59個(gè)測(cè)試案例中,有57個(gè)可以達(dá)到下界,在對(duì)比算法中只有IG和BBR能夠達(dá)到這一目標(biāo)。而且從表4可知,CNN-PPO算法有12個(gè)求解結(jié)果優(yōu)于TS算法,有3個(gè)求解結(jié)果優(yōu)于SA算法,有15個(gè)求解結(jié)果優(yōu)于LAHC算法,有4個(gè)求解結(jié)果優(yōu)于MHH算法,可見(jiàn)CNN-PPO算法的求解結(jié)果同IG和BBR算法,優(yōu)于SA,TS,LAHC,MHH算法,是目前最好的算法。對(duì)于P9,P12,P16,P24,P148問(wèn)題,CNN-PPO算法在20次求解中均能得到當(dāng)前最優(yōu)解,方差為0。對(duì)于P65和P205問(wèn)題,CNN-PPO算法也可為其所有案例求得當(dāng)前最優(yōu)解,只是求解結(jié)果稍有波動(dòng):6個(gè)P65問(wèn)題案例中,2個(gè)案例20次求解方差為0,其余4個(gè)案例雖有方差,但是僅CT=512案例的20次求解方差稍大,為0.21(均值為5.30,14次得到結(jié)果為5,6次得到結(jié)果為6),剩下3個(gè)案例的20次求解方差均小于0.1;18個(gè)P205問(wèn)題案例中,11個(gè)案例20次求解方差為0;其余7個(gè)案例方差均較小,最大僅為0.24(案例CT=2 454,20次求解均值為5.60,8次得到結(jié)果為5,12次得到結(jié)果為6)。以上結(jié)果充分說(shuō)明了本文所提CNN-PPO算法求解的穩(wěn)定性。

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

本文針對(duì)雙邊裝配線第一類平衡問(wèn)題,提出一種CNN-PPO深度強(qiáng)化學(xué)習(xí)算法,在原有PPO算法基礎(chǔ)上引入CNN提升了智能體的數(shù)據(jù)特征提取能力。同時(shí),根據(jù)雙邊裝配線問(wèn)題特征定義狀態(tài)特征,采用獨(dú)熱編碼將其轉(zhuǎn)換為狀態(tài)矩陣來(lái)描述雙邊裝配線問(wèn)題,引入標(biāo)記層輔助智能體進(jìn)行任務(wù)決策,并根據(jù)問(wèn)題優(yōu)化目標(biāo)設(shè)計(jì)了獎(jiǎng)勵(lì)函數(shù)。

為測(cè)試本文算法的有效性,用其求解所有規(guī)模的標(biāo)準(zhǔn)案例,并將結(jié)果與現(xiàn)有6種優(yōu)化算法進(jìn)行對(duì)比。結(jié)果表明,在所有案列中,CNN-PPO算法能夠獲得當(dāng)前最優(yōu)解,而且相對(duì)于傳統(tǒng)的啟發(fā)式算法、元啟發(fā)式算法、精確算法,本文所提基于深度強(qiáng)化學(xué)習(xí)方法的算法能夠從歷史求解經(jīng)驗(yàn)中進(jìn)行學(xué)習(xí),更新任務(wù)分配策略的特性,發(fā)展?jié)摿^大,在計(jì)算能力不斷提升、大規(guī)模并行計(jì)算的背景下有很好的發(fā)展前景。另外,為了驗(yàn)證算法的穩(wěn)定性,本文計(jì)算了所有問(wèn)題20次求解結(jié)果的均值和方差,結(jié)果顯示,在59個(gè)案例中,絕大多數(shù)(48個(gè))案例的方差為0,剩下11個(gè)案例雖有方差,但均較小,6個(gè)案例的方差小于0.1,大于0.1的5個(gè)案例中,方差最大的僅為0.24,說(shuō)明本文所提算法求解的結(jié)果波動(dòng)較小,具有較高的穩(wěn)定性。

本文所提方法目前只能求解雙邊裝配線第一類平衡問(wèn)題,未來(lái)可以考慮將其應(yīng)用于解決雙邊裝配線第二類平衡問(wèn)題、再平衡問(wèn)題等更加切合生產(chǎn)實(shí)際的問(wèn)題。