基于深度強(qiáng)化學(xué)習(xí)的二維不規(guī)則多邊形排樣方法①

曾煥榮,商慧亮

(復(fù)旦大學(xué) 工程與應(yīng)用技術(shù)研究院,上海 200433)

排樣問題(nesting problem)又稱下料問題(cutting stock problem),是一種經(jīng)典的帶幾何約束的組合優(yōu)化問題,主要涉及到數(shù)學(xué)、運(yùn)籌學(xué)、信息與計(jì)算科學(xué)以及工程管理學(xué)等學(xué)科.當(dāng)排樣對象限定在二維空間時,該問題是指將多個零件互不重疊地?cái)[放到板材當(dāng)中,且不超出板材限定的空間,要求在所有零件完成擺放以后,板材的空間利用率最大,或者說浪費(fèi)空間最小,這兩個指標(biāo)只要得到微小的提升,就能為企業(yè)節(jié)約大量的材料成本.根據(jù)排樣對象是否為規(guī)則形狀,二維排樣問題又可分為二維矩形排樣和二維不規(guī)則排樣.二維不規(guī)則排樣問題由于在工業(yè)生產(chǎn)中的應(yīng)用更為廣泛,因此相比二維矩形排樣問題有著更大的研究意義,但是由于二維不規(guī)則排樣問題中零件的形狀多變,在特征提取、序列決策以及重疊判斷等問題中有著更高的復(fù)雜度.

排樣問題為經(jīng)典的組合優(yōu)化問題,由于其NP-Hard的特性[1],這類問題的解空間非常大,時間復(fù)雜度隨著問題規(guī)模的增加迅速上升,特別是涉及到幾何計(jì)算時.因此在大多數(shù)情況下,排樣算法主要是基于特定規(guī)則的啟發(fā)式算法和以智能搜索為基礎(chǔ)的元啟發(fā)式算法為主.但是近年來,隨著深度強(qiáng)化學(xué)習(xí)[2]研究熱度的提升,研究人員也開始將深度強(qiáng)化學(xué)習(xí)應(yīng)用在組合優(yōu)化類問題當(dāng)中[3].深度學(xué)習(xí)的訓(xùn)練通常需要大量帶標(biāo)簽的訓(xùn)練樣本,但對于組合優(yōu)化問題來說,獲取大量有標(biāo)記的數(shù)據(jù)是很困難的,一種思路是使用啟發(fā)式算法得到的結(jié)果作為數(shù)據(jù)標(biāo)簽,但是這種方法無法得到比啟發(fā)式算法更優(yōu)的解;另一種思路是使用強(qiáng)化學(xué)習(xí)算法,由于無需使用有標(biāo)記的訓(xùn)練數(shù)據(jù),且組合優(yōu)化問題通常有著很明確的優(yōu)化目標(biāo),因此獎勵函數(shù)的設(shè)計(jì)較容易.同時,許多組合優(yōu)化問題的本質(zhì)都是序列決策問題,因此也非常適合使用強(qiáng)化學(xué)習(xí)方法.深度強(qiáng)化學(xué)習(xí)求解組合優(yōu)化問題的大致思路為:首先將樣本表示為可輸入神經(jīng)網(wǎng)絡(luò)模型的形式,通過大量樣本對深度神經(jīng)網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練,同時需要避免產(chǎn)生不符合約束條件的解,訓(xùn)練完成后將模型作為求解器,在測試階段即可把對測試樣例求解的過程轉(zhuǎn)化為一次神經(jīng)網(wǎng)絡(luò)的前向傳播過程.

深度強(qiáng)化學(xué)習(xí)在組合優(yōu)化問題上的成功應(yīng)用[4]印證了其在解決排樣優(yōu)化問題上的可行性.Hu 等人[5]首次將指針網(wǎng)絡(luò)(pointer network)[6]用于解決三維排樣問題,主要思想是用深度強(qiáng)化學(xué)習(xí)的方法來解決排樣件的定序問題,而定位問題以及排樣件的擺放方向問題則通過傳統(tǒng)啟發(fā)式算法來解決;Duan 等人[7]對這種思路進(jìn)一步改進(jìn),提出了多任務(wù)的深度強(qiáng)化學(xué)習(xí)模型,使用了監(jiān)督學(xué)習(xí)的方法來預(yù)測箱子的擺放方向;Zhao等人[8]為了解決在線裝箱問題(即模型在某時刻僅能得到下一個排樣件的信息),使用卷積神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)生成可行性掩碼(feasibility mask),從而直接預(yù)測排樣件的排樣位置;Hu 等人[9]使用深度強(qiáng)化學(xué)習(xí)與Seq2Seq 模型來解決二維及三維排樣問題中裝入順序的依賴問題.以上研究有一個共同特點(diǎn),即排樣對象的形狀都是規(guī)則的,如二維排樣問題中的矩形與三維排樣問題中的立方體,而工業(yè)生產(chǎn)中的排樣對象更多的是不規(guī)則的,將深度強(qiáng)化學(xué)習(xí)應(yīng)用在不規(guī)則物體的排樣問題中有著更好的研究意義與應(yīng)用前景.

