一種改進(jìn)蟻群算法的無人機(jī)避險(xiǎn)方法仿真研究

吳學(xué)禮 賈云聰 張建華 甄然

摘要：隨著低空空域的逐漸開放以及無人機(jī)產(chǎn)業(yè)的高速發(fā)展，無人機(jī)數(shù)量不斷上升，無人機(jī)間隨時(shí)有發(fā)生沖突的可能，需要一種可靠的沖突解脫技術(shù)使無人機(jī)可以避免危險(xiǎn)。針對(duì)無人機(jī)沖突解脫問題，提出基于改進(jìn)蟻群算法的無人機(jī)沖突解脫方法：采用參數(shù)自適應(yīng)調(diào)整策略，根據(jù)解的質(zhì)量，動(dòng)態(tài)調(diào)整參數(shù)值，防止算法早熟，提高收斂精度；在算法狀態(tài)轉(zhuǎn)移規(guī)則中引入擾動(dòng)因子，加快算法初期收斂。算法測(cè)試實(shí)驗(yàn)結(jié)果顯示，改進(jìn)蟻群算法收斂精度更高。仿真實(shí)驗(yàn)表明，改進(jìn)算法可以幫助兩無人機(jī)及時(shí)脫離危險(xiǎn)。該算法作為一種通用優(yōu)化算法，也可應(yīng)用到目標(biāo)識(shí)別、路徑規(guī)劃等問題中，具有重要的研究意義與廣泛的應(yīng)用價(jià)值。

關(guān)鍵詞：機(jī)器人控制；無人機(jī)；沖突解脫；蟻群算法；參數(shù)自適應(yīng)調(diào)整；擾動(dòng)因子

中圖分類號(hào)：TP273文獻(xiàn)標(biāo)志碼：A

收稿日期：20171216；修回日期：20180306；責(zé)任編輯：李穆

基金項(xiàng)目：河北省自然科學(xué)基金（F2015208128， F2014208119）； 河北省發(fā)改委項(xiàng)目（9130002017001）； 河北省科技廳項(xiàng)目（17212102D）

第一作者簡(jiǎn)介：吳學(xué)禮（1961—），男（滿族），黑龍江齊齊哈爾人，教授，博士，主要從事控制科學(xué)與工程方面的研究。

Email：wuxueli@hebust.edu.cn

吳學(xué)禮，賈云聰，張建華，等.一種改進(jìn)蟻群算法的無人機(jī)避險(xiǎn)方法仿真研究[J].河北科技大學(xué)學(xué)報(bào)，2018，39（2）：166175.

WU Xueli， JIA Yuncong， ZHANG Jianhua， et al.Simulation study of UAV conflict resolution based on an improved ant colony algorithm [J].Journal of Hebei University of Science and Technology，2018，39（2）：166175.Simulation study of UAV conflict resolution based on

an improved ant colony algorithm

WU Xueli1，2， JIA Yuncong1， ZHANG Jianhua1，2， ZHEN Ran1，2

（1.School of Electrical Engineering， Hebei University of Science and Technology， Shijiazhuang， Hebei 050018， China； 2. Hebei Provincial Research Center for Technologies in Process Engineering Automation， Shijiazhuang， Hebei， 050018， China）

Abstract：With the gradual opening of the lowaltitude airspace and the rapid development of Unmanned Aerial Vehicle（UAV） industry， the users of UAV are increasing continuously and the conflicts could occur at any time. It is necessary to develop a reliable UAV conflict resolution algorithm to avoid the danger. This paper proposes an UAV conflict resolution algorithm based on the improved ant colony algorithm with two advantages. Firstly， the algorithm adopts adaptive parameters adjustment strategy， which adjusts the parameters value dynamically according to the quality of the solution， prevents the algorithm premature convergence and improves the accuracy. In addition， the disturbance factors is introduced to the state transition rules of random selected path in order to accelerate the initial convergence. The simulation results have shown that the improved algorithm displays obvious superiority in convergence precision， helping the two UAVs avoiding dangers in time. The algorithm described in this paper could be applied to target identification， path planning and other issues as a general optimized algorithm， which is of great significance and wide application.

Keywords：robot control； UAV； conflict resolution； ant colony optimization； parameter adaptive adjustment； disturbance factor

近年來，由于無人機(jī)應(yīng)用日趨廣泛，致使低空空域變得越來越擁堵，無人機(jī)的飛行安全受到威脅。避險(xiǎn)系統(tǒng)對(duì)確保無人機(jī)安全自主地飛行，提高空域流量，高效完成任務(wù)有著重要的現(xiàn)實(shí)意義。沖突解脫算法是無人機(jī)避險(xiǎn)系統(tǒng)的核心，目前國(guó)內(nèi)外對(duì)無人機(jī)沖突解脫算法的研究還并不完善，如何在代價(jià)最小的情況下實(shí)現(xiàn)無人機(jī)的沖突解脫，有待進(jìn)一步研究。

