基于無人機(jī)航路規(guī)劃問題的蟻群算法綜述

柳丹，郭忠，張樹麗

（煙臺(tái)大學(xué)機(jī)電汽車工程學(xué)院，山東 煙臺(tái) 264000）

引言

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

1 蟻群算法的概敘

1.1 蟻群算法的簡(jiǎn)介

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

1.2 基本蟻群算法求解航路規(guī)劃問題

每只螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則從起點(diǎn)選擇下一個(gè)航路點(diǎn)，直到到達(dá)終點(diǎn)，在基本蟻群算法中，在t時(shí)刻第k只螞蟻在路徑點(diǎn)i轉(zhuǎn)移到路徑點(diǎn)j的狀態(tài)轉(zhuǎn)移規(guī)則如式(1)所示。

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

當(dāng)所有螞蟻完成一次航路點(diǎn)的選取后，各個(gè)航路點(diǎn)上的信息素根據(jù)公式（2）進(jìn)行更新：

其中，ρ是信息素?fù)]發(fā)系數(shù)，n是蟻群中螞蟻的數(shù)量，Q是一個(gè)常熟，Lk是螞蟻k走過航路點(diǎn)的總長(zhǎng)度。

2 蟻群算法在無人機(jī)航路規(guī)劃的發(fā)展

2.1 信息素問題

2.1.1 信息素初值問題

信息素初值的定義直接影響后面的狀態(tài)轉(zhuǎn)移規(guī)則，因此，信息素初始值的定義非常重要。張慶捷、徐華等[2]對(duì)蟻群算法的初始信息素強(qiáng)度進(jìn)行了改進(jìn)，定義軌跡的初始強(qiáng)度與距離成反比，最終可以得到最優(yōu)的初始航路。

2.1.2 信息素更新問題

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

2.2 狀態(tài)轉(zhuǎn)移規(guī)則問題

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

2.3 與其它算法結(jié)合問題

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

3 結(jié)語

本文主要從解決航路規(guī)劃問題的角度出發(fā)，介紹了蟻群算法的近幾年的研究現(xiàn)狀，總結(jié)出蟻群算法發(fā)展的三個(gè)主要方向。蟻群算法具有收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn)，本文主要是根據(jù)蟻群算法的缺點(diǎn)在基本蟻群算法的基礎(chǔ)上加以改進(jìn)。關(guān)于蟻群算法的理論研究及其應(yīng)用的研究將會(huì)是一個(gè)長(zhǎng)期的研究課題。

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

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

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

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

[5] 唐增明,蔣泰.一種改進(jìn)的動(dòng)態(tài)自適應(yīng)最大-最小蟻群算法[J].計(jì)算機(jī)與現(xiàn)代化, 2008.2008(3): 90-92.

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

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

[8] 尚夢(mèng)雨.無人機(jī)實(shí)時(shí)蟻群算法路徑規(guī)劃[J].自動(dòng)化應(yīng)用, 2016 (12):61-63.

[9] 陳謀,肖健,姜長(zhǎng)生.基于改進(jìn)蟻群算法的無人機(jī)三維航路規(guī)劃[J].吉林大學(xué)學(xué)報(bào) (工學(xué)版), 2008.38(4): 991-995.

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

[11] 李猛,王道波,柏婷婷,等.基于蟻群優(yōu)化算法和人工勢(shì)場(chǎng)的無人機(jī)航跡規(guī)劃[J].應(yīng)用科學(xué)學(xué)報(bào), 2012. 30(2): 215-220.

[12] 王芳,李昆鵬.基于人工勢(shì)場(chǎng)法優(yōu)化的蟻群無人機(jī)航路規(guī)劃[J].西安航空學(xué)院學(xué)報(bào), 2014. 32(5): 64-68.

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

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