一種基于并行交叉遺傳算法的二維不規則排樣問題求解

王靜靜 瞿少成 李科林

(華中師范大學物理科學與技術學院電子信息工程系 湖北 武漢 430079)

0 引 言

二維不規則排樣問題是指在給定的原材料板材空間上，合理放置若干不規則零件，使得零件之間互不重疊且板材利用率最大。該問題在服裝裁剪[1]、印刷包裝[2]、鈑金零件加工[3]、玻璃切割[4]等行業應用廣泛，是實際工業生產加工中的關鍵環節。同時，該問題可以歸為一類復雜的NP完全問題[5]，因此，長期以來受到國內外眾多學者的關注。

二維不規則排樣問題涉及運籌學、幾何數學等眾多學科，屬于典型的組合優化問題。近年來，二維不規則排樣問題常采用啟發式算法或智能優化算法求解。文獻[6]提出了一種多目標啟發式進化算法求解考慮批量問題的二維矩形件排樣問題，文獻[7]提出了一種基于重心臨界多邊形的啟發式排樣算法。可以看出，啟發式算法實現簡單，能夠快速給出求解方案，但難以取得全局最優解。因此，目前常采用模擬退火算法、遺傳算法等智能優化算法解決排樣優化問題。

遺傳算法通過模擬自然進化過程搜索最優解，全局搜索能力優秀，適合大規模空間求解復雜問題[8]，將其應用到排樣問題的求解上可以取得較好的排樣效果。文獻[9]結合遺傳算法和最低水平線算法求解矩形件排樣問題，但其尋優能力有待進一步改進。文獻[10]利用基于排擠機制的小生境遺傳算法求解排樣順序優化問題，但是算法效率有待提高。

針對以上問題，本文提出了一種基于并行交叉遺傳算法的排樣優化算法。結合排樣問題的特點，模擬了兩個獨立島上的生物雜交進化過程，構造了一個包含零件排放順序和旋轉角度的初始編碼序列，分別按照隨機和零件面積降序的方式生成排樣初始種群。主過程的交叉操作采用與從過程進化產生的最優個體雜交的方式，提高算法的收斂速度和尋優能力，從而優化二維不規則排樣問題的求解。

1 問題描述和數學模型

二維不規則多邊形排樣問題的具體描述為：在生產過程中，根據相應的工藝需求，將若干不規則零件互不重疊地放置在給定的寬度固定、長度不限的矩形板材內部，各個零件可以被旋轉一定的角度，使得排樣后原材料的利用率最高。

約束條件：

Ri∩Rj=?(i≠j)

(1)

Ri∈R

(2)

Oi∈O

(3)

目標函數：

minL=max{x|(x,y)∈Ri1≤i≤n}-

min{x|(x,y)∈Ri1≤i≤n}

(4)

(5)

式(1)保證各個零件之間不能重疊；式(2)保證排放后所有不規則零件都位于板材內部；式(3)中O為零件對應旋轉的角度。

圖1為一組二維不規則零件排樣結果。假設原材料矩形R的寬度為W，需排放n個二維不規則零件{R1,R2,…,Rn}，Si表示第i個零件的面積，L為排樣的最短長度，ρ表示原材料利用率。

圖1 二維不規則零件排樣結果

2 算法設計

傳統遺傳算法常采用隨機的方式生成初始種群，但這種方法產生的個體不一定是優秀的，且在排樣問題的高維解空間進行隨機搜索的效率較低，導致收斂速度變慢。此外，進化過程中的交叉操作幾乎都是在大規模離散空間中隨機進行的，這種搜索方式在進化初期能保證解的多樣性，但在進化后期，種群中就會出現大量相似個體，容易收斂于局部極值，出現早熟現象。因此，本文基于并行交叉遺傳算法求解二維不規則排樣問題。

2.1 個體編碼方式及構造初始種群

2.1.1個體編碼方式

本文基于對象的數據結構索引對個體進行編碼，對于包含n個待排放零件的排樣問題，可行解是由n個對象組成的序列，序列中每個零件對象都包含排放順序和旋轉角度兩個變量。

將待排放的n個零件按照排放順序編號，構成了一個整數序列{X1,X2,…,Xn}，Xi為第i個排放入板材的多邊形零件編號，Oi為第i個零件排放時相應的旋轉角度，1≤Xi≤n。每個可行解序列可以表示為：{(X1,O1),(X2,O2),…,(Xn,On)}，其中(Xi,Oi)表示編號為Xi的零件旋轉Oi度后排放。3個不規則零件排樣后的一個可行解為X={(1,0),(3,90),(2,180)}，其中零件的排放順序為1、3、2。編號為1的零件旋轉0°排放，編號為3的零件旋轉90°后排放，編號為2的零件旋轉180°排放。