河北科技大學(xué)學(xué)報(bào)2018年第2期吳學(xué)禮，等：一種改進(jìn)蟻群算法的無人機(jī)避險(xiǎn)方法仿真研究當(dāng)前，有許多傳統(tǒng)方法解決無人機(jī)沖突解脫問題，如Petri網(wǎng)絡(luò)算法[1]和基于數(shù)據(jù)融合的模糊規(guī)劃[2]等，但是這些方法的計(jì)算效率通常較低，因此，國(guó)內(nèi)外學(xué)者提出了幾種基于元啟發(fā)式算法的解決問題方案：文獻(xiàn)＼[3—4＼]采用了遺傳算法，但是遺傳算法在搜索解脫路徑時(shí)，雖然初期收斂較快，但收斂精度低，導(dǎo)致解脫路線不夠優(yōu)化；文獻(xiàn)＼[5＼]采用了模擬退火算法，該算法穩(wěn)定性高，但是尋得高質(zhì)量近似解所花費(fèi)時(shí)間較多；文獻(xiàn)＼[6＼]采用了粒子群算法，該算法雖然收斂較快，但是容易陷入早熟，并且局部尋優(yōu)能力較差；文獻(xiàn)＼[7—8＼]采用了基本蟻群算法，從中可以看到蟻群算法同樣存在易陷入早熟，且算法前期由于信息素匱乏，導(dǎo)致初期收斂速度慢的缺點(diǎn)，但是與其他幾種智能算法對(duì)比，蟻群算法性能更均衡，后期搜索速度快并具有很強(qiáng)的魯棒性，可以更好地應(yīng)對(duì)動(dòng)態(tài)問題并且蟻群算法易與其他算法或者策略相結(jié)合，以改善算法性能。

本文主要針對(duì)無人機(jī)避險(xiǎn)算法進(jìn)行研究，針對(duì)蟻群系統(tǒng)算法結(jié)果易早熟，收斂精度不高等問題，在現(xiàn)有研究基礎(chǔ)上提出了一種改進(jìn)算法，證明了算法的收斂性，并將其應(yīng)用于兩無人機(jī)沖突解脫問題，在保證無人機(jī)安全飛行的基礎(chǔ)上，減少因沖突帶來的消耗，通過Matlab仿真驗(yàn)證算法的有效性。

1蟻群算法及拓展

1.1基本蟻群算法

蟻群算法（ant colony optimization，ACO）是由 DORIGO等[9]首次提出的，蟻群中每個(gè)螞蟻信息互通，每個(gè)螞蟻的信息在蟻群內(nèi)部不斷更新并互相學(xué)習(xí)交流，使整體不斷優(yōu)化，算法通過外激素的濃度對(duì)最優(yōu)解進(jìn)行篩選[10]。

問題的解在蟻群中通過不斷迭代逐步被優(yōu)化。對(duì)于各種復(fù)雜優(yōu)化問題，蟻群算法通過定義解的分量來解決。開始時(shí)，解的分量對(duì)應(yīng)于每只螞蟻，備選解以重復(fù)增加解的分量的方式來產(chǎn)生[11]。螞蟻通過狀態(tài)轉(zhuǎn)移規(guī)則和正反饋機(jī)制，當(dāng)處于選擇點(diǎn)上時(shí)，決定哪個(gè)解的分量要加到它的當(dāng)前部分解。構(gòu)造完一個(gè)完整的解后，解的分量會(huì)被螞蟻涂上信息素，指導(dǎo)接下來整體和個(gè)體的活動(dòng)[12]。

ACO中包含了多個(gè)螞蟻，每個(gè)螞蟻的行為由狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則決定。

1）狀態(tài)轉(zhuǎn)移規(guī)則：pkij（t）=ταij（t）ηβij（t）∑r∈allowedkταir（t）ηβir（t），j∈allowedk；0，otherwise。（1）2）信息素更新規(guī)則：τij（t+1）=（1-ρ）·τij（t）+∑mk=1Δτkij（t），（2）

Δτkij=Q/Ck（t），k∈[i，j]；0，otherwise。（3）式（1）中，τij（t）表示在第t次迭代時(shí)，路徑（i，j）上的信息素濃度，ηij（t）=1/dij為啟發(fā)函數(shù)，表示螞蟻從i走到j(luò)的期望程度；α和β分別為累計(jì)信息重要程度因子和啟發(fā)函數(shù)重要程度因子；allowedk表示螞蟻k下一步允許訪問節(jié)點(diǎn)的集合。式（2）中ρ為信息素的保留比例，是一個(gè)取值范圍在0和1之間的常數(shù)。Δτkij為螞蟻k在t次迭代中，若經(jīng)過邊（i，j），則在（i，j）上增加的信息素量，其值由式（3）確定，其中Q是一個(gè)常數(shù)，Ck（t）是螞蟻k在t次迭代時(shí)所走的長(zhǎng)度[13]。

1.2蟻群算法的拓展

