陳光黎 雷歡 吳亮生 高小征 楊陽 周俊伍

?

基于改進(jìn)遺傳算法的多類圖元混合加工路徑優(yōu)化方法*

陳光黎1雷歡1吳亮生1高小征1楊陽1周俊伍2

（1.廣東省自動化研究所 廣東省現(xiàn)代控制技術(shù)重點實驗室廣東省現(xiàn)代控制與光機(jī)電技術(shù)公共實驗室 2.佛山金皇宇機(jī)械實業(yè)有限公司）

為解決數(shù)控加工中復(fù)雜軌跡的排序規(guī)劃問題，提出基于改進(jìn)遺傳算法的多類圖元混合加工路徑優(yōu)化方法。針對不同軌跡段圖形進(jìn)行分類編碼設(shè)計，將適用多類圖元混合路徑優(yōu)化的第二類GTSP模型轉(zhuǎn)化為TSP問題，同時在遺傳進(jìn)化過程中采用線性定標(biāo)和自適應(yīng)遺傳算子等方式進(jìn)行全局路徑排序，最后通過封閉式與非封閉式軌跡段的起點計算與局部尋優(yōu)求解最短路徑。通過擴(kuò)展應(yīng)用開源GAlib庫進(jìn)行了測試，試驗證明：算法快速收斂，有效解決多類圖元混合路徑優(yōu)化問題，可提升數(shù)控機(jī)床加工效率。

GTSP模型；遺傳算法；多類圖元混合軌跡；路徑優(yōu)化

0 引言

在數(shù)控加工作業(yè)中，通常要求CAM軟件能夠讀取AutoCAD的圖形數(shù)據(jù)并將其轉(zhuǎn)化為數(shù)控加工系統(tǒng)所執(zhí)行的加工G代碼。圖形交互式文件（drawing interchange format，DXF）是Autodesk公司推出的AutoCAD與CAD/CAM編程系統(tǒng)進(jìn)行加工圖形數(shù)據(jù)交換的標(biāo)準(zhǔn)格式文件[1]。但DXF文件中的圖形元素是依據(jù)產(chǎn)品設(shè)計人員繪制圖元的先后順序而自動保存的，具有一定的隨機(jī)性。若CAM系統(tǒng)對讀取的DXF文件圖元數(shù)據(jù)不進(jìn)行優(yōu)化處理而直接產(chǎn)生加工G代碼，會造成數(shù)控加工系統(tǒng)刀具的空程路徑過長和頻繁起落。根據(jù)加工對象的復(fù)雜度即加工軌跡段數(shù)量，非切削時間占整個加工任務(wù)周期的15%~30%[2]。當(dāng)加工軌跡段較復(fù)雜時將明顯降低加工效率并影響刀具使用壽命，因此對DXF文件中的加工圖元信息進(jìn)行空程路徑優(yōu)化顯然尤為重要。

目前，國內(nèi)外學(xué)者對數(shù)控加工路徑優(yōu)化做了許多研究，但大多集中在孔群加工路徑優(yōu)化[3-6]，平面加工輪廓的路徑優(yōu)化也有部分相關(guān)研究，但主要針對封閉式加工輪廓或支持簡單圖元類型，而對多圖元復(fù)雜混合軌跡加工路徑優(yōu)化問題的研究相對較少。通常孔群路徑優(yōu)化問題可當(dāng)作旅行商問題（traveling salesman problem，TSP）進(jìn)行求解，即孔群被認(rèn)為是一系列點來處理，由于處理對象單一，其數(shù)學(xué)模型較為簡單。而平面加工輪廓路徑優(yōu)化可轉(zhuǎn)化為廣義旅行商問題（generalized traveling salesman problem，GTSP）求解。針對平面封閉式輪廓軌跡路徑優(yōu)化的研究，相關(guān)算法有最短近鄰算法[7-8]、結(jié)合局部搜索的蟻群算法[9]和遺傳算法[10]，但此類研究均沒有對非封閉及多類圖元混合軌跡圖形路徑優(yōu)化進(jìn)行說明。

根據(jù)數(shù)控加工行業(yè)的需求，本文提出基于改進(jìn)遺傳算法的多類圖元混合復(fù)雜軌跡加工路徑優(yōu)化策略。針對復(fù)雜路徑優(yōu)化問題，引入直線、圓弧、橢圓弧和B樣條等圖元數(shù)據(jù)對象，基于GTSP問題模型，應(yīng)用改進(jìn)的遺傳算法求解全局最短路徑，并對封閉式軌跡段和非封閉式軌跡段進(jìn)行起點計算與局部尋優(yōu)，以實現(xiàn)多類圖元混合軌跡加工路徑優(yōu)化。該方法不僅可顯著減少刀具空走路徑，提高加工效率，而且可方便擴(kuò)展圖元類型，適用于木工、型材、電子等多個行業(yè)。