2.1.2構造初始種群

在遺傳算法中，初始種群的質量對算法的收斂速度和尋優能力影響較大。隨機生成初始種群的方式可以保證個體的多樣性，在排樣問題中，這種方法產生的初始解中零件的排放順序和旋轉角度都是隨機的。當零件數量較多時，解空間的規模會比較大，搜索范圍很廣，很難在一定時間內搜索到最優解，求解效率大大降低。

為了獲得高質量的初始種群，通過構造兩個獨立島上的進化過程A和B，本文提出了一種并行交叉遺傳算法。主過程A的初始種群通過隨機生成的方式構造，從過程B的初始種群則通過借鑒手工排樣的經驗，按照零件的面積從大到小排序生成，可以取得更好的排樣效果。

2.2 個體定位策略及適應度計算

2.2.1個體定位策略

計算個體適應度之前，需要在板材上為待排放的多邊形零件選擇一個合適的排放位置。這一過程常常涉及到很多復雜的幾何計算，如計算多邊形之間的最佳靠接位置、重疊判斷等。

在早期研究中，文獻[11]采用BL準則定位零件位置，該算法實現簡單，被廣泛應用于排樣問題的求解，但其容易造成空腔的浪費，且定位位置不一定是最優解。針對BL定位策略存在的問題，本文使用臨界多邊形(NFP)[12]判定零件之間的位置關系，同時結合BL定位原則，盡量選擇NFP最左、最下方的頂點排放零件，可以解決BL算法定位位置不合理的問題。基于NFP和BL準則的定位策略步驟描述如下：

Step1初始化排樣種群，獲得零件排樣序列。

Step2對于排樣序列中的零件A(Xi,Oi)，將其按照角度Oi旋轉后，構造零件與原材料板材B的NFPAB。

Step3在NFPAB選擇最左、最下的頂點作為零件A的排放位置。

Step4若零件序列中還存在待排放的零件，減去原材料B中的已排放的零件A，作為剩下的板材區域B放置待排放零件，轉到Step 2；否則，結束零件排放過程。

2.2.2適應度計算

在求解二維不規則排樣問題時，追求的目標就是使得原材料板材的利用率最大化。為了使適應度函數能夠更好地反映排樣方案的優劣，且盡可能使計算簡單，本文定義適應度函數如下：

F(Xi)=Sum/(W×Lmax(Xi))

(6)

圖2 最小的原材料板材長度

適應度函數值F(Xi)表示可行解Xi對應的板材利用率，F(Xi)越大，其對應可行解序列的質量越好。

2.3 并行交叉遺傳算法的進化過程

2.3.1選擇操作

種群經過交叉和變異之后，一部分個體將被挑選出來產生下一代群體，這個過程即為選擇操作。選擇過程中，通常基于個體的適應度進行優勝劣汰操作，適應度高的個體更容易進入下一代，適應度低的個體則被淘汰，這樣有利于優良基因的擴展。

目前常用的選擇方法有輪盤賭法、隨機遍歷選擇法及錦標賽選擇法等。本文基于保留最佳個體策略，采用輪盤賭法對執行交叉操作的兩個父代個體進行選擇，步驟如下：

Step1保留父代中適應度函數值最大的個體至下一代，并在父代中將其移除。

Step4重復Step 3，直至新的種群構建完成。

2.3.2交叉操作

常用的交叉操作有循環交叉法、部分匹配法、次序交叉法等方法。本文提出的并行交叉遺傳算法采用順序循環交叉法，即隨機生成兩個處于[1,n]之間的不同正整數作為交叉點位置Bit1和Bit2，保持兩個父代染色體Bit1和Bit2之間的基因不變，其余基因按照另一條染色體上的基因位置順序選取基因進行填充，且跳過已經出現的基因。這種交叉方法每次可產生兩個子代染色體，其交叉過程如圖3所示。

圖3 交叉操作

2.3.3變異操作

根據二維不規則排樣問題的具體情況和特點，我們選擇交換變異法進行變異操作。在執行變異操作時，需要通過變異概率pm與在[0,1]內生成的隨機數p的大小進行對比，來確定是否需要進行變異操作。當pm>p時執行變異操作；否則，不執行變異操作。

交換變異需要在[1,n]之間隨機生成兩個不同的正整數作為變異的位置Bit1和Bit2，其中0≤Bit1

圖4 交換變異

2.4 基于并行交叉遺傳算法的排樣優化算法

本文基于并行交叉遺傳算法求解二維不規則排樣優化問題，其主要思想是模擬兩個獨立島上的生物雜交進化過程。

