兩階段遺傳算法和貪心策略相結(jié)合的多約束排樣優(yōu)化方法

馬英鈞，鐘俊江

（廈門(mén)理工學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建 廈門(mén) 361024）

排樣優(yōu)化問(wèn)題本質(zhì)上也稱切割填充問(wèn)題，優(yōu)化的目的是合理規(guī)劃方形產(chǎn)品在板材上的布局，減少下料過(guò)程中的板材浪費(fèi)，簡(jiǎn)化切割過(guò)程。下料作為眾多制造企業(yè)生產(chǎn)鏈中產(chǎn)品及零部件生產(chǎn)的第一道工序，消耗的材料和資源不容小覷，如何提高材料利用率，降低原材料消耗，是企業(yè)減少資源和能源浪費(fèi)，承擔(dān)環(huán)境保護(hù)責(zé)任所要解決的關(guān)鍵問(wèn)題。

針對(duì)排樣優(yōu)化問(wèn)題，當(dāng)前已提出一些計(jì)算模型。王竹婷等［1］將層次聚類思想引入矩陣排樣優(yōu)化問(wèn)題中，通過(guò)計(jì)算矩形組件間的結(jié)合度，將結(jié)合度最高的組件進(jìn)行合并，并重復(fù)該過(guò)程來(lái)實(shí)現(xiàn)優(yōu)化方案設(shè)計(jì)。王偉等［2］提出了一種基于捕食策略的遺傳算法，通過(guò)對(duì)編碼、遺傳算子和適應(yīng)度算子進(jìn)行改進(jìn)，并結(jié)合最低輪廓線搜索算法來(lái)獲得最優(yōu)布局。曾曉亮等［3］利用六元數(shù)組對(duì)矩形組件進(jìn)行表征，并利用多島遺傳算法來(lái)設(shè)計(jì)排樣方案，結(jié)果表明，該方案具有較高的利用率和穩(wěn)定性。近年來(lái)，陳仕軍等［4］提出反悔算子、距離受限鄰域算子、滿足容忍度3種策略來(lái)改進(jìn)傳統(tǒng)的鄰域搜索算法，通過(guò)與以往方法的結(jié)果對(duì)比發(fā)現(xiàn)，該方法具有很高的求解效率。吳繼聰?shù)龋?］介紹了多種Meta-Heuristic 算法在排樣優(yōu)化研究中的應(yīng)用，并分析不同算法的性能和適用場(chǎng)景。與之前的方形組件的排樣優(yōu)化研究不同，張闖等［6］研究二維橢圓零件的排樣優(yōu)化問(wèn)題，提出了一種在仿射坐標(biāo)系下的變換，并建立整數(shù)規(guī)劃模型。以上成果雖然推動(dòng)了排樣優(yōu)化問(wèn)題的研究，但是它們僅考慮如何排樣以使材料最省，很少考慮到機(jī)器的具體切割限制，比如每次的切割可以保證板材分離及切割的次數(shù)不能過(guò)多的限制等?；诖耍槍?duì)多約束排樣優(yōu)化問(wèn)題的特點(diǎn)，本文提出了一種兩階段遺傳算法和貪婪策略相結(jié)合的排樣優(yōu)化方法，建立產(chǎn)品布局和條帶布局的數(shù)學(xué)模型，利用一種兩階段遺傳算法來(lái)進(jìn)行模型求解，并設(shè)計(jì)有效的解碼方案提升模型的求解效率。同時(shí)，為了進(jìn)一步提升利用率，針對(duì)“條帶余料”和“板材余料”建立2種基于貪婪策略的算法模型，并在多個(gè)數(shù)據(jù)集上執(zhí)行計(jì)算，以驗(yàn)證本文算法的有效性。

1 問(wèn)題分析

