改進蟻群算法的飛機沖突解脫路徑規(guī)劃方法*

倪　壯， 肖　剛， 敬忠良， 李旻哲

(上海交通大學 航空航天學院，上海200240)

改進蟻群算法的飛機沖突解脫路徑規(guī)劃方法*

倪壯， 肖剛， 敬忠良， 李旻哲

(上海交通大學 航空航天學院，上海200240)

摘要:沖突解脫是空中交通防撞系統(tǒng)中一個關鍵問題。提出了一種基于改進蟻群算法的沖突解脫路徑規(guī)劃方法。該方法通過優(yōu)化蟻群算法初始搜索角度，減少了盲目搜索的時間。此外，在搜索過程中引入“精英策略”，對當前時刻尋找的最優(yōu)解給予額外的信息素增強，使得算法的搜索具有一定的方向性，從而得到更優(yōu)的規(guī)劃路徑，縮短算法的搜索時間。通過仿真驗證，改進后的算法可以得到更優(yōu)的沖突解脫路徑，算法效率更高，在空中交通防撞系統(tǒng)中具有較好的發(fā)展前景。

關鍵詞:空中交通防撞系統(tǒng); 沖突解脫; 蟻群算法; 精英策略; 角度信息

0引言

空中交通防撞系統(tǒng)(trafficalertandcollisionavoidancesystem,TCAS)是飛機環(huán)境監(jiān)視系統(tǒng)(aircraftenvironmentsurveillancesystem,AESS)的一個重要組成部分。沖突解脫是TCAS中十分重要的一個模塊，主要功能是當預測到兩架或多架飛機發(fā)生沖突時，為飛機規(guī)劃出一條避免飛行沖突的理想路徑。近年來，在沖突解脫方面已經(jīng)有了大量的研究工作，例如：神經(jīng)網(wǎng)絡法[1]、遺傳算法[2]、人工勢場法[3]等。神經(jīng)網(wǎng)絡法的學習能力很好，但當動態(tài)環(huán)境中障礙物較多時，網(wǎng)絡結(jié)構(gòu)龐大且神經(jīng)元的閾值需要隨時間的變化而不斷改變；遺傳算法的全局搜索能力很好，但搜索的空間大，并且當環(huán)境改變時必須重新建立模型；人工勢場法雖然便于底層的實時控制，但缺乏全局信息，可能會出現(xiàn)局部最優(yōu)值的問題。

蟻群優(yōu)化[4](antcolonyoptimization,ACO)算法，又稱螞蟻算法，是一種用來尋找優(yōu)化路徑的幾率型算法。它由DorigoM在1992年提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法作為一種自組織算法，具有良好的擴展性、較強的魯棒性、算法實現(xiàn)也較簡單，使得該算法在解決旅行商問題(travelingsalesmanproblem,TSP)[5]、函數(shù)優(yōu)化[6]和路徑規(guī)劃[7,8]等問題都取得了較好的實驗結(jié)果。但是，傳統(tǒng)的蟻群算法的搜索效率受參數(shù)的設置影響很大，并且會出現(xiàn)收斂速度慢，陷入局部最優(yōu)等情況。針對這些情況，國內(nèi)外學者做了不少工作。StutzleT等人提出了一種最大最小螞蟻系統(tǒng)算法[9]，以防止早熟收斂現(xiàn)象的發(fā)生，但當信息平均分布在各個方向上時，螞蟻釋放的信息素將對蟻群的決策產(chǎn)生誤導。BoteeHM利用遺傳算法對蟻群算法參數(shù)的組合優(yōu)化進行了深入的研究[10]，但遺傳算法計算量大，優(yōu)化效果不明顯。

