基于無人機航路規劃問題的蟻群算法綜述

柳丹，郭忠，張樹麗

（煙臺大學機電汽車工程學院，山東 煙臺 264000）

引言

航路規劃是指在起始點與終點之間，為低空飛行器尋找出滿足某種性能指標和約束的路徑。在無人機飛行之前，首先要根據環境、自身約束條件來進行合理的航路規劃，在保證安全的情況下，以最短的路徑從起始點到達終點。本文首先介紹了基本蟻群算法，然后在基本蟻群算法的基礎上綜述了近幾年來改進的蟻群算法。

1 蟻群算法的概敘

1.1 蟻群算法的簡介

蟻群算法(ant colony algorithm, ACA)是由意大利學者M.Dorigo[1]等人于20世紀90年代初提出的一種新的模擬進化算法，其真實地模擬了自然界螞蟻群體的覓食行為。生物學家研究發現，自然界中的螞蟻覓食是一種群體性行為，并非單只螞蟻自行尋找食物源。螞蟻在尋找食物源時，會在其經過的路上釋放一種信息素，并能夠感知其他螞蟻釋放的信息素。信息素濃度的大小表征路徑的遠近，信息素濃度越高，表示對應的路徑距離越短。通常，螞蟻會以較大的概率優先選擇信息素濃度較高的路徑，并釋放一定量的信息素，以增強該路徑上的信息素濃度，路徑上的信息素濃度會隨著時間的推進而逐漸衰減，這樣形成一個正反饋。最終，螞蟻能夠找到一條從巢穴到食物源的最佳路徑，即最短距離。

1.2 基本蟻群算法求解航路規劃問題

每只螞蟻按照狀態轉移規則從起點選擇下一個航路點，直到到達終點，在基本蟻群算法中，在t時刻第k只螞蟻在路徑點i轉移到路徑點j的狀態轉移規則如式(1)所示。

式(1)中：τij(t) 表示螞蟻 k(k=1,2,…)從節點 i到節點 j的信息素值；ηij(t)為啟發函數，表示在t時刻螞蟻k從節點i到節點j的期望值，一般與兩點距離dij成反比，即：

當所有螞蟻完成一次航路點的選取后，各個航路點上的信息素根據公式（2）進行更新：

其中，ρ是信息素揮發系數，n是蟻群中螞蟻的數量，Q是一個常熟，Lk是螞蟻k走過航路點的總長度。

2 蟻群算法在無人機航路規劃的發展

2.1 信息素問題

2.1.1 信息素初值問題

信息素初值的定義直接影響后面的狀態轉移規則，因此，信息素初始值的定義非常重要。張慶捷、徐華等[2]對蟻群算法的初始信息素強度進行了改進，定義軌跡的初始強度與距離成反比，最終可以得到最優的初始航路。

2.1.2 信息素更新問題

當所有螞蟻完成一次航路點的選取后，各個航路點上的信息素將進行一次更新。焦振江、王正平等[3]提出了自適應信息素更新規則有效的提高了算法算收斂速度和解的性能；蔣定定、李萬泉等[4]改進信息素更新規則，對信息素的揮發因子做了調整，從而克服了基本蟻群算法的收斂速度慢、易于過早陷入局部最優的缺點；唐增明、蔣泰等[5]提出一種新的動態自適應調整信息素的策略，對最大—最小螞蟻系統的改進；邱小湖，邱永成等[6]前期采用了保留最優解和自適應航路點選擇策略對路徑進行優化，使之適應大規模問題求解;后期改進了基本蟻群算法中信息素、揮發因子的更新規則,通過改進使得每輪搜索后信息素的增量能更好地反映求解的質量，有效地避免陷入局部最優，加快了收斂，提高了搜索效率；房建卿、王和平等[7]提出的改進型蟻群算法，通過云模型來控制信息素強度 Q 和揮發系數 ρ 的大小，從而得到更好的收斂性與避免陷入局部最優解；尚夢雨等[8]采用信息素全局及局部信息素衰減法，改進了蟻群算法具有高效的迭代能力和快速的計算速度。

2.2 狀態轉移規則問題

