孫佳正，郭 駿

華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062

1 引言

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

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

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

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

2 矩形件排樣問(wèn)題的描述

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

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

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

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

矩形件排樣優(yōu)化問(wèn)題可描述為，滿足約束條件的同時(shí)，求解板材最大的利用率式（1）的最佳排樣方案：

且滿足約束條件：

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

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

3 最低水平線啟發(fā)式搜索排樣算法

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

然而傳統(tǒng)的最低水平線搜索排樣算法只有在最低水平線的寬度小于待排矩形件的寬度時(shí)才會(huì)向后搜索，搜索的頻率低，調(diào)整排樣順序的機(jī)會(huì)少。本文提出的最低水平線啟發(fā)式搜索排樣算法可以在排樣的同時(shí)進(jìn)行搜索，啟發(fā)式判斷是否有更合適的矩形件排放在當(dāng)前位置。

3.1 最低水平線搜索排樣算法改進(jìn)處理

本文改進(jìn)后的算法在當(dāng)前矩形件排放在最低水平線上后，最低水平線的剩余寬度無(wú)法繼續(xù)排放任何未排放的矩形件時(shí)包括剩余寬度為0的特殊情況，判斷在未排放的矩形件中是否有更合適的矩形件可以替換當(dāng)前矩形件，更加頻繁的動(dòng)態(tài)調(diào)整矩形件的排放順序。改進(jìn)的最低水平線排樣過(guò)程如下：

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

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

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

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

（5）在最低水平線上靠左排放當(dāng)前矩形件。更新水平線集合，選擇下一個(gè)待排放矩形件，轉(zhuǎn)入步驟（2）。若所有矩形件都排放完畢，結(jié)束。

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

改進(jìn)后的最低水平線排樣算法可以更加頻繁的動(dòng)態(tài)調(diào)整矩形件排放的順序，相當(dāng)于彌補(bǔ)遺傳算法局部搜索能力不足的缺陷，同時(shí)盡可能地利用板材的空間。改進(jìn)的最低水平線排樣算法流程如圖2所示。

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

改進(jìn)的原理是排樣時(shí)先排放大的矩形件，后排放小的矩形件。大的矩形件排放時(shí)產(chǎn)生的空洞，可以用小的矩形件來(lái)填充。

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

圖2 改進(jìn)的最低水平線排樣算法流程圖

傳統(tǒng)的最低水平線搜索排樣算法按順序排放矩形件{p1p2p3p4p5p6},p1p2p3p4排放后如圖3所示，傳統(tǒng)的最低水平線搜索算法排放p5后最低水平線無(wú)法繼續(xù)排放p6，因此會(huì)升高最低水平線，形成沒有利用的黑色的空洞，造成材料的浪費(fèi)，如圖4所示。圖5為改進(jìn)后的算法，當(dāng)要排放矩形件 p5時(shí)，改進(jìn)后的算法會(huì)檢測(cè)到最低水平線上剩余的寬度無(wú)法繼續(xù)排放矩形件 p6，然后尋找到未排放矩形件中寬度最大的矩形件p6與矩形件p5交換排放順序。

圖3 p1p2p3p4排放后

圖4 最低水平線搜索排樣

圖5 最低水平線啟發(fā)式搜索排樣

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

圖6 p1p2p3p4排放后

圖7 最低水平線搜索排樣

圖8 最低水平線啟發(fā)式搜索排樣

4 改進(jìn)的雙種群遺傳算法

矩形件的排樣結(jié)果和矩形件的排放順序緊密相關(guān)，本文使用遺傳算法作為排樣順序問(wèn)題的求解：遺傳算法模擬自然界生物的進(jìn)化過(guò)程，生物在繁衍的過(guò)程中染色體會(huì)交叉變異，經(jīng)過(guò)種群適者生存優(yōu)勝劣汰后，逐代產(chǎn)生更加優(yōu)秀的個(gè)體，從而實(shí)現(xiàn)解的優(yōu)化。排樣優(yōu)化問(wèn)題屬于多目標(biāo)優(yōu)化問(wèn)題，解空間是離散的，而遺傳算法可以從多個(gè)點(diǎn)出發(fā)尋找最優(yōu)解，具有優(yōu)秀的全局搜索能力，適合尋找大規(guī)模離散優(yōu)化問(wèn)題中的解。

