吳萬榮， 殷建坤

（中南大學(xué) 機電工程學(xué)院，湖南 長沙 410083）

三臂鑿巖臺車適用于隧道及地下大斷面工程采用鉆爆破的鉆孔施工作業(yè)，臺車鉆孔孔位根據(jù)爆破需要按一定規(guī)律隨機離散分布在隧道斷面上。鉆臂之間運動和控制相互獨立，每一個鉆臂可獨立完成鑿巖鉆孔任務(wù)，工作斷面上所有鉆孔任務(wù)是由3個鉆臂共同協(xié)作完成［1］，鉆孔順序是隨機的。對于多臂鑿巖臺車解決孔序規(guī)劃時，一般將單個鉆臂的作業(yè)孔序規(guī)劃看成獨立的TSP問題，多臂鑿巖臺車孔序規(guī)劃即為N－TSP問題［2］。三臂鑿巖臺車工作覆蓋面積由2部分組成，即單臂覆蓋區(qū)域及兩臂甚至三臂覆蓋區(qū)域。根據(jù)三臂鑿巖臺車作業(yè)覆蓋面積和鉆臂運動特點，考慮到鉆臂之間的干涉，將作業(yè)區(qū)域合理劃分，每個區(qū)域作業(yè)孔位基本相同，運用自適應(yīng)遺傳算法對3塊作業(yè)區(qū)域分別進行孔序計算［3］。

1 三臂鑿巖臺車孔序規(guī)劃的模型建立

三臂鑿巖臺車每個鉆臂有6個轉(zhuǎn)動自由度和3個移動自由度，左右鉆臂底座還各有2個移動自由度，在每個作業(yè)斷面上每個鉆臂要完成幾十甚至上百個鉆孔任務(wù)，進行鉆孔作業(yè)時，三臂必須協(xié)調(diào)時間關(guān)系和空間關(guān)系，保證鉆臂之間不發(fā)生干涉，能夠最大限度地提高鉆孔工作效率［4］。

三臂鑿巖臺車工作區(qū)域示意，如圖1所示。

由圖1可以看出，鑿巖臺車工作區(qū)域由6部分組成，第1部分只有左邊鉆臂可以覆蓋，第2部分由左邊鉆臂和中間鉆臂共同覆蓋，第3部分由3個鉆臂共同覆蓋，第4部分由左邊鉆臂和右邊鉆臂共同覆蓋，第5部分由中間鉆臂和右邊鉆臂共同覆蓋，第6部分只有右邊鉆臂可以覆蓋。

圖1 三鉆臂工作區(qū)域

鑿巖臺車工作區(qū)域是個軸對稱區(qū)域，而且左、右各有一部分區(qū)域只有1個鉆臂可以工作，考慮到鉆臂之間任務(wù)的均衡和工作時可能發(fā)生干涉，將鉆孔區(qū)域分成A、B、C、D、E區(qū)，如圖2所示。

圖2 協(xié)作工作空間

A、B、C區(qū)分別由左臂、中臂和右臂獨立完成鉆孔任務(wù)，而D和E區(qū)是協(xié)作區(qū)域，根據(jù)每個鉆臂任務(wù)進展，合理地分配D、E區(qū)域的鉆孔任務(wù)。在單臂的孔序計算中，協(xié)作區(qū)域內(nèi)的所有孔都計算在內(nèi)，根據(jù)實際工作情況選擇跳過或鉆孔，這樣既可以避免鉆臂間的干涉，也可以均衡鉆臂任務(wù)，使每個鉆臂鉆孔數(shù)量盡量相等，臺車工作效率達到最大化。在3個鉆臂都能正常工作的條件下，為保證鉆臂之間不發(fā)生干涉，規(guī)定同時間只有1個鉆臂在協(xié)作區(qū)域內(nèi)工作，獨立的工作區(qū)域內(nèi)其他鉆臂不參與鉆孔。

2 TSP問題數(shù)學(xué)模型建立

假設(shè)G＝（V，E）為賦權(quán)圖，V＝｛1，2，…，n｝為頂點集，E為邊集，各頂點間的距離為cij，已知cij＞0，i，j∈V。TSP問題就是求出通過所有頂點，且每個頂點只通過1次的最短距離，在本實例中就是尋找一條最短的遍歷n個工作孔位的路徑。以鉆架末端移動距離為優(yōu)化函數(shù)建立數(shù)學(xué)模型，即

則TSP問題可建立如下線性規(guī)劃：

其中，K是V的所有非空子集；｜K｜是集合K中所有包含圖G的頂點個數(shù)。

第1個和第2個約束條件旨在限制每個頂點只有1條邊進1條邊出，第3個約束條件限制了子回路的產(chǎn)生［5－6］。

3 TSP問題的遺傳算法求解與實例應(yīng)用

對于n個工位的鉆孔孔序可能的路徑就有（n－1）！個。當(dāng)n比較小時，可以得到最短的路徑，當(dāng)n逐漸增大，組合路徑數(shù)目成指數(shù)級規(guī)律急劇增長，以致無法計算求得精確解。目前針對目標(biāo)TSP問題多采用近似解法，常用的方法有神經(jīng)網(wǎng)絡(luò)法、模擬退火法、最小生成樹法和遺傳算法等。遺傳算法是近些年發(fā)展起來的一種可全局優(yōu)化的算法，通過選擇、遺傳和變異等作用機理，不斷地提高個體適應(yīng)度，最終得到一個滿意的個體，即TSP問題的近似最優(yōu)解［7］。