本研究的問(wèn)題引自2022 年“中國(guó)光谷·華為杯”研究生數(shù)學(xué)建模競(jìng)賽B 題第一問(wèn)。本問(wèn)題中的切割需要滿足以下條件：1）只考慮“齊頭切”的切割方式（直線切割、切割方向垂直于板材一條邊，并保證每次直線切割板材可分離成2塊）；2）切割階段數(shù)不超過(guò)3，同一個(gè)階段切割方向相同；3）假定板材原片僅有一種規(guī)格且數(shù)量充足；4）排樣方案不用考慮鋸縫寬度（即切割的縫隙寬度）影響；5）最終切割生成的產(chǎn)品項(xiàng)是完整的，非拼接而成。圖1是一種有效的3階段切割方式及其生成的模塊。

圖1 一種3階段切割方式及其生成模塊簡(jiǎn)圖Fig.1 A three-stage cutting mode and modules it generated

圖1 中：實(shí)豎線表示第一次切割得到兩個(gè)模塊分別是條帶1 和條帶2；長(zhǎng)橫虛線表示對(duì)于條帶的切割（即第二次切割）得到6個(gè)棧分別是棧1、棧2、棧3、棧4、棧5和棧6；短豎虛線表示對(duì)于棧的切割（即第三次切割）最終獲得17個(gè)產(chǎn)品。由圖1可以看出，以上的每次切割都是沿著板材的一條邊進(jìn)行的，并且每次切割都將板材分成2段。對(duì)于該問(wèn)題直接進(jìn)行二維布局，不僅計(jì)算復(fù)雜度高，而且很有可能導(dǎo)致不滿足“切割階段不超過(guò)3” 的約束。由圖1可知，第二刀切割會(huì)產(chǎn)生多個(gè)棧，每個(gè)棧都是由邊長(zhǎng)相等的產(chǎn)品組成的，因此，研究等邊長(zhǎng)的產(chǎn)品可以在一定程度上提升板材的利用效率。

為了減少切割的次數(shù)，先將邊長(zhǎng)相等的產(chǎn)品拼接為條帶，并將條帶沿著板材的長(zhǎng)邊放置。因此，根據(jù)產(chǎn)品的邊長(zhǎng)特點(diǎn)，將其分為3個(gè)類別：1）類別1包含有相等的邊長(zhǎng)，并且相等邊長(zhǎng)小于W（板材的寬）的產(chǎn)品；2）類別2 包含邊長(zhǎng)大于W的產(chǎn)品；3）類別3 包含與其他產(chǎn)品的邊長(zhǎng)都不相等的產(chǎn)品。對(duì)于類別1，建立一階段模型來(lái)實(shí)現(xiàn)產(chǎn)品組合為條帶優(yōu)化；對(duì)于類別1 得到的條帶和類別2 的產(chǎn)品（每個(gè)作為一個(gè)條帶），建立二階段模型來(lái)實(shí)現(xiàn)條帶在板材上的布局優(yōu)化；對(duì)于邊長(zhǎng)不相等的產(chǎn)品（類別3），利用前兩步的廢料和新板材，執(zhí)行余料再利用。具體求解框架見(jiàn)圖2。

圖2 多約束排樣優(yōu)化問(wèn)題的整體求解框架Fig.2 Solution framework for multi-constraint layout optimization

2 基于兩階段遺傳算法的產(chǎn)品布局優(yōu)化

本節(jié)主要通過(guò)兩階段遺傳算法來(lái)實(shí)現(xiàn)類別1 和類別2 的產(chǎn)品在板材上的優(yōu)化布局，主要包含3 個(gè)步驟：1）建立產(chǎn)品組合優(yōu)化數(shù)學(xué)模型；2）建立條帶優(yōu)化數(shù)學(xué)模型；3）構(gòu)建兩階段遺傳算法來(lái)初步實(shí)現(xiàn)兩類產(chǎn)品在板材上的最優(yōu)布局。

2.1 產(chǎn)品組合優(yōu)化數(shù)學(xué)模型的建立

對(duì)于物品很少的分組，如果直接組合為條帶，可能會(huì)導(dǎo)致空間的浪費(fèi)。因此，設(shè)置閾值ε，對(duì)邊長(zhǎng)相等的物品數(shù)大于ε的那些分組拼接為條帶。

