改進的雙種群遺傳算法在矩形件排樣中的應用

孫佳正，郭 駿

華東師范大學 計算機科學與軟件工程學院，上海 200062

1 引言

矩形件排樣優化問題是指把一定數量的矩形件排放到矩形板材上，在排樣后矩形件之間不能重疊且矩形件不能超出板材的邊界條件下，使得矩形板材的利用率盡可能的高。矩形件排樣優化問題常見于制造業中，例如玻璃、布料，鋼材切割等場景，關系到生產中材料的利用率，具有較高的經濟價值與研究價值。此問題是NP完全組合優化問題，在大規模矩形件排樣問題中，由于計算復雜度大，難以在短時間內找到最優解，因此一般研究方向是尋找啟發式算法尋找接受的較優解。

矩形件排樣優化問題一般可以分為排序和排放兩個步驟，即確定矩形件排放的先后順序和矩形件在板材中的排放方式，然后按照給定的排放方式，按順序逐個排放矩形件。早期生產中由人工排樣，耗時長，材料利用率低，增加了企業的生產成本。20世紀90年代以來，隨著計算機的興起，國內外學者從智能優化的角度對計算機輔助排樣進行相關研究，一般采用啟發式算法對排放順序進行尋優，例如遺傳算法[1-2]、模擬退火算法[3-4]、蟻群算法[5]等。在排放算法方面提出了BL排樣算法，最低水平線排樣算法。

Baker[6]提出BL排樣算法，按照最左最下的規則排放矩形件。Jakobs[7]采用遺傳算法求解排序，并采用與BL排樣算法相結合的方式解決矩形件排樣問題。針對BL排樣算法易產生矩形件傾斜的缺陷，Liu[8]提出了一種改進的BL算法，向下向左移動矩形件時，優先向下移動，并與遺傳算法結合起來解決矩形件排樣問題。Soke[9]分別將遺傳算法、模擬退火算法與改進的BL排樣算法進行結合并對比排樣效果。賈志欣[10]提出最低水平線排樣算法，即在最低高度的水平線上靠左排放矩形件。龔志輝[11]提出了最低水平線搜索算法，當最低水平線的寬度小于待排矩形件，向后搜索一個小于最低水平線的寬度的矩形件，然后交換這個矩形件與當前待排矩形件的排放順序。Liu[12]提出分階段遺傳算子來改進遺傳算法，當遺傳陷入停滯時，改變遺傳算子來跳出局部極值，并與最低水平線排樣算法結合起來處理矩形件排樣問題。劉海明[13]結合了分階段遺傳算子與最低水平線搜索算法。

本文主要工作：結合了遺傳算法與最低水平線搜索排樣算法，即利用遺傳算法對排放順序尋優，使用最低水平線搜索排樣算法排放矩形件，并分別加以改進。（1）傳統的遺傳算法采用一般的交叉方法在大規模離散空間內隨機搜索最優解時容易出現收斂速度慢，陷入局部極值，穩定性差等問題。針對此缺陷，引入部分按照面積大小排序的個體以達到加速收斂的目的。因為在生產中工人單純地按照矩形件面積大小的順序排樣通常比隨機順序排樣效果好。然而在同一種群中，這部分個體比隨機個體適應度高，迭代前期快速擴散，使得種群多樣性降低，導致遺傳算法過早熟。采用雙種群策略對遺傳算法的初始種群進行優化，一個種群按照矩形件面積從大到小的排序生成，另一個種群隨機生成。按照矩形件面積從大到小的排序生成的種群通過特定交叉方式與隨機初始化的種群進行基因交流，并保證子代個體大體上按照面積大小排序局部亂序，大體有序的基礎上在解空間內進行搜索。（2）最低水平線搜索排樣算法的改進：傳統的最低水平線搜索排樣算法只有在最低水平線的寬度小于待排矩形件的寬度時才會向后搜索合適的矩形件排放在最低水平線上。為增加搜索發生的時機，改進后的算法可以在排樣的同時啟發式判斷在未排放的矩形件中是否有更合適的矩形件可以替換當前要排放的矩形件。更加頻繁地動態調整矩形件的排放順序，相當于增強了遺傳算法的局部搜索能力。

2 矩形件排樣問題的描述

在不同的生產環境下，矩形件排樣問題描述可能有所不同，此問題一般化語言描述：給定一組長度寬度已知的矩形件，將它們排放到寬度固定，高度不限的矩形板材上，滿足要求：（1）矩形件之間不能重疊。（2）矩形件不能超出板材邊界。（3）矩形件可以90°旋轉后排放，排放后矩形件的底邊與板材底邊平行。矩形件排樣問題的目標是求出達到板材利用率最大的排樣方案。其中板材利用率的定義為這組矩形件面積之和與耗用板材材料面積之比。

