基于深度強化學習算法的雙邊裝配線第一類平衡

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

(1.上海交通大學 機械與動力工程學院,上海 200240;2.上海交通大學 海洋裝備研究院,上海 200240;3.中國重汽集團 工藝研究院,山東 濟南 250100)

0 引言

裝配線是車間流水生產的一種常見方式,常用于汽車、家電等大批量生產[1]。雙邊裝配線相對于傳統單邊作業的裝配線,擁有長度短、設備利用率高、物料搬運成本低等一系列優點,在裝載機、卡車、汽車等較大型機械產品裝配車間得到了廣泛應用[1]。

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

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

綜上所述,第一類平衡問題的求解算法主要有啟發式算法、精確算法和元啟發式算法三大類。啟發式算法雖然求解速度快、簡潔高效,但是求解結果不能達到全局最優;精確算法能夠得到最優解,但是求解速度慢;元啟發式算法的迭代搜索過程通常比較耗時,每個問題案例需要重新迭代求解。這些傳統優化算法很少利用歷史信息來調整行為,不能有效利用歷史求解經驗進行學習,許多算法在大規模問題上仍有很大提升空間。

目前,利用深度強化學習算法求解組合優化問題已有一些初步的成果,包括旅行商問題、凸包問題、最大割問題、點集匹配、車間調度問題等[13],這些研究通常將求解組合優化問題轉化為馬爾科夫決策過程(Markov Decision Process,MDP),狀態s描述問題狀態,強化學習智能體(Agent)觀察狀態s,并做出決策a,環境采用決策a更新狀態,并再將獎勵r反饋給智能體,通過與環境交互獲取決策經驗來更新模型,在最大化獎勵的同時最優化決策策略。

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

1 問題描述與建模

1.1 問題描述

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

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

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

(1)先序約束 任務分配必須遵守任務之間的執行順序關系。

(2)節拍約束 一個工位內所有任務的作業時間之和應該小于等于該工位的節拍時間。

(3)操作方位約束 任務只能分配到對應的操作邊。

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

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

1.2 數學模型

本文涉及的參數說明如下:

(1)基本參數

Ns為雙邊裝配線工作站數量;

I為任務集,I={1,2,…,i,…,m};

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

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

AL為只能在左工位執行的任務集,AL?I;

AR為只能在右工位執行的任務集,AR?I;

AE表示在左或右工位均可執行的任務集,AE?I;

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

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

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

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

Pc為沒有緊鄰先序約束關系的任務集;

ct表示節拍;

μ為一個較大的常數。

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

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

(2)決策變量

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

(3)指示變量

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

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

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)表示優化目標,即最小化工作站數量;式(2)表示每一個任務只能分配到一個工位;式(3)和式(4)表示每個任務的完工時間必須小于節拍,確保節拍約束;式(5)對應先序約束;式(6)～式(8)表示序列相關約束;式(9)～式(12)定義各個變量。

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

CNN-PPO算法求解雙邊裝配線第一類平衡問題的過程如圖3所示。CNN-PPO強化學習智能體觀察雙邊裝配線環境狀態st,采取任務分配決策at,環境完成任務at分配,并將獎勵rt反饋給智能體,智能體通過與環境不斷交互求解第一類平衡問題,同時獲取任務分配求解經驗,以數據驅動的方法學習經驗,更新模型,通過反復試錯獲取更高的獎勵值,在最大化累積獎勵的同時最優化任務分配策略。

2.1 CNN-PPO強化學習智能體

CNN-PPO強化學習智能體采用類似PPO的執行—評價(Actor-Critic)結構類型。其中Actor策略網絡根據雙邊裝配線環境狀態st做出任務分配決策at,Critic評價網絡對任務分配決策at的優劣進行評價。

Actor策略網絡用參數為θ的CNN逼近最優的任務分配策略pθ(at|st),網絡結構如圖4所示,包括兩層卷積網絡、三層全連接網絡。圖中,維度M×N的狀態矩陣是網絡在時刻t的輸入,對應雙邊裝配線環境狀態st,M為狀態特征數量,N為任務數量;pθ(at|st)為時刻tActor策略網絡的輸出,指Actor策略網絡在雙邊裝配線環境狀態st下輸出任務分配決策at的概率。

Critic評價網絡用參數為ψ的CNN逼近最優的策略評價值vψ(st|at)。本文Critic策略網絡結構前幾層和Actor網絡結構相同,只是最后一層為線性回歸層,即vψ(st|at)=f(h(t);ψ)=ω×h(t)+b替代Actor網絡中的SoftMax層,其中vψ(st|at)為t時刻Critic評價網絡輸出的策略評價值,h(t)為上一層的輸出,ψ為網絡內部單元節點的參數,包括權重ω和偏置項b。