首先，建立兩個進化過程A和B。主過程A的初始種群是隨機生成的，從過程B的初始種群按照零件面積從大到小排序生成。此外，A的每次進化都通過與B每次進化產生的最優個體進行雜交產生新的子代。在進化過程中，主過程A初始種群的隨機性保證了種群的多樣性，搜索解空間時包含了更多可能性；從過程B的初始種群借鑒了人工排樣的先驗知識，本身就是局部較優解，通過雜交可以為主過程的進化指導方向。這種模擬兩個獨立島嶼進化雜交的并行交叉遺傳算法加快了全局收斂速度，在短時間內就可以搜索到更優解。

結合基于臨界多邊形的BL定位策略和并行交叉遺傳算法的分析，本文提出的基于并行交叉遺傳算法的二維不規則排樣優化算法，步驟如下：

Step1隨機生成主過程A的初始排樣種群，按面積降序生成從過程B的初始種群(種群大小均為N)，分別產生N個個體。

Step2分別對種群A、B中的個體采用基于臨界多邊形的BL定位策略排放零件，計算所有個體的適應度函數，并按照適應度函數值的大小降序排列，保存種群B中的最優個體。

Step3對兩個種群中的個體執行選擇、交叉、變異操作后，分別產生N個新的個體。其中，將Step2中保存下來的種群B中的最優個體作為種群A執行交叉操作時的一個父代。

Step4對Step 3中產生的新個體繼續執行Step 2。同時，種群A和種群B分別保存最好的N個個體。

Step5判斷算法是否滿足終止條件。若不滿足，兩種群分別將Step 4中各自保存的個體作為新種群，繼續執行Step 3；否則，輸出當前種群A的最好個體，算法結束。

并行交叉遺傳算法的流程圖如圖5所示。

圖5 并行交叉遺傳算法

3 實 驗

為了驗證算法的可行性和有效性，采用Java語言實現了本文的排樣優化算法，并基于ESICUP提供的幾個基準用例測試了算法性能。

實驗統一采用原材料板材的利用率ρ作為主要比較參數，其計算公式如下：

(7)

表1為并行交叉遺傳算法的相關配置參數。實驗時對于每個測試用例都進行了10次實驗，并從板材的最優利用率和平均利用率兩方面將本文算法的實驗結果與TOPOS[13]算法和傳統遺傳算法的結果進行了比較。采用傳統遺傳算法求解排樣問題的實驗數據來源于文獻[14]。詳細的實驗結果對比見表2和表3。

表3 算法比較

觀察表2和表3可以發現，在求解二維不規則排樣問題時，本文采用的并行交叉遺傳算法結果均優于傳統遺傳算法。與TOPOS算法相比，本文算法的排樣效果明顯更優，尤其是SHIRTS用例，原材料利用率明顯提高。

上述測試用例的排樣效果圖見圖6。由于SHAPES0、SHAPESl用例包含較多凹度較大的凹多邊形的零件，排放時容易形成空洞和凹槽區域，且基于單一BL定位規則排放時，這種區域難以得到很好的利用。因此，本文算法對這兩個用例的排樣效果變差。對于MARQUES和TROUSERS這種以凸多邊形為主的用例，本文排樣策略與遺傳算法相結合后，可以獲得較高的原材料利用率。

圖6 基于并行交叉遺傳算法的排樣結果

此外，排樣結果中最優利用率和平均利用率的值比較接近，說明并行交叉遺傳算法在有限的進化代數下比較穩定。因此，本文提出的排樣優化算法具有很強的實用性，可以有效解決實際加工生產中的二維不規則排樣問題。

圖7為MARQUES測試樣例的最優解進化收斂曲線，可以看出種群經過較少的進化次數就趨于收斂，說明并行交叉遺傳算法具有較快的全局收斂速度。

圖7 MARQUES最優解進化收斂曲線圖

另外，隨著進化代數的遞增，曲線逐漸趨于穩定值，表明本文算法穩定可行。其中，曲線的平穩部分表示算法暫時處于局部最優狀態，出現階梯跳變則表示在解空間內搜索到了更優解。

4 結 語

針對工業生產加工中廣泛存在的二維不規則排樣問題，本文提出了一種基于并行交叉遺傳算法的排樣優化算法。根據排樣問題的特點，基于零件的排放順序及排樣旋轉角度對個體進行了編碼，并通過隨機和按零件面積降序的方式生成了兩個進化過程的初始種群，提高了算法的搜索效率。通過模擬兩個獨立島上的生物雜交進化過程，改進了遺傳算法中主進化過程的交叉策略，提高了全局尋優能力。對ESICUP提供的基準用例測試結果表明，該算法可以有效處理二維不規則排樣問題，是一個可行且排樣性能較好的排樣優化方法。