基于多種群遺傳算法和剩余矩形匹配算法不規(guī)則件優(yōu)化排樣

秦振浩

（河北工業(yè)大學經(jīng)濟管理學院， 天津 300400）

引言

二維不規(guī)則件排樣問題是指將一系列形狀不規(guī)則的二維平面零件盡可能以最優(yōu)方式排放到矩形板材當中，使得板材的利用率最大。該問題廣泛存在于現(xiàn)實的生產(chǎn)生活中，從鈑金下料、玻璃切割、紙品剪裁再到家具生產(chǎn)，都能夠看到其應用，在數(shù)學上該問題屬于NP-Hard 的組合優(yōu)化問題，計算過程復雜多變，計算量是呈爆炸性的，很難求出最優(yōu)解。因此，對二維不規(guī)則件排樣問題的研究具有重要的理論和實用價值。

本文通過矩形包絡法將二維不規(guī)則件排樣問題轉(zhuǎn)化為矩形件排樣問題，研究基于多種群遺傳算法在零件入排序列和角度上的應用，以及剩余矩形匹配算法在零件排放策略中的應用，從而實現(xiàn)二維不規(guī)則件排樣問題的綜合求解。

1 問題描述及模型建立

二維不規(guī)則件排樣問題通常可以描述為：將n 個形狀不完全相同的二維不規(guī)則件{p1，p2，…，pn}不重疊地排放到m 張長為W、寬為H 的矩形板材A 中，在排樣過程中，入排零件需要滿足特定的條件才能保證排樣過程順利進行。這些約束條件包括：

1）pi與pj互不重疊；i≠j，i，j=1，2，…，n.

2）pi必須排在板材A 內(nèi)部；i=1，2，…，n.

3）pi可以旋轉(zhuǎn)一定的角度；i=1，2，…，n.

假設F 表示板材利用率，S 表示所有入排零件的面積之和，本文的研究目標為板材利用率最大，定義板材利用率為所有入排零件的面積之和與板材面積之比，則二維不規(guī)則件的數(shù)學模型如下：

其中：式（2）確保了入排零件之間沒有交疊部分；式（3）確保了入排零件不超過板材的邊界；式（4）中的表示零件旋轉(zhuǎn)的角度，式（4）限制了零件可旋轉(zhuǎn)的角度。

2 相關方法描述

2.1 不規(guī)則件的預處理

直接將不規(guī)則件排放到板材內(nèi)部，操作起來相當復雜，需要考慮到復雜的幾何問題，包括需要計算不規(guī)則件的大小、判斷其排放位置和是否重疊等，為了簡化不規(guī)則件的排樣問題，學者們相繼提出了一些零件預處理方法，包括矩形包絡法、組合包絡法等[1]。本研究組合使用這兩種方法，對近似矩形的不規(guī)則件直接使用矩形包絡法求其最小包絡矩形，對形狀互補的兩個或多個零件首先進行平移、旋轉(zhuǎn)進行組合包絡，然后運用矩形包絡法求其最小包絡矩形，如圖1 所示。

2.2 多種群遺傳算法

零件的入排順序問題屬于典型的NP-Hard 組合優(yōu)化問題，針對該問題，本研究采用多種群遺傳算法，設置3 個進化種群，并將這3 個進化種群分為兩部分，第一部分有1 個種群，該種群內(nèi)的個體基因序列依據(jù)待排零件的面積有序生成，這是啟發(fā)于現(xiàn)實中工人的經(jīng)驗排樣，先排放面積大的零件再排放面積小的零件，這種排樣方式能夠起到加速收斂的目的，同時優(yōu)先排放面積大的零件，面積小的零件在后續(xù)排樣中將具有更高的靈活性[2]。第二部分有2 個種群，這2個種群內(nèi)的個體序列都是隨機生成的，設置2 個隨機種群也是為了提高算法的搜索范圍。

2.2.1 編碼

本研究采用組合編碼方式，用整數(shù)編碼來確定零件的入排順序，每個零件給定一個入排序號；用二進制編碼來確定零件的入排角度，1 代表零件旋轉(zhuǎn)90°，0 代表零件旋轉(zhuǎn)0°，將零件入排序號排列成串再加上一個與之對應的二進制編碼串就是一個可行解。

2.2.2 適應度函數(shù)

適應度函數(shù)是用來評價個體質(zhì)量優(yōu)劣的，個體的適應度值越高則質(zhì)量越高，反之質(zhì)量越低，文中采用的適應度函數(shù)為第2 節(jié)中的目標函數(shù)。

2.2.3 選擇操作

本文基于輪盤賭法對個體進行選擇操作，該方法以個體的適應度值為選擇和淘汰的依據(jù)，個體的適應度值越大被選中的可能性越大，反之被淘汰的可能性越大。

2.2.4 交叉操作

為了提高算法的局部尋優(yōu)性能，本研究采用自適應交叉概率pc，交叉概率的調(diào)整公式為：