矩形件排樣問題數學語言描述：設矩形板材的底邊寬度為W，n個矩形件(p1,p2,p3,…,pn)，第i個矩形件pi的寬度為wi，高度為hi，排放后左下角的橫坐標與縱坐標為xiyi。

H為n個矩形件排放完成后，所有矩形件上邊距離板材底邊的最大高度，如圖1所示。E為板材的利用率：矩形件面積之和與耗用板材材料面積之比。

圖1 所有矩形件上邊距離板材底邊的最大高度

矩形件排樣優化問題可描述為，滿足約束條件的同時，求解板材最大的利用率式（1）的最佳排樣方案：

且滿足約束條件：

（1）矩形件排放后不超出板材邊界。

（2）排放后的矩形件互不重疊。

3 最低水平線啟發式搜索排樣算法

龔志輝[11]提出最低水平線搜索排樣算法，排樣規則是在最低高度的水平線上靠左排放矩形件，如果高度最低的水平線有多條，在最左邊的一條排放矩形件。當排放不下當前待排放矩形件時，向后搜索一個小于最低水平線的寬度的矩形件，然后交換這個矩形件與當前待排矩形件的排放順序。找不到合適的矩形件時，提升最低水平線的高度到與之相鄰水平線中較低的一條的高度，合并高度相同的水平線，每次提升最低水平線時都會形成無法利用的空洞。趙新芳[14]在此基礎上提出基于最低水平線的擇優搜索，向后搜索能排放到最低水平線上寬度最大的，并且插入到當前待排放矩形件之前排放而不是交換排放順序，為了防止大尺寸矩形件累積到后面排放。

然而傳統的最低水平線搜索排樣算法只有在最低水平線的寬度小于待排矩形件的寬度時才會向后搜索，搜索的頻率低，調整排樣順序的機會少。本文提出的最低水平線啟發式搜索排樣算法可以在排樣的同時進行搜索，啟發式判斷是否有更合適的矩形件排放在當前位置。

3.1 最低水平線搜索排樣算法改進處理

本文改進后的算法在當前矩形件排放在最低水平線上后，最低水平線的剩余寬度無法繼續排放任何未排放的矩形件時包括剩余寬度為0的特殊情況，判斷在未排放的矩形件中是否有更合適的矩形件可以替換當前矩形件，更加頻繁的動態調整矩形件的排放順序。改進的最低水平線排樣過程如下：

（1）初始化水平線的集合，當前只包含一條水平線，即板材的底邊。初始化排放順序，按照順序逐個排放矩形件。

（2）在水平線集合中找到高度最低的水平線，如果有多條，選擇最左的一條。對當前待排矩形件 pi，判斷是否可以排放到最低水平線上，如果可以轉入步驟（4）。如果不可排放，轉入步驟（3）。

（3）向后搜索未排放的矩形件，找到的第一個可以排放到最低水平線上的矩形件 pj，把搜索到的矩形件 pj作為當前要排放矩形件，原待排放矩形件 pi作為下一個等待排放的矩形件，轉入步驟（4），如果找不到轉步驟（5）。

（4）最低水平線寬度減去待排放矩形寬度作為剩余的最低水平線，在排放矩形件之前向后搜索未排放矩形件中有沒有矩形件能繼續排放到剩余的最低水平線上，如果有，轉入步驟（5）。如果沒有，則在所有未排放的矩形件中尋找可以排放在最低水平線上，寬度最大的矩形件。如果有多個，則選擇最高的矩形件 pm，并與當前待排放矩形件交換排放的順序。

（5）在最低水平線上靠左排放當前矩形件。更新水平線集合，選擇下一個待排放矩形件，轉入步驟（2）。若所有矩形件都排放完畢，結束。

（6）升高最低水平線到與之相鄰水平線中較低的一條的高度，合并相同高度的水平線，更新水平線集合，轉入步驟（2）。

改進后的最低水平線排樣算法可以更加頻繁的動態調整矩形件排放的順序，相當于彌補遺傳算法局部搜索能力不足的缺陷，同時盡可能地利用板材的空間。改進的最低水平線排樣算法流程如圖2所示。

3.2 最低水平線啟發式搜索排樣算法原理

改進的原理是排樣時先排放大的矩形件，后排放小的矩形件。大的矩形件排放時產生的空洞，可以用小的矩形件來填充。