1 問題描述與求解框架

1.1 問題描述

本文在問題描述以及數(shù)學(xué)建模中所用到的變量定義如表1所示.

表1 變量定義

若有n個排樣零件,在給定的二維矩形排樣空間E中,根據(jù)排樣對象的幾何特性在 E中搜尋空間子集,其優(yōu)化目標(biāo)為:

即式(1)在固定矩形空間寬度的情況下,使得排樣后所圍成的矩形長度L最小化;式(2)使排樣空間的利用率p最大化.

同時,以上目標(biāo)函數(shù)需要滿足以下約束:

即選取的空間子集不得超出 E所限制的空間,且任意零件之間互不重疊.出于排樣任務(wù)的不同,可能會有旋轉(zhuǎn)等空間變換限制.

1.2 求解框架

排樣優(yōu)化問題是一個NP-Hard的離散組合優(yōu)化問題,研究人員提出了各種各樣的算法來解決“組合爆炸”這一難題,但現(xiàn)今并沒有一個算法能夠隨著問題規(guī)模的增大而在多項(xiàng)式時間內(nèi)能夠求得最優(yōu)解.排樣優(yōu)化問題中的組合個數(shù)T可以通過式(4)進(jìn)行計(jì)算:

其中,θ為物件允許旋轉(zhuǎn)的角度,N為待排樣的物件個數(shù),在N=15時,不考慮旋轉(zhuǎn)的情況下,其排列組合數(shù)就約有1.3×1012種.若考慮旋轉(zhuǎn)的情況,解空間則會迅速增大.確定性算法如線性規(guī)劃法只能在極小規(guī)模的排樣問題中在可接受的計(jì)算時間內(nèi)得到最優(yōu)解,中小規(guī)模的問題可以在啟發(fā)式算法的基礎(chǔ)上應(yīng)用元啟發(fā)式算法進(jìn)行優(yōu)化,從而在可接受的時間內(nèi)得到較為理想的解.排樣問題的求解框架可歸納總結(jié)為兩大模塊,即定序算法以及定位算法兩部分.定序算法用于搜索一組最優(yōu)的排樣順序,必要時可以對形狀進(jìn)行旋轉(zhuǎn)操作,目標(biāo)是使調(diào)用定位算法解碼后的板材利用率最大;定位算法用于對搜索到的序列進(jìn)行解碼,由算法中的定位規(guī)則確定零件在板材中的具體排放位置,由此生成排樣圖,并計(jì)算板材利用率.二維不規(guī)則排樣中,常用的定序算法有隨機(jī)法、基于特定排樣規(guī)則的啟發(fā)式算法、基于搜索的元啟發(fā)式算法等.

1.3 重疊檢測

由于排樣過程中任意零件之間不得發(fā)生重疊,本文在實(shí)驗(yàn)階段使用臨界多邊形完成零件間的重疊檢測.臨界多邊形(no-fit polygon,NFP)[10]用于定義兩個形狀之間的重疊區(qū)域.每個形狀都有一個參考點(diǎn).假設(shè)有兩個形狀,分別記為A和B.若把A的位置固定,A和B 之間的臨界多邊形是由B的參考點(diǎn)沿A的邊緣滑動一周的軌跡所圍成的閉合多邊形,記為NFPAB,在運(yùn)動過程中,B 與A 保持接觸且不重疊.圖1給出了一個臨界多邊形的構(gòu)建例子,其中,圖1(a)為形狀B的參考點(diǎn)P 沿著形狀A(yù) 運(yùn)行而形成的軌跡,圖1(b)為由運(yùn)動軌跡生成的NFPAB.

圖1 臨界多邊形構(gòu)建過程

臨界多邊形的幾何意義為:

(1)若將B 擺放以后,其參考點(diǎn)位于NFPAB以內(nèi),則說明A 與B 之間有重疊的部分;

(2)若參考點(diǎn)位于NFPAB以外,則A 與B 之間不重疊;

