楊陽(yáng) 吳亮生 馬敬齊 王楠 廖樹明

?

輕質(zhì)型材加工輔助優(yōu)化關(guān)鍵技術(shù)研究與實(shí)現(xiàn)*

楊陽(yáng)1,2吳亮生1,2馬敬齊1,2王楠1,2廖樹明3

（1.廣東省自動(dòng)化研究所 2.東莞中國(guó)科學(xué)院云計(jì)算產(chǎn)業(yè)技術(shù)創(chuàng)新與育成中心3.韶能集團(tuán)廣東綠洲紙模包裝制品有限公司）

針對(duì)輕質(zhì)型材零件加工材料利用率低、空走路徑長(zhǎng)和效率低等問題，研究零件的排料和走刀路徑優(yōu)化方法。通過對(duì)零件工藝特征參數(shù)圖形化設(shè)計(jì)，并以零件最小外接矩形進(jìn)行編碼設(shè)計(jì)，運(yùn)用遺傳算法求解最優(yōu)布局。同時(shí)為使加工刀具空走路徑最短，將路徑優(yōu)化問題抽象為GTSP求解，采用遺傳算法對(duì)路徑進(jìn)行優(yōu)化以達(dá)到最優(yōu)加工工序，并對(duì)優(yōu)化后路徑進(jìn)行局部尋優(yōu)，實(shí)現(xiàn)空程最短，加工軌跡最優(yōu)。最后進(jìn)行了輕質(zhì)型材輔助加工軟件的設(shè)計(jì)與開發(fā)，并應(yīng)用于數(shù)控機(jī)床上驗(yàn)證測(cè)試。結(jié)果表明：排料效果良好，提高了材料利用率及加工效率。

遺傳算法；排料優(yōu)化；路徑優(yōu)化；包絡(luò)矩形

0引言

目前，輕質(zhì)型材加工企業(yè)為降低生產(chǎn)成本，提高生產(chǎn)效率和經(jīng)濟(jì)效益，通常采用人工排料方法。此方法依靠個(gè)人經(jīng)驗(yàn)，耗時(shí)、耗力，僅能得到一個(gè)較好的準(zhǔn)優(yōu)解，即局部最優(yōu)，無法達(dá)到最大材料利用率。數(shù)控加工含有多個(gè)加工特征，工序隨機(jī)，下刀點(diǎn)設(shè)置隨意，人為影響因素較大，導(dǎo)致刀具空程路徑過長(zhǎng)和起落頻繁。由此增加的走刀路徑，加大能耗，降低加工效率，特別當(dāng)加工特征數(shù)量較大時(shí)，此影響更加明顯。因此研究輕質(zhì)型材加工輔助優(yōu)化技術(shù)，通過計(jì)算機(jī)輔助排料優(yōu)化和加工路徑優(yōu)化，降低材料損耗，提高加工效率，對(duì)輕質(zhì)型材加工具有重要的意義。

目前輕質(zhì)型材加工企業(yè)多采用Mastercam、UG 等國(guó)外編程軟件，不具備排料優(yōu)化與路徑優(yōu)化功能。排料優(yōu)化與路徑優(yōu)化問題，許多國(guó)內(nèi)外學(xué)者做了研究。排料優(yōu)化解決方法主要有啟發(fā)式算法、遺傳算法等。啟發(fā)式算法規(guī)則難以確定，其本質(zhì)是一種局部搜索方法，容易陷入局部最優(yōu)，不易求得問題的全局最優(yōu)解，使排樣結(jié)果不穩(wěn)定，難以在實(shí)際生產(chǎn)過程中得到應(yīng)用。多圖元類型的平面加工路徑優(yōu)化問題轉(zhuǎn)化為廣義旅行商問題（generalized traveling salesman problem，GTSP)，文獻(xiàn)[1]采用遺傳算法求解全局最優(yōu)路徑，但實(shí)際加工中局部走刀路徑無法取得較好的規(guī)劃；文獻(xiàn)[2]采用相鄰最短算法進(jìn)行路徑優(yōu)化，但無法實(shí)現(xiàn)較復(fù)雜路徑圖形求解。