當前等待排放的矩形件排放后，最低水平線剩余的寬度無法繼續排放任何未排放的矩形件時，傳統的最低水平線搜索排樣算法會提高最低水平線，形成無法利用的空洞。本文改進的算法在這種情況下可以在所有未排放的矩形件中尋找可以排放在最低水平線上，寬度最大的矩形件 pm，并與當前待排放矩形件交換排放的順序，盡可能地利用最低水平線的寬度。交換排放順序目的是讓大矩形件先排放，小的矩形件后排放。

圖2 改進的最低水平線排樣算法流程圖

傳統的最低水平線搜索排樣算法按順序排放矩形件{p1p2p3p4p5p6},p1p2p3p4排放后如圖3所示，傳統的最低水平線搜索算法排放p5后最低水平線無法繼續排放p6，因此會升高最低水平線，形成沒有利用的黑色的空洞，造成材料的浪費，如圖4所示。圖5為改進后的算法，當要排放矩形件 p5時，改進后的算法會檢測到最低水平線上剩余的寬度無法繼續排放矩形件 p6，然后尋找到未排放矩形件中寬度最大的矩形件p6與矩形件p5交換排放順序。

圖3 p1p2p3p4排放后

圖4 最低水平線搜索排樣

圖5 最低水平線啟發式搜索排樣

傳統的最低水平線搜索排樣算法按順序排放矩形件{p1p2p3p4p5p6}，p1p2p3p4排放后如圖6所示，傳統的最低水平線搜索算法排放會按順序排放p5p6，如圖7所示。圖8為改進后的算法，當要排放矩形件 p5時，改進后的算法會檢測到最低水平線上剩余寬度為0，然后尋找到未排放矩形件中寬度與 p5相同但高度比 p5高的的矩形件p6，與矩形件p5交換排放順序。

圖6 p1p2p3p4排放后

圖7 最低水平線搜索排樣

圖8 最低水平線啟發式搜索排樣

4 改進的雙種群遺傳算法

矩形件的排樣結果和矩形件的排放順序緊密相關，本文使用遺傳算法作為排樣順序問題的求解：遺傳算法模擬自然界生物的進化過程，生物在繁衍的過程中染色體會交叉變異，經過種群適者生存優勝劣汰后，逐代產生更加優秀的個體，從而實現解的優化。排樣優化問題屬于多目標優化問題，解空間是離散的，而遺傳算法可以從多個點出發尋找最優解，具有優秀的全局搜索能力，適合尋找大規模離散優化問題中的解。

由于排樣問題的解空間是離散的，劣質解附近可能會存在優秀解，對此蔣興波[15]與楊衛波[16]用遺傳模擬退火算法彌補傳統遺傳算法局部搜索能力不足的缺陷。

傳統的遺傳算法中隨機生成初始種群，容易造成排樣結果時好時壞，穩定性差。未利用有效信息，在人工排樣的過程中，熟練的工人單純的按照矩形件面積從小到大排樣往往可以取得不錯的效果。同時，傳統的遺傳算法在大規模離散空間內隨機搜索，容易造成收斂速度慢和陷入局部極值進而收斂停滯。

4.1 雙種群遺傳算法相關處理

在遺傳算法的隨機初始的種群中加入部分按照面積大小排序的個體以達到加速收斂的目的。如果在同一個種群中，這部分個體比隨機個體適應度高，迭代前期不易被淘汰反而快速擴散，使得種群多樣性降低，導致遺傳算法過早熟。本文提出把隨機生成的個體作為一個種群，按照面積大小排序生成的個體作為另一個種群并采用與隨機初始化的種群個體交叉進行迭代，并且通過特定的交叉方式，保證子代的排放順序為面積較大的矩形件最先排放，面積較小矩形件最后排放，達到大體上有序局部亂序的目的。

4.1.1 遺傳算法個體編碼方式及適應度函數

遺傳個體的編碼方式：由于目的是得到矩形件的排放順序，直觀起見，本文采取十進制整數的編碼方式，從1開始，對每個矩形件按照順序編號，由編號組成的序列表示矩形件的排樣順序，并且符號位表示是否旋轉，正值表示不旋轉，負值表示90°旋轉矩形件。例如排樣序列（－3，1，2）表示先把第3號矩形件旋轉90°排放，然后再排放1號矩形件，最后再排放2號矩形件。

適應度函數：采用上文提出的最低水平線啟發式搜索排樣算法排樣后的板材的利用率作為適應度的值，板材的利用率為矩形件面積之和與耗用板材材料面積之比，其取值范圍為0到1，板材的利用率越高，表示排樣效果越優秀。

