肖軍民

（中山職業(yè)技術(shù)學(xué)院機(jī)電系，廣東中山 528404）

一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化*

肖軍民

（中山職業(yè)技術(shù)學(xué)院機(jī)電系，廣東中山 528404）

數(shù)控加工中心采用鉆削或鉸削方式加工孔群時，為了縮短加工中心刀具空走行程并提高孔群的加工效率，須對孔群加工路徑進(jìn)行優(yōu)化。數(shù)控加工中心孔群加工路徑優(yōu)化屬于NP完全問題，到目前為止還沒有一個非常有效的算法能求解出NP問題的最優(yōu)解。針對數(shù)控孔群加工路徑具體優(yōu)化問題，采用了一種整數(shù)染色體的遺傳算法，這種遺傳算法以孔號為染色體，采用“優(yōu)勝劣汰”的生物進(jìn)化方法尋找問題的最優(yōu)近似解。經(jīng)過實例證明該方法的求解精度高于粒子群和蟻群等其它智能優(yōu)化算法，因此改進(jìn)的整數(shù)染色體遺傳算法能較好地解決孔群加工路徑優(yōu)化問題。

遺傳算法；孔群加工；路徑優(yōu)化；數(shù)控加工；NP完全問題

0　引言

由于目前所有數(shù)控自動編程軟件都沒有孔群加工路徑優(yōu)化模塊，所以數(shù)控編程人員都是憑借自己的經(jīng)驗隨機(jī)地確定各個孔的加工順序。而在數(shù)控鉆削或鉸削加工中，孔群加工的比重大，由編程人員隨機(jī)確定孔群的加工路徑難以實現(xiàn)對路徑的優(yōu)化，在批量生產(chǎn)中這將極大影響生產(chǎn)效率。因此優(yōu)化孔群加工路徑，縮短加工中心刀具在XY平面的空行程距離，將有助于提高生產(chǎn)效率和節(jié)省能耗?？兹杭庸ぢ窂降膬?yōu)化是CAM中需要首先解決的問題，是目前的一個研究熱點［1］。孔群加工路徑優(yōu)化是典型旅行商問題（Travelling Salesman Problem，TSP），其解空間存在“組合爆炸”。該問題理論上可以獲得精確解，但對于大規(guī)模節(jié)點，這種精確解法將耗時巨大，難以滿足工程中實際的應(yīng)用［2］。TSP問題都屬于組合數(shù)學(xué)中的NP完全問題，屬于世界性的難題。該問題隨著節(jié)點數(shù)的增加，其求得理論最優(yōu)值所需的計算量便呈幾何級數(shù)增長，如當(dāng)節(jié)點數(shù)為200時，每秒計算數(shù)億次的大型計算機(jī)仍需要10358年才可能求得最優(yōu)解［3］。因此對于TSP問題人們已提出了許多常見的近似解法，如最鄰計算法、最小樹加權(quán)近似法、插入法和多邊交換調(diào)整算法等，這些傳統(tǒng)的最優(yōu)近似解法雖然可以獲取相關(guān)問題的近似解，但是由于它們方法本身的缺陷有可能導(dǎo)致近似解與理論最優(yōu)解偏差較大，甚至遠(yuǎn)離最優(yōu)解。近年來，一些智能優(yōu)化方法被用于TSP問題求解，如蟻群算法［4］、粒子群算法［5-6］、遺傳算法［7］和模擬退火算法等［8］。作為一種隨機(jī)搜索算法，遺傳算法借鑒了生物進(jìn)化的遺傳機(jī)制，通過“優(yōu)勝劣汰”的選擇、交叉和變異等基本操作搜索問題的最優(yōu)解。遺傳優(yōu)化算法實現(xiàn)比較簡單，求解過程中不需要導(dǎo)數(shù)信息，魯棒性強(qiáng)，且具有并行計算的能力，空間搜索能力強(qiáng)［9］。因此運(yùn)用遺傳算法求解孔群加工路徑優(yōu)化問題，可有效處理CAD中的數(shù)據(jù)，并能使得孔群加工的效率有較大幅度的提高。本文提出的基于整數(shù)染色體遺傳算法能較好地處理孔群編碼問題，并通過改進(jìn)算法能避免遺傳算法早熟收斂等缺點，通過具體的實例求解，可以證明本文提出的遺傳算法求解精度高于粒子群和蟻群等其它智能優(yōu)化算法。

1　問題模型描述

