一種改進蟻群算法的無人機避險方法仿真研究

吳學禮 賈云聰 張建華 甄然

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

關鍵詞：機器人控制；無人機；沖突解脫；蟻群算法；參數自適應調整；擾動因子

中圖分類號：TP273文獻標志碼：A

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

基金項目：河北省自然科學基金（F2015208128， F2014208119）； 河北省發改委項目（9130002017001）； 河北省科技廳項目（17212102D）

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

Email：wuxueli@hebust.edu.cn

吳學禮，賈云聰，張建華，等.一種改進蟻群算法的無人機避險方法仿真研究[J].河北科技大學學報，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

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

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

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

1蟻群算法及拓展

1.1基本蟻群算法

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

問題的解在蟻群中通過不斷迭代逐步被優化。對于各種復雜優化問題，蟻群算法通過定義解的分量來解決。開始時，解的分量對應于每只螞蟻，備選解以重復增加解的分量的方式來產生[11]。螞蟻通過狀態轉移規則和正反饋機制，當處于選擇點上時，決定哪個解的分量要加到它的當前部分解。構造完一個完整的解后，解的分量會被螞蟻涂上信息素，指導接下來整體和個體的活動[12]。

ACO中包含了多個螞蟻，每個螞蟻的行為由狀態轉移規則和信息素更新規則決定。

1）狀態轉移規則：pkij（t）=ταij（t）ηβij（t）∑r∈allowedkταir（t）ηβir（t），j∈allowedk；0，otherwise。（1）2）信息素更新規則：τ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次迭代時，路徑（i，j）上的信息素濃度，ηij（t）=1/dij為啟發函數，表示螞蟻從i走到j的期望程度；α和β分別為累計信息重要程度因子和啟發函數重要程度因子；allowedk表示螞蟻k下一步允許訪問節點的集合。式（2）中ρ為信息素的保留比例，是一個取值范圍在0和1之間的常數。Δτkij為螞蟻k在t次迭代中，若經過邊（i，j），則在（i，j）上增加的信息素量，其值由式（3）確定，其中Q是一個常數，Ck（t）是螞蟻k在t次迭代時所走的長度[13]。

1.2蟻群算法的拓展

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

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

τij=（1-ξ）·τij+ξ·τ0。（6）式中：Δτgbij（t）=（Cgb）-1，（Cgb）-1為當前全局最優路徑長度；τ0是每條邊的初始信息素；ρ和ξ均為信息素揮發系數，是取值范圍在[0，1]之間的常數。

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

另外，在蟻群算法初始化參數值時，一般都是憑經驗設置。經過國內外專家多次研究測試發現，參數α和β對蟻群算法中螞蟻行為有重要影響，螞蟻的行為強烈依賴于給定參數的值。

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

文獻＼[16＼]提出了參數α，β自適應調整策略，通過建立α與β的互鎖關系，即α+β=M，M為固定值，針對不同迭代次數NC，2個參數會對應取不同的值，以應對不同時期算法不同的特點，如式（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的常數；αmax，βmax為α和β所能達到的上界。

以上2種參數自適應方法雖然在一定程度上改善了算法性能，但是2種都各自增加了2個參數的設定，使算法產生了更多不確定因素。

2改進的蟻群算法

蟻群算法有魯棒性強、全局搜索、并行分布計算、易與其他問題結合等優點，并在實踐中體現出了優越性，蟻群算法是解決飛機避險，路徑規劃及TSP問題的較好的優化算法之一，但是仍然存在算法初期收斂慢，易停滯陷入早熟等問題。在對第1部分所提及的方法進行分析與研究的基礎上，本文將ACS與自適應參數調節進行融合，并且引入擾動因子，提出了一種新的改進蟻群算法。

2.1算法的改進

2.1.1參數自適應調節策略

α和β是2個重要參數，α是軌跡相對重要性，反映了螞蟻在尋優過程中積累信息素，指導后來螞蟻們在搜索中的相對重要程度，代表了螞蟻在搜索路徑中隨機作用大小，α越大搜索隨機性越弱，越小則易陷入盲目搜索。β代表能見度相對重要性，反映了優化過程中的確定因素，是先驗知識在指導螞蟻搜索過程中的相對重要程度，β越小搜索隨機性越大，β越大收斂速度加快但易陷入局部最優。α和β的取值是至關重要的，直接影響算法性能。

