飛機裝配機器人制孔路徑規(guī)劃與算法研究實現(xiàn)*

劉艷梅，呂 笛

（沈陽航空航天大學自動化學院，沈陽 110136）

0 引言

隨著工業(yè)4.0的到來，航空領(lǐng)域迎來了新的挑戰(zhàn)?，F(xiàn)代飛機日漸復雜，對其性能、安全性、經(jīng)濟性都提出了更高的要求。飛機制造商要在滿足高質(zhì)量的前提下，去考慮客戶的經(jīng)濟承擔能力，這就促使提高生產(chǎn)效率成為當下飛機制造的重要議題[1]。影響飛機服役時間長短主要是裝配連接的質(zhì)量[2]。根據(jù)資料統(tǒng)計，70%的飛機疲勞事故來自于結(jié)構(gòu)連接的部分，其中近3/4是由于連接孔的疲勞而斷裂，所以提高制孔的質(zhì)量與效率是飛機生產(chǎn)的關(guān)鍵[3]。國外自動制孔技術(shù)相對比較成熟，如美國的GEMCOR和英國的DELCAM等公司，擁有自主知識產(chǎn)權(quán)的飛機裝配自動鉆鉚系統(tǒng)[4]。目前國內(nèi)飛機制造領(lǐng)域，對于自動制孔技術(shù)的研究還處于發(fā)展階段，對于自動制孔的路徑規(guī)劃算法的研究國內(nèi)學者已取得諸多研究成果。

蟻群算法是解決路徑規(guī)劃問題的常用算法，是一種通過模仿自然界中的螞蟻產(chǎn)生的智能群算法，其最大特點是具有正反饋特性[5]。然而，傳統(tǒng)的蟻群算法仍然存在收斂時間長、容易產(chǎn)生陷入局部最優(yōu)解的現(xiàn)象[6]。為了解決上述缺陷，許多學者紛紛提出了改進傳統(tǒng)蟻群算法的思路。楊立瑋等[7]通過初始信息素階梯分配原則，解決了蟻群早期搜索的盲目性問題。按優(yōu)化目標重構(gòu)多因子信息素更新方式，并運用最大最小螞蟻系統(tǒng)和自適應(yīng)策略提高了全局搜索能力，規(guī)避了墜入局部最優(yōu)的局面；沈葭櫟等[8]開發(fā)了一種改進蟻群算法，依靠對信息素濃度進行動態(tài)分級設(shè)置，使信息素濃度在迭代過程中緩緩減少，成功地令算法收斂速度得到提升，當陷入局部最優(yōu)解的情況發(fā)生時，加入了懲罰系數(shù)的概念來調(diào)節(jié)目前最優(yōu)路徑中信息素的濃度，提高了算法的全局搜索能力，增強了算法隨機性；石立新等[9]本著保證路徑長度的原則，將轉(zhuǎn)向次數(shù)這一因素加入到啟發(fā)函數(shù)中，與此同時限制了信息素變化的范圍，增加了算法搜索空間的大小，使算法收斂到局部最優(yōu)解需要的時間變長。

蟻群算法在前期由于信息素不足，執(zhí)行周期比較長，免疫算法則正好相反，算法早期搜索速度快，但是當?shù)M行了一定次數(shù)之后由于缺少反饋，算法進化速度驟然下降[10]。針對上述問題，本文提出一種動態(tài)優(yōu)化信息素揮發(fā)因子，改善了傳統(tǒng)蟻群算法的盲目性，并在傳統(tǒng)蟻群算法的基礎(chǔ)上引入免疫算法，提出優(yōu)化免疫蟻群算法，以改善蟻群算法在初始搜索階段收斂所花費的時間過長、易于陷入局部最優(yōu)解等缺陷。此算法對提升飛機裝配機器人自動制孔效率具有重要意義。

1 基本原理

1.1 傳統(tǒng)蟻群算法

蟻群算法是根據(jù)生物界中的螞蟻創(chuàng)造出來的一種仿生啟發(fā)式算法，并帶有正反饋特性[11]。在現(xiàn)實生活中，螞蟻在移動時會同時釋放出一種生物信息素，這種信息素像水一樣，在自然狀態(tài)下會隨著時間的流逝而慢慢蒸發(fā)消失。因此，信息素含量在不同路徑上會有明顯的差別。螞蟻爬行的路徑長度越短，其所爬行的路徑上存在的信息素含量就越高，路徑長度越長，因為揮發(fā)現(xiàn)象的存在，其路徑上的信息素保留的就會越少，因此，信息素含量高的路徑被之后的螞蟻選擇的概率就相對大上許多，繼續(xù)釋放信息素加強了這條路徑上信息素的含量[12]。螞蟻們就是根據(jù)這樣正反饋的方式，總能尋找出一條最短的路徑。

