遺傳算法在風管制造排樣中的應用

陳潔瓊，樊留群，楊 劍

（同濟大學 中德學院，上海 201804）

遺傳算法在風管制造排樣中的應用

陳潔瓊，樊留群，楊 劍

（同濟大學 中德學院，上海 201804）

針對風管制造下料的排樣問題，結合包絡矩形算法、空余面積掃描算法和遺傳算法應用，對零件進行旋轉拼接、碰靠處理，提高原材料的利用率。改進了遺傳算法的設計編碼和適應度值，保證整條風管生產線的生產效率和連續(xù)性。設計了排樣程序并進行仿真，結果表明了所提出的算法具有可行性與有效性。

風管；包絡矩形；空余面積掃描；遺傳算法

0 引言

風管生產工序包括：1.卷料自動送料；2.校平、壓筋；3.沖角；4.切斷；5.傳輸；6.咬口；7.共板法蘭成型；8.折彎成型。材料的利用率是下料工藝中要考慮的一個重要問題。排樣方法直接影響材料利用率、零件的精度和加工效率。因此，高效、優(yōu)良的排樣技術是風管零件制造中的關鍵技術之一。利用BIM技術，在風管成型軟件中，將三維立體風管模型進行數字化處理[1]，拆解成二維平面的零件圖紙，形成與排樣系統(tǒng)可通訊的CAM信息，并完成自動化排樣、生成數控加工代碼的過程，將大大減少因人工干預而形成的效率降低和誤差增多現象，并將對降低人工成本、提高產品質量起到根本性作用。

排樣問題可以描述為在一定的板材上，對給定形狀和數量的風管零件進行排布，保證這些零件互不干涉、重疊，且都不超出排樣區(qū)域外。同時要確保材料利用率盡可能高。由于風管在拆分后，大量的零件屬于二維不規(guī)則件，所以不同零件之間的靠接、判交等運算比較復雜，計算量大，加上排樣次序組合的變化、旋轉角度的改變都會生成不同的排樣方案。從計算復雜度上看，這個屬于NP完全問題。因此長期以來，國內外眾多學者都有通過各種方法對這個問題進行了大量的研究，提出了一些解決方法。從當前的研究求解方法歸總起來，針對規(guī)模較大的問題，采用啟發(fā)式算法求解是比較常用的方法，比較經典的啟發(fā)式算法有BL算法及其改進的BLF算法；孫波、李粉利、劉璐[2]等設計了利用剩余矩形排樣算法對二維矩形件排樣問題進行了優(yōu)化，并利用遺傳算法進行排樣求解；謝友寶[3]等人設計了結合遺傳算法和模擬退火算法的混合算法求解了在飛機鈑金零件排樣中的問題。由上述可知，性能穩(wěn)定的遺傳算法被應用的最為廣泛成熟，并且在許多復雜優(yōu)化問題中，都可以得到較為滿意的解。

本文旨在對拆分后的風管零件進行排樣，對現有風管成型軟件中存在排樣方案過于簡單的問題進行優(yōu)化，對二維不規(guī)則零件采用包絡法的預處理，利用空余面積掃描法，并結合遺傳算法，提出一個有效且具有實際應用價值的求解二維不規(guī)則零件排樣優(yōu)化的方法，以提高風管制造材料的利用率。

1 改進的優(yōu)化排樣算法

針對矩形件排樣算法，目前提出的排樣數學模型[4]已經非常成熟，因此本文就不再贅述。本文提出的算法優(yōu)化主要是：1）對二維不規(guī)則零件的矩形包絡處理；2）多塊且長寬有限的板材排樣問題；3）考慮到排樣下料切割板材后要對零件進行風管成型加工，同一編號風管的零部件放在鄰近的板材上進行排樣，優(yōu)化了評價指標。包絡矩形算法，在處理二維不規(guī)則零件排樣上運用廣泛且實用性較高，空余面積掃描算法與傳統(tǒng)的BL排樣算法、下臺階排樣算法、最低水平線排樣算法相比有著較強的局部優(yōu)化性能，而遺傳算法在全局尋優(yōu)搜索方面的性能較好，將三者結合使用，能更加有效的解決風管零件的排樣優(yōu)化問題，據此來尋找最優(yōu)的排樣方案。圖1是整個排樣算法流程圖。

1.1 零件預處理

目前風管零件類型有很多，圖2中列舉出了幾種常見的風管類型和拆分后的零部件。

圖1 排樣流程圖

圖2 常見的風管類型及拆分零部件詳圖

