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

王靜靜 瞿少成 李科林

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

0 引 言

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

二維不規(guī)則排樣問題涉及運(yùn)籌學(xué)、幾何數(shù)學(xué)等眾多學(xué)科，屬于典型的組合優(yōu)化問題。近年來，二維不規(guī)則排樣問題常采用啟發(fā)式算法或智能優(yōu)化算法求解。文獻(xiàn)[6]提出了一種多目標(biāo)啟發(fā)式進(jìn)化算法求解考慮批量問題的二維矩形件排樣問題，文獻(xiàn)[7]提出了一種基于重心臨界多邊形的啟發(fā)式排樣算法?？梢钥闯?，啟發(fā)式算法實(shí)現(xiàn)簡單，能夠快速給出求解方案，但難以取得全局最優(yōu)解。因此，目前常采用模擬退火算法、遺傳算法等智能優(yōu)化算法解決排樣優(yōu)化問題。

遺傳算法通過模擬自然進(jìn)化過程搜索最優(yōu)解，全局搜索能力優(yōu)秀，適合大規(guī)?？臻g求解復(fù)雜問題[8]，將其應(yīng)用到排樣問題的求解上可以取得較好的排樣效果。文獻(xiàn)[9]結(jié)合遺傳算法和最低水平線算法求解矩形件排樣問題，但其尋優(yōu)能力有待進(jìn)一步改進(jìn)。文獻(xiàn)[10]利用基于排擠機(jī)制的小生境遺傳算法求解排樣順序優(yōu)化問題，但是算法效率有待提高。

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

1 問題描述和數(shù)學(xué)模型

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

約束條件：

Ri∩Rj=?(i≠j)

(1)

Ri∈R

(2)

Oi∈O

(3)

目標(biāo)函數(shù)：

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

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

(4)

(5)

式(1)保證各個(gè)零件之間不能重疊；式(2)保證排放后所有不規(guī)則零件都位于板材內(nèi)部；式(3)中O為零件對(duì)應(yīng)旋轉(zhuǎn)的角度。

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

圖1 二維不規(guī)則零件排樣結(jié)果

2 算法設(shè)計(jì)

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

2.1 個(gè)體編碼方式及構(gòu)造初始種群

2.1.1個(gè)體編碼方式

本文基于對(duì)象的數(shù)據(jù)結(jié)構(gòu)索引對(duì)個(gè)體進(jìn)行編碼，對(duì)于包含n個(gè)待排放零件的排樣問題，可行解是由n個(gè)對(duì)象組成的序列，序列中每個(gè)零件對(duì)象都包含排放順序和旋轉(zhuǎn)角度兩個(gè)變量。

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

2.1.2構(gòu)造初始種群

在遺傳算法中，初始種群的質(zhì)量對(duì)算法的收斂速度和尋優(yōu)能力影響較大。隨機(jī)生成初始種群的方式可以保證個(gè)體的多樣性，在排樣問題中，這種方法產(chǎn)生的初始解中零件的排放順序和旋轉(zhuǎn)角度都是隨機(jī)的。當(dāng)零件數(shù)量較多時(shí)，解空間的規(guī)模會(huì)比較大，搜索范圍很廣，很難在一定時(shí)間內(nèi)搜索到最優(yōu)解，求解效率大大降低。

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

2.2 個(gè)體定位策略及適應(yīng)度計(jì)算

2.2.1個(gè)體定位策略

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

在早期研究中，文獻(xiàn)[11]采用BL準(zhǔn)則定位零件位置，該算法實(shí)現(xiàn)簡單，被廣泛應(yīng)用于排樣問題的求解，但其容易造成空腔的浪費(fèi)，且定位位置不一定是最優(yōu)解。針對(duì)BL定位策略存在的問題，本文使用臨界多邊形(NFP)[12]判定零件之間的位置關(guān)系，同時(shí)結(jié)合BL定位原則，盡量選擇NFP最左、最下方的頂點(diǎn)排放零件，可以解決BL算法定位位置不合理的問題?；贜FP和BL準(zhǔn)則的定位策略步驟描述如下：

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

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

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

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

2.2.2適應(yīng)度計(jì)算

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

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

(6)

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

適應(yīng)度函數(shù)值F(Xi)表示可行解Xi對(duì)應(yīng)的板材利用率，F(xiàn)(Xi)越大，其對(duì)應(yīng)可行解序列的質(zhì)量越好。

2.3 并行交叉遺傳算法的進(jìn)化過程

2.3.1選擇操作

種群經(jīng)過交叉和變異之后，一部分個(gè)體將被挑選出來產(chǎn)生下一代群體，這個(gè)過程即為選擇操作。選擇過程中，通?；趥€(gè)體的適應(yīng)度進(jìn)行優(yōu)勝劣汰操作，適應(yīng)度高的個(gè)體更容易進(jìn)入下一代，適應(yīng)度低的個(gè)體則被淘汰，這樣有利于優(yōu)良基因的擴(kuò)展。