當?shù)M行到第t次時，k螞蟻從孔位i點爬行到孔位j點的轉(zhuǎn)移概率為pkij，其表達式為：

式中：k為螞蟻的標號；下標前一位為當前位置，后一位為將要爬行到的位置，τij為t時刻孔i到孔j之間路徑上的信息素濃度；ηij(t)為由孔i爬到孔j的期望程度，是i到j(luò)路徑上的啟發(fā)函數(shù)，其值與時間無關(guān)，ηij=1/dij，dij為孔i和孔j之間的歐式距離；H為螞蟻可爬行的孔位信息的集合。

在迭代過程中，信息素更新規(guī)則如下：

其中信息素揮發(fā)系數(shù)為ρ（0≤ρ≤1），其功能是控制信息素的揮發(fā)程度的快慢。Δτkij(t)表示第k只螞蟻t時刻在孔i與孔j之間的路徑上殘留的信息素增量，它的大小與所選的蟻群算法的模型有關(guān)系，本文采用的是蟻周模型，故其公式為：

式中：Q為信息素強弱程度；Lk為螞蟻k所爬行的路徑的距離。

蟻群算法的具體步驟如下：

（1）設(shè)置初始參數(shù)及環(huán)境，包括確定參數(shù)值螞蟻循環(huán)次數(shù)N、螞蟻數(shù)量M、初始時刻的信息素常數(shù)τc、信息素揮發(fā)系數(shù)ρ、邊（i，j）的信息素軌跡強度τij的相對重要性α、螞蟻到達目標點所釋放的信息素總量Q、邊（i，j）能見度ηij的相對重要性β等有關(guān)參數(shù)；

（2）根據(jù)螞蟻的狀態(tài)轉(zhuǎn)移概率、環(huán)境模型及初始參數(shù)信息，完成從起始點到目標點的路徑搜索，比較并記錄M只螞蟻的最短路徑，以這條最短路徑完成一次信息素的全局更新；

（3）繼續(xù)步驟（2），直到達到螞蟻的最大循環(huán)次數(shù)N。輸出N次循環(huán)中的最短路徑及路徑長度，即為所求的從起始點到目標點的最短路徑，結(jié)束。

1.2 優(yōu)化蟻群算法

蟻群之間，螞蟻和環(huán)境之間的交流依靠信息素，所以蟻群算法的關(guān)鍵也在于信息素的更迭。在算法中，信息素揮發(fā)因子ρ直接影響著信息素揮發(fā)的速度，所以蟻群算法的收斂速度很大程度上是被信息素揮發(fā)因子所決定的。傳統(tǒng)的蟻算法在搜尋最優(yōu)路徑時需要依靠多只螞蟻進行多次迭代，在進行處理大規(guī)模數(shù)據(jù)的模型時，螞蟻在搜索路徑的時候信息素不斷揮發(fā)直至0，令某些路徑不再被搜索，導致少數(shù)路徑從沒被搜索或很少被搜索，嚴重影響著算法的搜索能力。傳統(tǒng)蟻群算法的信息素揮發(fā)因子ρ的初始取值范圍為0～1之間，初始ρ值不同最后得到的最優(yōu)路徑就會不一樣。所以本文應(yīng)用TSP常用的數(shù)據(jù)庫中的eil51，對ρ的初始值從0.1～0.9進行了試驗，得到的路徑結(jié)果如圖1所示。由圖和實際算法運行中發(fā)現(xiàn)，ρ大于0.6之后的路徑結(jié)果不是很理想，甚至有時會出現(xiàn)算法崩潰的現(xiàn)象，這是因為當ρ過大時蟻群算法會陷入局部最優(yōu)解，無法完成全局搜索，故無法得到路徑長度；在ρ取0.1～0.3之間時，得到的路徑長度也不是盡如人意；在ρ取0.3～0.6之間比較理想，尤其是0.4時為435.722 9。綜上所示，當ρ的初始值取0.4時可以使算法達到最優(yōu)效果，即全局搜索效果最好。因此，本文提出一種為應(yīng)對傳統(tǒng)蟻群算法全局搜索時間長，改進全局搜索能力低，搜索多次無法達到理想結(jié)果的情況，提出了一種對信息素揮發(fā)因子ρ隨時間而改變的方法，即對其限制在0.3～0.6之間。其表達式為：

