孟子暄

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

引言

板材下料問題又稱為二維板材排樣問題（Nesting Problems），是指將一系列二維平面圖形互不交叉的放置在某一板材上，使得所覆蓋的板材面積最大[1]。對(duì)于企業(yè)而言，板材的利用率越高，越節(jié)約材料，所用成本越少，對(duì)提高企業(yè)經(jīng)濟(jì)效益起到關(guān)鍵作用。

將遺傳算法與改進(jìn)后的BL算法進(jìn)行結(jié)合，解決矩形件排樣問題，取得了不錯(cuò)的排樣效果。但本文運(yùn)用遺傳算法與最低水平線法相結(jié)合，解決了BL算法的局限性。

1 排樣問題及數(shù)學(xué)描述

假設(shè)板材的長(zhǎng)度為L(zhǎng)，寬為W，面積為S，需要切割的小板材長(zhǎng)為xi，寬為yi（i表示第i種需要切割的小板材，i=1，2，3…，n），板材剩余面積為 Areal。當(dāng)零件橫放時(shí)占用的空間為li，豎放占用的空間是ki。xili表示在原料板上第j塊區(qū)域內(nèi)橫放零件的行數(shù)；yiki表示板材上第j塊區(qū)域內(nèi)小板材豎放的行數(shù)。nj表示板材上第j塊區(qū)域內(nèi)零件橫放時(shí)每行的個(gè)數(shù)；mj表示大板材上第j塊區(qū)域內(nèi)小板材豎放時(shí)每行的個(gè)數(shù)。

本研究目標(biāo)：板材利用率最高，即板材剩余面積最小。

排放基本原則：將所需零件排放在定長(zhǎng)定寬的原材料板中，零件的長(zhǎng)或?qū)捙c原材料板平行，零件之間不可交叉，且不得超過原材料板的長(zhǎng)或?qū)?。即滿足：

根據(jù)給出的約束條件和目標(biāo)函數(shù)的數(shù)學(xué)模型，評(píng)估各個(gè)染色體的優(yōu)劣，篩選出符合該數(shù)學(xué)模型的可行解，該可行解即為最優(yōu)解。

2 遺傳算法

2.1 染色體編碼與解碼

染色體編碼是遺傳算法最關(guān)鍵的步驟，其是一種可以將實(shí)際待優(yōu)化問題的可行解轉(zhuǎn)化到遺傳算法可以處理的搜索空間中的一種方法。本文采用整數(shù)編碼，對(duì)待排零件按順序進(jìn)行編碼，例如 2、3、5、1、4 代表將零件如圖1所示順序進(jìn)行依次排放，0代表零件橫放，1代表零件豎放。運(yùn)用“最低水平線”進(jìn)行解碼。

圖1 板材排放順序示意圖

2.2 種群初始化

隨機(jī)產(chǎn)生N個(gè)染色體作為初始種群，遺傳過程中的收斂速度會(huì)受到初始種群大小的影響，因此N的取值應(yīng)選擇適當(dāng)，一般N取值在50～200之間，本文N選取60。

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

適應(yīng)度函數(shù)指引著遺傳算法的搜索方向，適應(yīng)度函數(shù)的選擇應(yīng)該根據(jù)具體的問題而定，本研究中適應(yīng)度函數(shù)為板材剩料率，即為目標(biāo)函數(shù)。

2.4 遺傳算子

2.4.1 選擇算子

輪盤賭選擇算法是遺傳算法中最常用的選擇算法，其根據(jù)群體中每個(gè)染色體的適應(yīng)值得到群體所有染色體的適應(yīng)值總和，并分別計(jì)算每個(gè)染色體適應(yīng)值與群體適應(yīng)值總和的比pi；較優(yōu)染色體的pi值較大，被選擇的概率就相對(duì)較大。

2.4.2 交叉算子

交叉操作是遺傳算法中的的核心操作步驟,是種群中產(chǎn)生新個(gè)體的主要途徑之一。一般情況下,設(shè)置交叉概率為0.4～0.9之間。

本文涉及的交叉操作算子方法為：首先在染色體上選擇一個(gè)位置作為交叉位置，交叉位置之前的基因片段不交叉，交叉位置之后的片段交叉。

去除染色體X和Y的不變片段中相同基因，將X染色體中剩余基因存至數(shù)組P中，同理，將Y染色體中剩余基因存至數(shù)組Q中。

將染色體X和Y的交叉部分進(jìn)行比較,將相同部分進(jìn)行替換，替換之后染色體符合實(shí)際要求。

2.4.3 變異算子

在遺傳算法中，產(chǎn)生新一代的個(gè)體主要依靠的是選擇和交叉，變異操作是一種產(chǎn)生多樣性個(gè)體的輔助手段，變異算子設(shè)計(jì)的好壞能決定算法的局部搜索能力。變異概率較小，一般設(shè)為0.000 1～0.1之間。

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

為了檢驗(yàn)遺傳算法在求解工程二維不規(guī)則排樣問題方面的有效性，本文以K公司為例，從其套料零件數(shù)據(jù)庫(kù)中隨機(jī)選取了一組具有不同形狀的多種類、多數(shù)量零件進(jìn)行混合排樣計(jì)算，零件種類為10種，零件總數(shù)量為44，加工余量為2 mm，從板材庫(kù)中選擇矩形板材長(zhǎng)為2 500 mm，寬為1 250 mm；設(shè)置算法基本運(yùn)行參數(shù):種群大小200、初始交叉率0.16、變異率0.106，設(shè)置最大迭代數(shù)為500，調(diào)用遺傳算法確定零件的排放順序和旋轉(zhuǎn)角度，用基于最低水平線法策略的動(dòng)態(tài)掃描線算法的解碼定位算法確定零件在板材的位置。排樣布局如圖2所示。

圖2 多種矩形件算法排樣結(jié)果示意圖

優(yōu)化結(jié)果與公司實(shí)際排樣結(jié)果對(duì)比如表1所示。

表1 算法結(jié)果對(duì)比示意表

根據(jù)上述結(jié)果對(duì)比可以看出，本文算法具有很好的穩(wěn)定性，尋優(yōu)運(yùn)行時(shí)間較短，板材利用率更高，具有很強(qiáng)的工程實(shí)用價(jià)值，因此，本文遺傳算法能夠有效求解矩形零件的排樣問題。

4 結(jié)語

針對(duì)鈑金矩形件的排樣問題，本文提出運(yùn)用遺傳算法進(jìn)行優(yōu)化，將板材運(yùn)用整數(shù)順序編碼法進(jìn)行編碼，運(yùn)用最低水平線算法進(jìn)行解碼的方法對(duì)矩形件運(yùn)用遺傳算法進(jìn)行優(yōu)化求解，運(yùn)算結(jié)果顯示，該算法優(yōu)于公司實(shí)際排樣效果，大大提高板材利用率，節(jié)約公司成本。