基于遺傳算法的不規(guī)則鋼構(gòu)件排料問題

沈祎萍

摘 要：本文采用遺傳算法結(jié)合臨界多邊形算法與凸包算法，設(shè)計了自助排料的流程，客觀有效地提高了排樣速度。

關(guān)鍵詞：遺傳算法；材料利用率

1 遺傳算法求解不規(guī)則排料問題

1.1 染色體編碼算法

假設(shè)k個零件的編號分別為P1，P2……Pi，k個零件要裝入板材當(dāng)中，需要說明的是，第一塊板材不一定能容下所有的零件，很有可能只是排下其中的一部分，剩下的零件就放入下一塊板材，各個零件Pi（i=1，2，……m）所放入板材中的編號順序就構(gòu)成了該問題的染色體編碼。即我們使用的是等長的字符代碼編碼方法，而不采用通常的二進制編碼方法，因為二進制編碼方法不能較好的適用于該類組合優(yōu)化問題。

1.2 目標(biāo)函數(shù)和適應(yīng)度函數(shù)

目標(biāo)函數(shù)是指在排樣過程中用于判定優(yōu)化結(jié)果的計算式。排料的目標(biāo)是用盡量少的板材排下盡量多的零件，并使板材的利用率最高。假設(shè)一共排放了m塊板材，其中m塊尚未排滿，其余已經(jīng)排滿，每張板材的面積為S，第m塊板材上零件的凸包面積為Sm，本文將目標(biāo)函數(shù)設(shè)為

可見所用板材面積越小，則λ值越大，適應(yīng)度越高。

2 對于不規(guī)則鋼構(gòu)件的排料問題

2.1 模型假設(shè)

（1）假設(shè)不考慮板材厚度影響；

（2）假設(shè)零件與零件之間靠接無損耗，不考慮人為因素使板料破損；

（3）假設(shè)不考慮零件不同部位切割工藝的不同。

2.2 模型建立與求解

已知：（單位：mm）L表示的是直線，L后邊的4個數(shù)字分別表示直線兩端點的坐標(biāo)，板材：2380×1630（一張）

零件一（14個）【五邊形板材】

零件二（14個）【六邊形板材】

自動排料關(guān)鍵問題是在排料的過程中，如何找到排放零件的最佳位置（不重疊且利用率最高）。假設(shè)板材上已經(jīng)排放了n個零件，如何找到排放第n+1個零件的最優(yōu)位置，通常采用的是移動碰觸檢測法，不規(guī)則的零件視為多邊形，具有有限個頂點（如表1）依據(jù)已知所得的不規(guī)則零件，根據(jù)第 n+1個零件的參考點，把第n+1零件排放在臨界多邊形的邊上或頂點上就可以保證零件之間彼此相互接觸，但是彼此之間不重疊。同時，大量研究表明，把零件的參考點排放在臨界多邊形的頂點上，可以達到利用率最高。

所以，臨界多邊形的求解具有重要意義，臨界多邊形構(gòu)成了排料算法的核心算法。當(dāng)求解得到兩個多邊形的臨界多邊形后，由于臨界多邊形具有多個頂點，仍然無法確定第n+1個零件放在哪個位置更優(yōu)，所以通過求解兩個多邊形的凸包，然后計算一下每個頂點的利用率。利用率是已經(jīng)擺放在板材上的零件和零件凸包面積之間的比值，選取比值大的保留。

臨界多邊形的計算只是針對兩個多邊形的計算，所以當(dāng)在板材上擺放了一個新零件后，必須把板材上的多邊形零件合成為一個多邊形，為排放下一個零件做準(zhǔn)備即合成多邊形算法。同時，每個零件都可以旋轉(zhuǎn)任意的角度，零件的排放角度直接影響板材的利用率，但是，我們無法也不可能對零件的每個角度都進行一次計算，通常我們?nèi)讉€特殊的角度來計算，然后去一個最優(yōu)的角度，在本文中，允許零件旋轉(zhuǎn)90，180和270度。

自動排料算法如圖2所示：

板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積的比值。通過計算我們得到板材的利用率為：

2.3 結(jié)果分析

因此，在對多邊形零件直接排樣的研究討論中，我們采用遺傳算法結(jié)合臨界多邊形算法與凸包算法，設(shè)計了自助排料的流程，依據(jù)算法，最終得到板料的利用率最高為85.293%。

參考文獻

[1]黃艷群，徐燕申.基于遺傳算法的不規(guī)則零件近優(yōu)板材排料[J].機械設(shè)計，2002，19（5）：33-35.

（作者單位：南京師范大學(xué)泰州學(xué)院）