圖1 信息素揮發(fā)因子ρ與路徑長度關(guān)系

式（4）中t≠0，因為已經(jīng)把初始（t=0）時ρ取值為0.4。這樣就可以避免因為ρ過大，路徑上留存的信息素揮發(fā)過于迅速，不同螞蟻之間的交流變少，算法的收斂時間過長，甚至存在算法陷入局部最優(yōu)的死循環(huán)中的風險；ρ過小，路徑上就會留存一些長時間滯留的信息素，有機會多次搜尋到已經(jīng)確定過的路徑，從而降低了算法的隨機性，使算法缺少多樣性，降低了全局搜索能力。

2 優(yōu)化免疫蟻群算法

2.1 傳統(tǒng)免疫算法

工免疫算法是生命科學與工程數(shù)學相互碰撞產(chǎn)生的一種優(yōu)秀的智能優(yōu)化算法[13]。人工免疫算法是將人類（高等脊椎動物）的生物免疫系統(tǒng)作為理論原型的[14]。因此，生物免疫系統(tǒng)是免疫算法的最直接的來源。免疫算法是根據(jù)免疫系統(tǒng)來設(shè)計的，例如抗原識別、免疫調(diào)節(jié)、克隆變異、免疫記憶等，免疫算法的概念與基礎(chǔ)理論被應(yīng)用到算法計算中[15]。

傳統(tǒng)人工免疫算法的一般流程如下。

（1）識別抗原：確定親和度評價函數(shù)和抗體濃度函數(shù)和目標函數(shù)。

（2）初始抗體產(chǎn)生：隨機產(chǎn)生一個初始抗體群（目標函數(shù)在約束條件下的任意一個可行解）。

（3）親和力計算：計算抗體群中每一個抗體的親和度值。

（4）產(chǎn)生記憶細胞：抗體根據(jù)親和程度從小到大進行分類，從抗體中分離出親和力最高的抗體形成新的抗體群，選取前5%的親和度較高的抗體形成記憶庫。

（5）對于抗體的促進和抑制：計算抗體的濃度。促進低濃度高親和力的抗體；抑制高濃度親和力低的抗體。

（6）群體更新：利用交叉、變異等操作對群體進行更新。

（7）條件判斷：判斷是否滿足終止要求，即達到規(guī)定迭代次數(shù)到達最大值或找到最優(yōu)質(zhì)的解，是則結(jié)束迭代，否則跳轉(zhuǎn)到第（3）步。

2.2 優(yōu)化免疫蟻群算法

人工免疫算法和蟻群算法都屬于智能集群算法。細胞之間、螞蟻之間都進行著相互交流，單獨的每個個體都和環(huán)境也都存在著交流影響，來更好地適應(yīng)環(huán)境的變化。兩種算法既有相似又有不同。人工免疫算法具有快速隨機搜索的特點，但在算法運行后期信息利用不足，存在大量的繁瑣的無效的迭代，算法效率不理想。蟻群算法具有并行搜索的特點，利用信息素的逐漸累積和迭代中不斷更新信息素使算法漸漸收斂于最優(yōu)路徑，但其初次的信息素分布是隨機產(chǎn)生的，易導致算法收斂速度慢。

本文將人工免疫算法和優(yōu)化蟻群算法相結(jié)合，提出一種優(yōu)化免疫蟻群算法，算法主要分成3個部分，第一步利用免疫算法初期快速隨機搜素的特點，首先對所求問題找一個較優(yōu)可行解。其次通過得到的較優(yōu)可行解對蟻群算法初始的（t=0）信息素分布進行生成。最后依靠優(yōu)化蟻群算法的具有正反饋的特點和并行性來增強算法求解效率，并在算法迭代時應(yīng)用上文提到的對信息素揮發(fā)因子的改進，得到最后所求的最優(yōu)解。優(yōu)化免疫蟻群算法的具體流程如圖2所示。

圖2 優(yōu)化免疫算法流程

具體步驟如下。

（1）確定抗原、抗體及初始參數(shù)和環(huán)境設(shè)置。

（2）生成初始種群。

（3）計算每個抗體的親和力。

（4）抗體的促進和抑制：計算抗體的濃度。促進高親和度低濃度的抗體；抑制低親和度高濃度的抗體。

（5）群體更新：利用交叉、變異等操作對群體進行更新。

（6）輸出可行解，若滿足條件，執(zhí)行步驟（7），若不滿足，回到步驟（2）。

