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

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

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

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

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

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

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

0引言

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

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

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

1理論背景

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

(1)

式中τij(t)為城市i與城市j連接路徑上在t時(shí)刻的信息素濃度；η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間距離。

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

(3)

(4)

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

1.2改進(jìn)蟻群算法

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

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

(5)

(6)

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

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

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

假設(shè)城市r信息素初始值為

(7)

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

2建模與分析

2.1沖突解脫問題建模

(8)

(9)

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

(10)

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

2.2問題分析

假設(shè)飛機(jī)的起始點(diǎn)為S，終點(diǎn)為D，兩點(diǎn)間距離為L，飛機(jī)解脫角度為θ，最小解脫角度為θ0。場景如圖1所示。

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

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

2.3沖突解脫算法

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

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

改進(jìn)的蟻群算法具體算法步驟如下：

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

2)將各只螞蟻隨機(jī)的放置在n個(gè)不同的出發(fā)點(diǎn)(代表n架飛機(jī)的初始出發(fā)點(diǎn))，在搜索初始階段加入角度的信息，指導(dǎo)所有的螞蟻?zhàn)咄曷窂剑?/p>

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

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn):

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

[2]刑煥來，潘煒，鄒喜華.一種解決組合優(yōu)化問題的改進(jìn)型量子遺傳算法[J].電子學(xué)報(bào)， 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]．計(jì)算機(jī)科學(xué)，2007(10):181-184.

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

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

[8]鄭峰峻.改進(jìn)的蟻群算法在物流配送路徑問題中的實(shí)現(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] 張家善，王志宏，陳應(yīng).一種基于精英策略的改進(jìn)蟻群算法及應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012,21(10):105-108.

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

[13] 郭茜.空中交通飛行沖突解決方法研究[D].天津：中國民航大學(xué),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

*基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61175028)

中圖分類號:V 271.1

文獻(xiàn)標(biāo)識碼:A

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

作者簡介:

倪壯(1989-)，男，安徽淮南人，碩士研究生，主要研究方向?yàn)榭罩薪煌ǚ雷蚕到y(tǒng)。