雖然ACO中的正反饋機(jī)制能使較好的解得到不斷優(yōu)化，但是由于算法初期信息素積累差異不明顯，導(dǎo)致蟻群算法初期收斂速度較慢，并且對(duì)于規(guī)模較大的問題，ACO容易出現(xiàn)停滯現(xiàn)象，不能對(duì)解空間進(jìn)行進(jìn)一步搜索，不利于發(fā)現(xiàn)更好的解，為了解決這些問題，國(guó)際上一些專家提出了多種方法對(duì)蟻群算法進(jìn)行改進(jìn)，期望提高算法收斂速度和精度，改善停滯問題。

在文獻(xiàn)＼[14＼]中，蟻群算法開創(chuàng)者DORIGO對(duì)基本蟻群算法進(jìn)行改進(jìn)，提出了蟻群系統(tǒng)算法（ant colony system，ACS）。ACS對(duì)基本蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則進(jìn)行了改進(jìn)。對(duì)狀態(tài)轉(zhuǎn)移規(guī)則的改進(jìn)如式（4）所示。s=arg maxj∈allowedk{τ（i，j）·η（i，j）}，if q≤q0；pkij，else。（4）將常量q0加入到狀態(tài)轉(zhuǎn)移規(guī)則中，采用貪婪的路徑選取方式還是隨機(jī)探索新路徑的主次關(guān)系由q0大小決定，其是一個(gè)固定值，根據(jù)經(jīng)驗(yàn)取0.9，q是在[0，1]區(qū)間均勻分布的隨機(jī)數(shù)，在第t次迭代時(shí)大概率選擇[τ（i，j）]·[η（i，j）]最大的節(jié)點(diǎn)，這就使螞蟻探索范圍變小，減少前期算法搜索時(shí)間，并且使用全局與局部信息素雙重更新規(guī)則。τij（t+1）=（1-ρ）·τij（t）+ρ·Δτgbij（t），（5）

τij=（1-ξ）·τij+ξ·τ0。（6）式中：Δτgbij（t）=（Cgb）-1，（Cgb）-1為當(dāng)前全局最優(yōu)路徑長(zhǎng)度；τ0是每條邊的初始信息素；ρ和ξ均為信息素?fù)]發(fā)系數(shù)，是取值范圍在[0，1]之間的常數(shù)。

首先，對(duì)截止當(dāng)前迭代次數(shù)時(shí)，算法所找到的屬于全局最優(yōu)解的路徑進(jìn)行更新，如式（5）所示；然后，對(duì)螞蟻?zhàn)哌^的，不屬于全局最優(yōu)解的路徑進(jìn)行局部信息素更新，如式（6）所示。在ACS中，通過設(shè)定此種優(yōu)先級(jí)，即只有構(gòu)成全局最優(yōu)路徑的那些才有機(jī)會(huì)增加其信息素水平，其他邊的信息素，則由于揮發(fā)作用逐漸降低，那些屬于最佳路徑的信息素水平就會(huì)明顯高于其他的邊，對(duì)找尋最優(yōu)路徑就變得目的性更強(qiáng)。局部外激素更新規(guī)則采用負(fù)反饋，目的是降低已經(jīng)搜索過的路徑被選擇的機(jī)會(huì)，降低早熟現(xiàn)象發(fā)生概率。每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照式（6）被相應(yīng)地消除一部分，實(shí)現(xiàn)一種信息素的局部調(diào)整。但是由于信息素的全局更新作用，再經(jīng)過幾次搜索以后，所有屬于最佳路徑的邊，其信息素水平遠(yuǎn)遠(yuǎn)高于其他邊相差一個(gè)數(shù)量級(jí)。因此，信息素的局部更新作用不能有效地阻止搜索陷入局部最優(yōu)化。另外，由于信息素的局部更新在每一步搜索之后都要進(jìn)行，因此，消耗了大量的計(jì)算時(shí)間。

另外，在蟻群算法初始化參數(shù)值時(shí)，一般都是憑經(jīng)驗(yàn)設(shè)置。經(jīng)過國(guó)內(nèi)外專家多次研究測(cè)試發(fā)現(xiàn)，參數(shù)α和β對(duì)蟻群算法中螞蟻行為有重要影響，螞蟻的行為強(qiáng)烈依賴于給定參數(shù)的值。

文獻(xiàn)＼[15＼]針對(duì)ACS進(jìn)行了詳細(xì)分析，發(fā)現(xiàn)無論在尋優(yōu)能力還是尋優(yōu)速度上，ACS與基本蟻群算法相比都有明顯的提升，并且通過TSP中Eil51問題對(duì)ACS進(jìn)行大量實(shí)驗(yàn)測(cè)試，確定了ACS參數(shù)的最佳取值范圍：α∈[1.0，3.0]，β∈[2.0，4.0]，ρ∈[0.5，0.8]，但是ACS在解決實(shí)際問題中，仍然存在易停滯，收斂速度不理想的情況。