（7）生成蟻群算法的初始信息素的分布。

（8）設(shè)定初始參數(shù)，并確定狀態(tài)轉(zhuǎn)移概率。

（9）更新信息素。

（10）若滿足條件，輸出最優(yōu)解，完成搜索。若不滿足條件，回到步驟（8）。

2.3 蟻群算法與優(yōu)化免疫蟻群算法仿真比較

為驗證本文的優(yōu)化免疫算法的合理性，選擇了國際上通用的測試庫eil51分別對兩種算法進行了仿真實驗。通過對圖3～4傳統(tǒng)蟻群算法和優(yōu)化免疫蟻群算法的收斂曲線仿真結(jié)果進行比較分析，優(yōu)化免疫蟻群算法在迭代50次左右就已經(jīng)收斂找到了最短路徑，而傳統(tǒng)的蟻群算法150～200次甚至更久才能找到該算法的最優(yōu)解。由圖5～6兩種算法的路徑圖可以發(fā)現(xiàn)優(yōu)化免疫算法的最短路徑遠遠好于傳統(tǒng)蟻群算法，為446.155 6，其圖像中的交叉線段明顯減少。由此可見，優(yōu)化免疫蟻群算法的收斂速度要好于傳統(tǒng)蟻群算法，找到的最優(yōu)路徑也比傳統(tǒng)蟻群算法要等優(yōu)秀。說明優(yōu)化免疫蟻群算法改善了全局搜索能力和收斂速度慢的問題。

圖3 優(yōu)化免疫算法收斂

圖4 蟻群算法收斂

圖5 優(yōu)化免疫算法路徑

圖6 蟻群算法路徑

3 機器人制孔路徑規(guī)劃仿真

為了驗證優(yōu)化免疫蟻群算法可以有效地應(yīng)用在飛機制孔路徑中，本文對飛機裝配機器人制孔路徑規(guī)劃設(shè)計并實現(xiàn)了仿真實驗。實驗中選取的參數(shù)為：免疫算法部分：群體規(guī)模n=100，克隆個數(shù)10，交叉概率Pc=0.95，迭代次數(shù)G=500，變異概率Pm=0.02。優(yōu)化蟻群算法部分：螞蟻群體的個數(shù)m=100，啟發(fā)式因子α=2，自啟發(fā)式因子β=3，初始信息素揮發(fā)常數(shù)ρ=0.4，常數(shù)Q=1，迭代次數(shù)NC=500。本文首先在CATIA軟件下建立某型號飛機的矩形翼模型，因本文提取的制孔點位信息在矩形翼的曲面上又對其孔位信息進行了提取，如圖7所示。應(yīng)用所提出的優(yōu)化免疫蟻群算法設(shè)計路徑規(guī)劃，并利用MATLAB進行仿真實現(xiàn)。試驗結(jié)果如圖8所示，為簡化仿真本文選取了一個長方體x=[0，500]，y=[0，100]，z=[-20，20]的空間為實驗區(qū)間。仿真結(jié)果表明優(yōu)化免疫蟻群算法可以應(yīng)用在飛機零部件制孔當中，找到的制孔路徑長度為1 350，是飛機裝配機器人制孔所能找到的最優(yōu)最短路徑。

圖7 矩形翼模型孔位信息提取

圖8 優(yōu)化蟻群算法路徑

4 結(jié)束語

本文應(yīng)用CATIA軟件對某型號飛機的矩形翼進行建模。針對飛機裝配機器人制孔路徑規(guī)劃問題，設(shè)計了優(yōu)化免疫蟻群算法，其核心是將免疫算法與蟻群算法相結(jié)合并適當?shù)貙λ阉鬟^程中信息素揮發(fā)因子ρ進行改變，對于傳統(tǒng)蟻群算法的收斂速度進行了提升，并對全局搜尋最優(yōu)值的能力進行了明顯的加強。從客觀上來看，減少了傳統(tǒng)蟻群算法的收斂時間，提升了全局搜尋的能力等特點，說明傳統(tǒng)蟻群算法的缺陷已經(jīng)被優(yōu)化蟻群算法所彌補，為飛機裝配機器人制孔路徑規(guī)劃提供了基礎(chǔ)理論與技術(shù)支持。利用仿真結(jié)果可以看出，設(shè)計的優(yōu)化免疫蟻群算法，根據(jù)某型號飛機的矩形翼的制孔得到了一條最優(yōu)路徑來實現(xiàn)，并得到了較為理想的結(jié)果。