(3)若參考點(diǎn)位于NFPAB的邊界,則說明A 與B相鄰.

因此,NFPAB的邊界及其外部是可以放置B 并避免與A 發(fā)生重疊的可行區(qū)域.使用了該方法以后,重疊檢測可以簡化為判斷參考點(diǎn)是否在臨界多邊形以內(nèi),極大降低了排樣過程中的幾何運(yùn)算量.

2 形狀特征提取

在機(jī)器學(xué)習(xí)中,常常需要用向量或矩陣來表示學(xué)習(xí)對象,作為網(wǎng)絡(luò)的輸入.向量或矩陣之間的歐氏距離也是衡量兩個目標(biāo)之間相似性的一個指標(biāo).

規(guī)則排樣最大的特點(diǎn)是形狀特征的表示通常較為簡單,如僅用長、寬兩個值便可表示一個矩形.而在二維不規(guī)則排樣問題中,特征點(diǎn)往往比較多,不同的求解方案通常使用不同的幾何表示,而幾何圖形的表示法一定程度上決定了模型和算法的設(shè)計(jì)、計(jì)算精度以及計(jì)算時間.形狀特征的提取方法常常用于形狀分類、目標(biāo)檢測等問題上,常見的特征有鏈碼、傅里葉描述子、形狀上下文等[11].在這類問題中,一個良好的特征表示通常在旋轉(zhuǎn)、平移和仿射變換下是不變的.但是在排樣問題中,由于圖形旋轉(zhuǎn)及仿射變換對其擺放位置的選擇影響較大,因此本文僅考慮平移不變性.即形狀相同,但是旋轉(zhuǎn)角度不同的兩個圖形以及經(jīng)過仿射變換的圖形可以看作不同的圖形.

在排樣問題當(dāng)中,形狀的區(qū)域信息以及輪廓信息同等重要.作為神經(jīng)網(wǎng)絡(luò)的輸入,特征向量不能有太多的冗余,同時要保證對數(shù)據(jù)的表示要有一定的精度.本文使用多邊形質(zhì)心到輪廓距離作為特征編碼,充分考慮到了形狀的區(qū)域信息以及輪廓信息,把形狀特征嵌入到一維向量從而便于輸入到神經(jīng)網(wǎng)絡(luò)中.

質(zhì)心是多邊形的幾何中心,可以通過對多邊形輪廓線上均等采樣點(diǎn)的坐標(biāo)求均值得到.雖然說質(zhì)心的計(jì)算方法較為固定,但是該質(zhì)心-輪廓距離的計(jì)算方法一般只適用于凸多邊形,以及質(zhì)心在圖形內(nèi)部的非凸多邊形.在排樣問題當(dāng)中,經(jīng)常會遇到一些較為復(fù)雜的多邊形,其質(zhì)心位于多邊形以外,若簡單地使用該質(zhì)心計(jì)算其到多邊形輪廓的距離,對進(jìn)一步的研究沒有任何意義.為了解決該問題,可以將質(zhì)心移至圖形內(nèi)部[12,13].考慮到現(xiàn)實(shí)排樣問題中大多排樣對象質(zhì)心都在圖形內(nèi)部,為了簡化問題的運(yùn)算,本文主要考慮質(zhì)心在多邊形內(nèi)部的情況.

歐式幾何距離(Euclidean distance)是指在n維空間中的兩個點(diǎn)之間的直線距離,或者向量的自然長度,即點(diǎn)到原點(diǎn)的距離.在二維空間中,點(diǎn)a與點(diǎn)b之間的歐式距離可用式(5)計(jì)算:

在求得多邊形的質(zhì)心以后,可通過歐式距離計(jì)算公式獲得質(zhì)心到輪廓的距離,主要思路為:從以質(zhì)心為原點(diǎn)發(fā)散N條射線,相鄰射線之間的距離為,選定一條起始射線,取質(zhì)心到交點(diǎn)的距離加入特征向量中,若射線與形狀之間有多個交點(diǎn),則取距離質(zhì)心最遠(yuǎn)的交點(diǎn)并把該距離加入特征向量中,如圖2所示,該圖形的質(zhì)心坐標(biāo) (xc,yc)=(5,5),當(dāng)向量維度為10×1 時,從該圖形的質(zhì)心引出10 條射線,獲得質(zhì)心到交點(diǎn)的距離加入到特征向量當(dāng)中,獲得的特征向量為:V=(1.50,0.85,1.58,0.85,1.50,0.85,1.58,1.58,0.85)T.

圖2 形狀特征向量提取