令M1表示需要拼接的物品的個(gè)數(shù)，li表示第i產(chǎn)品的另一邊（除了相等邊長(zhǎng)的另一邊）的長(zhǎng)度，M2表示預(yù)估需要的條帶個(gè)數(shù)，xij表示第i產(chǎn)品是否放置于條帶j中，當(dāng)?shù)趇產(chǎn)品置于條帶j中時(shí)，xij=1，反之，xij=0。為了使得用料最省，要求在不超過(guò)每個(gè)條帶的限制長(zhǎng)度L（板材的長(zhǎng)邊）情況下，使得所用的條帶的數(shù)量盡可能少。此時(shí)，其模型為

需要注意的是，以dataA1的邊長(zhǎng)為58的產(chǎn)品為例，其84個(gè)產(chǎn)品另一邊長(zhǎng)的總和為100 830，而每個(gè)條帶的最大長(zhǎng)度為2 440，因此，M＞100 830/2 440 ≈41.32。對(duì)于式（1）描述的混合0～1 規(guī)劃問(wèn)題，變量的個(gè)數(shù)至少為84 × 42。

2.2 條帶組合優(yōu)化數(shù)學(xué)模型的建立

式（2）中：δ(x)為判斷函數(shù)，與式（1）中的定義類似。由式（2）可以看出，目標(biāo)函數(shù)要求選取的板材數(shù)盡可能小。第一個(gè)約束條件要求每個(gè)板材剪裁的條帶的總寬度小于板材的寬度W，第二個(gè)約束要求每個(gè)條帶必須有一個(gè)板材來(lái)剪裁，第三個(gè)約束條件要求yij是0～1決策變量。

需要注意的是，以dataA1 和閾值ε=10 為例，根據(jù)類別1 拼接得到108 個(gè)條帶和類別2 的102 個(gè)條帶，一共得到210 個(gè)條帶。這些條帶的總寬度為71 754，因此，至少需要的板材數(shù)量N=71 754/1 220 ≥59。也就是說(shuō)，式（2）描述的模型中決策變量的個(gè)數(shù)至少為210 × 59。

2.3 基于兩階段遺傳算法的模型求解

節(jié)2.1 和節(jié)2.2 描述的問(wèn)題都是混合0～1 規(guī)劃模型，并且模型中決策變量的個(gè)數(shù)都比較多，利用傳統(tǒng)的優(yōu)化方法很難求解，甚至很難得到可行解?；诖?，本研究采用遺傳算法進(jìn)行求解?，F(xiàn)以產(chǎn)品組合優(yōu)化的求解進(jìn)行介紹。

遺傳算法的優(yōu)化方案包含編碼、生成初始種群、計(jì)算適應(yīng)度、交叉、變異等操作。

1）編碼。為了提升編碼效率，本研究使用序號(hào)編碼來(lái)生成染色體。對(duì)于M個(gè)產(chǎn)品，任意一條染色體可表示為X={x1，x2，…，xM}，其中{x1，x2，…，xM}表示產(chǎn)品編號(hào){1，2，…，M}的任意排列。染色體X表示的意義是依次實(shí)現(xiàn)產(chǎn)品x1，x2，…，xM的剪裁。

2）目標(biāo)函數(shù)。對(duì)于染色體X={x1，x2，…，xM}，條帶的長(zhǎng)度限制L，產(chǎn)品另一邊長(zhǎng)度{l1，l2，…，lM}，計(jì)算條帶總數(shù)的計(jì)算步驟如下：

Step1將產(chǎn)品項(xiàng)按照染色體X={x1，x2，…，xM}的順序排列；初始化K=0，i=1，j=1，F(xiàn)1=?，Z=0。

Step2將當(dāng)前第i個(gè)產(chǎn)品放入Fj中，即Fj={Fj，xi}，并計(jì)算Z=Z+lxk。

Step3當(dāng)Z≤L時(shí)，表示前條帶有剩余；否則，刪除集合Fj的最后一個(gè)元素，選擇下一個(gè)條帶，即j=j+1，F(xiàn)j={xi}，Z=0。

Step4i=i+1，若i≤M，執(zhí)行步驟Step2和Step3；否則，返回需要的條帶總數(shù)K=j。