2.2 雙邊裝配線狀態

狀態的定義應與雙邊裝配線平衡問題特征緊密相關。2016年,張智聰等[18]對強化學習在調度問題的狀態選擇提出以下準則:

(1)調度環境的主要特點和變化能夠通過狀態特征描述,包括調度系統的全局特征和局部特征。

(2)可以通過一個通用特征集表示所有問題的所有狀態。

(3)狀態特征可以用來表示和概括各種不同調度問題的狀態。

(4)狀態特征是調度問題狀態變量的數值表征。

(5)狀態特征應易于計算。

結合肖鵬飛對非置換流水車間調度問題提出的狀態特征[19],本文針對雙邊裝配線平衡問題提出雙邊裝配線狀態特征,如表1所示。

表1 雙邊裝配線狀態特征

續表1

其中,狀態特征1～5的特征值為相應的任務序列號,狀態特征6～14反映雙邊裝配線的整體特征,特別地,對狀態特征11～14進行取整處理。假設,某雙邊裝配線任務數量為N,對表1中的狀態特征進行獨熱編碼處理,得到該雙邊裝配線環境狀態矩陣st,其維度為14×N。若序號為i的狀態特征的特征值j≠0,則矩陣st第i行第j列的值為1,第i行其他列的值均為0;若狀態特征i的特征值j大于矩陣列數,則取j的值為矩陣列數。

以P16問題為例,由圖2a可知,在求解初始,裝配線開啟左工位,可分配的無先序任務集合為{1,2},對應的作業時間為{6,5},因此表1中,第1個狀態特征PTime的特征值為1,其他狀態特征可同理依次求得,如表2第3列所示,經過獨熱編碼處理得到的狀態矩陣s1如圖5a所示。隨后,CNN-PPO強化學習智能體觀察狀態矩陣s1,做出任務分配決策,若輸出待分配任務1,并按下文裝配線環境任務分配邏輯分配任務1(詳見2.4節任務分配),則裝配線開啟右工位?？紤]操作方位約束和序列相關約束,可分配的無先序任務集合變為{2},對應的作業時間為{5},因此PTime的狀態特征值變為2,其他狀態特征的參數相應發生變化,如表2第4列所示,經過獨熱編碼處理得到狀態矩陣s2如圖5b的狀態矩陣所示。

表2 P16問題狀態特征值變化

2.3 任務決策

CNN-PPO強化學習智能體根據雙邊裝配線狀態矩陣st輸出pθ(at|st),并按概率分布采樣,獲得待分配任務at。然而,因為雙邊裝配線第一類平衡問題具有先序、操作方位、序列相關等約束,如果直接按概率分布采樣,獲得待分配任務at,則會出現算法難以收斂、陷入局部最優等問題,所以本文引入標記層(mask)來保證滿足先序、操作方位、序列相關約束的任務能被采取,以充分利用智能體從經驗中進行學習的能力。

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

2.4 任務分配

雙邊裝配線環境任務分配流程如圖7所示。

2.5 獎勵函數

CNN-PPO強化學習智能體通過最大化累積獎勵rsum,實現最優的任務分配策略pθ(at|st),繼而實現優化目標最優化。本文采用稀疏獎勵,即智能體與環境交互過程中獎勵r1,r2,…,rn-1均為0,當環境分配完所有N個任務后,給智能體反饋獎勵rn,則累積獎勵rsum=rn。若直接定義累積獎勵為優化目標的負值,即rsum=rn=-ns,則環境給智能體反饋的信息太少,不利于智能體學習,因此本文累積獎勵不僅包括優化目標,還包括該問題其他能輔助優化目標優化的子目標。

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

(13)

(14)

(15)

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

考慮優化目標ns和子優化目標nw,LE,SI,CSI間的關系,本文首先采用線性規劃法進行目標轉化,以便高效獲得較優的任務分配方案。參考文獻[20],合并轉化的函數方程式為

(16)

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

因此,取rsum=rn=-f。

2.6 模型更新

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

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

1:初始化Actor-Critic網絡參數θ,φ,初始化迭代最大回合數episode、經驗池容量buffersize、經驗池最大容量max buffer size、批量樣本大小batchsize

2:for each episode do:

3: t=1

4: 初始化雙邊裝配線環境,生成狀態st,清空經驗池

5: While buffer size

6: while雙邊裝配線所有任務沒有被分配完do:

7: 智能體觀察環境狀態st,根據策略pθ(at|st)決定待分配任務at

8: 環境分配任務at,反饋獎勵rt

9: t=t+1

10: 更新環境狀態st

11: end while

12: 智能體將交互軌跡τ(求解經驗)存入經驗池

13: end while

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

15: 計算Actor策略網絡損失函數actor loss,Critic評價網絡損失函數critic loss

16: 更新Actor策略網絡pθ(at|st)

17: 更新Critic評價網絡vΨ(st|at)

18: end for

19: θold,φold←θ,Ψ

20:end for

3 實驗驗證

采用Python語言編程,環境為Python 3.6,在操作系統為Ubuntu 20.04 LTS、CPU頻率為2.90 GHz、內存為16 G的計算機上運行。以面向對象的形式搭建了雙邊裝配線環境類,包括狀態更新、任務分配、獎勵生成,并用Pytorch框架和Python編程語言搭建了CNN-PPO強化學習智能體。

本文用基準問題進行算法測試,包括P9,P12,P16,P24,P65,P148,P205共7個問題,59個案例,問題數據同文獻[6]。

3.1 模型訓練

在模型訓練開始之前,本文算法的參數主要根據經驗值和智能體交互過程的實際數據設置,具體如表3所示。

表3 算法參數

完成算法參數設定后開始訓練,在迭代過程中記錄智能體獲得的累積獎勵、Actor策略網絡損失函數、Critic評價網絡損失函數的變化情況,并與PPO算法對比。PPO算法為5層全連接網絡,其輸入為14×1的一維向量,14為狀態特征個數,其輸出和CNN-PPO一樣都有mask層處理。

圖8所示為改進前后的算法在P65、節拍CT=381案例上迭代訓練過程的對比。

對比圖8a和圖8b可見,隨著訓練回合數的增加,增加CNN的CNN-PPO算法的累積獎勵逐漸上升,而PPO算法一直在振蕩,收斂困難,CNN-PPO算法的優化過程明顯好于PPO算法,其收斂過程更穩定,優化結果更好。說明CNN的數據表征學習能力能夠有效提取雙邊裝配線狀態矩陣的數據特征,并能更快更好地完成任務分配。圖8c中PPO算法的Actor網絡損失曲線振蕩很厲害,收斂困難,而CNN-PPO算法的Actor網絡損失曲線隨著迭代次數的增加趨于收斂,策略趨于穩定。圖8d中PPO算法的Critic網絡損失曲線始終變化不大,即策略評價變化不大,表明Actor策略網絡沒有收斂,策略變化不大,而CNN-PPO算法的Critic網絡損失曲線收斂過程更穩定,效果更好,說明CNN-PPO算法的優化過程更好。

綜上所述,訓練過程整體表明,相對于PPO算法,CNN-PPO算法的訓練過程穩定,求解能力更強,更能滿足雙邊裝配線第一類平衡問題求解的需求,驗證了算法改進的有效性。

3.2 模型驗證

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

表4 求解結果對比

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 求解結果達到下界的個數對比

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

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

4 結束語

本文針對雙邊裝配線第一類平衡問題,提出一種CNN-PPO深度強化學習算法,在原有PPO算法基礎上引入CNN提升了智能體的數據特征提取能力。同時,根據雙邊裝配線問題特征定義狀態特征,采用獨熱編碼將其轉換為狀態矩陣來描述雙邊裝配線問題,引入標記層輔助智能體進行任務決策,并根據問題優化目標設計了獎勵函數。

為測試本文算法的有效性,用其求解所有規模的標準案例,并將結果與現有6種優化算法進行對比。結果表明,在所有案列中,CNN-PPO算法能夠獲得當前最優解,而且相對于傳統的啟發式算法、元啟發式算法、精確算法,本文所提基于深度強化學習方法的算法能夠從歷史求解經驗中進行學習,更新任務分配策略的特性,發展潛力較大,在計算能力不斷提升、大規模并行計算的背景下有很好的發展前景。另外,為了驗證算法的穩定性,本文計算了所有問題20次求解結果的均值和方差,結果顯示,在59個案例中,絕大多數(48個)案例的方差為0,剩下11個案例雖有方差,但均較小,6個案例的方差小于0.1,大于0.1的5個案例中,方差最大的僅為0.24,說明本文所提算法求解的結果波動較小,具有較高的穩定性。

本文所提方法目前只能求解雙邊裝配線第一類平衡問題,未來可以考慮將其應用于解決雙邊裝配線第二類平衡問題、再平衡問題等更加切合生產實際的問題。