為了驗(yàn)證形狀提取特征的效果,本文對特征向量進(jìn)行形狀重建,并與原形狀作對比.本文隨機(jī)生成了3 030個頂點(diǎn)個數(shù)在3–8 個之間的多邊形加入測試.使用N=180對圖形進(jìn)行向量化表示,并對該向量進(jìn)行形狀重建,以評價該向量對圖形的表示效果.評價指標(biāo)有兩個,分別為:(1)面積覆蓋率(ACR),用于評價重建后的形狀對原有圖形的覆蓋情況;(2)面積超出率(AER),用于表示重建后的形狀超出原有圖形部分的占比.通過統(tǒng)計(jì)這兩個指標(biāo)不同范圍內(nèi)的形狀個數(shù),可以評價出該向量對形狀特征的提取效果.結(jié)果如表2所示.

表2 形狀重建結(jié)果

由此可見,基于質(zhì)心-輪廓距離的特征提取法能夠基本實(shí)現(xiàn)1%以內(nèi)的壓縮損失,足以表達(dá)形狀的語義信息,便于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練.此外,本文對不同的N的重建效果也進(jìn)行了測試,測試結(jié)果發(fā)現(xiàn)重建效果也跟N的大小相關(guān),即N越大(小于360),面積覆蓋率就越大,面積超出率就越小,重建效果越好.

3 算法描述

3.1 編碼器-解碼器結(jié)構(gòu)

本文在Duan 等人[7]提出的多任務(wù)三維裝箱模型基礎(chǔ)之上,提出了一種融合注意力機(jī)制以及多任務(wù)的不規(guī)則多邊形排樣序列預(yù)測模型,整體采用了基于編碼器-解碼器[14]的結(jié)構(gòu),由于輸入零件的數(shù)目不定,傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)難以處理不定長的輸入.一種解決思路是用Seq2Seq 模型[15],在編碼階段,每一時刻輸入一個零件信息,在解碼階段將編碼器的輸出作為解碼器的輸入,輸出目標(biāo)類的條件概率分布,但是其輸出目標(biāo)類的長度是固定的,對于排樣問題此類的組合優(yōu)化問題,其輸出的目標(biāo)類數(shù)量完全取決于輸入序列的長度,而輸入是一個可變的序列,因此使用普通的Seq2Seq 難以解決如排樣問題這類的序列決策問題,但是在基本的Seq2Seq 模型中加入注意力機(jī)制可以很好地解決此類問題,指針網(wǎng)絡(luò)就是一種典型的使用此方法的模型,用于保證輸出只能從輸入中選擇這個先驗(yàn)信息.對于傳統(tǒng)的注意力模型,在計(jì)算權(quán)重之后會對編碼器的隱層進(jìn)行加權(quán),求得加權(quán)后的向量.而指針網(wǎng)絡(luò)則在計(jì)算權(quán)重之后,直接選擇概率最大的編碼器狀態(tài)作為輸出.此外,在本文中,編碼器與解碼器均使用LSTM[16]網(wǎng)絡(luò)結(jié)構(gòu)以解決梯度消失的問題.

3.2 Actor-Critic 算法

Actor-Critic 算法源于策略梯度[17]方法,并在此基礎(chǔ)上結(jié)合了基于值函數(shù)的方法.Actor-Critic 算法需要同時訓(xùn)練Actor和Critic 兩個神經(jīng)網(wǎng)絡(luò),分別負(fù)責(zé)學(xué)習(xí)策略和值函數(shù):

Actor 網(wǎng)絡(luò)也稱策略網(wǎng)絡(luò),用神經(jīng)網(wǎng)絡(luò)來表示策略函數(shù).根據(jù)輸入信息學(xué)習(xí)動作集上的概率分布,基于概率生成動作,并根據(jù)Critic 網(wǎng)絡(luò)的評價調(diào)整策略,網(wǎng)絡(luò)輸出是動作.在本文中,Actor 網(wǎng)絡(luò)的輸入序列x=(x1,x2,···,xn)是 多邊形的特征向量序列,輸出y=(y1,y2,···,yn)為排樣件的排樣順序以及方向.策略函數(shù)pθ(y|x)表示給定輸入序列x的情況下輸出y的概率.本文選擇最短排樣長度作為模型的獎勵信息,則Actor 網(wǎng)絡(luò)的作用就是增加能夠獲得最短排樣長度的輸出方案被選擇的概率.

Critic 網(wǎng)絡(luò)也稱估值網(wǎng)絡(luò),通過計(jì)算值函數(shù)來評估策略.根據(jù)Actor 網(wǎng)絡(luò)的動作評價策略的價值,并反饋給Actor 網(wǎng)絡(luò),網(wǎng)絡(luò)輸出是對目標(biāo)函數(shù)的預(yù)測.

