秦振浩

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

引言

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

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

1 問題描述及模型建立

二維不規(guī)則件排樣問題通?？梢悦枋鰹椋簩 個(gè)形狀不完全相同的二維不規(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）中的表示零件旋轉(zhuǎn)的角度，式（4）限制了零件可旋轉(zhuǎn)的角度。

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

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

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

2.2 多種群遺傳算法

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

2.2.1 編碼

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

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

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

2.2.3 選擇操作

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

2.2.4 交叉操作

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

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

2.2.5 變異操作

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

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

2.2.6 移民操作

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

2.3 剩余矩形匹配算法

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

1）初始剩余矩形集為整個(gè)板材；

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

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

3 實(shí)例驗(yàn)證與分析

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

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

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

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

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

4 結(jié)論

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