在以上步驟中，集合Fj表示第j條帶剪裁的產(chǎn)品集合，K表示條帶總數(shù)。由以上步驟可以看出，解碼步驟的算法復(fù)雜度為O(n)。本研究中的每個(gè)染色體都是利用貪心算法進(jìn)行解碼，不僅保證每個(gè)染色體是可行解，而且是局部最優(yōu)的。

3）交叉和變異。由于本文采用序號(hào)編碼，在交叉的時(shí)候可能會(huì)導(dǎo)致染色體損壞。因此，采用部分交叉映射來(lái)對(duì)染色體進(jìn)行修正［7-9］。部分交叉映射的主要思想是：對(duì)兩個(gè)待交叉染色體交叉區(qū)域內(nèi)的基因互換，并利用交叉區(qū)域內(nèi)的映射關(guān)系將交叉區(qū)域外的基因進(jìn)行修正。為了提升計(jì)算效率，保證變異之后染色體的有效性，變異操作采用基因交換的方式，即隨機(jī)選擇待變異染色體兩個(gè)位置的基因進(jìn)行交換［10］。

4）重組。為了提升算法效率，保證優(yōu)秀染色體可以進(jìn)入下一代，本文設(shè)置代溝操作，并在每一次交叉變異之后，選取上一代最優(yōu)的10%的個(gè)體直接進(jìn)入下一代。

遺傳算法的具體流程見(jiàn)圖3。

圖3 遺傳算法流程圖Fig.3 Genetic algorithm flow

綜上，首先利用遺傳算法求解節(jié)2.1的問(wèn)題來(lái)獲取產(chǎn)品組裝為條帶的最優(yōu)方案，然后再利用遺傳算法求解節(jié)2.2實(shí)現(xiàn)條帶在板材上的最優(yōu)布局。

3 基于貪心策略的余料再利用

在產(chǎn)品組合優(yōu)化和條帶組合優(yōu)化的過(guò)程中，都可能會(huì)出現(xiàn)余料，合理利用這些余料可以在很大程度上提升板材的利用效率。因此，基于貪心策略［11-12］，本文提出兩方面的余料利用策略，即產(chǎn)品組合的余料再利用和條帶組合的余料再利用。

3.1 產(chǎn)品組合的余料再利用

條帶剪裁產(chǎn)品的過(guò)程中，若條帶中產(chǎn)品項(xiàng)的總長(zhǎng)度小于L，導(dǎo)致余料S1產(chǎn)生。圖4 給出了余料S1的再利用示意圖。

圖4 余料S1的再利用示意圖Fig.4 Reuse of residual material S1

如圖4所示，對(duì)于組裝條帶產(chǎn)生的余料S1，其高為h1，寬為w1，從剩余的產(chǎn)品中選擇可以放入S1的產(chǎn)品集合，即={x|min {hx，wx}＜min {h1，w1}且max {hx，wx}＜max {h1，w1}}。從集合中選擇面積最大的產(chǎn)品C1進(jìn)行放置，為保證切割總數(shù)不超過(guò)3 的約束，C1的左下角必須與余料S1的左下角重合。此時(shí)，如圖4兩邊的兩個(gè)圖所示，由于C1的擺放方式不同，可得到不同的可使用余料分別為和，容易看出余料可使用面積更大，因此，按照?qǐng)D4 中最右圖的方式擺放。余料S1的再利用步驟如下：

Step1令余料S1的寬為w、高為h，且剩余m個(gè)需要剪裁產(chǎn)品{C1，C2，…，Cm}的寬分別為{w1，w2，…，wm}，高分別為{h1，h2，…，hm}，當(dāng)前可用產(chǎn)品集合T=?。

Step2當(dāng)min{w，h}＞min{wi，hi} 且 max{w，h}＞max{wi，hi}，說(shuō)明此時(shí)第i個(gè)產(chǎn)品項(xiàng)可利用余料S1剪裁，更新T={T，i}。

Step3i=i+1，若i≤M，執(zhí)行步驟Step2；否則，執(zhí)行Step4。

Step4從T中挑選面積最大的第k產(chǎn)品放入余料S1中，且保證該產(chǎn)品左下邊頂點(diǎn)與S1左上頂點(diǎn)重合，計(jì)算此時(shí)可用余料。