文獻(xiàn)＼[16＼]提出了參數(shù)α，β自適應(yīng)調(diào)整策略，通過建立α與β的互鎖關(guān)系，即α+β=M，M為固定值，針對(duì)不同迭代次數(shù)NC，2個(gè)參數(shù)會(huì)對(duì)應(yīng)取不同的值，以應(yīng)對(duì)不同時(shí)期算法不同的特點(diǎn)，如式（7），式（8）所示：α=α1，NC≤NC1；α2，NC1

β=β1，NC≤NC1；β2，NC1

β（t+1）=ξ2β（t），ifξ2<βmax；βmax，otherwise。（10）式中：ξ1，ξ2均為大于1的常數(shù)；αmax，βmax為α和β所能達(dá)到的上界。

以上2種參數(shù)自適應(yīng)方法雖然在一定程度上改善了算法性能，但是2種都各自增加了2個(gè)參數(shù)的設(shè)定，使算法產(chǎn)生了更多不確定因素。

2改進(jìn)的蟻群算法

蟻群算法有魯棒性強(qiáng)、全局搜索、并行分布計(jì)算、易與其他問題結(jié)合等優(yōu)點(diǎn)，并在實(shí)踐中體現(xiàn)出了優(yōu)越性，蟻群算法是解決飛機(jī)避險(xiǎn)，路徑規(guī)劃及TSP問題的較好的優(yōu)化算法之一，但是仍然存在算法初期收斂慢，易停滯陷入早熟等問題。在對(duì)第1部分所提及的方法進(jìn)行分析與研究的基礎(chǔ)上，本文將ACS與自適應(yīng)參數(shù)調(diào)節(jié)進(jìn)行融合，并且引入擾動(dòng)因子，提出了一種新的改進(jìn)蟻群算法。

2.1算法的改進(jìn)

2.1.1參數(shù)自適應(yīng)調(diào)節(jié)策略

α和β是2個(gè)重要參數(shù)，α是軌跡相對(duì)重要性，反映了螞蟻在尋優(yōu)過程中積累信息素，指導(dǎo)后來螞蟻們?cè)谒阉髦械南鄬?duì)重要程度，代表了螞蟻在搜索路徑中隨機(jī)作用大小，α越大搜索隨機(jī)性越弱，越小則易陷入盲目搜索。β代表能見度相對(duì)重要性，反映了優(yōu)化過程中的確定因素，是先驗(yàn)知識(shí)在指導(dǎo)螞蟻搜索過程中的相對(duì)重要程度，β越小搜索隨機(jī)性越大，β越大收斂速度加快但易陷入局部最優(yōu)。α和β的取值是至關(guān)重要的，直接影響算法性能。

針對(duì)此問題，根據(jù)自然選擇規(guī)則，在算法的狀態(tài)轉(zhuǎn)移規(guī)則中對(duì)參數(shù)α和β采用自適應(yīng)參數(shù)適配方法，構(gòu)造參數(shù)解集Φk（t）=[αk（t），βk（t）]，更新公式如式（11）、式（12）所示：Φwinner（t+1）=[αwinner（t）+Δ， βwinner（t）]；（11）

Φloser（t+1）=[αwinner（t）， βwinner（t）]。（12）每次迭代之后，該方法評(píng)估每只螞蟻構(gòu)建路徑的質(zhì)量，如果某只螞蟻找到了當(dāng)前迭代的最優(yōu)路徑，結(jié)構(gòu)參數(shù)根據(jù)式（11）更新，而式（12）用于找到了最差路徑的螞蟻。也就是說，找到當(dāng)前迭代最優(yōu)路徑的螞蟻會(huì)被獎(jiǎng)勵(lì)，找到最差路徑的螞蟻會(huì)被懲罰，根據(jù)獲勝者失敗者反饋機(jī)制，在這個(gè)機(jī)制下，只要螞蟻找到當(dāng)前最佳路徑，α的幅度就會(huì)增加Δ=0.01，隨著算法的進(jìn)行，獲勝的螞蟻對(duì)信息素濃度的感應(yīng)變得更加敏感，并產(chǎn)生具有相同結(jié)構(gòu)參數(shù)值的后代，而作為失敗者的螞蟻被獲勝者的新生代所代替。在整個(gè)螞蟻種群的α值可以增加的情況下，本文只允許獲勝者螞蟻增加α的幅度，以加強(qiáng)定向搜索。

文獻(xiàn)＼[15＼]中大量實(shí)驗(yàn)測(cè)試結(jié)果表明，當(dāng)α≥1作為安全下限時(shí)，算法能夠達(dá)到令人滿意的性能，并且[2.0，4.0]是β的合理范圍，因此，在所提出的改進(jìn)算法中，每個(gè)螞蟻在開始構(gòu)造路徑時(shí)具有相同初始值α=1，同時(shí)β的值是在區(qū)間[2.0，4.0]中隨機(jī)的，并且相同的α起始值允許螞蟻通過識(shí)別可能導(dǎo)致更優(yōu)解β的值進(jìn)行公平的競(jìng)爭(zhēng)。

