基于多種群遺傳算法和剩余矩形匹配算法不規則件優化排樣

秦振浩

（河北工業大學經濟管理學院，天津 300400）

引言

二維不規則件排樣問題是指將一系列形狀不規則的二維平面零件盡可能以最優方式排放到矩形板材當中，使得板材的利用率最大。該問題廣泛存在于現實生產生活中，從鈑金下料、玻璃切割、紙品剪裁到家具生產，都能夠看到其實際應用。在數學上該問題屬于NP-hard的組合優化問題，計算過程復雜多變，計算量是呈爆炸性的，很難求出最優解。因此，對二維不規則件排樣問題的研究具有重要的理論和實用價值。本文通過矩形包絡法將二維不規則件排樣問題轉化為矩形件排樣問題，研究基于多種群遺傳算法在零件入排序列和角度上的應用以及剩余矩形匹配算法在零件排放策略中的應用，從而實現二維不規則件排樣問題的綜合求解。

1 問題描述及模型建立

二維不規則件排樣問題通?？梢悦枋鰹椋簩個形狀不完全相同的二維不規則件{p1，p2，…，pn}不重疊地排放到m張長為W、寬為H的矩形板材A中，在排樣過程中，入排零件需要滿足特定的條件，才能保證排樣過程順利進行。這些約束條件包括：

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

2）pi必須排在板材A內部，i＝1，2，…，n；

3）pi可以旋轉一定的角度，i＝1，2，…，n。

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

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

2 相關方法描述

2.1 不規則件的預處理

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

圖1 零件的預處理

2.2 多種群遺傳算法

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

2.2.1編碼

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

2.2.2 適應度函數

適應度函數是用來評價個體質量優劣的，個體的適應度值越高，質量越高。反之，質量越低。文中采用的適應度函數為目標函數。

2.2.3 選擇操作

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

2.2.4 交叉操作

為了提高算法的局部尋優性能，本研究采用自適應交叉概率，交叉概率的調整公式為：

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

2.2.5 變異操作

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

式中：fm為種群內待變異個體的適應度值；pm1和pm2為預先設定的兩個固定值。對變異概率進行動態的調整既能保持種群內個體的多樣化，還可以克服算法限入局部解的弊端。

判斷某個染色體是否變異，通過在（0，1）內隨機生成一個數r，當pm＞r時，執行變異操作，否則不執行。文中變異操作是對零件的入排順序向量和入排角度向量進行的，對零件的入排順序向量執行交換變異，對入排角度向量執行旋轉變異。

2.2.6 移民操作

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

2.3 剩余矩形匹配算法

在由多種群遺傳算法產生個體編碼后，需要對其進行解碼。本文采用目前最有效的排樣定位方法——剩余矩形匹配算法進行解碼，該方法排樣效果優于其他板材定位方法，可充分利用板材區域，使板材利用率達到最大。具體執行步驟如下：

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

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

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

3 實例驗證與分析

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

本文算法的參數設置為：每個種群大小均為40，交叉概率和變異概率分別?。?.6，0.9］、［0.05，0.1］之間的動態值，最優個體最少保持代數為40代。公司實際排樣結果和本文算法所得排樣結果如表1所示。

表1 排樣結果對比

本文算法得到的第1張板材排樣圖，如下頁圖2所示。

圖2 第1張板材排樣圖

由表1可以看出，排完所需零件公司和本文算法均需使用3張板材。但本文算法對原材料利用的更加充分，前2張板材的平均利用率高達97.25%，第3張板材的利用率僅為67.3%，要優于公司的排樣結果。并且，本文算法的運行結果相對穩定，運行時間相對也較短，因此，使用本文算法對板材進行優化排樣，可提高板材的利用率和排樣效率，節約生產成本。

4 結論

為了求解現代工業生產中普遍存在的二維不規則件排樣問題，提出一種基于多種群遺傳算法和剩余矩形匹配算法的排樣優化算法。通過提取不規則件的最小包絡矩形，將其轉化為矩形件排樣問題，然后應用多種群遺傳算法在全局范圍內搜尋可行解，采用剩余矩形匹配算法作為解碼算法，將搜索到的可行解解碼為排樣圖，最后進行量化評價，推動種群的進化，找到最優解。實例證明，本文算法優于公司現有排樣方法，可提高板材的利用率和排樣效率，降低企業的生產成本。