飛機裝配機器人制孔路徑規劃與算法研究實現*

劉艷梅，呂 笛

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

0 引言

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

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

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

1 基本原理

1.1 傳統蟻群算法

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

當迭代進行到第t次時，k螞蟻從孔位i點爬行到孔位j點的轉移概率為pkij，其表達式為：

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

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

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

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

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

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

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

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

1.2 優化蟻群算法

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

圖1 信息素揮發因子ρ與路徑長度關系

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

2 優化免疫蟻群算法

2.1 傳統免疫算法

工免疫算法是生命科學與工程數學相互碰撞產生的一種優秀的智能優化算法[13]。人工免疫算法是將人類（高等脊椎動物）的生物免疫系統作為理論原型的[14]。因此，生物免疫系統是免疫算法的最直接的來源。免疫算法是根據免疫系統來設計的，例如抗原識別、免疫調節、克隆變異、免疫記憶等，免疫算法的概念與基礎理論被應用到算法計算中[15]。

傳統人工免疫算法的一般流程如下。

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

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

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

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

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

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

（7）條件判斷：判斷是否滿足終止要求，即達到規定迭代次數到達最大值或找到最優質的解，是則結束迭代，否則跳轉到第（3）步。

2.2 優化免疫蟻群算法

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

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

圖2 優化免疫算法流程

具體步驟如下。

（1）確定抗原、抗體及初始參數和環境設置。

（2）生成初始種群。

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

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

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

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

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

（8）設定初始參數，并確定狀態轉移概率。

（9）更新信息素。

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

2.3 蟻群算法與優化免疫蟻群算法仿真比較

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

圖3 優化免疫算法收斂

圖4 蟻群算法收斂

圖5 優化免疫算法路徑

圖6 蟻群算法路徑

3 機器人制孔路徑規劃仿真

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

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

圖8 優化蟻群算法路徑

4 結束語

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