算法利用自然選擇規(guī)則來尋找構(gòu)造參數(shù)值的自適應(yīng)趨勢(shì)，從而能夠識(shí)別出合適的值，在整個(gè)搜索過程中以這種方式逐漸地增加α的值，使得螞蟻在開始階段繼續(xù)探索搜索空間（對(duì)應(yīng)于較小的α），有助于防止算法提前收斂到搜索空間的小區(qū)域。另外，逐漸增加參數(shù)α的值將強(qiáng)調(diào)更好的搜索空間區(qū)域，所以，搜索將被引導(dǎo)到后期的更優(yōu)的路徑（對(duì)應(yīng)于大的α值），提高算法的收斂精度。

2.1.2引入擾動(dòng)因子

在ACS中，q0是狀態(tài)轉(zhuǎn)移規(guī)則控制參數(shù)，決定了ACS以貪婪方式還是隨機(jī)方式選擇路徑的概率，一般取固定值0.9，在算法初期可以大概率通過貪婪方式去選擇路徑，有助于前期信息素積累，加快前期收斂速度。但是由于算法前期收斂加快，導(dǎo)致算法容易停滯并且采用隨機(jī)選擇方式去拓展新路徑概率較低，減弱了參數(shù)自適應(yīng)調(diào)節(jié)的作用。

針對(duì)這個(gè)問題，本文在ACS的基礎(chǔ)上，引入擾動(dòng)因子w0代替q0，w0具體公式如式（13）所示：w0=1et/b，n=1，2，…，NC，（13）式中：t為迭代次數(shù)；b為正的常數(shù)；在算法剛開始時(shí)，w0大概率大于q，所以算法前期路徑以貪婪選擇方式為主，使信息素可以迅速積累，加速算法前期收斂，隨著迭代次數(shù)增加，w0小于q的概率變大，隨機(jī)選擇路徑規(guī)則為主，此時(shí)參數(shù)自適應(yīng)調(diào)節(jié)機(jī)制開始發(fā)揮作用，當(dāng)α較小時(shí)，算法擴(kuò)展搜索范圍，豐富路徑多樣性，防止因前期加速收斂可能會(huì)導(dǎo)致的早熟問題，當(dāng)α逐漸增大，定向搜索加強(qiáng)，所以算法收斂精度得以提升。這樣將概率合理分配于各階段，實(shí)際上是加速算法收斂，增加了改進(jìn)算法的全局搜索能力，使算法具備了跳出早熟的能力。

則改進(jìn)算法的狀態(tài)轉(zhuǎn)移規(guī)則為s=arg maxj∈allowedk{τ（i，j）·η（i，j）}，ifq≤w0；pkij，ifq>w0；（14）

pkij=[τij（t）]αk（t）·[ηij（t）]βk（t）∑s∈allowedk[τis（t）]αk（t）·[ηis（t）]βk（t），j∈allowedk；0，otherwise。（15）2.2改進(jìn)算法收斂性證明

由于蟻群算法具有很強(qiáng)的魯棒性，所以，本文對(duì)改進(jìn)的蟻群算法進(jìn)行收斂性證明。

證明思路如下：首先證明對(duì)于任意迭代次數(shù)t，搜索區(qū)域A中任意一段路徑（i，j）∈A上的信息素濃度是有界的，接下來再證明改進(jìn)的算法能以任意趨近于1的概率找到最優(yōu)路徑。

命題：對(duì)任意迭代次數(shù)n中的任意路徑（i，j）∈A，τij（n）存在上界τmax和下界τmin，即：τmin≤τij（t）≤τmax，（16）式中，τij（t）是路徑（i，j）上的信息素濃度。

證明：全局信息素更新規(guī)則和局部信息素更新規(guī)則可以被寫成如式（17）形式：ah+1=（1-φ）·ah+φb，h≥1，（17）式中，ah+1和ah代表τij（t+1）和τij（t），相應(yīng)的，b=g（s*），τ0，g（s*）為全局最優(yōu)解的信息素濃度，φ=ρ，ξ。那么可以容易的通過歸納得到：ah=（1-φ）（h-1）a1+∑h-2i=0（1-φ）iφb=（1-φ）（h-1）a1+b[1-（1-φ）h-1]，（18）因?yàn)椋?>φ>0，所以隨著h→∞，ah趨近于b。

下面，就序列{ah}的單調(diào)性進(jìn)行討論，ah的導(dǎo)數(shù)為a′h=（a1-b）（1-φ）（h-1）ln（1-φ），（19）因?yàn)閘n（1-φ）<0，在算法開始時(shí)，根據(jù)信息素更新規(guī)則，信息素濃度的值τij=τ′肯定要比τ0大，但是比全局最優(yōu)路徑信息素濃度g（s*）小，并且局部信息素更新規(guī)則會(huì)通過更新逐步降低螞蟻訪問過邊的濃度。因此假設(shè)在最壞的情況下，邊（k，l）一直在蒸發(fā)信息素，從沒有獲得過加強(qiáng)，那么信息素的濃度也絕不會(huì)小于τ0，所以信息素最小值為τmin=τ0，所以τmin≤τij（t）≤τmax=g（s*）。