3.3 Actor 網(wǎng)絡(luò)結(jié)構(gòu)

本文主要使用深度強(qiáng)化學(xué)習(xí)的方法來解決排樣問題中的定序問題,而該問題又包括兩個子問題,一是零件的排樣順序,二是零件的旋轉(zhuǎn)角度.Hu 等人[9]在解決二維矩形排樣問題時,將經(jīng)旋轉(zhuǎn)后的矩形與原矩形看作為兩個不同的形狀并輸入到RNN 神經(jīng)網(wǎng)絡(luò)中,若其中一個形狀被選擇,則使用屏蔽機(jī)制將兩個形狀同時屏蔽.但是不規(guī)則圖形在排樣中可選擇的角度較多,若使用該方法則會使得輸入的形狀數(shù)量成倍地增加.因此,本文在引言所述的三維裝箱問題解決方案的基礎(chǔ)之上,設(shè)計(jì)了一種改進(jìn)型的基于多任務(wù)的二維不規(guī)則排樣定序算法,可以在零件序號的選擇的同時,確定零件的旋轉(zhuǎn)角度.圖3為本文Actor 網(wǎng)絡(luò)的架構(gòu)圖.

圖3 Actor 網(wǎng)絡(luò)架構(gòu)圖

由于零件序列的決策受已排列零件的影響較大,為了充分利用解碼器所產(chǎn)生的序列信息,在編碼階段以及解碼階段均使用了注意力機(jī)制,在解碼階段,在t時刻之前產(chǎn)生的零件權(quán)重可用式(6)計(jì)算:

通過把t時刻前產(chǎn)生的零件隱層向量與其權(quán)重進(jìn)行加權(quán)求和,可以得到解碼器在t時刻的權(quán)重向量:

在零件序號的確定上,本文運(yùn)用指向機(jī)制,使用通過式(7)得到的加權(quán)向量可以用來計(jì)算“指針”所指向量的概率分布.在t?1時 刻,解碼器輸出零件序號st?1與旋轉(zhuǎn)角度orit?1后形成旋轉(zhuǎn)后的零件圖形,經(jīng)形狀特征提取后作為yt輸入到解碼器網(wǎng)絡(luò)中,得到hdj,將其與attdt進(jìn)行向量拼接以后得到的新向量可以用于預(yù)測零件被選擇的概率.在t時刻,零件序號的選擇概率如式(8)、式(9)所示:

其中,hej表示編碼器中第j個形狀的隱層向量,hdt表示解碼器在t時刻的隱層向量,vT為可學(xué)習(xí)的注意力向量,W為可學(xué)習(xí)的注意力矩陣.

經(jīng)過式(9)的計(jì)算后可以得到t時刻每一個零件被選擇的概率.由于在排樣問題中一般不允許已選擇的零件再次被選擇,因此,可以運(yùn)用屏蔽機(jī)制,通過將決策序列中出現(xiàn)過的零件的概率置為0,確保模型只會指向未被選擇過的零件,具體如式(10)所示:

其中,π (j)表示j號零件被選擇的時間,如果沒有被選擇過,則該值為0.

式(9)所得概率可以視為每個零件的注意力權(quán)重,使用該權(quán)重對編碼器中零件的隱層向量進(jìn)行加權(quán)求和,可得到編碼器在t時刻的注意力加權(quán)向量,如式(11)、式(12)所示:

通過把a(bǔ)tttd、attet、hdt進(jìn)行向量拼接,我們可以得到t時刻的語義向量,本文使用該向量進(jìn)行零件旋轉(zhuǎn)角度的預(yù)測,如式(13)所示:

其中,σ為激活函數(shù),W與b均為可學(xué)習(xí)的參數(shù).若零件允許旋轉(zhuǎn)的最小角度為θ,則其輸出有個類,第i類輸出代表零件旋轉(zhuǎn)θ×(i?1)度.

編碼器-解碼器模型中,編碼器負(fù)責(zé)處理輸入的排樣件信息.一個排樣實(shí)例中的元素應(yīng)該是無序的,而在編碼器中零件的形狀信息是按順序輸入到神經(jīng)網(wǎng)絡(luò)的,會對神經(jīng)網(wǎng)絡(luò)的求解造成一定的影響[16].因此,本文在原有模型的基礎(chǔ)之上,加入glimpse 機(jī)制.這一操作可以在計(jì)算時間不明顯增加的同時,能夠較好地消除輸入順序?qū)敵鼋Y(jié)果的影響.則零件被選擇的概率可以通過以下公式得到:

使用式(14)、式(15)替換式(8)、式(9)即可使glimpse 機(jī)制生效.

3.4 Critic 網(wǎng)絡(luò)結(jié)構(gòu)

在組合優(yōu)化類問題強(qiáng)化學(xué)習(xí)的訓(xùn)練過程中,智能體與環(huán)境交互以后獲得可獲得一個預(yù)測序列以及其獎勵(reward),在二維排樣問題中,獎勵可以是板材面積利用率或者排樣后多邊形圍成的矩形長度.此時需要一個基準(zhǔn)值(baseline)對此預(yù)測序列的效果進(jìn)行估計(jì),然后用這個估計(jì)值代替真實(shí)的獎勵值形成策略梯度,再用這個梯度來進(jìn)行網(wǎng)絡(luò)的更新.

Hu 等人[5]在其模型中使用了一種類似記憶重放的方法來更新基準(zhǔn)值,首先使用啟發(fā)式算法對每個樣本si都獲取一個預(yù)測序列oi,并計(jì)算出其獎勵值為b(si)的初始值,之后的訓(xùn)練過程中通過以下方式更新基準(zhǔn)值:

其中,reward為對oi使用如啟發(fā)式算法這類的傳統(tǒng)方法后求解得到的值,但是若在大規(guī)模的訓(xùn)練集上使用傳統(tǒng)方法進(jìn)行基準(zhǔn)值的求解,無疑會造成大量時間與資源的浪費(fèi).另外一種方法是使用Critic 網(wǎng)絡(luò)來預(yù)估輸入序列的基準(zhǔn)值,訓(xùn)練好的Critic 網(wǎng)絡(luò)能夠較好地預(yù)估基準(zhǔn)值,在節(jié)約了使用傳統(tǒng)方法計(jì)算基準(zhǔn)值時間的同時,降低了梯度方差,顯著地提升了模型的性能[18].

本文同樣使用編碼器-解碼器結(jié)構(gòu)作為Critic 網(wǎng)絡(luò).其中,編碼器結(jié)構(gòu)與Actor 網(wǎng)絡(luò)一致,將零件的特征向量x輸入映射到隱層向量h中,并將該隱層向量輸入到LSTM 網(wǎng)絡(luò)中,隨后,編碼器的隱層向量被送往解碼器的LSTM 處理塊(processing blocks)中,若有m個處理塊,則對編碼器中的隱層向量進(jìn)行m次運(yùn)算,并運(yùn)用glimpse 機(jī)制消除輸入序列間的依賴關(guān)系.最后,在得到最后一個處理塊的輸出以后,輸入到層數(shù)分別為l和1的兩個全連接層當(dāng)中,將最后一個全連接層的輸出作為對基準(zhǔn)值b(si)的預(yù)測,即si序列預(yù)期獲得的獎勵值.

3.5 訓(xùn)練

3.5.1 探索與利用

若模型在對零件序列進(jìn)行預(yù)測時,為了短期利益僅根據(jù)已掌握的信息做決策,即僅局限于已知的最優(yōu)動作,選擇當(dāng)前概率最大的零件,則有可能因?yàn)闆]有環(huán)境中獲得足夠的信息而學(xué)習(xí)不到全局最優(yōu)解.為了更好地對環(huán)境進(jìn)行探索,模型在進(jìn)行序列決策的時候需要采取一些與當(dāng)前策略不同的決策.在訓(xùn)練過程中,模型根據(jù) ε-greedy策 略來進(jìn)行序列決策,即有ε的概率使用貪心策略以及1?ε的概率使用隨機(jī)策略。具體操作為:模型在[0,1]區(qū)間內(nèi)隨機(jī)采樣一個實(shí)數(shù),當(dāng)該實(shí)數(shù)小于ε 時,則選擇概率最大的決策;當(dāng)實(shí)數(shù)大于等于ε 時,則 根據(jù)各決策的概率大小來選擇決策.

3.5.2 損失定義

本文Actor-Critic 框架使用回合更新的REINFORCE策略梯度法進(jìn)行訓(xùn)練,基于整個決策序列來訓(xùn)練網(wǎng)絡(luò)優(yōu)化策略函數(shù).網(wǎng)絡(luò)的損失函數(shù)包含了兩個損失,分別為Actor 網(wǎng)絡(luò)的損失Lθ|x以及Critic 網(wǎng)絡(luò)的損失Lφ|x.Lθ|x可以通過以下公式進(jìn)行計(jì)算.