由于排樣問(wèn)題的解空間是離散的，劣質(zhì)解附近可能會(huì)存在優(yōu)秀解，對(duì)此蔣興波[15]與楊衛(wèi)波[16]用遺傳模擬退火算法彌補(bǔ)傳統(tǒng)遺傳算法局部搜索能力不足的缺陷。

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

4.1 雙種群遺傳算法相關(guān)處理

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

4.1.1 遺傳算法個(gè)體編碼方式及適應(yīng)度函數(shù)

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

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

4.1.2 種群A遺傳過(guò)程

本文采用雙種群遺傳算法，第一個(gè)種群A遺傳過(guò)程如下：

初始種群：本種群的初始個(gè)體是隨機(jī)的，即產(chǎn)生隨機(jī)序列，隨機(jī)方向，數(shù)量為m1個(gè)個(gè)體。

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

交叉方式：采用兩點(diǎn)環(huán)形交叉方式[17]，設(shè)交叉算子為 pcA，0＜pcA＜1，產(chǎn)生 pcAm1個(gè)個(gè)體。兩點(diǎn)交叉的過(guò)程為：產(chǎn)生兩個(gè)不相等的，取值范圍為1到n隨機(jī)正整數(shù)ab為交叉點(diǎn)位置，n代表排樣序列的長(zhǎng)度。種群中隨機(jī)抽取父代S1，S2。

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

表1 染色體交叉案例

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

表2 染色體交叉案例

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

為保證每代個(gè)體數(shù)目不變，滿足條件：

種群A迭代一定次數(shù)結(jié)束后，產(chǎn)生第二個(gè)種群B。

4.1.3 種群B遺傳過(guò)程

初始種群：按照面積從大到小，方向隨機(jī)產(chǎn)生數(shù)量為m2個(gè)個(gè)體。

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

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

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

表3 染色體交叉案例

為保證每代個(gè)體數(shù)目不變，滿足條件：

種群迭代一定次數(shù)，取兩個(gè)種群的最優(yōu)解。改進(jìn)的遺傳算法過(guò)程如圖9所示。

圖9 改進(jìn)的遺傳算法過(guò)程

4.1.4 種群內(nèi)相似度計(jì)算

統(tǒng)計(jì)個(gè)體X，Y之間的編碼同一位置處相同的矩形件編號(hào)的個(gè)數(shù)之和公式：

個(gè)體X，Y相似度計(jì)算公式：

其中n是染色體長(zhǎng)度，當(dāng)XY同一位置對(duì)應(yīng)的矩形件的編號(hào)相同時(shí)，k=1，否則k=0。

種群P內(nèi)部相似度計(jì)算公式：

m代表種群P中個(gè)體總數(shù)，PiPj代表種群中的不同個(gè)體。種群內(nèi)相似度越高，代表種群內(nèi)多樣性越低。

4.2 雙種群遺傳算法改進(jìn)原理

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

表4 矩形件描述信息

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

種群B的交叉方式為先按照面積大小排序矩形件，然后在序列中間的矩形件的順序繼承自迭代完成后種群A，原理是開始時(shí)排放大矩形件，最后排放小矩形件，因?yàn)楫?dāng)大矩形件排放后出現(xiàn)的空洞可以用后面未排放的小矩形件填充，中間位置矩形件的排放順序參照種群A的迭代結(jié)果，利用了種群A迭代后的隱藏信息：矩形件之間排放順序的優(yōu)先級(jí)。這樣可以在種群B初始適應(yīng)度不錯(cuò)的基礎(chǔ)上有效利用了種群A迭代后的隱藏信息，保證了排樣的效果的基礎(chǔ)上更加有效的搜索最優(yōu)解。

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

將隨機(jī)個(gè)體與有序個(gè)體分成兩個(gè)種群，也避免出現(xiàn)迭代過(guò)程中由于種群中隨機(jī)個(gè)體數(shù)目減少導(dǎo)致種群多樣性降低，從而引發(fā)收斂停滯的問(wèn)題。

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

5 實(shí)驗(yàn)分析