目前常用的選擇方法有輪盤賭法、隨機(jī)遍歷選擇法及錦標(biāo)賽選擇法等。本文基于保留最佳個(gè)體策略，采用輪盤賭法對(duì)執(zhí)行交叉操作的兩個(gè)父代個(gè)體進(jìn)行選擇，步驟如下：

Step1保留父代中適應(yīng)度函數(shù)值最大的個(gè)體至下一代，并在父代中將其移除。

Step4重復(fù)Step 3，直至新的種群構(gòu)建完成。

2.3.2交叉操作

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

圖3 交叉操作

2.3.3變異操作

根據(jù)二維不規(guī)則排樣問題的具體情況和特點(diǎn)，我們選擇交換變異法進(jìn)行變異操作。在執(zhí)行變異操作時(shí)，需要通過變異概率pm與在[0,1]內(nèi)生成的隨機(jī)數(shù)p的大小進(jìn)行對(duì)比，來確定是否需要進(jìn)行變異操作。當(dāng)pm>p時(shí)執(zhí)行變異操作；否則，不執(zhí)行變異操作。

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

圖4 交換變異

2.4 基于并行交叉遺傳算法的排樣優(yōu)化算法

本文基于并行交叉遺傳算法求解二維不規(guī)則排樣優(yōu)化問題，其主要思想是模擬兩個(gè)獨(dú)立島上的生物雜交進(jìn)化過程。

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

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

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

Step2分別對(duì)種群A、B中的個(gè)體采用基于臨界多邊形的BL定位策略排放零件，計(jì)算所有個(gè)體的適應(yīng)度函數(shù)，并按照適應(yīng)度函數(shù)值的大小降序排列，保存種群B中的最優(yōu)個(gè)體。

Step3對(duì)兩個(gè)種群中的個(gè)體執(zhí)行選擇、交叉、變異操作后，分別產(chǎn)生N個(gè)新的個(gè)體。其中，將Step2中保存下來的種群B中的最優(yōu)個(gè)體作為種群A執(zhí)行交叉操作時(shí)的一個(gè)父代。

Step4對(duì)Step 3中產(chǎn)生的新個(gè)體繼續(xù)執(zhí)行Step 2。同時(shí)，種群A和種群B分別保存最好的N個(gè)個(gè)體。

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

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

圖5 并行交叉遺傳算法

3 實(shí) 驗(yàn)

為了驗(yàn)證算法的可行性和有效性，采用Java語言實(shí)現(xiàn)了本文的排樣優(yōu)化算法，并基于ESICUP提供的幾個(gè)基準(zhǔn)用例測(cè)試了算法性能。

實(shí)驗(yàn)統(tǒng)一采用原材料板材的利用率ρ作為主要比較參數(shù)，其計(jì)算公式如下：

(7)

表1為并行交叉遺傳算法的相關(guān)配置參數(shù)。實(shí)驗(yàn)時(shí)對(duì)于每個(gè)測(cè)試用例都進(jìn)行了10次實(shí)驗(yàn)，并從板材的最優(yōu)利用率和平均利用率兩方面將本文算法的實(shí)驗(yàn)結(jié)果與TOPOS[13]算法和傳統(tǒng)遺傳算法的結(jié)果進(jìn)行了比較。采用傳統(tǒng)遺傳算法求解排樣問題的實(shí)驗(yàn)數(shù)據(jù)來源于文獻(xiàn)[14]。詳細(xì)的實(shí)驗(yàn)結(jié)果對(duì)比見表2和表3。

表3 算法比較

觀察表2和表3可以發(fā)現(xiàn)，在求解二維不規(guī)則排樣問題時(shí)，本文采用的并行交叉遺傳算法結(jié)果均優(yōu)于傳統(tǒng)遺傳算法。與TOPOS算法相比，本文算法的排樣效果明顯更優(yōu)，尤其是SHIRTS用例，原材料利用率明顯提高。

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

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

此外，排樣結(jié)果中最優(yōu)利用率和平均利用率的值比較接近，說明并行交叉遺傳算法在有限的進(jìn)化代數(shù)下比較穩(wěn)定。因此，本文提出的排樣優(yōu)化算法具有很強(qiáng)的實(shí)用性，可以有效解決實(shí)際加工生產(chǎn)中的二維不規(guī)則排樣問題。

圖7為MARQUES測(cè)試樣例的最優(yōu)解進(jìn)化收斂曲線，可以看出種群經(jīng)過較少的進(jìn)化次數(shù)就趨于收斂，說明并行交叉遺傳算法具有較快的全局收斂速度。

圖7 MARQUES最優(yōu)解進(jìn)化收斂曲線圖

另外，隨著進(jìn)化代數(shù)的遞增，曲線逐漸趨于穩(wěn)定值，表明本文算法穩(wěn)定可行。其中，曲線的平穩(wěn)部分表示算法暫時(shí)處于局部最優(yōu)狀態(tài)，出現(xiàn)階梯跳變則表示在解空間內(nèi)搜索到了更優(yōu)解。

4 結(jié) 語

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