式(17)中的數(shù)學(xué)期望無法直接計(jì)算,通常構(gòu)造多個排樣序列x1,x2,···,xB并根據(jù)蒙特卡洛方法采樣每個實(shí)例對應(yīng)的排樣序列,其中y～pθ(·|xi),則式(17)的損失可以轉(zhuǎn)化為:

評論家網(wǎng)絡(luò)采用隨機(jī)梯度下降的方法訓(xùn)練網(wǎng)絡(luò)參數(shù),其目標(biāo)函數(shù)為均方誤差表示,如式(19)所示:

3.5.3 算法流程

綜合上述分析,可以將本文模型的訓(xùn)練算法流程總結(jié)為算法1.

算法1.Actor-Critic 訓(xùn)練算法輸入:訓(xùn)練集,訓(xùn)練步數(shù),批樣本容量θ X T B輸出:返回網(wǎng)絡(luò)參數(shù)初始化網(wǎng)絡(luò)參數(shù)for step=1 to T do～sample(X)for i=1,2,···,B xi for i=1 to B do for i=1 to N do～ε?greedy(pθ(·|yi,1,yi,2,···,yi,t?1))xi,t orii,t←(xi,t,orii,t)～ε?greedy(pθ(·|yi,1,yi,2,···,yi,t?1))bi yi,t←bφ(xi)end for end for?θLθ|x←1 B∑Bi=1(reward(yi|xi)?bφ(xi))?θ log pθ(yi|xi)L?|x=1 B∑Bi=1||b?(xi)? (yi| xi)||22 reward θ←ADAM(θ,?θLθ|x)ADAM end for return θ ?← (?,?φL?|x)

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)集準(zhǔn)備

本文介紹的基于機(jī)器學(xué)習(xí)的算法性能和數(shù)據(jù)集有較強(qiáng)的關(guān)聯(lián)性,為了能夠合理比較本文所介紹算法的性能,本文參考了目前流行的二維排樣問題研究的數(shù)據(jù)集,分別生成了用于訓(xùn)練和測試的多邊形,其中訓(xùn)練集10 000 組,測試集300 組,每組又分為10、15、20 個多邊形3 種情況,每種數(shù)量的數(shù)據(jù)集又分可旋轉(zhuǎn)(R)與不可旋轉(zhuǎn)(NR)兩種情況.多邊形的頂點(diǎn)數(shù)量在[3,8]之間,面積在[50,300]之間.由于本文主要考慮質(zhì)心在多邊形內(nèi)部的情況,因此當(dāng)生成的多邊形質(zhì)心在多邊形外部時,則將其丟棄.為了加速訓(xùn)練過程,本文在數(shù)據(jù)集生成后進(jìn)行數(shù)據(jù)的預(yù)處理,即計(jì)算每個圖形的特征向量,以及每一組多邊形的NFP 并進(jìn)行本地緩存.

4.2 實(shí)驗(yàn)設(shè)置

排樣寬度為80,最小旋轉(zhuǎn)角度為90 度,優(yōu)化目標(biāo)為排樣后多邊形圍成的矩形長度L.模型使用Adam 優(yōu)化器[19]訓(xùn)練300 個epoch 完成,并在測試集上進(jìn)行測試,訓(xùn)練過程中采用梯度截?cái)喾乐固荻缺ǖ漠a(chǎn)生.其中,神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練在NVIDIA GeForce RTX 2080Ti GPU 上完成,重疊檢測、獎勵值計(jì)算等操作以及傳統(tǒng)方法如啟發(fā)式算法及遺傳算法的計(jì)算在Intel Xeon E5-2667 v4 CPU 上完成.

為了驗(yàn)證本文模型的效果,本文與隨機(jī)法、啟發(fā)式算法以及經(jīng)典的遺傳算法[20]進(jìn)行實(shí)驗(yàn)對比.其中啟發(fā)式算法對零件分別按特定規(guī)則進(jìn)行排序(如面積、長度等),結(jié)果取其各種排列方式的最優(yōu)值;遺傳算法具體的參數(shù)如表3所示,其中變異包括了交叉與旋轉(zhuǎn)兩種情況.

表3 遺傳算法參數(shù)

在確定定序算法以后,本文使用左下填充定位法(bottom left fill)作為排樣的定位算法[21].按定序算法生成的排樣順序,將零件逐個盡可能地排到底部,再向左進(jìn)行平移,使其盡可能靠近最左側(cè).并在所有空間與已排樣件依次進(jìn)行重合試排,盡可能地將未被利用的空余空間填滿,從而減少中空的區(qū)域,提高了整體的排樣利用率.