針對上述出現(xiàn)的問題，本文通過對多架飛機沖突解脫問題的建模，引入飛行的角度信息，對蟻群算法初始時刻的搜索范圍進行了約束，同時,在每次循環(huán)結(jié)束后即對當前時刻尋找的最優(yōu)解給予額外的信息素增強，提出了一種基于改進的蟻群算法的沖突解脫算法。由于該算法在搜索過程中有一定的方向性，又避免了初始階段的盲目搜索，使得運算效率和系統(tǒng)的實時性得到了提高。

1理論背景

1.1蟻群算法的數(shù)學模型

(1)

式中τij(t)為城市i與城市j連接路徑上在t時刻的信息素濃度；ηij(t)為啟發(fā)函數(shù)，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度；α為累積信息重要程度因子，β為啟發(fā)函數(shù)重要程度因子；allowedk(k=1,2,…,m)表示螞蟻k下一步允許訪問城市的集合。

傳統(tǒng)蟻群算法中，啟發(fā)函數(shù)ηij(t)為

ηij(t)=1/dij

(2)

式中dij為城市i與城市j間距離。

當所有螞蟻完成一次循環(huán)后，各個城市之間連接路徑上的信息素濃度需要進行實時更新，多路徑的選優(yōu)計算公式為

(3)

(4)

式中Q為信息素濃度的常數(shù)；Lk為螞蟻k在本次循環(huán)中所走路徑的長度。

1.2改進蟻群算法

文獻[11]提出了一種改進的蟻群算法，引入了精英策略(elitiststrategy)，它的基本思想是： 在每次循環(huán)結(jié)束后即對當前時刻尋找的最優(yōu)解給予額外的信息素增強，使其在下一時刻循環(huán)中對蟻群更加具有吸引力。信息素根據(jù)下式進行更新

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(5)

(6)

式中Q為信息素濃度的常數(shù)，Lbest為最短路徑，Lworst為最長路徑，ρ為蒸發(fā)因子，Δτij(t)為城市i到城市j螞蟻所引起的信息素的增加量。

如式(6)所示，更新后每條邊的信息素限制在所經(jīng)過的最長路徑信息素濃度和最短信息素濃度之間，避免某些邊上的信息素過大。該算法減小了各條邊信息素的差距，擴大了解的搜索空間，可以防止算法過早陷入局部收斂。

此外，由于蟻群算法一開始沒有一個確切的路徑，搜索時間大多消耗在搜索的初始階段。針對該情況，文獻[12]提出了一種新的改進的蟻群算法，解決了搜索算法初始階段沒有明確的方向?qū)е碌拿つ克阉鞯膯栴}，縮小了搜索范圍，減少了搜索時間，提升了算法效率。

假設城市r信息素初始值為

(7)

式中W為常數(shù)，Lp,r為起始城市p到城市r間的距離，Lr,q為城市r到目的城市q間的距離。由于W為常數(shù)，當Lr較小時，τr(0)較大。通過比較L的大小確定算法在初始階段大致的搜索方向。

2建模與分析

2.1沖突解脫問題建模

(8)

(9)

所以，沖突解脫問題就是找到解脫路徑，使n架飛機的延誤距離之和最小。在時刻t，任意兩架飛機i和j之間的距離滿足

(10)

式中δ為空管所規(guī)定的在水平空域中飛機之間必須保持的安全距離，一般取5海里。

2.2問題分析

假設飛機的起始點為S，終點為D，兩點間距離為L，飛機解脫角度為θ，最小解脫角度為θ0。場景如圖1所示。

圖1　飛行場景角度示意圖Fig 1　Angle chart of flight scene

為了使延誤距離最小，顯然在滿足式(10)的約束條件下，優(yōu)先選擇較小的角度θ。所以，在使用蟻群算法搜索最優(yōu)路徑的初始時刻，應當首先計算解脫路徑與原航線的偏離角度，從較小的路徑角度開始搜索。同時，根據(jù)“精英策略”，在搜索過程中應當動態(tài)更新下一時刻路徑與原航線的角度，在每次循環(huán)結(jié)束后即對當前時刻尋找的最優(yōu)解給予額外的信息素增強，使其在下一時刻循環(huán)中對蟻群更具吸引力。