4.1.2 種群A遺傳過程

本文采用雙種群遺傳算法，第一個種群A遺傳過程如下：

初始種群：本種群的初始個體是隨機的，即產生隨機序列，隨機方向，數量為m1個個體。

選擇方式：直接保留優秀個體，設選擇算子為 psA，0＜psA＜1，將個體按照適應度從大到小排序，前 psAm1個的直接保留到下一代。

交叉方式：采用兩點環形交叉方式[17]，設交叉算子為 pcA，0＜pcA＜1，產生 pcAm1個個體。兩點交叉的過程為：產生兩個不相等的，取值范圍為1到n隨機正整數ab為交叉點位置，n代表排樣序列的長度。種群中隨機抽取父代S1，S2。

如果a＜b，a位置到b位置之間的基因繼承自S1，其他基因繼承自S2，即保持在S2中的順序和方向。例如表1中交叉點位置為a=3，b=5時染色體交叉情況。

表1 染色體交叉案例

如果a＞b，1到b區間，a到n區間的基因繼承自S1，其他基因繼承自S2，即保持在S2中的順序和方向。例如表2中交叉點位置為a=6，b=2時染色體交叉情況。

表2 染色體交叉案例

變異操作：可分為旋轉變異和交換變異。旋轉變異指把某個矩形件旋轉90°，交換變異指把兩個矩形件的排放順序進行交換。設旋轉變異算子為 pm1A，0＜pm1A＜1，交換變異算子 pm2A，0＜pm2A＜1，分別產生pm1Am1和 pm2Am1個個體。

為保證每代個體數目不變，滿足條件：

種群A迭代一定次數結束后，產生第二個種群B。

4.1.3 種群B遺傳過程

初始種群：按照面積從大到小，方向隨機產生數量為m2個個體。

選擇操作：直接保留優秀個體，設選擇算子為 psB，0＜psB＜1，將個體按照適應度從大到小排序，前 psBm2個的直接保留到下一代。

交叉操作：設交叉算子為 pcB，0＜pcB＜1，產生pcBm2個個體。與上一個迭代結束后的種群A進行兩點交叉操作：產生隨機不相等正整數ab為交叉點位置，且a＜b，a和b的取值范圍為1到n，n代表排樣序列的長度。父代S1從種群B中隨機抽取，父代S2從迭代完成后的種群A中隨機抽取，交叉的過程為1到a，b到n區間的基因繼承自S1，其他基因繼承自S2即保持在S2中的順序和方向，例如表3中交叉點位置為a=2，b=6時染色體交叉情況。

變異操作：可分為旋轉變異和交換變異。旋轉變異指把某個矩形件旋轉90°，交換變異指把兩個矩形件的排放順序進行交換。設旋轉變異算子為 pm1B，0＜pm1B＜1，交換變異算子 pm2B，0＜pm2B＜1，分別產生pm1Bm2和 pm2Bm2個個體。

表3 染色體交叉案例

為保證每代個體數目不變，滿足條件：

種群迭代一定次數，取兩個種群的最優解。改進的遺傳算法過程如圖9所示。

圖9 改進的遺傳算法過程

4.1.4 種群內相似度計算

統計個體X，Y之間的編碼同一位置處相同的矩形件編號的個數之和公式：

個體X，Y相似度計算公式：

其中n是染色體長度，當XY同一位置對應的矩形件的編號相同時，k=1，否則k=0。

種群P內部相似度計算公式：

m代表種群P中個體總數，PiPj代表種群中的不同個體。種群內相似度越高，代表種群內多樣性越低。

4.2 雙種群遺傳算法改進原理

雙種群遺傳算法改進的思路：種群A初始值隨機產生，采用兩點交叉法可以增強遺傳算法在離散解空間的搜索能力，在迭代停止后種群A隱含了矩形件之間排放順序的優先級信息。

表4 矩形件描述信息

種群B是按照矩形件面積從大到小排序生成，原理是從早期人工排樣的經驗得知，單純的按照矩形件從大到小的順序排放矩形件能得到不錯的板材利用率，種群B可以保證排樣效果的穩定性。

種群B的交叉方式為先按照面積大小排序矩形件，然后在序列中間的矩形件的順序繼承自迭代完成后種群A，原理是開始時排放大矩形件，最后排放小矩形件，因為當大矩形件排放后出現的空洞可以用后面未排放的小矩形件填充，中間位置矩形件的排放順序參照種群A的迭代結果，利用了種群A迭代后的隱藏信息：矩形件之間排放順序的優先級。這樣可以在種群B初始適應度不錯的基礎上有效利用了種群A迭代后的隱藏信息，保證了排樣的效果的基礎上更加有效的搜索最優解。