最小包絡矩形算法是一種常用的處理二維不規(guī)則零件排樣優(yōu)化的方法。這種算法的思想就是：利用圖形識別、圖形處理技術，在排樣的初始階段，根據二維不規(guī)則零件的形狀進行相應處理，將零件處理成近似矩形的排樣單元，并以此為基礎對近似成矩形的二維不規(guī)則零件在原材料板材上進行合理的排放，從而獲得全局的近似最優(yōu)排樣方案[5]。

對不規(guī)則風管零件各邊進行矩形包絡，并將形成包絡矩形后的風管零件面積通過比較風管零件面積與包絡后的矩形面積比值，選擇面積最小的包絡矩形作為排樣方案中的待選零件集。設置一個最小包絡率，篩選出待選零件集中小于該包絡率的不規(guī)則風管零件，對其進行圖形拼接與碰靠組合。

對不規(guī)則零件首先進行圖形旋轉拼接與碰靠進行組合后，再進行矩形包絡。以R接頭的兩個零部件舉例說明，如圖3所示。

圖3 R接頭零部件拼接組合包絡

R接頭完成拼接與碰靠組合后進行的矩形包絡，明顯比單個零件進行包絡所占用的面積要小。當所需排樣的所有風管零件都生成最小包絡矩形后，不規(guī)則風管零件的排樣問題就轉化為標準的矩形件排樣問題。

1.2 個體編碼設計

對于采用空余面積掃描法的排樣算法，決定最終排樣方案的是各個零件排到板材上的順序以及零件放置的角度。而由于零件采用最小包絡矩形進行了預處理，因此零件的放入角度只有橫放和豎放兩種情況。最終決定采用三層染色體編碼作為遺傳算法的編碼方案。

圖4 編碼方式

在該編碼方案中，第一層染色體的數字代表著零件的順序，第二層染色體的數字代表所屬風管編號，第三層染色體的數字代表組成第二層中風管的零件編號，而正負號代表零件的放入方向，正號代表橫放，負號代表豎放。例如，當一個染色體的編碼為{-41，32，21，-12，43}時，代表著編號4風管序號為1的零部件，編號3風管的序號為2的零部件，編號2風管的序號為1的零部件，編號1風管的序號為2的零部件，編號4風管的序號為3的零部件按照12345的順序放入板材。其中41和12零件為豎放，23、34、43號零件為橫放。

圖5 樣片染色體三層編碼方法

這樣，染色體就與排樣結果之間就形成了一一對應的關系。通過對染色體組成的種群進行擇優(yōu)、交叉、變異的操作，最終得到最優(yōu)個體，也就得到了最優(yōu)的排樣方案。

1.3 排樣定位方法

空余面積掃描算法是基于剩余矩形排樣算法提出的一種排樣算法。剩余矩形排樣算法在計算時，是統(tǒng)計板材上所有未被利用的剩余空白矩形區(qū)域，將待排矩形件插入到剩余的空白矩形面積，能有效的提高板材的利用率。而本文所使用的空余面積掃描算法是將板材中的剩余空白區(qū)域算為一個數據集。每一個待排入的矩形件都要根據這個剩余空白區(qū)域數據集記錄的位置來選擇一個合理的位置排放。設一組經過最小包絡法預處理的風管零件的排樣序列Pi（i=1，2，3，…，n）

空余面積掃描算法的具體步驟為：

1）設置初始剩余空白區(qū)域數據集為整個板材。

2）成功排入矩形件Pi-1后更新剩余空白區(qū)域數據集，為矩形件Pi的排入做準備。

3）矩形件Pi在排入時，先選擇空白區(qū)域數據集中最左下的點進行嘗試，將矩形件Pi的左下角頂點與空白區(qū)域最左下的點（x，y）重合，在此點坐標（x，y）上加個矩形件Pi的wi和hi值，得到坐標（x+wi，y+hi），通過與空白區(qū)域數據集的長寬坐標點對比，若均不超出空白數據集的長寬坐標點，則將該矩形件排入。如果不能排入，則將空白區(qū)域最左下的坐標點（x，y）在X軸、Y軸方向上各加一個步進值，重新嘗試排入。

4）當矩形件Pi在排入板材Ri時，在該塊板材中的所有空白區(qū)域數據集中都無法將該矩形件排入，則將該矩形件排入板材Ri+1中。

5）重復上述步驟，直到將所有矩形件全部排入板材中為止。

1.4 評價指標