2.3沖突解脫算法

根據(jù)以上分析，本文基于改進的蟻群算法，給出了飛機在沖突解脫時的最優(yōu)路徑搜索算法。算法流程如圖2所示。

圖2　改進蟻群算法的算法流程圖Fig 2　Flow chart of the improved ant colony algorithm

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

1)初始化參數(shù)，初始化改進蟻群算法的最大迭代次數(shù)NCmax，螞蟻數(shù)量m、起始點為S，終點為D；

2)將各只螞蟻隨機的放置在n個不同的出發(fā)點(代表n架飛機的初始出發(fā)點)，在搜索初始階段加入角度的信息，指導所有的螞蟻走完路徑；

3)根據(jù)不同路徑的螞蟻之間的約束條件式(10)來約束螞蟻在路徑中的行為，確保螞蟻在行走的過程中無沖突發(fā)生；

4)計算每個螞蟻到終點后與初始目標點的距離，由式(9)來計算最優(yōu)化目標函數(shù)的值，記錄并選擇當前迭代次數(shù)中的最優(yōu)解，同時給予最短路徑較大的信息素增強，對各路徑上的信息素濃度進行更新；

5)如果迭代次數(shù)沒有達到最大，則清空螞蟻經(jīng)過路徑的記錄，返回步驟(2)；否則，計算終止，輸出最優(yōu)解。

3實驗結(jié)果與分析

假設在一塊200km×200km的空域范圍內(nèi)，初始時刻出現(xiàn)4架飛機，飛機勻速飛行，起點分別位于[0,100],[100,200],[200,200],[200,0]km四個點，目標終點為[200,100],[100,0],[0,0],[0,200]km。目標飛行20步，并在第10步4架飛機會同時發(fā)生沖突。將改進后的蟻群算法與原始的蟻群算法進行對比，實驗中選取的螞蟻總數(shù)m=80 只,ρ=0.35,Q=1000,迭代次數(shù)NCmax=200。本文通過Matlab對原始蟻群算法和改進后的蟻群算法進行仿真，圖3為原始蟻群算法規(guī)劃出的沖突解脫仿真結(jié)果，圖4為改進蟻群算法規(guī)劃出的沖突解脫仿真結(jié)果，圖5為原始蟻群算法與改進后的蟻群算法的延誤路徑總長度曲線圖，表1為原始蟻群算法與改進后的蟻群算法的平均運行時間表。

圖3　原始蟻群算法仿真結(jié)果Fig 3　Simulation results by original ant colony algorithm

圖4　改進后蟻群算法仿真結(jié)果Fig 4　Simulation results by improved ant colony algorithm

通過觀察可知，本文提出的改進蟻群算法規(guī)劃的路徑更接近于原有航線，延誤路徑總長度更小，在解脫的同時能盡量按原航線方向飛行，使得解脫后的飛行路線更優(yōu)。此外，本文提出的改進蟻群算法的算法效率，運行時間都明顯優(yōu)于原始蟻群算法,平均運行時間縮短了約35.5 %。仿真結(jié)果證實了改進的蟻群算法能有效地解決多架飛機間沖突解脫路徑規(guī)劃問題。

仿真次數(shù)12345678910原始蟻群平均運行時間/s54.454.752.752.553.551.852.452.852.451.9改進蟻群平均運行時間/s34.534.735.134.834.435.034.534.634.434.1

4結(jié)束語

本文提出了運用改進的蟻群算法對多架飛機間沖突解脫進行路徑規(guī)劃的方法。傳統(tǒng)的蟻群算法搜索效率較低，本文引入了“精英策略”， 對當前時刻尋找的最優(yōu)解給予額外的信息素增強，使得算法在搜索過程中具有一定的方向性，提升了算法搜索效率；此外，在算法搜索的初始階段引入了角度信息，避免了初始階段的盲目搜索，縮短了算法的搜索時間。最后利用改進的蟻群算法實現(xiàn)了飛機間沖突解脫進行路徑規(guī)劃，仿真實驗證明了該路徑規(guī)劃方法的有效性與可行性。