本文針對(duì)目前輕質(zhì)型材加工工藝特點(diǎn)，進(jìn)行了輕質(zhì)型材加工輔助優(yōu)化關(guān)鍵技術(shù)研究與實(shí)現(xiàn)，主要包括：對(duì)常用加工圖形進(jìn)行參數(shù)化設(shè)計(jì)并計(jì)算加工圖元最小外接矩形；排料優(yōu)化問題建模并應(yīng)用遺傳算法對(duì)其求解；采用基于GTSP的遺傳算法進(jìn)行全局加工路徑的優(yōu)化，并進(jìn)行局部再優(yōu)化處理，減少加工過程中空走路徑。

1零件圖形預(yù)處理

1.1零件圖形化參數(shù)設(shè)計(jì)

輕質(zhì)型材加工行業(yè)中，零件工藝參數(shù)化能夠?qū)崿F(xiàn)快速設(shè)計(jì)，滿足零件形狀、精度、工藝的加工需求，提高企業(yè)生產(chǎn)效率。參數(shù)化工藝設(shè)計(jì)是指對(duì)具有代表性的某零件的特征進(jìn)行工藝設(shè)計(jì)，制成模板卡片的形式，卡片中可變部分用參數(shù)進(jìn)行變量化的表達(dá)。在做新零件的工藝時(shí)，只需配置相應(yīng)參數(shù)內(nèi)容，自動(dòng)生成工藝卡片。輕質(zhì)型材加工中常用的零件圖形為圓形、矩形、腰形、鎖孔、圓弧等，對(duì)于任意多邊形，通過DXF文件讀取模塊獲得多邊形實(shí)體數(shù)據(jù)[3]，如頂點(diǎn)坐標(biāo)、邊長(zhǎng)度等。工藝參數(shù)分為公有加工工藝特征變量和私有加工工藝特征變量，其中，公有加工工藝特征變量包括加工深度、下刀高度、抬刀高度、加工平面和加工刀具號(hào)；私有特征變量包括點(diǎn)坐標(biāo)、半徑、長(zhǎng)度、寬度、孔長(zhǎng)和弧寬等。弧形零件工藝參數(shù)如圖1所示。

圖1　圓弧零件圖形化參數(shù)

1.2求取零件最小外接矩形

不規(guī)則圖形排料非常復(fù)雜，難以求出最優(yōu)解。為簡(jiǎn)化求解過程，提取不規(guī)則圖形外部輪廓數(shù)據(jù)，求得零件最小外接矩形，從而轉(zhuǎn)化為矩形件排料問題求解。根據(jù)對(duì)輕質(zhì)型材加工工藝分析，加工過程中為保證零件精度，需對(duì)零件進(jìn)行刀具補(bǔ)償。首先，刀具補(bǔ)償算法依據(jù)文獻(xiàn)[4]提出的基于矢量分析的判別方法，減少刀具補(bǔ)償過程中的冗余計(jì)算；其次，根據(jù)刀具補(bǔ)償形式（左補(bǔ)償或右補(bǔ)償）判斷外補(bǔ)償或內(nèi)補(bǔ)償；最后，依據(jù)補(bǔ)償方式、刀具參數(shù)（刀具半徑）、工藝卡變量計(jì)算零件最小外接矩形面積，其中為矩形長(zhǎng)度，為矩形寬度。內(nèi)補(bǔ)償時(shí)，補(bǔ)償參數(shù)；外補(bǔ)償時(shí)，補(bǔ)償參數(shù)。

1) 常規(guī)圖形

2) 任意多邊形

任意多邊形由多條直線段組成，根據(jù)圖形數(shù)據(jù)計(jì)算多邊形的最小凸包，選取凸包的一條邊作為起始邊，并以該邊中點(diǎn)為中心旋轉(zhuǎn)，使該邊與坐標(biāo)軸平行，計(jì)算此時(shí)多邊形的最小綁定矩形面積和旋轉(zhuǎn)角度，同理得出凸包其他邊所對(duì)應(yīng)的最小綁定矩形面積和旋轉(zhuǎn)角度。對(duì)比選出面積最小者，并按其邊所對(duì)應(yīng)旋轉(zhuǎn)角度逆旋轉(zhuǎn)即得所需的最小面積外接矩形[5]。

2基于最小外接矩形的板材排料優(yōu)化