在該問題中所要優(yōu)化的目標函數為F=H，即要使排樣后所有零件占用板材的總體高度H最小，另一個就是同編號的風管零件要求排放在鄰近的板材上，以每三塊板材進行篩選，統(tǒng)計種群中個體里能完整組成同編號風管的染色體數量，數值越高的個體，適應度函數越高。而在遺傳算法中，適應度函數代表著個體適應選擇的能力，適應度函數越高，則個體越容易在選擇中留存下來。故選取適應度函數Ffitness=1/H。這樣個體對應的排樣方案中零件所占的高度H越小，個體的適應度函數就越高。

在按評價指標擇優(yōu)后，上一代種群中的個體需要通過選擇、交叉、變異三個過程來產生下一代種群。

2 實例應用

本文的算法主要將應用于風管制造數控下料切割軟件系統(tǒng)中，系統(tǒng)運用C#語言在Visual Studio中編程設計系統(tǒng)，結合上述三種算法排樣，以三種規(guī)格風管BIM模型為例，進行排樣應用，最終生成可視化PDF格式的風管零件排樣圖紙，以及其對應NC代碼的CNC格式文件，并且將每次排樣的運算時間，零件編號、左下角坐標值以及最佳適應度值輸出在txt格式文本文件。為了測試本文中使用的算法的有效性，對此進行了實例排樣驗證，最終用以解決風管制造數控下料的排樣問題。

算例：測試排樣數據如下：板材的尺寸為2000mm×1500mm，利用Visual Studio設計的系統(tǒng)UI界面總共包括了三個部分：

1）算法排樣區(qū)：該區(qū)域設有“讀取數據”按鈕，在后臺代碼中添加了讀取零件坐標值和尺寸，并且對拆分的風管零件進行最小包絡法預處理的功能?！伴_始排序”按鈕則是對獲取的零件，通過空余面積掃描法和遺傳算法的混合算法，進行排樣處理，最終獲取各零件在板材中的坐標值，并在后臺導出各點坐標值的文本文件，為后續(xù)生成切割所用NC代碼做準備。排樣進度條的作用可以使用戶對排樣算法時間有個直觀的了解，在后臺的文本中，對每次排樣的運算時間也有相應的記錄，該算法經多次運算測試，在代數為50代的情況下，運算時間穩(wěn)定在5s～10s之間。

2）展示區(qū)：在該區(qū)域中顯示出最終排樣結果的圖紙，用于檢驗排樣算法的有效性，令整個排樣結果可視化，并且保存成PDF的文件格式，供用戶打印閱覽。

3）工藝區(qū)：調用后臺產生的坐標值文本文件，根據項目風管制造商所使用設備的ACL控制器代碼標準，顯示數控下料切割系統(tǒng)可直接讀取運行的NC代碼。并保存成CNC文件格式，直接可以利用U盤等數據傳輸工具，導入數控下料切割系統(tǒng)中運行。

【】【】

圖6展示了測試排樣零件最終的排樣結果和切割用NC代碼。

圖6 排樣實例展示圖

3 結束語

本文的排樣方法是使用包絡矩形處理，將不規(guī)則風管零件包絡成矩形進行排樣，并且結合空余面積掃描算法的局部優(yōu)化特點和遺傳算法全局搜索的優(yōu)點，進行排樣處理，取得了理想的結果。并最終將該算法成功應用到風管零件排樣中。與現有的風管排樣方式比較，提高了風管板材的原材料利用率，也提高了風管生產的效率，降低了成本，對風管制造生產有著一定的實際應用價值。

[1] 賀明玄,沈峰.基于BIM的鋼結構數字化制造[A].2014年中國鋼結構行業(yè)大會論文集[C].2014,10：121-136.

[2] 孫波.鈑金件剩余矩形排樣遺傳優(yōu)化方法研究[J].西安工業(yè)大學學報,2015,35(4)：287-292.

[3] 謝友寶,羅婷婷,李凌輝,呂永海.混合遺傳算法在飛機鈑金零件排樣中的應用[J].機械與電子,2009,(12)：18-21.

[4] 楊衛(wèi)波.基于遺傳模擬退火算法的矩形件優(yōu)化排樣[J].計算機工程與應用,2016,52(7)：259-263.

[5] 盧齊飛,唐平,張光富,包夢華.改進的遺傳算法優(yōu)化二維不規(guī)則圖形排樣[J].計算機工程與設計,2013,34(4)：1409-1414.

Genetic algorithm application in air duct sheet metal parts layout

CHEN Jie-qiong, FAN Liu-qun, YANG Jian

TP391

：A

：1009-0134(2017)05-0113-04

2017-02-09

陳潔瓊（1991 -），女，浙江杭州人，碩士研究生，研究方向為自動化生產線。