基于深度強化學習的二維不規則多邊形排樣方法①

曾煥榮,商慧亮

(復旦大學 工程與應用技術研究院,上海 200433)

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

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

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

1 問題描述與求解框架

1.1 問題描述

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

表1 變量定義

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

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

同時,以上目標函數需要滿足以下約束:

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

1.2 求解框架

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

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

1.3 重疊檢測

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

圖1 臨界多邊形構建過程

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

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

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

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

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

2 形狀特征提取

在機器學習中,常常需要用向量或矩陣來表示學習對象,作為網絡的輸入.向量或矩陣之間的歐氏距離也是衡量兩個目標之間相似性的一個指標.

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

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

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

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

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

圖2 形狀特征向量提取

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

表2 形狀重建結果

由此可見,基于質心-輪廓距離的特征提取法能夠基本實現1%以內的壓縮損失,足以表達形狀的語義信息,便于神經網絡的訓練.此外,本文對不同的N的重建效果也進行了測試,測試結果發現重建效果也跟N的大小相關,即N越大(小于360),面積覆蓋率就越大,面積超出率就越小,重建效果越好.

3 算法描述

3.1 編碼器-解碼器結構

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

3.2 Actor-Critic 算法

Actor-Critic 算法源于策略梯度[17]方法,并在此基礎上結合了基于值函數的方法.Actor-Critic 算法需要同時訓練Actor和Critic 兩個神經網絡,分別負責學習策略和值函數:

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

Critic 網絡也稱估值網絡,通過計算值函數來評估策略.根據Actor 網絡的動作評價策略的價值,并反饋給Actor 網絡,網絡輸出是對目標函數的預測.

3.3 Actor 網絡結構

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

圖3 Actor 網絡架構圖

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

通過把t時刻前產生的零件隱層向量與其權重進行加權求和,可以得到解碼器在t時刻的權重向量:

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

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

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

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

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

通過把atttd、attet、hdt進行向量拼接,我們可以得到t時刻的語義向量,本文使用該向量進行零件旋轉角度的預測,如式(13)所示:

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

編碼器-解碼器模型中,編碼器負責處理輸入的排樣件信息.一個排樣實例中的元素應該是無序的,而在編碼器中零件的形狀信息是按順序輸入到神經網絡的,會對神經網絡的求解造成一定的影響[16].因此,本文在原有模型的基礎之上,加入glimpse 機制.這一操作可以在計算時間不明顯增加的同時,能夠較好地消除輸入順序對輸出結果的影響.則零件被選擇的概率可以通過以下公式得到:

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

3.4 Critic 網絡結構

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

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

其中,reward為對oi使用如啟發式算法這類的傳統方法后求解得到的值,但是若在大規模的訓練集上使用傳統方法進行基準值的求解,無疑會造成大量時間與資源的浪費.另外一種方法是使用Critic 網絡來預估輸入序列的基準值,訓練好的Critic 網絡能夠較好地預估基準值,在節約了使用傳統方法計算基準值時間的同時,降低了梯度方差,顯著地提升了模型的性能[18].

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

3.5 訓練

3.5.1 探索與利用

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

3.5.2 損失定義

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

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

評論家網絡采用隨機梯度下降的方法訓練網絡參數,其目標函數為均方誤差表示,如式(19)所示:

3.5.3 算法流程

綜合上述分析,可以將本文模型的訓練算法流程總結為算法1.

算法1.Actor-Critic 訓練算法輸入:訓練集,訓練步數,批樣本容量θ X T B輸出:返回網絡參數初始化網絡參數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 實驗與結果分析

4.1 數據集準備

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

4.2 實驗設置

排樣寬度為80,最小旋轉角度為90 度,優化目標為排樣后多邊形圍成的矩形長度L.模型使用Adam 優化器[19]訓練300 個epoch 完成,并在測試集上進行測試,訓練過程中采用梯度截斷防止梯度爆炸的產生.其中,神經網絡模型的訓練在NVIDIA GeForce RTX 2080Ti GPU 上完成,重疊檢測、獎勵值計算等操作以及傳統方法如啟發式算法及遺傳算法的計算在Intel Xeon E5-2667 v4 CPU 上完成.

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

表3 遺傳算法參數

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

4.3 實驗結果與分析

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

表4 排樣長度均值實驗結果

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

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

5 結論與展望

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