Step5計(jì)算產(chǎn)品旋轉(zhuǎn)90o后的可用余料，當(dāng)旋轉(zhuǎn)后依舊可以放置，并且＞S′1時(shí)，將該產(chǎn)品旋轉(zhuǎn)90o，更新余料S1=，更新余料S1的寬w′和高h(yuǎn)′，T=?；否則，更新余料S1=，更新余料S1的寬w′和高h(yuǎn)′，T=?。

Step6更新步驟Step2、Step3、Step4 和Step5，直至不能找到可放置的產(chǎn)品。返回關(guān)于當(dāng)前余料S1的再利用方案。

根據(jù)以上步驟可以看出，對(duì)于任意產(chǎn)品的放置，都需要對(duì)所有的可能產(chǎn)品遍歷一次，因此，其算法復(fù)雜度為O(n2)。

3.2 條帶組合的余料再利用

在板材剪裁條帶的過(guò)程中，若板材中條帶的總寬度小于W，導(dǎo)致余料S2產(chǎn)生。余料S2的再利用示意圖見(jiàn)圖5。

圖5 余料S2的使用示意圖Fig.5 Reuse of residual material S2

板材剪裁條帶過(guò)程中產(chǎn)生的余料如圖5所示。首先，利用貪心策略，從剩余需要剪裁的產(chǎn)品中選擇最優(yōu)的，即滿足剪裁要切，面積最大，且放置方式要保證可利用余料的可利用面積最大。然后，經(jīng)過(guò)第一次放置，有2塊余料產(chǎn)生，即余料和余料。對(duì)于余料的處理方式與第一步類似，而余料的處理方式如節(jié)3.1余料S1的再利用步驟所示。余料S2的再利用步驟如下：

Step1令余料S2的寬w和高h(yuǎn)，且剩余m個(gè)需要剪裁產(chǎn)品{C1，C2，…，Cm}的寬分別為{w1，w2，…，wm}，高分別為{h1，h2，…，hm}。

Step2按照余料S1的再利用算法，尋找產(chǎn)品放入S2中，得到剩余余料和余料。

Step3對(duì)剩余余料，重復(fù)余料S1的再利用算法，直至不能放置產(chǎn)品。

Step4對(duì)剩余余料，重復(fù)步驟Step2和Step3，直至不能放置產(chǎn)品。輸出余料S2的再利用方案。

4 模型整體求解結(jié)果和分析

4.1 兩階段遺傳算法的優(yōu)化性能分析

對(duì)于類別1和類別2中的產(chǎn)品，利用兩階段遺傳算法來(lái)獲得產(chǎn)品的初始布局?，F(xiàn)以dataA1中邊長(zhǎng)為58 的84 個(gè)產(chǎn)品組合條帶和210 個(gè)條帶組合在板材上布局為例來(lái)分析兩階段遺傳算法的優(yōu)化性能，結(jié)果見(jiàn)圖6。

圖6 關(guān)于dataA1的兩階段遺傳優(yōu)化過(guò)程圖Fig.6 Two-stage genetic optimization process for dataA1

由圖6（a）可以看出，初始隨機(jī)方案的條帶數(shù)為51，條帶利用率為100 830/(2 440 × 51)=81.03%。隨著算法進(jìn)行，所需的條帶數(shù)逐漸降低，最終需要的條帶數(shù)為46，條帶利用率為100 830/(2 440 ×46)=89.83%。條帶的數(shù)量降低4 個(gè)，條帶的利用率提升8.81%。由圖6（b）可以看出，隨著迭代過(guò)程的進(jìn)行，組裝210個(gè)條帶需要的板材數(shù)量逐漸降低。初始隨機(jī)生成的組裝方案需要64個(gè)板材，板材的橫向利用率為71 754/(1 220 × 70)=84.02%，其中71 754為210個(gè)條帶的總寬度；當(dāng)?shù)螖?shù)為150次以后，板材的個(gè)數(shù)穩(wěn)定到64個(gè)，板材的橫向利用率為71 754/(1 220 × 64)=91.90%，提升了7.88%。

4.2 閾值對(duì)模型性能的影響

