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

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

?

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

3.1.1 染色體編碼

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

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

3.1.2 初始化種群

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

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

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

3.1.3 適應度函數(shù)

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

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

3.1.4 選擇、交叉和變異

1) 交叉和變異概率的自適應處理

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