為提高輕質(zhì)型材零件加工原材料的利用率，本文對(duì)零件進(jìn)行排料優(yōu)化。以零件最小外接矩形為對(duì)象，根據(jù)給定數(shù)量和規(guī)格的原材料，矩形件長(zhǎng)、寬小于型材長(zhǎng)、寬等約束條件建立數(shù)學(xué)模型，采用遺傳算法尋找平面最優(yōu)布局，求取最優(yōu)解[6-7]。

2.1數(shù)學(xué)模型建立

輕質(zhì)型材加工零件排料問題用數(shù)學(xué)語(yǔ)言描述：

2.2染色體編碼

編碼方法在很大程度上決定了如何進(jìn)行群體遺傳進(jìn)化運(yùn)算的效率，常用的編碼方式有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼和格雷碼編碼等。為使遺傳操作易于實(shí)現(xiàn)，本文選用浮點(diǎn)數(shù)編碼，其個(gè)體結(jié)構(gòu)如下：

Typedef struct __Rect_Info

{

Flaot fAngle; //旋轉(zhuǎn)角度

Float fPosX; //外接矩形左上角頂點(diǎn)橫坐標(biāo)

Float fPosY; //外接矩形左上角頂點(diǎn)縱坐標(biāo)

Float fWid; //外接矩形寬度

Float fHei; //外接矩形高度

Float fFitValue; //適應(yīng)度值

}Rect_Info

2.3適應(yīng)度函數(shù)

對(duì)于矩形件排料，板材利用率采用適應(yīng)度函數(shù)來衡量，其值越大，說明板材的利用率越高。適應(yīng)度函數(shù)定義為所排的所有矩形件面積之和與給定尺寸板材的面積之比，即

2.4遺傳操作

1) 選擇算子

采用轉(zhuǎn)輪盤式選擇操作，將群體中適應(yīng)度最差的部分個(gè)體用適應(yīng)度較好的個(gè)體替換，提高種群的整體適應(yīng)度，個(gè)體被選為父代個(gè)體的概率

其中，為種群大?。粸檫m應(yīng)度函數(shù)值。

2) 交叉算子

采用自識(shí)別交叉算子[x1] ，設(shè)定初始交叉概率，最小交叉概率，問題維數(shù)，臨界距離系數(shù)，當(dāng)前迭代次數(shù)，終止代數(shù)，交叉運(yùn)算步驟：

④ 結(jié)束交叉操作。

3) 變異算子

變異算子采用集中因子[8]描述種群的集中程度，利用集中因子控制變異概率，變異運(yùn)算步驟：

3基于GTSP模型的路徑優(yōu)化

針對(duì)排料優(yōu)化后形成的加工圖形亂序排布情況，為減少刀具空程路徑，提升加工效率，本文對(duì)排料后的零件圖形進(jìn)行路徑優(yōu)化。根據(jù)輕質(zhì)型材行業(yè)排料零件圖形多為圓、鎖孔、矩形等封閉圖形特點(diǎn)，將路徑優(yōu)化問題抽象為GTSP求解問題[9]，采用遺傳算法對(duì)路徑進(jìn)行優(yōu)化以達(dá)到最優(yōu)工序，并對(duì)優(yōu)化后路徑進(jìn)行局部尋優(yōu)，可實(shí)現(xiàn)刀具空程最短。

3.1染色體編碼

根據(jù)加工軌跡段類型進(jìn)行分類編碼，染色體編碼如表1所示，其中，C表示第個(gè)編碼點(diǎn)對(duì)象采用實(shí)數(shù)編碼方式。

表1　加工軌跡圖形編碼表

3.2 適應(yīng)度函數(shù)

每段加工軌跡本身長(zhǎng)度不變，其長(zhǎng)度總和視為常數(shù)C。采用線性定標(biāo)適應(yīng)度的方式對(duì)適應(yīng)度函數(shù)進(jìn)行優(yōu)化調(diào)整，個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)為

其中，和為適應(yīng)度調(diào)整系數(shù)；()為路徑長(zhǎng)度。

3.3 選擇、交叉、變異操作

通過遺傳算法選擇、交叉、變異操作[9]，確定初步路徑，其中，是第條軌跡段的編碼幾何點(diǎn)（=1,2,3,...,）；是軌跡段總數(shù)；的長(zhǎng)度為

3.4 優(yōu)化路徑局部尋優(yōu)

圖2　圓軌跡優(yōu)化（有交點(diǎn)）

