陳潔瓊，樊留群，楊 劍

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

遺傳算法在風(fēng)管制造排樣中的應(yīng)用

陳潔瓊，樊留群，楊 劍

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

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

風(fēng)管；包絡(luò)矩形；空余面積掃描；遺傳算法

0 引言

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

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

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

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

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

1.1 零件預(yù)處理

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

圖1 排樣流程圖

圖2 常見的風(fēng)管類型及拆分零部件詳圖

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

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

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

圖3 R接頭零部件拼接組合包絡(luò)

R接頭完成拼接與碰靠組合后進(jìn)行的矩形包絡(luò)，明顯比單個(gè)零件進(jìn)行包絡(luò)所占用的面積要小。當(dāng)所需排樣的所有風(fēng)管零件都生成最小包絡(luò)矩形后，不規(guī)則風(fēng)管零件的排樣問題就轉(zhuǎn)化為標(biāo)準(zhǔn)的矩形件排樣問題。

1.2 個(gè)體編碼設(shè)計(jì)

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

圖4 編碼方式

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

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

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

1.3 排樣定位方法

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

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

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

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

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

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

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

1.4 評價(jià)指標(biāo)

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

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

2 實(shí)例應(yīng)用

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

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

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

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

3）工藝區(qū)：調(diào)用后臺(tái)產(chǎn)生的坐標(biāo)值文本文件，根據(jù)項(xiàng)目風(fēng)管制造商所使用設(shè)備的ACL控制器代碼標(biāo)準(zhǔn)，顯示數(shù)控下料切割系統(tǒng)可直接讀取運(yùn)行的NC代碼。并保存成CNC文件格式，直接可以利用U盤等數(shù)據(jù)傳輸工具，導(dǎo)入數(shù)控下料切割系統(tǒng)中運(yùn)行。

【】【】

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

圖6 排樣實(shí)例展示圖

3 結(jié)束語

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

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

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

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

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

[5] 盧齊飛,唐平,張光富,包夢華.改進(jìn)的遺傳算法優(yōu)化二維不規(guī)則圖形排樣[J].計(jì)算機(jī)工程與設(shè)計(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 -），女，浙江杭州人，碩士研究生，研究方向?yàn)樽詣?dòng)化生產(chǎn)線。