型進(jìn)行表示，具體如下：G=（V，E）是一個帶正權(quán)的完全圖，V是完全圖的頂點集合，V=｛V1，V2，…，Vn｝，n為孔群內(nèi)孔的數(shù)量，Vi為頂點集合中第i個位置孔的編號，E表示邊的集合，邊（i，j）的權(quán)值記為dij，dij為加工路徑中相鄰兩點的直線距離。i，j為路徑中相鄰兩孔的孔號，i，j=1，2，…，n，且i≠j。G的一條巡回路線是經(jīng)過圖V中每個頂點恰好一次的單向路徑，當(dāng)遍歷到最后一個點時數(shù)控刀具不需要返回到起點處，該條巡回路線不封閉，它不是一個回路。因此路徑優(yōu)化問題就在集合V中，采用遺傳算法找到一個不重復(fù)的全排列V=｛V1，V2，…，Vn｝，使得整個路徑的距離L最小，其目標(biāo)函

采用數(shù)控鉆削或鉸削方式加工孔時，孔群中不同類型的孔需要通過切換不同加工刀具來完成。對于數(shù)控加工中心而言，所有刀具的更換都需要刀具重新回到機(jī)床參考點位置進(jìn)行，因此要提高數(shù)控加工中心孔群的加工效率，只需考慮一種刀具情況下最短路徑的優(yōu)化。在上述前提下，數(shù)控孔群加工的過程可以描述如下：對某一類大小的孔，換上對應(yīng)刀具后，刀具從機(jī)床參考點移動到孔群的某一個孔，沿著最短路徑，從一個孔移動到下一個孔，直到該類孔都被加工完，刀具再返回到機(jī)床參考點處進(jìn)行換刀。上述問題可以用如下數(shù)學(xué)優(yōu)化模數(shù)優(yōu)化數(shù)學(xué)模型可表述如式（1）：

2　改進(jìn)遺傳算法

遺傳算法需要通過編碼和各種遺傳算子的作用來產(chǎn)生新的后代，在后代中以高概率地方式選擇優(yōu)良的種群作為遺傳的種子，用以下一代的遺傳操作。如果父代個體的競爭力高于子代個體，則父代作為良種繼續(xù)遺傳操作，而競爭力較弱的父代個體將被子代替代。如此反復(fù)進(jìn)行，留下的優(yōu)良子代即可作為問題的最優(yōu)近似解。遺傳算法在求解TSP問題中，編碼、交叉和變異等方案非常關(guān)鍵，不同的編碼、交叉和變異方案將有可能導(dǎo)致不同精度的解，有些不妥的方案甚至導(dǎo)致迭代過程中無法收斂，因此需要對上述方案進(jìn)行特別處理。

2.1編碼和交叉方案

以孔號作為染色體，采用自然數(shù)編碼，這種編碼意義明確，操作直接，但是隨機(jī)產(chǎn)生后代和交叉后代過程中會遇到一定的問題，即求出的個體并非都是有效個體。為了避免出現(xiàn)錯誤的后代，需要對個體內(nèi)染色體做一定的檢驗和處理，經(jīng)檢驗和處理后的下一代個體必須滿足如下三點：①隨機(jī)產(chǎn)生的染色體首先必須是自然數(shù)；②各個染色體對應(yīng)的自然數(shù)要屬于頂點集合V=｛11，2，…，n ｝，其中n為孔的數(shù)量；③個體內(nèi)的染色體互不相等。這種直接采用孔號為染色體的編碼方案不僅簡單而且不需要文獻(xiàn)［1］中繁雜的編碼和解碼步驟，這將問題的求解變得更簡單和更容易理解。

交叉算子是兩個父代共同產(chǎn)生后代的一種方式，是優(yōu)良父代把優(yōu)良的基因遺傳到子代中的一種方式。遺傳算法中發(fā)展出了很多交叉算子，其中有部分映射交叉算子、循環(huán)交叉算子、基于序的交叉算子、序交叉算子和子巡回交換交叉算子等［10］。上述交叉算子對于一般優(yōu)化問題的求解都有著很好的優(yōu)點，能夠?qū)崿F(xiàn)優(yōu)良基因的遺傳，但是對于采用孔號為染色體的編碼方案這些交叉算子將有一定的缺陷。不論按照上述哪種交叉算子，交叉算法都是在兩個父代之間進(jìn)行，這樣就不可避免地會產(chǎn)生錯誤的遺傳，從而導(dǎo)致遺傳算法無法正常進(jìn)行。因為以孔號為染色體的編碼方案是不允許在同一個體內(nèi)有相同的染色體，而按照上述的交叉算子都是不可避免地發(fā)生，因此需要對交叉算子做特別處理。具體的處理方法如下：①可先選定兩個位置交叉，然后分別進(jìn)行個體最優(yōu)之間的交叉，產(chǎn)生的新個體如果存在染色體相同的情況則進(jìn)行調(diào)整，采用的調(diào)整方法為用個體中未包括的染色體替代重復(fù)的染色體，具體實現(xiàn)方式如下：假設(shè)優(yōu)良個體［1 5 4 7 3 2 6 8 10 9］與另一優(yōu)良個體［3 5 6 1 3 2 8 6 10 9］在位置3和6的交叉，產(chǎn)生新一代的個體為［1 5 4 1 3 2 6 8 10 9］，顯然新個體有重復(fù)的染色體，所以按照調(diào)整原則將相同染色體“1”其中的一個用未出現(xiàn)的染色體“4”來替代，則可以獲得滿足要求的新個體［7 5 4 1 3 2 6 8 10 9］。