4輕質(zhì)型材行業(yè)輔助優(yōu)化加工流程

本文通過設(shè)計(jì)零件工藝參數(shù)，實(shí)現(xiàn)加工零件的快速設(shè)計(jì)，利用工藝卡及刀具補(bǔ)償參數(shù)計(jì)算最小面積外接矩形；應(yīng)用遺傳算法進(jìn)行排料優(yōu)化，以減少加工型材浪費(fèi)，提高利用率；利用基于GTSP模型的遺傳算法對(duì)加工圖元路徑進(jìn)行優(yōu)化，優(yōu)化后的路徑進(jìn)行局部尋優(yōu)，實(shí)現(xiàn)加工路徑最短，提高加工效率。輔助加工優(yōu)化技術(shù)流程如圖4所示。

算法步驟：

1) 設(shè)計(jì)零件參數(shù)工藝卡，讀取DXF文件數(shù)據(jù)；

2) 判斷補(bǔ)償方式，計(jì)算零件最小面積外接矩形；

3) 根據(jù)浮點(diǎn)數(shù)編碼規(guī)則對(duì)所有矩形編碼；

4) 確定選擇、交叉、變異操作算子，設(shè)置參數(shù)（群體容量、最大遺傳代數(shù)、初始交叉率等）；

5) 通過評(píng)價(jià)函數(shù)對(duì)染色體群體進(jìn)行評(píng)價(jià)，若滿足結(jié)束條件轉(zhuǎn)至7)，以最大材料利用率為判斷標(biāo)準(zhǔn)；

6) 根據(jù)操作算子產(chǎn)生新一代染色體，返回至5)；

7) 排料優(yōu)化計(jì)算結(jié)束；

8) 建立GTSP模型，對(duì)幾何點(diǎn)信息進(jìn)行編碼，根據(jù)路徑距離最小定義適應(yīng)度函數(shù)，本文以路徑距離大小作為判斷標(biāo)準(zhǔn)；

9) 確定操作算子，設(shè)定參數(shù)（初始種群，遺傳代數(shù)，初始交叉率，變異系數(shù)）；

10) 根據(jù)適應(yīng)度函數(shù)計(jì)算適應(yīng)度值，與評(píng)定函數(shù)比較，滿足條件轉(zhuǎn)至12)；

11) 按照遺傳操作形成下一代群體，返回至10)；

12) 路徑優(yōu)化遺傳算法結(jié)束；

13) 對(duì)優(yōu)化路徑進(jìn)行局部尋優(yōu)，得到最優(yōu)路徑。

以上算法中迭代運(yùn)算過程直至達(dá)到預(yù)定的迭代數(shù)時(shí)為止。

圖4 輔助加工優(yōu)化技術(shù)流程

5開發(fā)實(shí)例

基于WINDOWS操作系統(tǒng)和Visual Studio 2010平臺(tái)開發(fā)實(shí)現(xiàn)了鋁型材行業(yè)輔助優(yōu)化加工軟件，如圖5所示。對(duì)常規(guī)圖形圓、矩形、鎖孔、腰孔、圓弧等進(jìn)行參數(shù)式圖形卡的設(shè)計(jì)，如圖5所示。根據(jù)圖形參數(shù)做圖形化顯示，結(jié)合DXFLIB庫(kù)實(shí)現(xiàn)了DXF圖形的讀取。

圖5　鋁型材數(shù)控板材加工CAM軟件

圖6中中部為設(shè)計(jì)零件顯示區(qū)，零件進(jìn)行排料優(yōu)化初始種群大小20，遺傳代數(shù)33。零件進(jìn)行排料優(yōu)化后的最優(yōu)排料結(jié)果如圖6所示。

圖6　排料優(yōu)化效果圖

優(yōu)化加工軌跡圖如圖7所示，圖中為局部?jī)?yōu)化后的局部路徑及加工圖元路徑，以華中數(shù)控世紀(jì)星編碼格式進(jìn)行G代碼生成，并在數(shù)控板材加工中心進(jìn)行實(shí)際加工，效果良好。

圖7　優(yōu)化加工軌跡圖

6結(jié)語(yǔ)