航路點的選取即每只螞蟻按照狀態轉移規則從起點選擇下一個航路點，直到到達終點。最初的蟻群算法有收斂速度慢、計算時間長、易于陷入局部最優等缺。針對這些缺點，增強整體搜索能力，加快收斂速度，焦振江、王正平等[3]提出了保留最優解、自適應狀態轉換規則，有效的提高了算法算收斂速度和解的性能；陳謀、肖健等[9]將最短路徑的信息反饋到系統中作為搜索的指導信號,并改進了節點選擇方法,加快了搜索的效率，也容易找到最優解；李增、顧文燦等[10]提出了具有多種群的蟻群算法，并將導引因子引入到狀態轉移策略中，減少螞蟻局部搜索的盲目性，確保螞蟻最終完成航路搜索；蔣定定、李萬泉等[4]改進了螞蟻狀態轉移規則，從而克服了基本蟻群算法的收斂速度慢、易于過早陷入局部最優的缺點。

2.3 與其它算法結合問題

蟻群算法具有很強的魯棒性和較好的搜索能力，很容易與多種啟發式算法結合，以改善算法性能。李猛，王道波等[11]提出了結合蟻群算法與人工勢場的航跡規劃方法，該方法有效地提高了航跡規劃的收斂精度，同時具有良好的動態收斂過程和更短的規劃時間；王芳，李昆鵬等[12]提出一種勢場法優化的蟻群航路規劃算法，該方法改善蟻群初始路徑搜索過程中的盲目性，將人工勢場法的規劃結果作為先驗知識，對蟻群初始到達的柵格進行鄰域信息素的初始化，進而運用改進的蟻群算法完成航路搜索任務；姚永杰，席慶彪，劉慧霞等[13]提出了一種改進的遺傳蟻群算法，遺傳算法階段給出了一種小變異和引入新種群算子，維持了較優種群的多樣性，蟻群算法階段設計了一種基于航路代價的初始信息素獲取規則，保證蟻群具有較好的初始信息素分布，在求解時能夠避免陷入局部最優；田偉，張安等[14]基于兩種改進蟻群算法，分別將遺傳算法的交叉操作和 Dijkstra算法結合到蟻群系統的無人作戰飛機航路尋優過程中，使無人作戰飛機以最小的發現概率與可接受的航程到達目標點，并提高了無人作戰飛機的航路尋優能力。

3 結語

本文主要從解決航路規劃問題的角度出發，介紹了蟻群算法的近幾年的研究現狀，總結出蟻群算法發展的三個主要方向。蟻群算法具有收斂速度慢、易陷入局部最優等缺點，本文主要是根據蟻群算法的缺點在基本蟻群算法的基礎上加以改進。關于蟻群算法的理論研究及其應用的研究將會是一個長期的研究課題。

[1] Dorigo M. Optimization, learning and natural algorithms[J]. Ph. D.Thesis, Politecnico di Milano, Italy, 1992.

[2] 張慶捷,徐華,霍得森等.基于改進蟻群算法的偵察無人機航路規劃與實現[J]. 運籌與管理,2007.16(3): 97-102.

[3] 焦振江,王正平.基于改進蟻群算法的無人機航路規劃[J].航空計算技術, 2006, 36(4): 112-114.

[4] 蔣定定,李萬泉.基于改進蟻群算法的無人機偵察航路規劃研究[J].飛機設計, 2008. 28(2): 70-72.

[5] 唐增明,蔣泰.一種改進的動態自適應最大-最小蟻群算法[J].計算機與現代化, 2008.2008(3): 90-92.

[6] 邱小湖,邱永成.優化蟻群算法在無人機航路規劃中的應用[J].計算機仿真, 2010 (9): 102-105.

[7] 房建卿,王和平.云模型蟻群算法在無人機航跡規劃中的應用[J].科學技術與工程, 2012.20(18): 4455-4460.

[8] 尚夢雨.無人機實時蟻群算法路徑規劃[J].自動化應用, 2016 (12):61-63.

[9] 陳謀,肖健,姜長生.基于改進蟻群算法的無人機三維航路規劃[J].吉林大學學報 (工學版), 2008.38(4): 991-995.

[10] 李增,顧文燦,張宏亮,等.基于混合多種群自適應蟻群算法的無人機航路規劃[J].計算機測量與控制, 2015. 23(5): 1751-1753.

[11] 李猛,王道波,柏婷婷,等.基于蟻群優化算法和人工勢場的無人機航跡規劃[J].應用科學學報, 2012. 30(2): 215-220.

[12] 王芳,李昆鵬.基于人工勢場法優化的蟻群無人機航路規劃[J].西安航空學院學報, 2014. 32(5): 64-68.

[13] 姚永杰,席慶彪,劉慧霞.基于改進遺傳蟻群算法的無人機航路規劃[J].計算機仿真, 2011.28(6): 44-47.

[14] 田偉,張安.改進蟻群算法的無人機航路規劃[J].火力與指揮控制,2008. 33(11): 69-72.