1 加工路徑圖元數(shù)據(jù)讀取

為滿足CAM編程系統(tǒng)的兼容性與擴(kuò)展性，采用C++面向?qū)ο蟮乃枷?，并基于開源C++庫dxflib構(gòu)建DXF文件讀取類庫。其中，dxflib庫的可靠性高，可實現(xiàn)任何操作系統(tǒng)上的DXF文件的讀取，且不產(chǎn)生任何附加成本[11]。DXF文件具有嚴(yán)格規(guī)范的存儲格式，由標(biāo)題段、表段、塊段、實體段、對象區(qū)段和文件結(jié)束段6部分組成，其中加工圖形幾何信息均定義在實體段中，一個實體對應(yīng)一個圖元。DXF文件讀取流程如圖1所示。

圖1 加工路徑圖元數(shù)據(jù)讀取流程

2 問題描述與數(shù)學(xué)模型

在數(shù)控加工過程中，通常需要對多個軌跡圖形進(jìn)行一次加工完成，以縮短換刀次數(shù)和換刀時間，提高機(jī)床加工效率。但在多個軌跡圖形加工過程中，相鄰兩個加工圖元之間需要跳刀空走，并從加工圖形文件讀取的加工圖元排列無序，且加工軌跡圖形數(shù)量通常較龐大，若不進(jìn)行加工空程路徑優(yōu)化，將嚴(yán)重影響加工效率。

針對木工、型材、電子等行業(yè)數(shù)控雕刻、切割、鉆銑加工，其加工軌跡從曲線類型上一般包含點、直線段、圓弧、橢圓弧和B樣條等圖元。由于加工路徑由一系列軌跡圖形組成，路徑優(yōu)化即是對加工軌跡圖形進(jìn)行合理排序，使軌跡間跳刀距離總和最短。由于優(yōu)化過程中只需關(guān)注圖元間的距離，因此為簡化問題模型及便于遺傳算法編碼，本文提出將加工圖元重構(gòu)：1) 對于由點、圓、橢圓形成的單軌跡圖形，只考慮圖元的中心點；2) 對于由直線、圓弧、橢圓弧或B樣條形成的單圖元軌跡圖形，只考慮圖元的兩端點；3) 對于由多個圖元構(gòu)成的非封閉式軌跡圖形，將該多個圖元組成一個組合體，忽略圖形中間節(jié)點，取軌跡圖形兩端點；4) 對于由多個圖元構(gòu)成的封閉式軌跡圖形，取其中任意一點作為初始點。

多圖元混合加工路徑可看作不同類型軌跡段圖形（包括單個非封閉圖元、單個封閉圖元、多圖元非封閉式圖形和多圖元封閉式圖形）的集合。對于單個非封閉圖元或多圖元非封閉式圖形，兩端點均可作為加工軌跡段起始點；對于單個封閉圖元，軌跡段圖形上任一點可為加工起始點；對于多圖元封閉式圖形，任一節(jié)點都可以作為加工軌跡段的起始點。加工路徑的優(yōu)化即通過算法對所有加工軌跡段進(jìn)行排序及加工軌跡起點與方向選擇，使得按所排順序形成的加工回路最短。

因此，多圖元混合加工路徑優(yōu)化問題的數(shù)學(xué)模型為：給定個點集1,2,…,V,…,V，把V內(nèi)的點數(shù)記作n，則個點集的總點數(shù)=1+2+…+n+…+n(=1,2,…,)。從每個點集V中取1~2點（如對于非封閉軌跡段取兩端點，對于封閉軌跡段任取一點）構(gòu)成賦權(quán)圖G(=1,2,…,1,2,…,n)，需要找到一條可遍歷個點集的最短Hamilton回路L，則刀具的最短加工路徑應(yīng)滿足[10]

(1)

其中()、(L)分別表示路徑和L的長度。