為驗(yàn)證本文改進(jìn)后的算法效果，以文獻(xiàn)[12]的案例見表4作為本文算法實(shí)驗(yàn)的測(cè)試數(shù)據(jù)，板材寬度為400。進(jìn)行50次實(shí)驗(yàn)，各種算法種群內(nèi)板材最優(yōu)利用率的均值對(duì)比見圖10。實(shí)驗(yàn)采用種群A見表5的遺傳策略，分別結(jié)合最低水平線排樣算法，最低水平線搜索排樣算法，最低水平線擇優(yōu)插入算法，本文提出的最低水平線啟發(fā)式搜索算法。

圖10 種群A與各排樣算法結(jié)合實(shí)驗(yàn)效果對(duì)比

表5 種群A相關(guān)參數(shù)

根據(jù)圖10，對(duì)隨機(jī)初始的種群A迭代的情況觀測(cè)可以看出來(lái)，由于最低水平線啟發(fā)式搜索排樣算法可以更頻繁地動(dòng)態(tài)調(diào)整矩形件的排放順序，種群內(nèi)初始利用率比其他算法更高。同時(shí)，更頻繁地動(dòng)態(tài)調(diào)整矩形件的排放順序也意味著更優(yōu)秀的搜索能力，也彌補(bǔ)傳統(tǒng)遺傳算法局部搜索能力不足的缺陷。

在種群A20次迭代終止后的基礎(chǔ)上，開始種群B迭代，種群B相關(guān)參數(shù)見表6?；旌戏N群由隨機(jī)和按面積大小排序的個(gè)體組成初始種群，迭代過(guò)程參考種群A的過(guò)程，其相關(guān)參數(shù)見表7。隨機(jī)種群A，種群B，混合種群結(jié)合本文排樣算法的對(duì)比實(shí)驗(yàn)見圖11。圖12是混合種群和隨機(jī)種群A結(jié)合本文排樣算法在迭代過(guò)程中種群內(nèi)相似度對(duì)比。

表6 種群B相關(guān)參數(shù)

表7 混合種群相關(guān)參數(shù)

圖11 各種群結(jié)合本文排樣算法實(shí)驗(yàn)效果對(duì)比

根據(jù)圖11，種群A內(nèi)進(jìn)行兩點(diǎn)交叉，可以有效在離散解空間內(nèi)搜索最優(yōu)解，在后續(xù)的迭代中可以穩(wěn)步提升種群內(nèi)最優(yōu)板材利用率。

圖12 混合種群與隨機(jī)種群A種群內(nèi)相似度對(duì)比

圖13 50次實(shí)驗(yàn)最優(yōu)結(jié)果

表8 13組測(cè)試用例實(shí)驗(yàn)結(jié)果對(duì)比

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

根據(jù)圖12，混合種群60代左右種群內(nèi)相似度到達(dá)較高的50%，對(duì)比采用相同的遺傳過(guò)程隨機(jī)種群的相似度在120代左右到達(dá)50%。說(shuō)明混合種群在迭代的前期種群多樣性迅速降低，導(dǎo)致算法過(guò)早熟，無(wú)法跳出局部最優(yōu)解。

圖13為實(shí)驗(yàn)中得到的最優(yōu)結(jié)果，板材的利用率到達(dá)96.36%，圖中黑色部分代表提高最低水平線時(shí)形成的沒有利用的空洞。

為進(jìn)一步測(cè)試本文算法的普適性，采用通用的測(cè)試用例，文獻(xiàn)[18]中的13個(gè)實(shí)驗(yàn)測(cè)試用例進(jìn)行實(shí)驗(yàn)并與文獻(xiàn)[16]的IAGSA算法、Burke[18]的BF 算法、Huang[19]的HA算法做比較。種群A相關(guān)參數(shù)同表5，種群B相關(guān)參數(shù)同表6，對(duì)每個(gè)測(cè)試用例單獨(dú)實(shí)驗(yàn)20次后統(tǒng)計(jì)結(jié)果見表8。

由表8可見，本文算法在此13組測(cè)試用例上表現(xiàn)優(yōu)秀，說(shuō)明算法實(shí)用性強(qiáng)，且穩(wěn)定性很高，最優(yōu)值與平均值差距很小或者沒有差距。

6 結(jié)束語(yǔ)

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