證畢。

定理令P*（n）為算法在前n次迭代中至少找出1個(gè)最優(yōu)解的概率，則對(duì)于一個(gè)絕對(duì)小的ε>0而言，當(dāng)n足夠大時(shí)，有：P*（n）≥1-ε，（20）

limn→∞P*（n）=1。（21）證明：根據(jù)偽隨機(jī)比例法則，假設(shè)路徑（i，j）沒有相關(guān)的最大信息素路徑，選擇路徑（i，j）的概率為隨機(jī)選擇路徑的概率，即P（q>q0）·pij，所以在任意1次迭代n中，做出任何特定選擇概率為Pij（n）=P（q>q0）·[τij（n）]α[ηij]β[∑（i，j）τij（n）]α[ηij]β≥P（q>q0）·（γΓ）β·[τij（n）∑（i，j）τij（n）]α≥

P（q>q0）·（γΓ）β·[τmin|V|τmax]α=P′min，（22）式中，|V|表示固定節(jié)點(diǎn)的可行后繼的最大數(shù)目。任何產(chǎn)生的解s′，包括最優(yōu)解s*∈S*，生成的概率為≥（P′min）l>0。（23）式中l(wèi)<+∞為序列的最大長(zhǎng)度。所以，P*（n）≥1-（1-）n，（24）因此limn→∞P*（n）=1，此外，對(duì)于任意小的ε>0而言，當(dāng)n足夠大時(shí)，有：P*（n）≥1-ε，（25）證畢。

2.3改進(jìn)蟻群算法的性能分析

TSP問題是最經(jīng)常研究的組合優(yōu)化問題之一[18]，它是一種NP難題但有一個(gè)相對(duì)簡(jiǎn)單的定義，使人們能夠?qū)⒆⒁饬性谒惴ㄉ希虼薚SP問題事實(shí)上已經(jīng)成為測(cè)試啟發(fā)式算法的標(biāo)準(zhǔn)問題。本文依然選擇TSP問題作為測(cè)試改進(jìn)蟻群算法性能的工具。

根據(jù)文獻(xiàn)＼[19＼]所述，最佳性能指標(biāo)為評(píng)價(jià)蟻群算法優(yōu)劣程度的基本指標(biāo)。最佳性能指標(biāo)由相對(duì)誤差Eo定義，其公式如式（26）所示：Eo=gb-g*g*×100%，（26）式中：gb為算法經(jīng)過多次運(yùn)行得到的最優(yōu)化的值；g*為所解決的問題理論上的最優(yōu)值。最佳性能指標(biāo)用來衡量蟻群算法對(duì)問題的最佳優(yōu)化程度，其值越小意味著算法優(yōu)化性能越好，收斂精度越高。

下面將ACS與改進(jìn)的蟻群算法分別求解TSP問題中的Oliver30問題和Eil51問題，并對(duì)其性能進(jìn)行比較分析。其中2種算法初始參數(shù)設(shè)置見表1。

從圖2中可以看出ACS求解Oliver30，在算法前期收斂較快，但是在迭代次數(shù)137次時(shí)算法就停止繼續(xù)收斂，而對(duì)于改進(jìn)的蟻群算法（見圖4），則沒有出現(xiàn)相較于ACS過久的停滯，算法在95次迭代以后仍然逐步向最優(yōu)解收斂。對(duì)于解決規(guī)模更大的Eil51問題，ACS的最優(yōu)路徑與路線長(zhǎng)度如圖5、圖6所示，改進(jìn)蟻群算法如圖7、圖8所示。

通過圖6和圖8對(duì)比，可以更明顯地看出，改進(jìn)蟻群算法在規(guī)定迭代次數(shù)內(nèi)并沒有出現(xiàn)明顯停滯，相較于ACS，改進(jìn)蟻群算法對(duì)Eil51問題規(guī)劃出的路徑更合理，路徑長(zhǎng)度更短。實(shí)驗(yàn)詳細(xì)測(cè)試對(duì)比結(jié)果見表2。

問題最優(yōu)值/mACS最優(yōu)值/m改進(jìn)算法最優(yōu)值/mACS相對(duì)誤差/%改進(jìn)算法相對(duì)誤差/%Oliver30423.735 6433.105 2427.466 62.211 20.880 5Ei151426458.306 2442.129 07.583 63.786 2

從表2中可以看出，隨著解決問題規(guī)模的擴(kuò)大，算法的相對(duì)誤差都有上升，對(duì)應(yīng)算法性能都出現(xiàn)一定程度的下降，但是改進(jìn)的蟻群算法得出的最優(yōu)路徑長(zhǎng)度與相對(duì)誤差方面均小于ACS，即改進(jìn)過后的算法與ACS相比性能要更好，是一種有效的改進(jìn)算法。

3沖突解脫問題建模及仿真模擬

3.1沖突解脫問題建模