3.1 算法設(shè)計

標(biāo)準(zhǔn)的遺傳算法包括初始種群的產(chǎn)生、選擇、交叉和變異。算法流程如圖3所示。

圖3 算法流程

本例中采用自適應(yīng)遺傳算法，適應(yīng)值高的選擇小的交叉和變異概率，適應(yīng)值低的選擇大的交叉和變異概率。這樣既可以保護優(yōu)良個體，又可以迅速淘汰差的個體。

應(yīng)用遺傳算法求解問題，遺傳基因的編碼是十分重要的一個環(huán)節(jié)，編碼遺傳基因應(yīng)考慮到是否有利于交叉和變異操作。

在本例求解孔序的TSP問題中，用最簡單、自然的孔序表示編碼方式。

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

在遺傳算法中產(chǎn)生的每一個種群個體，任一個體的孔序序列s＝（v1，v2，…，vn），這個序列相鄰孔位之間距離之和的倒數(shù)為適應(yīng)度函數(shù)，即

個體的適應(yīng)度函數(shù)值越大，其存活下來的幾率越大。

3.3 選擇、交叉及變異操作

根據(jù)個體適應(yīng)值的大小選擇操作，即從起點到終點的總路徑長度越短，被選中的概率越大。被選中的就有機會產(chǎn)生子代個體。為了保證每一代個體中最優(yōu)的個體不被破壞，采用精英選擇策略，使最優(yōu)個體直接復(fù)制到下一代。

交叉操作直接關(guān)系到種群的收斂速度和最優(yōu)解的得到。在自適應(yīng)遺傳算法中，交叉概率pc與種群個體適應(yīng)度函數(shù)值有關(guān)。

其中，fmax是種群中最大個體的適應(yīng)度值；f′是要交叉的2個個體中較大的適應(yīng)值；favg是種群個體的平均適應(yīng)值；f是要交叉或變異個體的適應(yīng)值；pc1、pc2為常數(shù)，一般取值pc1＝0.9，pc2＝0.6。

變異操作有交換變異、插入變異和倒位變異，3種變異方法中只有倒位變異考慮到了邊的銜接關(guān)系，TSP算法編程采用倒位變異，這樣有利于較好的優(yōu)良性能遺傳到下一代，且可以提高尋優(yōu)速度［7－11］。變異概率與種群個體適應(yīng)值有關(guān)，根據(jù)種群個體適應(yīng)值大小選擇合理的變異概率，即

3.4 實例應(yīng)用

本例中在鉆機工作區(qū)域內(nèi)隨機產(chǎn)生90個工位，利用Matlab進行自適應(yīng)遺傳算法編程，分別對左邊鉆臂、中間鉆臂和右邊鉆臂進行孔序優(yōu)化，結(jié)果如圖4、圖5所示。

圖4 尋優(yōu)最優(yōu)路徑

圖5 尋優(yōu)過程

4 結(jié)束語

本文提出了一種三臂鑿巖臺車的孔序規(guī)劃算法，結(jié)合三臂鑿巖臺車本身的工作特點，合理地劃分臺車工作區(qū)域，然后將每塊工作工位利用改進遺傳算法，求解出一個比較理想的鉆孔孔序，而且該算法有很大靈活性，可根據(jù)不同工況不同工位，迅速有效地規(guī)劃鉆孔工位。

［1］周友行.基于個體的雙機械手離散隨機合作任務(wù)規(guī)劃算法研究［J］.湘潭大學(xué)學(xué)報：自然科學(xué)版2006，28（1）：84－88.

［2］周友行，何清華.雙臂鑿巖機器人離散任務(wù)規(guī)劃［J］.中國機械工程，2006，17（13）：1334－1337.

［3］張 穎，吳成東，原寶龍.機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望［J］.控制工程，2003，10（5）：152－155.

［4］周友行.鑿巖機器人孔序規(guī)劃的研究與實現(xiàn)［D］.長沙：中南大學(xué)，2003.

［5］Dubowsky S，Blubaugh T D.Planning time－optimal robotic manipulator motions and work places for point－to－point tasks［J］.IEEE Transaction on Robotics and Automation，1998，5（3）：377－381.

［6］Laporte G.The TSP：an overview of exact and approximate algorithm ［J］.European Journal of Operation Research，1992，59（1）：231－247.

［7］李 春，葛茂根，張銘鑫，等.遺傳粒子群算法的動態(tài)計劃與排程問題研究［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（1）：5－9.

［8］李敏強.遺傳算法的基本理論與應(yīng)用［M］.北京：科學(xué)出版社，2000：42－54.

［9］玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學(xué)出版社，2004：2－30.

［10］Reinelt G.The traveling salesman：computational solutions for TSP applications［M］／／Lecture Notes in Computer Science.Berlin：Springer－Verlag，1994：23－31.

［11］高經(jīng)緯，張 煦，李 峰，等.求解TSP問題的遺傳算法實現(xiàn)［J］.計算機時代，2004（2）：19－21.