曾煥榮,商慧亮

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

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

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

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

1 問(wèn)題描述與求解框架

1.1 問(wèn)題描述

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

表1 變量定義

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

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

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

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

1.2 求解框架

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

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

1.3 重疊檢測(cè)

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

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

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

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

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

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

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

2 形狀特征提取

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

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

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

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

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

在求得多邊形的質(zhì)心以后,可通過(guò)歐式距離計(jì)算公式獲得質(zhì)心到輪廓的距離,主要思路為:從以質(zhì)心為原點(diǎn)發(fā)散N條射線,相鄰射線之間的距離為,選定一條起始射線,取質(zhì)心到交點(diǎn)的距離加入特征向量中,若射線與形狀之間有多個(gè)交點(diǎn),則取距離質(zhì)心最遠(yuǎn)的交點(diǎn)并把該距離加入特征向量中,如圖2所示,該圖形的質(zhì)心坐標(biāo) (xc,yc)=(5,5),當(dāng)向量維度為10×1 時(shí),從該圖形的質(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)證形狀提取特征的效果,本文對(duì)特征向量進(jìn)行形狀重建,并與原形狀作對(duì)比.本文隨機(jī)生成了3 030個(gè)頂點(diǎn)個(gè)數(shù)在3–8 個(gè)之間的多邊形加入測(cè)試.使用N=180對(duì)圖形進(jìn)行向量化表示,并對(duì)該向量進(jìn)行形狀重建,以評(píng)價(jià)該向量對(duì)圖形的表示效果.評(píng)價(jià)指標(biāo)有兩個(gè),分別為:(1)面積覆蓋率(ACR),用于評(píng)價(jià)重建后的形狀對(duì)原有圖形的覆蓋情況;(2)面積超出率(AER),用于表示重建后的形狀超出原有圖形部分的占比.通過(guò)統(tǒng)計(jì)這兩個(gè)指標(biāo)不同范圍內(nèi)的形狀個(gè)數(shù),可以評(píng)價(jià)出該向量對(duì)形狀特征的提取效果.結(jié)果如表2所示.

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

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

3 算法描述

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

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

3.2 Actor-Critic 算法

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

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

Critic 網(wǎng)絡(luò)也稱(chēng)估值網(wǎng)絡(luò),通過(guò)計(jì)算值函數(shù)來(lái)評(píng)估策略.根據(jù)Actor 網(wǎng)絡(luò)的動(dòng)作評(píng)價(jià)策略的價(jià)值,并反饋給Actor 網(wǎng)絡(luò),網(wǎng)絡(luò)輸出是對(duì)目標(biāo)函數(shù)的預(yù)測(cè).

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

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

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

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

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

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

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

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

其中,π (j)表示j號(hào)零件被選擇的時(shí)間,如果沒(méi)有被選擇過(guò),則該值為0.

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

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

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

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

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

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

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

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

其中,reward為對(duì)oi使用如啟發(fā)式算法這類(lèi)的傳統(tǒng)方法后求解得到的值,但是若在大規(guī)模的訓(xùn)練集上使用傳統(tǒng)方法進(jìn)行基準(zhǔn)值的求解,無(wú)疑會(huì)造成大量時(shí)間與資源的浪費(fèi).另外一種方法是使用Critic 網(wǎng)絡(luò)來(lái)預(yù)估輸入序列的基準(zhǔn)值,訓(xùn)練好的Critic 網(wǎng)絡(luò)能夠較好地預(yù)估基準(zhǔn)值,在節(jié)約了使用傳統(tǒng)方法計(jì)算基準(zhǔn)值時(shí)間的同時(shí),降低了梯度方差,顯著地提升了模型的性能[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個(gè)處理塊,則對(duì)編碼器中的隱層向量進(jìn)行m次運(yùn)算,并運(yùn)用glimpse 機(jī)制消除輸入序列間的依賴(lài)關(guān)系.最后,在得到最后一個(gè)處理塊的輸出以后,輸入到層數(shù)分別為l和1的兩個(gè)全連接層當(dāng)中,將最后一個(gè)全連接層的輸出作為對(duì)基準(zhǔn)值b(si)的預(yù)測(cè),即si序列預(yù)期獲得的獎(jiǎng)勵(lì)值.

3.5 訓(xùn)練

3.5.1 探索與利用

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

3.5.2 損失定義

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論與展望

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