參考文獻:

[1]鄧萬，鄭慶，陳琳，等.神經(jīng)網(wǎng)絡急速學習方法研究[J].計算機學報，2010,33(2):279-287.

[2]刑煥來，潘煒，鄒喜華.一種解決組合優(yōu)化問題的改進型量子遺傳算法[J].電子學報， 2007,35(10)：1999-2007.

[3]DerekJBennet,ColinRMcInnes.Distributedcontrolofmulti-robotsystemsusingbifurcatingpotentialfield[J].RoboticsandAutonomousSystems,2010,58(3):256-264.

[4]DorigoM,ManiezzoV,ColorniA.Antsystem:Optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,Man,andCybernetics—PartB,1996,26(1):29-41.

[5]郭平，鄢文晉．基于TSP問題的蟻群算法綜述[J]．計算機科學，2007(10):181-184.

[6]馬衛(wèi),朱慶保.求解函數(shù)優(yōu)化問題的快速連續(xù)蟻群算法[J].電子學報,2008,36(11):2120-2124.

[7]段愛民,陳澤琳.基于改進蟻群算法的物流配送路徑優(yōu)化[J].計算機技術(shù)與發(fā)展，2011(12):178-181.

[8]鄭峰峻.改進的蟻群算法在物流配送路徑問題中的實現(xiàn)[J].物流科技,2010(2):22-24.

[9]StutzleT,HoosHH.Max-minantsystemandlocalsearchforthetravellingsalesmanproblem[C]∥IEEEInternationalConferenceonEvolutionaryComputation，Indianapolis:IEEE,1997:309-314.

[10]BoteeHM,BonabeauE.Evolvingantcolonyoptimization[J].CompexSystem,1998,1(2):149-159.

[11] 張家善，王志宏，陳應.一種基于精英策略的改進蟻群算法及應用[J].計算機系統(tǒng)應用，2012,21(10):105-108.

[12] 葉仕通,萬智萍.一種基于改進全局信息素更新效率的蟻群算法及仿真[J].計算機應用與軟件，2014,31(1):176-179.

[13] 郭茜.空中交通飛行沖突解決方法研究[D].天津：中國民航大學,2008:36-40.

Pathplanningmethodforaircraftsconflictresolutionbasedonimprovedantcolonyalgorithm*

NIZhuang,XIAOGang,JINGZhong-liang,LIMin-zhe

(SchoolofAeronauticsandAstronautics,ShanghaiJiaoTongUniversity,Shanghai200240,China)

Abstract:Conflict resolution is one of key issues of traffic alert and collision avoidance system (TCAS).A path planning method for conflict resolution based on an improved ant colony algorithm is presented.The proposed method initializes ant colony optimization algorithm with the angle information to reduce blind search time."Elite" strategy is also introduced which can provide additional pheromone enhanced during search procedure for the optimal solution.This scheme accelerates the algorithm searches with a suitable direction,which results in better planning path,shortens search time.The simulation results show that the proposed algorithm derives better path for conflict resolution with a higher efficiency,and has good prospects for development in air traffic collision avoidance system.

Key words:traffic alert and collision avoidance system(TCAS); conflict resolution; ant colony algorithm; elite strategy; angle information

DOI:10.13873/J.1000—9787(2016)04—0130—04

收稿日期：2015—07—15

*基金項目：國家自然科學基金資助項目(61175028)

中圖分類號:V 271.1

文獻標識碼:A

文章編號:1000—9787(2016)04—0130—04

作者簡介:

倪壯(1989-)，男，安徽淮南人，碩士研究生，主要研究方向為空中交通防撞系統(tǒng)。