沈祎萍

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

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

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

1.1 染色體編碼算法

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

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

目標(biāo)函數(shù)是指在排樣過程中用于判定優(yōu)化結(jié)果的計(jì)算式。排料的目標(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個(gè)數(shù)字分別表示直線兩端點(diǎn)的坐標(biāo)，板材：2380×1630（一張）

零件一（14個(gè)）【五邊形板材】

零件二（14個(gè)）【六邊形板材】

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

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

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

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

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

2.3 結(jié)果分析

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

參考文獻(xiàn)

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

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