秦振浩

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

引言

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

1 問題描述及模型建立

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

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。

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

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

2 相關(guān)方法描述

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

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

圖1 零件的預(yù)處理

2.2 多種群遺傳算法

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

2.2.1編碼

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

2.2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來評價個體質(zhì)量優(yōu)劣的，個體的適應(yīng)度值越高，質(zhì)量越高。反之，質(zhì)量越低。文中采用的適應(yīng)度函數(shù)為目標(biāo)函數(shù)。

2.2.3 選擇操作

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

2.2.4 交叉操作

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

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

2.2.5 變異操作

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

式中：fm為種群內(nèi)待變異個體的適應(yīng)度值；pm1和pm2為預(yù)先設(shè)定的兩個固定值。對變異概率進(jìn)行動態(tài)的調(diào)整既能保持種群內(nèi)個體的多樣化，還可以克服算法限入局部解的弊端。

判斷某個染色體是否變異，通過在（0，1）內(nèi)隨機(jī)生成一個數(shù)r，當(dāng)pm＞r時，執(zhí)行變異操作，否則不執(zhí)行。文中變異操作是對零件的入排順序向量和入排角度向量進(jìn)行的，對零件的入排順序向量執(zhí)行交換變異，對入排角度向量執(zhí)行旋轉(zhuǎn)變異。

2.2.6 移民操作

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

2.3 剩余矩形匹配算法

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

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

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

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

3 實例驗證與分析

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

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

表1 排樣結(jié)果對比

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

圖2 第1張板材排樣圖

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

4 結(jié)論

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