規(guī)劃避險(xiǎn)路徑是無人機(jī)避險(xiǎn)問題的目的，并且要使無人機(jī)的避險(xiǎn)路徑與原航跡相比延誤距離之和最小，從而實(shí)現(xiàn)航跡最短。在規(guī)劃避險(xiǎn)路徑之前，將兩沖突無人機(jī)航線分別分成k等份，所以，定義優(yōu)化目標(biāo)函數(shù)為f=min（∑ki=1dAi+∑ki=1dBi），（27）式中，i=1，2，…，k，dAi與dBi為無人機(jī)A和B在第i步時(shí)，與原飛行路線的距離。并且為了確保兩無人機(jī)不相撞，在任意時(shí)刻無人機(jī)A和B之間的距離滿足：（xB-xA）2+（yB-yA）2≥req，（28）式中，req為無人機(jī)間最小間隔，由于各種無人機(jī)性能差別較大，所以根據(jù)每架無人機(jī)性能特點(diǎn)，制定了適合無人機(jī)的最小安全間隔，具體公式如式（29）所示：req=3V1（VfVa+VfVd+VbVa+VbVd）4×τ，（29）式中：Vf為最大前進(jìn)速度；Vb為最大后退速度；Va為最大垂直上升速度；Vd為最大下降速度；V1為最大水平橫向速度；τ為監(jiān)視系統(tǒng)刷新速率[20]。

3.2仿真驗(yàn)證

本文對(duì)兩無人機(jī)的避險(xiǎn)問題進(jìn)行Matlab仿真，以在同一海拔平面為例。首先構(gòu)建一個(gè)200 m×200 m的區(qū)域，并設(shè)置無人機(jī)A和B的起始點(diǎn)分別為（100，0）和（0，100），它們分別從各自起點(diǎn)向?qū)ο蝻w行。假設(shè)兩無人機(jī)性能相同，若各自均保持勻速，直線飛行，那么兩無人機(jī)將在（100，100）處相沖突，如圖9所示。

以對(duì)避險(xiǎn)算法要求較高森林防火無人機(jī)為例，算法中，參數(shù)分別初始化為α=1，ξ=0.5，ρ=0.6，m=60，NC=100，τ0=0.01。本文采用基于ADSB制式的無人機(jī)監(jiān)視設(shè)備，刷新頻率為0.5 s/次，森林防火無人機(jī)其最大水平飛行速度為Vf=Vb=V1=45 m/s，最大上升下降速度Va=Vd=30 m/s，所以根據(jù)式（29）可知，兩無人機(jī)間最小安全間隔req=19.655 6 m，為方便計(jì)算，取整為20 m。將本文所提出的改進(jìn)蟻群算法應(yīng)用到無人機(jī)避險(xiǎn)問題中，進(jìn)行Matlab仿真驗(yàn)證。

改進(jìn)蟻群算法的沖突解脫軌跡與兩無人機(jī)距離如圖10、圖11所示。從圖10中可以看出，無人機(jī)A由于改進(jìn)蟻群算法，調(diào)整了航跡，由圖11可知，兩無人機(jī)在開始時(shí)逐漸接近，在第9步時(shí)達(dá)到了最小安全距離，但是隨后成功實(shí)現(xiàn)解脫，避免了相撞的危險(xiǎn)。

圖12為在沖突解脫算法過程中迭代次數(shù)與兩無人機(jī)延誤距離之間的關(guān)系，可以看出算法在保證兩機(jī)大于最小安全間隔的基礎(chǔ)上，在第34次迭代時(shí)，能夠找到延誤距離相對(duì)較小的路徑，減少了因兩無人機(jī)沖突帶來的飛行消耗。仿真結(jié)果表明改進(jìn)蟻群算法能夠較好地解決兩無人機(jī)沖突解脫問題。

4結(jié)語

針對(duì)無人機(jī)沖突解脫問題在ACS的基礎(chǔ)上提出一種改進(jìn)的蟻群算法，對(duì)算法參數(shù)采用自適應(yīng)調(diào)整策略，算法根據(jù)解的質(zhì)量，動(dòng)態(tài)調(diào)整參數(shù)值，使算法具備了跳出早熟的能力，提高了收斂精度；在算法狀態(tài)轉(zhuǎn)移規(guī)則中引入擾動(dòng)因子，加快算法前期收斂速度。證明了改進(jìn)算法的收斂性，并采用Oliver30和Eil51兩個(gè)問題對(duì)ACS和改進(jìn)的蟻群算法進(jìn)行了測(cè)試對(duì)比，測(cè)試結(jié)果表明改進(jìn)算法在最佳性能方面有了提升。將改進(jìn)的算法應(yīng)用到無人機(jī)沖突解脫中進(jìn)行Matlab仿真，仿真結(jié)果表明改進(jìn)的蟻群算法成功使2架即將發(fā)生碰撞的無人機(jī)脫離危險(xiǎn)。本文僅研究了兩無人機(jī)沖突解脫情況，今后將對(duì)多無人機(jī)沖突解脫問題進(jìn)行更加深入的研究。

參考文獻(xiàn)/References：