2.2選擇和變異方案

選擇算子是解決父代中如何選擇兩個個體進(jìn)行遺傳操作的問題，也是如何為下一代挑選雙親的問題。由于父代個體的優(yōu)良程度是不同的，按照生物進(jìn)化論其基因在子代中的生存能力也是不同的，因此需要進(jìn)行一定的選擇操作使優(yōu)良的基因能獲得更大的機(jī)會遺傳到下一代中去。遺傳算法中有很多選擇算子，比如隨機(jī)均勻分布法、剩余法、均勻法、輪盤賭法和錦標(biāo)賽法等［11］。遺傳算法中判斷個體優(yōu)良與否的準(zhǔn)則就是各自的適應(yīng)度，這一操作是借用進(jìn)化原則，即個體適應(yīng)度越高，其被選擇的機(jī)會就越多［12］。為此，采用與適應(yīng)度值成正比的概率來進(jìn)行選擇，其具體操作是：首先，計算群體中所有個體適應(yīng)度的總和∑fi；其次，計算每個個體的適應(yīng)度所占的比例，第i個體所占比例為fi/∑fi，并以此作為每個個體遺傳到下一代群體中的概率值。每個概率值為一個區(qū)域，全部概率之和為1；最后再產(chǎn)生一個0到1之間的隨機(jī)數(shù)，由隨機(jī)數(shù)出現(xiàn)在哪一個概率區(qū)來確定各個體被選中的次數(shù)。

變異是產(chǎn)生子代新個體的一種不可缺少的方式，變異的目的是為了防止丟失一些有用的遺傳基因，尤其是當(dāng)群體中的個體經(jīng)遺傳運(yùn)算可能使某些串位失去多樣性，從而可能失去有用的遺傳基因，同時也可以克服局部最優(yōu)解的弊端，變異運(yùn)算是挖掘群體中個體的多樣性。變異操作是按位進(jìn)行的，以很小的概率隨機(jī)地改變某一位或兩位的值。雖然遺傳算法有很多變異算子，但由于采用了孔號為染色體的遺傳方案，因此變異不能采用通常的隨機(jī)概率去改變個體的染色體，否則在個體內(nèi)又會產(chǎn)生相同染色體的錯誤情形。為了解決上述可能發(fā)生的情況，須在遺傳算法的程序內(nèi)編寫“不產(chǎn)生相同染色體”的約束條件，然后再采用“依賴約束條件”的變異算子進(jìn)行計算。變異的具體實現(xiàn)方式如下：假設(shè)某一新代的個體［1 5 4 1 3 2 6 8 10 9］被選中要變異，則按照約束條件隨機(jī)地選擇兩個染色體進(jìn)行位置對調(diào)，比如第2和第6的位置實現(xiàn)對調(diào)變異，則可產(chǎn)生變異的新個體［1 2 4 1 3 5 6 8 10 9］。

3　計算實例與討論

本文以文獻(xiàn)［6］提供的孔群為研究對象，以表1的相關(guān)數(shù)據(jù)為計算依據(jù)，按照本文提出的改進(jìn)遺傳算法對表1中孔的編號和坐標(biāo)點數(shù)據(jù)進(jìn)行處理和計算。對孔群加工路徑進(jìn)行優(yōu)化得到的目標(biāo)就是使加工刀具在該零件上所有孔間的空行程移動路徑最短。本文改進(jìn)遺傳算法的流程圖如圖1所示。改進(jìn)遺傳算法求解的最優(yōu)加工路徑是：17—20—18—22—14—5—7—2—4—9—3—6—16—21—23—15—13—12—8—11—1—19—10，按照這條優(yōu)化加工路徑數(shù)控刀具在加工中心上的最短空行程距離為291.968cm。文獻(xiàn)［6］采用了粒子群算法和蟻群算法對表1中的孔群也進(jìn)行了路徑優(yōu)化，表2是改進(jìn)遺傳算法、粒子群算法和蟻群算法三種智能算法的結(jié)果比較，從表2的比較結(jié)果可知，本文的最優(yōu)數(shù)控加工路徑是最短的，它更接近最優(yōu)解。

表1　孔的坐標(biāo)數(shù)據(jù)

表2　不同算法優(yōu)化結(jié)果比較

圖1　改進(jìn)遺傳算法流程圖

4　結(jié)束語