針對此問題，根據自然選擇規則，在算法的狀態轉移規則中對參數α和β采用自適應參數適配方法，構造參數解集Φk（t）=[αk（t），βk（t）]，更新公式如式（11）、式（12）所示：Φwinner（t+1）=[αwinner（t）+Δ， βwinner（t）]；（11）

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

文獻＼[15＼]中大量實驗測試結果表明，當α≥1作為安全下限時，算法能夠達到令人滿意的性能，并且[2.0，4.0]是β的合理范圍，因此，在所提出的改進算法中，每個螞蟻在開始構造路徑時具有相同初始值α=1，同時β的值是在區間[2.0，4.0]中隨機的，并且相同的α起始值允許螞蟻通過識別可能導致更優解β的值進行公平的競爭。

算法利用自然選擇規則來尋找構造參數值的自適應趨勢，從而能夠識別出合適的值，在整個搜索過程中以這種方式逐漸地增加α的值，使得螞蟻在開始階段繼續探索搜索空間（對應于較小的α），有助于防止算法提前收斂到搜索空間的小區域。另外，逐漸增加參數α的值將強調更好的搜索空間區域，所以，搜索將被引導到后期的更優的路徑（對應于大的α值），提高算法的收斂精度。

2.1.2引入擾動因子

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

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

則改進算法的狀態轉移規則為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改進算法收斂性證明

由于蟻群算法具有很強的魯棒性，所以，本文對改進的蟻群算法進行收斂性證明。

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

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

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

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

證畢。

定理令P*（n）為算法在前n次迭代中至少找出1個最優解的概率，則對于一個絕對小的ε>0而言，當n足夠大時，有：P*（n）≥1-ε，（20）

limn→∞P*（n）=1。（21）證明：根據偽隨機比例法則，假設路徑（i，j）沒有相關的最大信息素路徑，選擇路徑（i，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|表示固定節點的可行后繼的最大數目。任何產生的解s′，包括最優解s*∈S*，生成的概率為≥（P′min）l>0。（23）式中l<+∞為序列的最大長度。所以，P*（n）≥1-（1-）n，（24）因此limn→∞P*（n）=1，此外，對于任意小的ε>0而言，當n足夠大時，有：P*（n）≥1-ε，（25）證畢。

2.3改進蟻群算法的性能分析

TSP問題是最經常研究的組合優化問題之一[18]，它是一種NP難題但有一個相對簡單的定義，使人們能夠將注意力集中在算法上，因此TSP問題事實上已經成為測試啟發式算法的標準問題。本文依然選擇TSP問題作為測試改進蟻群算法性能的工具。

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

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

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

通過圖6和圖8對比，可以更明顯地看出，改進蟻群算法在規定迭代次數內并沒有出現明顯停滯，相較于ACS，改進蟻群算法對Eil51問題規劃出的路徑更合理，路徑長度更短。實驗詳細測試對比結果見表2。

問題最優值/mACS最優值/m改進算法最優值/mACS相對誤差/%改進算法相對誤差/%Oliver30423.735 6433.105 2427.466 62.211 20.880 5Ei151426458.306 2442.129 07.583 63.786 2

從表2中可以看出，隨著解決問題規模的擴大，算法的相對誤差都有上升，對應算法性能都出現一定程度的下降，但是改進的蟻群算法得出的最優路徑長度與相對誤差方面均小于ACS，即改進過后的算法與ACS相比性能要更好，是一種有效的改進算法。

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

3.1沖突解脫問題建模

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

3.2仿真驗證

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

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

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

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

4結語

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

參考文獻/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]蔣忠中， 汪定偉. 物流配送車輛路徑優化的模糊規劃模型與算法[J]. 系統仿真學報， 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]裴志剛， 李華星， 王慶勝. 模擬退火遺傳算法在飛行沖突解脫中的應用[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]甄然， 司超， 吳學禮， 等. 基于改進粒子群算法的飛行器沖突解脫方法研究[J]. 河北科技大學學報，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]屈鴻， 黃利偉， 柯星. 動態環境下基于改進蟻群算法的機器人路徑規劃研究[J]. 電子科技大學學報， 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]黃志華.基于自適應蟻群算法的旅行商問題的求解[J].嘉應學院學報（自然科學），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]吳華鋒， 陳信強， 毛奇凰. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學報， 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]. 傳感技術學報， 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期河北科技大學學報Vol.39，No.2

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