本文針對(duì)輕質(zhì)型材零件加工中零件排料無法達(dá)到全局最優(yōu)和軌跡段加工走刀路徑優(yōu)化帶來的問題，研究了輕質(zhì)型材加工輔助優(yōu)化技術(shù)。通過對(duì)加工零件進(jìn)行參數(shù)式圖形卡設(shè)計(jì)并計(jì)算最小面積外接矩形，以矩形件為對(duì)象編碼，以面積最大利用率為目標(biāo)函數(shù)，采用遺傳算求解零件的最優(yōu)排布，顯著地提高原材料利用率，同時(shí)將路徑優(yōu)化問題抽象為GTSP，采用遺傳算法對(duì)路徑進(jìn)行優(yōu)化以達(dá)到最優(yōu)工工序，并對(duì)優(yōu)化后路徑進(jìn)行局部尋優(yōu)，可實(shí)現(xiàn)空程最短，提高加工效率。

[1] 徐建明,林示麟,董輝,等.基于遺傳算法的輪廓切割順序受限路徑優(yōu)化[J].控制工程,2011,18(5):767-770.

[2] 沈志榮,謝明紅.基于DXF的數(shù)控切割優(yōu)化排序算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(15):32-35,96.

[3] 雷歡,黃東運(yùn),吳亮生.開放式數(shù)控CAM軟件關(guān)鍵模塊庫(kù)的設(shè)計(jì)與開發(fā)[J].自動(dòng)化與信息工程,2013,34(3):7-12.

[4] 孫海洋,范大鵬.一種新的刀具圓弧過渡補(bǔ)償算法[J].中國(guó)機(jī)械工程,2007,18(3):277-281.

[5] 程鵬飛,閆浩文,韓振輝.一個(gè)求解多邊形最小面積外接矩形的算法[J].工程圖學(xué)學(xué)報(bào),2008(1):122-126.

[6] 毛美姣.基于遺傳規(guī)劃的連接板優(yōu)化排料算法的研究[J].機(jī)械科學(xué)與技術(shù),2008,27(2):180-183.

[7] 杜時(shí)英.遺傳算法在矩形布料排樣中的應(yīng)用研究[J].科教文匯,2015(1):220-221,228.

[8] 孟佳娜,王立宏.具有自識(shí)別能力的遺傳算法求解旅行商問題[J].計(jì)算機(jī)工程與應(yīng)用,2006,26(13):51-52.

[9] 譚陽(yáng),郝志峰,黃翰,等.求解第二類GTSP的距離矩陣重構(gòu)遺傳算法[J].華南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2013,41(3):29-34.

The Optimization of the Key Technology for Lightweight Profile Processing

Yang Yang1,2Wu Liangsheng1,2Ma Jingqi1,2Wang Nan1,2Liao Shuming3

(1. Guangdong Institute of Automation 2.Cloud Computing Center Chinese Academy of Sciences 3.Shaoneng Group Guangdong Luzhou Paper Mould Packing Prouducts Co., Ltd.)

The optimization of the parts discharging and cutting path are studied for the problem of low utilization ratio and long invalid path in the process of lightweight profile processing industry. Through the graphic design of the parts process characteristics, and coding design for the minimum external rectangle of the part. The method uses genetic algorithm to solve the optimal layout. At the same time, in order to make the shortest invalid path of the cutting tool, the path optimization problem is abstracted as GTSP’s solute, and uses genetic algorithm to optimize the path to achieve the optimal processing. Finally, a lightweight profile auxiliary processing software is designed and verified on the CNC machine tools.

Genetic Algorithm; Nesting Allocation Optimization; Path Optimization; Envelope Rectangle

楊陽(yáng)，男，1987年生，本科，主要研究方向：運(yùn)動(dòng)控制、機(jī)器視覺。E-mail: yangyang9814@126.com

吳亮生，男，1987年生，本科，主要研究方向：運(yùn)動(dòng)控制、機(jī)器視覺。

馬敬齊，男，1988年生，碩士，主要研究方向：機(jī)器視覺，自動(dòng)化。

王楠，女，1989年生，碩士，主要研究方向：運(yùn)動(dòng)控制、機(jī)器視覺。

廖樹明，男，1983年生，大專，主要研究方向：工業(yè)自動(dòng)化。

廣東省科技計(jì)劃項(xiàng)目（2013B011302013，2013B091300013，2013B091300011，2014B090920004，2016B090918101）；廣東省科學(xué)院青年科學(xué)研究基金（qnjj201507）。