由數(shù)學(xué)描述可見，多圖元混合加工路徑優(yōu)化問題是一個帶約束且節(jié)點可變的第二類GTSP問題。目前針對該類問題的研究相對較少，文獻(xiàn)[12]提出了基于最短路徑思想的重構(gòu)距離矩陣算法，將第二類GTSP轉(zhuǎn)化為第一類GTSP，再利用混合遺傳算法進(jìn)行求解，該算法復(fù)雜，實現(xiàn)過程較困難。本文針對加工路徑中不同軌跡類型進(jìn)行個性化編碼設(shè)計，直接將多圖元混合加工路徑優(yōu)化問題轉(zhuǎn)化為TSP問題求解，然后通過軌跡段（包括封閉式與非封閉式）起點計算和路徑自調(diào)整簡易算法對優(yōu)化后的軌跡段序列進(jìn)行后處理，從而獲得多圖元混合加工路徑最短空程距離。

3 多類圖元混合加工路徑優(yōu)化策略

遺傳算法是一種通過模擬自然界的進(jìn)化過程，搜索全局最優(yōu)解或近似最優(yōu)解的方法，具有良好的魯棒性、隱式并行性和全局搜尋能力，對于加工路徑的優(yōu)化具有良好效果，但也存在易于過早收斂和難以跳出局部最優(yōu)解的不足。文獻(xiàn)[13]與貪心算法結(jié)合，提高了搜索效率和結(jié)果，但增加了程序運行成本。為將多圖元混合加工路徑優(yōu)化復(fù)雜問題轉(zhuǎn)化為數(shù)學(xué)模型簡單的TSP問題，對不同軌跡段圖形進(jìn)行分類編碼設(shè)計，并采用線性定標(biāo)及自適應(yīng)遺傳算子等方式進(jìn)行初步路徑排序，最后通過加工路徑后處理算法求解最短加工路徑。

3.1 基于改進(jìn)遺傳算法的全局路徑優(yōu)化

3.1.1 染色體編碼

實數(shù)序列編碼相對于二進(jìn)制編碼、參數(shù)編碼等方式，具有良好的適用性和可操作性，可解決多圖元軌跡混合路徑編碼帶來的復(fù)雜問題，故本文采用實數(shù)序列編碼。由于多圖元混合加工路徑存在直線、圓弧、橢圓弧和B樣條單個圖元以及非封閉軌跡圖形，為適用TSP問題的遺傳算法求解，故根據(jù)加工軌跡段圖形類型進(jìn)行分類編碼，染色體編碼見表1，P表示第個編碼點對象。

表1 多類圖元混合軌跡圖形編碼表

3.1.2 初始化種群

當(dāng)染色體編碼完成后，需產(chǎn)生一個初始種群當(dāng)作遺傳進(jìn)化的初始解。對于加工路徑優(yōu)化問題，種群大小一般隨著軌跡段數(shù)目而改變，取值范圍50~200[8]。根據(jù)軌跡段數(shù)量自適應(yīng)調(diào)整種群大小的函式定義：

其中，表示種群數(shù)目；表示加工軌跡段數(shù)目；表示不同加工軌跡所對應(yīng)的取值。

如式(2)所示，種群個數(shù)在50~200之間隨加工軌跡段數(shù)目不同而自動變化。

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

適應(yīng)度函數(shù)是評判種群中個體優(yōu)劣程度的指標(biāo)，根據(jù)所求問題的目標(biāo)函數(shù)進(jìn)行評估。適應(yīng)度值大的個體被遺傳到下一代的概率較大，適應(yīng)度值小的個體被遺傳到下一代的概率較小。由于每段加工軌跡本身長度不變，其長度總和可視為常數(shù)C。為保持良好個體的競爭力并且抑制早熟情況的出現(xiàn)，針對適應(yīng)度函數(shù)引入線性定標(biāo)方式進(jìn)行調(diào)整，由此個體適應(yīng)度函數(shù)為

其中，和為適應(yīng)度調(diào)整系數(shù)。

3.1.4 選擇、交叉和變異

1) 交叉和變異概率的自適應(yīng)處理

通常遺傳算法中的交叉和變異概率均采用固定數(shù)值，無法反映種群的進(jìn)化過程。為進(jìn)一步避免出現(xiàn)早熟現(xiàn)象，防止算法在搜索空間中陷入局部最優(yōu)情況，對交叉和變異概率在平均適應(yīng)度值處進(jìn)行自適應(yīng)緩慢調(diào)整處理，提高適應(yīng)度接近平均適應(yīng)度個體的交叉和變異概率，保證當(dāng)代種群中優(yōu)良個體仍具一定的交叉和變異概率。為了能在算法演化后期盡可能地保留較優(yōu)個體，應(yīng)平滑最大適應(yīng)度值處的自適應(yīng)調(diào)整曲線，改進(jìn)后的交叉和變異概率自適應(yīng)處理函數(shù)為