式中：f1、favg和fmax分別表示要執(zhí)行交叉操作的兩個父代個體中較大的適應度值、種群內(nèi)當前進化代數(shù)中父代個體的平均適應度值和種群內(nèi)當前進化代數(shù)中父代個體中最大的適應度值；pc1和pc2為預先設定的兩個固定值，從上式中可以看出個體的交叉概率pc會隨著適應度值的取值情況動態(tài)地進行調(diào)整，為此可克服算法的不成熟收斂并避免優(yōu)秀染色體被破壞[3]。判斷兩個父代個體是否交叉，通過在（0，1）內(nèi)隨機生成一個數(shù)r，當pc＞r 時，執(zhí)行交叉操作，否則不執(zhí)行。當染色體執(zhí)行交叉操作時采用兩點環(huán)形交叉方式[4]。

2.2.5 變異操作

與交叉操作相同，本研究同樣基于自適應的思想，采用自適應的變異概率pm，變異概率的調(diào)整公式為：

式中：fm代表種群內(nèi)待變異個體的適應度值；pm1和pm2為預先設定的兩個固定值。對變異概率進行動態(tài)的調(diào)整既能保持種群內(nèi)個體的多樣化，還可以克服算法限入局部解的弊端。判斷某個染色體是否變異，通過在（0，1）內(nèi)隨機生成一個數(shù)r，當pm＞r 時，執(zhí)行變異操作，否則不執(zhí)行。文中變異操作是對零件的入排順序向量和入排角度向量進行的，對零件的入排順序向量執(zhí)行交換變異[3]，對入排角度向量執(zhí)行旋轉(zhuǎn)變異[4]。

2.2.6 移民操作

移民操作主要通過移民算子來進行，以使各個種群的進化不是相互獨立的，而是相互影響、相互協(xié)調(diào)、協(xié)同進化的過程[5]。實施的原則是將每個種群中適應度值最低的個體用相鄰種群中適應度值最高的個體進行替代。

2.3 剩余矩形匹配算法

在由多種群遺傳算法產(chǎn)生個體編碼后需要對其進行解碼，本文采用目前提出的較為有效的排樣定位方法- 剩余矩形匹配算法進行解碼，該方法排樣效果優(yōu)于其他板材定位方法，可充分利用板材區(qū)域，使板材利用率達到最大，具體執(zhí)行步驟如下：

1）初始剩余矩形集為整個板材；

2）按排樣序列將零件排入到板材中，當排入零件時，先從最下方剩余矩形嘗試排入，如果剩余矩形的長和寬均大于入排零件的長和寬則排入，排入時將零件放置到剩余矩形的左下方，更新剩余矩形集；如果待排零件不能排入到最下方剩余矩形的話，對其旋轉(zhuǎn)90°再嘗試進行排放，如能排入則更新入排零件的入排角度，更新剩余矩形集；如還不能排入，則嘗試下一個剩余矩形，如果所有的剩余矩形都不能排入，則嘗試排放下一個零件，更新零件的入排序列。

3）直到目前正在使用的板材已經(jīng)拍不下任何零件后，則將剩余未入排的零件排放到下一張板材中，排放方法同第一張板材，直至所有零件全部排放到板材中。

3 實例驗證與分析

為了驗證本文算法的實用性和有效性，本文通過Matlab2018 進行編程實現(xiàn)，從A 公司收集了一些已經(jīng)排樣完的零件數(shù)據(jù)，對其進行預處理，采用預處理完的零件數(shù)據(jù)作為實驗數(shù)據(jù)，所使用的原材料板材的規(guī)格為2 500 mm×1 250 mm。

本文算法的參數(shù)設置為：每個種群大小均為40、交叉概率和變異概率分別取[0.6，0.9]、[0.05，0.1]之間的動態(tài)值、最優(yōu)個體最少保持代數(shù)為40 代，公司實際排樣結果和本文算法所得排樣結果見表1 所示。

表1 排樣結果對比

本文算法得到的第一張板材的排樣圖如圖2所示。

從表1 中可以看出，排完所需零件公司和本文算法均需使用三張板材，但本文算法對原材料利用的更加充分，前兩張板材的平均利用率高達97.25%，第三張板材的利用率僅為67.3%，要優(yōu)于公司的排樣結果。并且，本文算法的運行結果相對穩(wěn)定，運行時間相對也較短，因此使用本文算法對板材進行優(yōu)化排樣可提高板材的利用率和排樣效率，節(jié)省公司的生產(chǎn)成本。

4 結論

本研究以鈑金件排樣過程為應用背景，通過對不規(guī)則件進行預處理，求出不規(guī)則件的最小包絡矩形，把不規(guī)則排樣轉(zhuǎn)化為矩形件正交排樣，結合多種群遺傳算法和剩余矩形匹配算法進行優(yōu)化排樣，找到問題的最優(yōu)解，確定零件在板材上的合理排放位置。實例證明，本文算法能夠提高板材的利用率和排樣效率，降低企業(yè)的生產(chǎn)成本。