種群B采用特定的交叉方式，保證子代中面積較大的矩形件最先排放，面積較小矩形件最后排放，在大體有序的基礎上搜索最優解，更有方向性和目的性。

將隨機個體與有序個體分成兩個種群，也避免出現迭代過程中由于種群中隨機個體數目減少導致種群多樣性降低，從而引發收斂停滯的問題。

本文的雙種群遺傳算法充分結合了遺傳算法的全局搜索能力與先排放大矩形件后排放小矩形件的原理，可以有效改善傳統遺傳算法的搜索效率低及過早收斂，穩定性差等不足。

5 實驗分析

為驗證本文改進后的算法效果，以文獻[12]的案例見表4作為本文算法實驗的測試數據，板材寬度為400。進行50次實驗，各種算法種群內板材最優利用率的均值對比見圖10。實驗采用種群A見表5的遺傳策略，分別結合最低水平線排樣算法，最低水平線搜索排樣算法，最低水平線擇優插入算法，本文提出的最低水平線啟發式搜索算法。

圖10 種群A與各排樣算法結合實驗效果對比

表5 種群A相關參數

根據圖10，對隨機初始的種群A迭代的情況觀測可以看出來，由于最低水平線啟發式搜索排樣算法可以更頻繁地動態調整矩形件的排放順序，種群內初始利用率比其他算法更高。同時，更頻繁地動態調整矩形件的排放順序也意味著更優秀的搜索能力，也彌補傳統遺傳算法局部搜索能力不足的缺陷。

在種群A20次迭代終止后的基礎上，開始種群B迭代，種群B相關參數見表6。混合種群由隨機和按面積大小排序的個體組成初始種群，迭代過程參考種群A的過程，其相關參數見表7。隨機種群A，種群B，混合種群結合本文排樣算法的對比實驗見圖11。圖12是混合種群和隨機種群A結合本文排樣算法在迭代過程中種群內相似度對比。

表6 種群B相關參數

表7 混合種群相關參數

圖11 各種群結合本文排樣算法實驗效果對比

根據圖11，種群A內進行兩點交叉，可以有效在離散解空間內搜索最優解，在后續的迭代中可以穩步提升種群內最優板材利用率。

圖12 混合種群與隨機種群A種群內相似度對比

圖13 50次實驗最優結果

表8 13組測試用例實驗結果對比

混合種群由于加入部分按照面積大小排序的個體，初始適應度高比隨機種群的更高。然而50代左右由于種群內多樣性降低，陷入局部最優解，搜索停滯，出現過早熟問題。種群B在種群A的基礎上迭代，可以有效利用信息，初始值比混合種群更好，同時種群B通過與種群A交叉的方式進行迭代，可以跳出局部最優解，直到100代左右算法收斂，避免了過早熟。

根據圖12，混合種群60代左右種群內相似度到達較高的50%，對比采用相同的遺傳過程隨機種群的相似度在120代左右到達50%。說明混合種群在迭代的前期種群多樣性迅速降低，導致算法過早熟，無法跳出局部最優解。

圖13為實驗中得到的最優結果，板材的利用率到達96.36%，圖中黑色部分代表提高最低水平線時形成的沒有利用的空洞。

為進一步測試本文算法的普適性，采用通用的測試用例，文獻[18]中的13個實驗測試用例進行實驗并與文獻[16]的IAGSA算法、Burke[18]的BF 算法、Huang[19]的HA算法做比較。種群A相關參數同表5，種群B相關參數同表6，對每個測試用例單獨實驗20次后統計結果見表8。

由表8可見，本文算法在此13組測試用例上表現優秀，說明算法實用性強，且穩定性很高，最優值與平均值差距很小或者沒有差距。

6 結束語

本文通過啟發式判斷是否有更加合適的未排放矩形件來代替當前要排放的矩形件，動態調整矩形件排放順序，改進了傳統的最低水平線排樣算法，可以有效提高板材利用率，減少板材空間的浪費。針對遺傳算法收斂速度慢，過早熟問題，本文采用雙種群遺傳算法，結合先排放大矩形件，后排放小矩形件規律，改進了交叉算子，有效提升遺傳算法的穩定性和在離散解空間的搜索效率。實驗結果表明，本文改進后的算法具有較好的實用性。在未來的工作中，將從滿足工業界中特殊的工藝要求的角度出發，繼續探討排樣問題。