如節(jié)2.2所述，對(duì)于某些存在邊長(zhǎng)相等但數(shù)量很少的物品，直接組合為條帶可能會(huì)導(dǎo)致板材的浪費(fèi)。通過(guò)設(shè)置閾值ε=2，3，…，20來(lái)分析相等邊長(zhǎng)物品的數(shù)量與板材利用率的關(guān)系。具體地，當(dāng)ε=2時(shí)，考慮所有存在邊長(zhǎng)相等的物品（相等邊長(zhǎng)小于1 220）；當(dāng)ε=3 時(shí)，考慮相等邊長(zhǎng)的物品數(shù)量≥3的情況。以dataA1為例，對(duì)于不同的閾值，代入以上過(guò)程，可得到相應(yīng)的板材利用率，結(jié)果見(jiàn)圖7。

圖7 dataA1中閾值和利用率的關(guān)系Fig.7 Relationship between threshold and utilization in dataA1

由圖7可以看出，隨著閾值的增加，板材的利用率也在逐漸提高，當(dāng)閾值ε=10左右時(shí)，板材的利用率最高可達(dá)到82.71%。因此，對(duì)于數(shù)據(jù)集1，本文取ε=10，即對(duì)那些邊長(zhǎng)相等的物品數(shù)量≥10的分組利用第2節(jié)的操作來(lái)組合為條帶，邊長(zhǎng)相等的物品數(shù)量小于10的個(gè)體歸入類別3。

4.3 板材布局

對(duì)于2022 年“中國(guó)光谷·華為杯”研究生數(shù)學(xué)建模競(jìng)賽B 題中的dataA1、dataA2、dataA3、dataA4和dataA5這5個(gè)數(shù)據(jù)集，利用以上過(guò)程來(lái)執(zhí)行排樣優(yōu)化，并選取禁忌搜索算法［13-14］進(jìn)行對(duì)比，最終得到的結(jié)果見(jiàn)表1。

表1 排樣優(yōu)化在5個(gè)數(shù)據(jù)集上的結(jié)果對(duì)比Table 1 Results of layout optimization across five data sets compared

由于并不知道實(shí)際的最優(yōu)板材數(shù)量，但可以計(jì)算最優(yōu)板材數(shù)量的下界，即“最優(yōu)板材數(shù)量下界”，它通過(guò)利用產(chǎn)品項(xiàng)的總面積和除以板材面積，并向上取整得到。由表1 可以看出，本文的方法在5個(gè)數(shù)據(jù)集上的板材利用率基本上都可保持在80%以上，并且高于禁忌搜索算法的結(jié)果。其中，對(duì)于dataA1，物品總面積為2.486 9×108，需要的板材數(shù)量為101 個(gè)，板材的利用率為82.71%。圖8 給出了dataA1的第一個(gè)板材上的排樣效果圖。

圖8 dataA1中第一個(gè)板材上的產(chǎn)品排樣Fig.8 Product layout on the first plate in dataA1

5 結(jié)論

針對(duì)多約束產(chǎn)品排樣問(wèn)題，提出一種兩階段遺傳算法和貪心策略相結(jié)合的排樣優(yōu)化方法。該方法通過(guò)分析產(chǎn)品排樣問(wèn)題的特征，設(shè)計(jì)局部最優(yōu)解碼方案，采用兩階段遺傳算法來(lái)實(shí)現(xiàn)產(chǎn)品和條帶的最優(yōu)布局，并針對(duì)產(chǎn)品余料和條帶余料分別設(shè)計(jì)基于貪心策略的再利用方案。利用2022年研究生數(shù)學(xué)建模競(jìng)賽B題的5種數(shù)據(jù)集進(jìn)行測(cè)試，通過(guò)模型對(duì)比和分析，驗(yàn)證了本研究模型的有效性。該模型的建立為有切割次數(shù)和切割限制的排樣優(yōu)化問(wèn)題提供了一種新的求解方案。下一步的工作將針對(duì)多約束排樣優(yōu)化問(wèn)題的特點(diǎn)建立集成學(xué)習(xí)模型，從而設(shè)計(jì)更為有效的鄰域搜索策略，以進(jìn)一步提升板材的利用率。