基于遺傳算法的不規則鋼構件排料問題

沈祎萍

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

關鍵詞：遺傳算法；材料利用率

1 遺傳算法求解不規則排料問題

1.1 染色體編碼算法

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

1.2 目標函數和適應度函數

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

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

2 對于不規則鋼構件的排料問題

2.1 模型假設

（1）假設不考慮板材厚度影響；

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

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

2.2 模型建立與求解

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

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

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

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

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

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

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

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

2.3 結果分析

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

參考文獻

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

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