4.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)階段使用不同方法對各測試集進(jìn)行排樣,取其排樣長度的均值為實(shí)驗(yàn)結(jié)果,如表4所示.其中,本文算法與隨機(jī)法均采用了“多次采樣”的策略,取其中的最優(yōu)排樣長度為實(shí)驗(yàn)結(jié)果.由于遺傳算法的限制是每換一組輸入序列都要重新花費(fèi)時間來進(jìn)行迭代計(jì)算,本文的目標(biāo)是使用機(jī)器學(xué)習(xí)方法設(shè)計(jì)一個通用的求解模型,能夠從數(shù)據(jù)中學(xué)習(xí)到高維特征,對新的輸入也能在最短的時間預(yù)測出較優(yōu)的解決方案,減少運(yùn)行遺傳算法所需的多余計(jì)算時間.為突出本文算法相較于遺傳算法在運(yùn)行時間上的優(yōu)勢,本文算法將采樣次數(shù)設(shè)置為100,耗費(fèi)時間約為遺傳算法進(jìn)行3 次迭代所用時間.由實(shí)驗(yàn)結(jié)果可以觀察到,在運(yùn)行時間大幅減少的前提下,本文算法仍能夠得到比其它算法更優(yōu)的解,這在一定程度上驗(yàn)證了本文算法的可行性.由于本文在解碼器中加入了注意力機(jī)制,模型能夠根據(jù)已排列零件的信息對下一個零件的序號以及方向進(jìn)行預(yù)測,相比遺傳算法,能夠使得新排入的零件盡可能地貼合已排列的零件,面積利用率更高.同時,為了優(yōu)化排樣長度,模型需要同時考慮尚未排列的零件信息,做到兩者之間的平衡.

表4 排樣長度均值實(shí)驗(yàn)結(jié)果

此外,無論是深度強(qiáng)化學(xué)習(xí)法還是遺傳算法均有一定的排樣優(yōu)化空間.排樣效果在一定程度上受旋轉(zhuǎn)角度約束的影響,理論上最小旋轉(zhuǎn)角度越小,能夠得到最優(yōu)排樣的可能性就越高.但是旋轉(zhuǎn)角度過多會使網(wǎng)絡(luò)的訓(xùn)練變得十分復(fù)雜,且遺傳算法也非常難以收斂于最優(yōu)解.為了簡化問題復(fù)雜度,本文將最小旋轉(zhuǎn)角度僅限制在90°,即一個零件僅有4 個方向可用于排樣.雖然對旋轉(zhuǎn)角度進(jìn)行了限制,但是通過本文方法可以迅速獲得較優(yōu)的初始解,隨后可以使用收縮法[22]對該解進(jìn)行優(yōu)化.

此外,本文將排樣空間的寬度W固定為80,以便于模型的訓(xùn)練,為了把模型推廣到其他高度,可以使用縮放的思路,即對于其他排樣寬度W′,將多邊形同比縮放到W′/W倍后再進(jìn)行特征提取,接下來便可以使用預(yù)訓(xùn)練 后的模型進(jìn)行多邊形的排樣.

5 結(jié)論與展望

本文為不規(guī)則多邊形的排樣問題設(shè)計(jì)了一種基于Actor-Critic 算法與編解碼結(jié)構(gòu)的多任務(wù)深度強(qiáng)化學(xué)習(xí)模型.通過質(zhì)心到輪廓的距離提取多邊形的形狀特征,并將該特征映射到定長的一維向量中,使得神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)到多邊形的語義信息,并對排樣順序、旋轉(zhuǎn)角度進(jìn)行預(yù)測.由于本文中特征提取是基于有損的方法,本文方法缺點(diǎn)在于無法處理復(fù)雜的圖形排樣,在算力允許的條件下,未來可以考慮使用無損的形狀特征來處理復(fù)雜圖形.此外,如果更換數(shù)據(jù)集,則可能需要重新對模型進(jìn)行訓(xùn)練,但是通過預(yù)訓(xùn)練的方法,可以使得網(wǎng)絡(luò)能夠適應(yīng)新的數(shù)據(jù)集,因此本文模型具有一定的泛化能力.通過與傳統(tǒng)排樣算法的對比,本文在最佳排樣長度、運(yùn)算時間等指標(biāo)均有一定優(yōu)勢,能夠在最短時間生成合理的排樣圖,并為大規(guī)模排樣的解決提供了可能性,具有實(shí)際的研究與應(yīng)用前景.