[1]MOHANTA J C， PARHI D R， PATEL S K. Path planning strategy for autonomous mobile robot navigation using PetriGA optimisation[J]. Computers & Electrical Engineering， 2011， 37（6）：10581070.

[2]蔣忠中， 汪定偉. 物流配送車輛路徑優(yōu)化的模糊規(guī)劃模型與算法[J]. 系統(tǒng)仿真學(xué)報(bào)， 2006， 18（11）：33013304.

JIANG Zhongzhong， WANG Dingwei. Fuzzy programming model and algorithm of logistics distribution vehicle routing problem[J]. Journal of System Simulation， 2006， 18（11）：33013304.

[3]ROBERGE V， TARBOUCHI M， LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for realtime uav path planning[J]. IEEE Transactions on Industrial Informatics， 2012， 9（1）：132141.

[4]TSAI C C， HUANG H C， CHAN C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J]. IEEE Transactions on Industrial Electronics， 2011， 58（10）：48134821.

[5]裴志剛， 李華星， 王慶勝. 模擬退火遺傳算法在飛行沖突解脫中的應(yīng)用[J]. 交通信息與安全， 2005， 23（1）：115117.

PEI Zhigang， LI Huaxing， WANG Qingsheng. Application of simulated annealing genetic algorithm in flight conflicts resolution[J].Computer and Communications， 2005， 23（1）：115117.

[6]甄然， 司超， 吳學(xué)禮， 等. 基于改進(jìn)粒子群算法的飛行器沖突解脫方法研究[J]. 河北科技大學(xué)學(xué)報(bào)，2016，37（5）：491496.

ZHEN Ran， SI Chao， WU Xueli， et al. Aircraft conflict relief method based on improved particle swarm algorithm research[J]. Journal of Hebei University of Science and Technology， 2016， 37（5）：491496.

[7]ZHANG W， GONG X， HAN G， et al. An improved ant colony algorithm for path planning in one scenic area with many spots[J]. IEEE Access， 2017，5：1326013269.

[8]LISSOVOI A， WITT C. Runtime analysis of ant colony optimization on dynamic shortest path problems[J]. Theoretical Computer Science， 2015， 561：7385.

[9]DORIGO M， BIRATTARI M， STUZLE T. Ant colony optimization[J]. Computational Intelligence Magazine IEEE， 2004， 1（4）：2839.

[10]GUO P， ZHU L. Ant colony optimization for continuous domains[C]// Eighth International Conference on Natural Computation. [S.l.]：IEEE， 2012：758762.

[11]YU B， YANG Z Z， YAO B. An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research， 2009， 196（1）：171176.

[12]屈鴻， 黃利偉， 柯星. 動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J]. 電子科技大學(xué)學(xué)報(bào)， 2015， 44（2）：260265.

QU Hong， HUANG Liwei， KE Xing. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of University of Electronic Science and Technology of China， 2015， 44（2）：260265.

[13]FUELLERER G， DOERNER K F， HARTL R F， et al. Ant colony optimization for the twodimensional loading vehicle routing problem[J]. Computers & Operations Research， 2009， 36（3）：655673.

[14]DORIGO M， GAMBARDELLA L M. Ant colony system： A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）：5366.

[15]JIANG L Y， ZHANG J. Analysis of parameters in ant colony system[J]. Computer Engineering & Applications， 2007，43（20）：3136.

[16]LIU Y， CHEN Z， WANG X， et al. Research on adaptive ant colony algorithm in robot hole making path planning[J]. International Journal of Control & Automation， 2017， 10（5）：189198.

[17]黃志華.基于自適應(yīng)蟻群算法的旅行商問題的求解[J].嘉應(yīng)學(xué)院學(xué)報(bào)（自然科學(xué)），2017，35（2）：1823.

HUANG Z H， MARHEMATICS S O， UNIVERSITY J. Solution of traveling salesman problem based on adaptive ant colony algorithm[J]. Journal of Jiaying University（Natural Science）， 2017， 35（2）：1823.

[18]吳華鋒， 陳信強(qiáng)， 毛奇凰. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學(xué)報(bào)， 2013（4）：165170.

WU Huangfeng， CHEN Xinqiang， MAO Qihuang. Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications， 2013（4）：165170.

[19]杭海存， 郭愛煌， 舒文杰. 基于LEACH與蟻群算法的WSN路由機(jī)制及性能分析[J]. 傳感技術(shù)學(xué)報(bào)， 2008， 21（10）：17351738.

HANG Haicun， GUO Aihuang， SHU Wenjie. Performance analysis of WSN routing scheme based on LEACH and ant algorithm[J]. Chinese Journal of Sensors and Actuators， 2008， 21（10）：17351738.

[20]XIANG J， YANG L， LUO Z. Flight safety measurements of UAVs in congested airspace[J].Journal of Aeronautics， 2016， 29（5）：13551366.第39卷第2期河北科技大學(xué)學(xué)報(bào)Vol.39，No.2

2018年4月Journal of Hebei University of Science and TechnologyApr. 2018