（1）針對孔群加工路徑優(yōu)化問題，提出了一種整數(shù)染色體的遺傳算法。這種遺傳算法以孔號為染色體，采用“優(yōu)勝劣汰”的生物進(jìn)化方法尋找問題最優(yōu)近似解。這種采用孔號為染色體的編碼方案不僅簡單而且不需要繁雜的編碼和解碼步驟，簡化了遺傳算法的編程。

（2）遺傳算法中的“交叉”和“變異”是產(chǎn)生新種群必要的步驟，為了避免在這些過程中產(chǎn)生不合格的個體，編制遺傳算法程序時需要給定約束條件：產(chǎn)生的新個體不能包括重復(fù)的染色體，如果有重復(fù)的染色體則需要用未包括的染色體將其中一個替代。

（3）應(yīng)用本文提出的改進(jìn)遺傳優(yōu)化算法所獲得的加工路徑與參考文獻(xiàn)［6］計算的結(jié)果進(jìn)行對比檢驗，本文的計算結(jié)果具有更優(yōu)的目標(biāo)函數(shù)值，表明本文提出的改進(jìn)遺傳算法在處理孔群加工路徑優(yōu)化問題是有效的。

［1］許兆美，金衛(wèi)鳳，李健.基于遺傳算法的孔群加工路徑優(yōu)化［J］.機(jī)械設(shè)計與制造，2011（2）：31-33.

［2］陳琳，劉曉琳，潘海鴻，等.孔群分類加工路徑的優(yōu)化算法［J］.制造業(yè)自動化，2013，35（17）：46-49.

［3］丁靜，尚欣，周文玉.鈑金件沖孔路徑優(yōu)化研究［J］.機(jī)床與液壓，2006（3）：112-114

［4］曹宗華，吳斌，黃玉清，等.基于改進(jìn)蟻群算法的多機(jī)器人任務(wù)分配［J］.組合機(jī)床與自動化加工技術(shù)，2013（2）：34-37.

［5］朱興濤，張則強(qiáng)，胡俊逸.基于粒子群算法的U型裝配線平衡問題研究［J］.組合機(jī)床與自動化加工技術(shù)，2012（4）：5-8.

［6］陳震，彭先濤.改進(jìn)粒子群算法在緊固螺母路徑中的優(yōu)化［J］.制造業(yè)自動化，2013，35（17）：86-89.

［7］吳忻生，吳超成，劉海明.基于改進(jìn)遺傳算法的矩形件排樣優(yōu)化算法［J］.制造業(yè)自動化，2013，35（19）：55-58.

［8］馮劍，岳琪.模擬退火算法求解TSP問題［J］.森林工程，2008，24（1）：94-96.

［9］趙靜，路銀川，孔金生.基于量子遺傳算法的多峰函數(shù)優(yōu)化研究［J］.制造業(yè)自動化，2013，35（5）：94-96.

［10］張德豐.MATLAB實用數(shù)值分析［M］.北京：清華大學(xué)出版社，2012.

［11］馬莉.MATLAB數(shù)學(xué)實驗與建模［M］.北京：清華大學(xué)出版社，2010.

［12］趙俊書.優(yōu)化技術(shù)與MATLAB優(yōu)化工具箱［M］.北京：機(jī)械工業(yè)出版社，2011.

（編輯 趙蓉）

Optimization of NC Machining Path for Holes Based on Improved Genetic Algorithm

XIAO Jun-min
（Department of Mechanical and Electrical Engineering，Zhongshan Polytechnic，Zhongshan Guangdong 528404，China）

In order to shorten the vacant path of machining center tool and improve machining efficiency holes machining path needs to be optimized in the process of drilling and reaming.Holes machining path optimization of CNC machining center is a NP complete problem，so far there is not a very efficient algorithm to solve the optimal solution of NP problem.In order to solve the path optimization problem of holes machining a genetic algorithm of integer chromosome is proposed in the paper，and holes number is set as chromosome in the improved genetic algorithm.The genetic algorithm of integer chromosome can solve the approximate optimal solution based on the method of biological evolution.The solution example can show that the solution accuracy of improved genetic algorithm in the paper is higher than the solution accuracy of particle swarm algorithm and ant colony algorithm，so the improved genetic algorithm proposed in the paper can solve the path optimization problem of holes machining better.

genetic algorithm；holes machining；path optimization；CNC machining；NP problem

TH166；TG506

A

1001-2265（2015）02-0151-03 DOI：10.13462/j.cnki.mmtamt.2015.02.043

2014-06-04

廣東省高等學(xué)校優(yōu)秀青年教師培養(yǎng)計劃資助項目（Yq2013195）

肖軍民（1978—），男，江西峽江人，中山職業(yè)技術(shù)學(xué)院副教授，碩士，研究方向為先進(jìn)制造技術(shù)，（E-mail）xiaojunmin517@163.com。