精英擴散蟻群優(yōu)化算法求解運輸無人機三維路徑規(guī)劃 *

宋阿妮,包賢哲

(湖北工業(yè)大學電氣與電子工程學院，湖北 武漢 430068)

1 引言

隨著科學技術(shù)的發(fā)展，無人機技術(shù)日趨成熟并開始運用于救援、運輸、監(jiān)測、農(nóng)業(yè)和軍事等各個領(lǐng)域，無人機在執(zhí)行任務過程中面臨的最主要問題是如何在復雜環(huán)境中避開障礙物尋找最短路徑安全到達目的地。在空間中無人機需要考慮障礙物大小和形狀進行高度和姿態(tài)的調(diào)整，地形復雜的山區(qū)或城區(qū)對無人機識別、判斷路徑的性能要求更高。如何解決此問題已經(jīng)成為了該領(lǐng)域研究的熱點，提高無人機復雜環(huán)境下的尋徑性能將提高各領(lǐng)域無人機工作效率，具有較高的研究價值。

國內(nèi)外學者對此做過許多研究，如闞平等[1]將補給總次數(shù)、返航補給總時間、總耗時和最小補給時間間隔用權(quán)重系數(shù)化為單目標函數(shù)，根據(jù)作業(yè)區(qū)域面積結(jié)合柵格法提出了一種改進的粒子群算法。該算法以最大迭代次數(shù)的一半為分界線給予進化公式不同的慣性權(quán)重加快算法收斂，對無人機返航順序和返航位置進行尋優(yōu)。最后將其運用于多植物保護無人機協(xié)同系統(tǒng)中，較好地綜合了最大作業(yè)距離規(guī)劃和最小返航距離規(guī)劃的優(yōu)點。黃小毛等[2]對田塊形狀進行分類并結(jié)合貪婪算法解決了復雜形狀農(nóng)田環(huán)境下無人機作業(yè)問題。Li等[3]首先通過無人機的位置和耐久性劃分搜索區(qū)域，再利用并行搜索策略找到最優(yōu)路徑。Duchoň等[4]發(fā)現(xiàn)傳統(tǒng)A*算法無法高效利用長距離單元格的有用空間，并且在搜索過程中有些單元格無法用鋸齒形線連接的問題，為此改進算法讓其進行多角度搜索，根據(jù)跳轉(zhuǎn)點搜索JPS(Jump Point Search)方法在實際評估的細胞周圍種植鄰近細胞,以強化算法搜索性能,提出了JPS(A*)算法，并將其運用于復雜標準網(wǎng)格環(huán)境中進行實驗。結(jié)果表明，就快速尋找路徑而言，該算法比Basic Theta*性能更好，但該算法在搜尋的路徑長度方面表現(xiàn)較差，搜索得到的路徑長度更長，不利于機器人快速完成任務。

嚴煒等[5]以無人機總飛行距離和多余覆蓋率為目標函數(shù)，采用差分進化算法和量子退火算法相結(jié)合的方式求解無人機最優(yōu)路徑，最后的仿真結(jié)果表明算法能夠有效減小無人機的飛行距離。王飛等[6]針對三維移動機器人路徑規(guī)劃問題，重新設(shè)定了蟻群算法中的啟發(fā)函數(shù)，彌補了傳統(tǒng)蟻群算法啟發(fā)函數(shù)未能考慮下一個節(jié)點到目標點距離的缺陷；并采用非均勻的初始化信息素濃度保證算法前期不會盲目搜索，采用自適應信息揮發(fā)因子平衡搜索能力；最終通過實驗表明其改進效果較好，但螞蟻個體之間的關(guān)聯(lián)性不強，收斂速度較慢，不適應于高速多無人機系統(tǒng)。劉可等[7]通過設(shè)置各類參數(shù)并重新設(shè)計啟發(fā)函數(shù)建立二維的任務源和參數(shù)矩陣，設(shè)定機器人只能朝5個方向前進，將設(shè)置的參數(shù)映射到三維空間中，根據(jù)映射擴展后的三維遷移圖，結(jié)合譜圖理論中參數(shù)遷移圖和拉普拉斯矩陣之間的對應關(guān)系得到最優(yōu)參數(shù)簇，從而獲得機器人在三維空間的路線。該方法可以大幅度減少機器人得到最優(yōu)路徑的計算時間，但是該方法只適合于特定的環(huán)境且對于機器人屬性有一定限制。徐興等[8]則通過將原有2點間直線路徑更改為平行于各個坐標軸的折線路徑，以滿足立體倉庫中平面移動和垂直移動的要求，并通過cumsum 函數(shù)對每段路徑元素累加求和改進蟻群算法的概率公式,防止算法陷入局部最優(yōu)。最終將該算法運用于立體倉庫的實際問題中，與其他算法的對比表明了改進的有效性，但算法個體之間聯(lián)系較少且信息素初始化濃度相同，會導致算法收斂緩慢。張洪海等[9]將無人機編隊分為路徑規(guī)劃和速度規(guī)劃2個階段，在路徑規(guī)劃階段，采用Dubins曲線在6種不同路線形式下尋找滿足曲率約束條件的連接，規(guī)定切線方向的2點之間的最短路徑作為最優(yōu)解；在速度規(guī)劃階段，通過空間柵格化將路徑區(qū)分為“安全區(qū)間”“非安全區(qū)間”和“隊形調(diào)整區(qū)間”，為不同區(qū)間設(shè)定差異化速度規(guī)劃規(guī)則，在降低速度規(guī)劃的復雜度的同時，用5次多項式曲線規(guī)劃無人機位移和時間的關(guān)系，得到連續(xù)平滑的速度曲線。將該方法運用于多無人機系統(tǒng)中能夠有效平衡路徑長度、轉(zhuǎn)向頻度和跟蹤誤差之間的關(guān)系，加快無人機的集結(jié)速度和反應速度，增加了路徑的平滑程度。

王云常等[10]采用人工勢場法搜索全局路徑，用A*算法指導局部路徑尋優(yōu)避開障礙物，最后通過仿真表明該算法能夠增強避障性能，縮短尋優(yōu)時間，但在搜索中存在抖動性問題。Sun等[11]發(fā)現(xiàn)經(jīng)典的APF(Artificial Potential Field)算法僅限于單個無人機UAV(Unmanned Aerial Vehicle)軌跡規(guī)劃，通常無法保證完全避免碰撞,為克服這一問題，提出了一種具有距離因子和跳躍策略的方法來解決不可達目標等較為復雜的問題，確保無人機不會與任何障礙物發(fā)生碰撞。該方法將無人機同伴視為實現(xiàn)協(xié)同彈道規(guī)劃的動態(tài)障礙，以避免無人機之間的相互干擾。此外，還使用動態(tài)步進調(diào)整方法解決了抖動問題。胡潔等[12]考慮無人機有限續(xù)航和障礙物問題提出一種集中式逐次貪婪路徑規(guī)劃算法，迭代時每次選擇一個節(jié)點進行匹配組合，能夠在最大化收益的同時滿足各種約束條件。Scott等[13]提出了2種無人機物流運輸模型來提供醫(yī)療相關(guān)服務。Boualem等[14]對無人機的能耗和負載做出約束，建立了運輸物品總成本最小的優(yōu)化模型。唐立等[15]針對山區(qū)應急物資無人機運輸問題，提出一種考慮路徑安全度的改進的蟻群算法，以避開障礙物縮短運輸路徑，仿真表明其算法收斂速度更快，但該算法并未考慮障礙物在三維空間內(nèi)的形狀及大小。Byung等[16]考慮到飛行時間、可裝載能力和貨物重量等對無人機飛行能力的影響，提出了混合整數(shù)線性規(guī)劃MILP(Mixed Integer Linear Programming)公式，用于推導無人機交付時間表。 為了解決計算問題，開發(fā)了后退平線任務分配RHTA(Receding Horizon Task Assignment)啟發(fā)式方法，且根據(jù)當前裝載的產(chǎn)品量開發(fā)了實時權(quán)重函數(shù)以平衡裝載產(chǎn)品量對無人機飛行時間的影響，提高了算法的實用性。通過數(shù)值示例對島嶼區(qū)域交付進行了測試，表明該算法能夠在短時間內(nèi)為大型無人機系統(tǒng)提供路徑方案。

雖然許多優(yōu)化算法在無人機路徑規(guī)劃問題上都有著不錯的效果，但仍然存在著收斂速度過慢、精度不高和參數(shù)設(shè)置復雜等問題。針對這些問題本文提出一種精英擴散蟻群優(yōu)化EDACO(Elite Diffusion Ant Colony Optimization)算法，該算法首先通過極值限定策略限制信息素濃度的范圍，防止算法陷入局部最優(yōu)；然后采用精英策略改進信息素更新公式，加快算法收斂；再引入信息素擴散策略，加大距離較近螞蟻的交流合作，以加快算法收斂，防止算法過早停滯。最后用傳統(tǒng)蟻群優(yōu)化ACO(Ant Colony Optimization)算法、精英擴散蟻群優(yōu)化EDACO算法、遺傳算法GA(Genetic Algorithm)和螢火蟲算法FA(Firefly Algorithm) 在4個算例下進行仿真實驗,實驗結(jié)果表明EDACO算法在三維空間無人機路徑規(guī)劃問題上有著良好的適應性。

2 模型建立與問題分析

假設(shè)某一山區(qū)由于突發(fā)自然災害導致山路受阻，無法通過陸路運輸救援物資，此時派出無人機為山區(qū)居民運送必要的生活用品。假設(shè)該地區(qū)是一個大小為a1×b1×c1km3的空間(第4節(jié)中a1=b1=c1=1)，將山峰等障礙物簡化為不同高度的單峰函數(shù)如式(1)所示:

(1)

其中,Zi(x,y)表示第i個山峰上點(x,y)處的高度，即縱坐標。k1,k2為2個可調(diào)整參數(shù)，用來改變山峰的形狀和大小。xi,yi表示山峰中心的橫坐標和縱坐標,xpi,ypi則代表山峰i在x方向和y方向的坡度。

無人機在飛行過程中需要避開所有山峰，即無人機在點(xm,ym)上的飛行高度要大于山峰在該點的高度，否則會導致無人機損傷或墜毀，如式(2)所示:

V(xm,ym)>Zi(xm,ym),xm∈Si，ym∈Si

(2)

其中,V(xm,ym)表示無人機所在的位置，Si表示第i個山峰投影在xy平面上的所有點的集合。

但在實際情況中，由于山峰坡度不同且無人機有一定體積，在無人機體心飛行高度恰好高過山峰高度時仍然會發(fā)生碰撞。設(shè)無人機的長為a,寬為b，高為h(第4節(jié)中，a=0.5 m，b=0.6 m,h=0.5 m)，將無人機簡化為一個長方體，其平面示意圖如圖1所示。

Figure 1 Schematic diagram of the location of UAV and mountains圖1 無人機與山峰位置示意圖

根據(jù)圖1所示無人機飛行情況，如果按照式(1)的約束條件求解，即無人機在(xm,ym)的中心縱坐標大于山峰的縱坐標時，無人機會與山峰發(fā)生碰撞，如圖1中虛線所示。無人機與山峰碰撞不僅與其體積有關(guān)，也與山峰碰撞面的陡度有關(guān)，但由于山峰各個面的曲率不同且隨著高度的升高而發(fā)生變化，難以對所有山峰建立具體模型。為了能夠保證任何時刻無人機位置都不與山峰碰撞，將無人機放置于以其體對角線的一半作為半徑的球體中，如圖2所示。

Figure 2 Simplified model of UAV圖2 無人機簡化模型圖

圖2中的長方體即為無人機的簡化示意圖，其中球體的半徑如式(3)所示:

(3)

以無人機中心坐標當前位置為原點，建立極坐標系，引入球體的極坐標公式，如式(4)所示:

(4)

其中,R(x,y,z)表示球體R上的任意一點，φ是通過z軸和空間任意點的平面與坐標面zOx所構(gòu)成的角；θ是極點和任意點組成的直線與z軸正方向的夾角。

當滿足式(5)時，即球體上任意一點(x,y,z)都不在山峰表面或內(nèi)部時，就能夠保證在任何情況下無人機都不會與山峰發(fā)生碰撞。

R(xm,ym,z)>Zi(xm,ym),xm,ym∈Si

(5)

無人機的飛行高度存在限制，超過最大值將會影響控制信號，而由于地形原因，在飛行途中無人機高度低于最小值存在與石塊和樹木碰撞的危險，如式(6)所示：

Hmin≤Hi≤Hmax

(6)

其中,Hmin為無人機飛行最小高度(第4節(jié)中Hmin=10 m)，Hmax為無人機飛行最大高度(第4節(jié)中Hmax=1000 m)。

評判無人機路徑優(yōu)劣的指標包括路徑長短、路徑平滑度和路徑飛行高度等，為了能夠得到最優(yōu)路徑，將3種因素整合作為評判路徑優(yōu)劣的指標，無人機飛行過程中經(jīng)過的2點間的距離如式(7)所示:

(7)

其中,(xi,yi,zi)是無人機經(jīng)過的第i個點的坐標，由此無人機所經(jīng)過的總路程如式(8)所示:

(8)

其中，N為無人機一共經(jīng)過的點個數(shù)。無人機在飛行過程中每一次轉(zhuǎn)過的角度如圖3所示。

Figure 3 Schematic diagram of the rotation angle between two points of UAV圖3 無人機在2點間轉(zhuǎn)角示意圖

根據(jù)圖3可知，無人機從AB段到BC段轉(zhuǎn)過的角度為θ，其整體路徑的平均平滑度如式(9)所示:

(9)

其中,Ai表示無人機經(jīng)過的第i個點與第i+1個點組成的向量。由于無人機飛行高度增高會增加能耗且對控制信號有一定影響，所以要在保持無人機路徑安全的情況下盡可能降低飛行高度。無人機飛行過程中總的飛行平均高度如式(10)所示:

(10)

由式(7)～式(9)可以得到最終的優(yōu)化目標函數(shù)，如式(11)所示:

minM=Lall+Q+Hall

(11)

3 改進的蟻群算法

3.1 傳統(tǒng)蟻群算法

蟻群算法是由Dorigo[17]于1992年在他的博士論文中提出的一種用來尋找優(yōu)化路徑的概率型算法。其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，螞蟻在尋找食物的過程中會在爬過的道路上釋放一種信息素，螞蟻根據(jù)每條路徑上的信息素濃度選擇前進方向，直到找到最優(yōu)路徑。

螞蟻按照不同路徑上的信息素濃度選擇下一個到達的區(qū)域，螞蟻k從區(qū)域i到區(qū)域j的轉(zhuǎn)移概率如式(12)所示:

(12)

其中,μij(t)表示在t時刻區(qū)域i與區(qū)域j之間的信息素濃度;α為一常數(shù),是信息素啟發(fā)因子，表示信息素對路徑選擇概率的影響力(第4節(jié)中α=0.7);φij(t)則表示t時刻區(qū)域i到區(qū)域j的期望；σ為期望啟發(fā)因子，表示期望對區(qū)域選擇概率的影響力(第4節(jié)中σ=0.7);S表示去除螞蟻走過的區(qū)域后剩余的區(qū)域集合。期望φij(t)如式(13)所示:

(13)

其中，Lij表示區(qū)域i與區(qū)域j之間的路徑，|Lij|表示區(qū)域i與區(qū)域j之間的距離。在所有螞蟻遍歷完區(qū)域點后，對每條道路的信息素進行更新，更新公式如式(14)所示:

μij(t+1)=(1-λ)μij(t)+Δμij

(14)

其中，λ為信息素揮發(fā)系數(shù)(第4節(jié)中λ=0.3)，若一條道路長時間沒有螞蟻經(jīng)過，其上的信息素濃度會隨著迭代次數(shù)的增加而逐漸減小。螞蟻經(jīng)過導致的信息素變化量如式(15)所示:

(15)

3.2 改進的蟻群算法

3.2.1 極值限定策略

傳統(tǒng)蟻群算法會因為某些路徑上走過的螞蟻較多而信息素濃度持續(xù)上升，而其它無螞蟻經(jīng)過的路徑信息素濃度不斷下降，這樣會導致蟻群算法過早陷入局部最優(yōu)，所以要對信息素濃度的大小做出限定[18]，如式(16)和式(17)所示。

(16)

(17)

其中,|Lbest|是當前全局最優(yōu)解的路徑總長度;η為常數(shù)(第4節(jié)中η=0.2);Dbest為每次迭代結(jié)束后全局最優(yōu)解個數(shù)占總個體數(shù)的比例。蟻群的信息素濃度μij(t)∈[μmin(t),μmax(t)],限制信息素范圍能夠擴大算法前期的搜索范圍，防止其過早陷入局部最優(yōu)。

3.2.2 精英策略

最優(yōu)解對所有螞蟻的路徑選擇有指導作用，能夠幫助算法快速收斂減少運算時間，在信息素濃度更新公式中引入精英個體，如式(18)所示:

(18)

(19)

其中，γ為當前最優(yōu)解個數(shù)，Pbest表示當前全局最優(yōu)個體經(jīng)過的路徑集合。指數(shù)函數(shù)和全局最優(yōu)路徑長度的加入，保證了算法在迭代次數(shù)逐漸增加的過程中，最優(yōu)個體對算法中其它個體的影響隨著迭代次數(shù)的增多而逐步增大，在保證算法前期的搜索范圍較大的情況下，使得算法整體的收斂速度加快，從而提高算法工作效率。

精英策略在算法原有搜索模式不變的情況下，加入了最優(yōu)個體對其他個體的引導影響，這將顯著提升算法的搜索性能。

3.2.3 擴散策略

螞蟻釋放的信息素能夠?qū)Ω浇浵伒男袆赢a(chǎn)生影響，指導后續(xù)螞蟻的行動。根據(jù)螞蟻的這一協(xié)作特征，引入信息素擴散策略來加強位置相近螞蟻之間的協(xié)作，以加快算法的收斂。

各類揮發(fā)性物質(zhì)和氣體在空氣中的擴散呈正態(tài)分布，離擴散源位置越遠其信息素濃度越低，將其模型在空間中表示出來，如圖4所示。

Figure 4 Pheromone diffusion space model圖4 信息素擴散空間模型

如圖4所示為信號源o點擴散出的信息素在空間中的濃度分布情況。其中β和hu為常數(shù)，可以根據(jù)算法效果進行調(diào)整，一般hu=1.2，β=π/2時得到的算法效果最好。R為信息素擴散的最大半徑，其與h、β的關(guān)系如式(20)所示:

hutanβ=R

(20)

根據(jù)圖4所示，可以得到當螞蟻k從區(qū)域i向區(qū)域j移動且不經(jīng)過路徑id時，在其擴散范圍內(nèi)路徑id接收到的由路徑ij擴散的信息素濃度如式(21)所示:

(21)

其中,ψ為一常數(shù)，|Lid|為區(qū)域i與區(qū)域d之間的距離，此時螞蟻k在路徑id上的信息素濃度改變量如式(22)所示:

(22)

通過引入信息素濃度擴散策略，距離較近的螞蟻之間可以得到周圍螞蟻散發(fā)的信息素指引，個體總路徑越優(yōu)秀，對周圍所有螞蟻的信息素濃度影響就越大，這樣可以增加較近螞蟻之間的交流合作，加快蟻群的進化收斂速度，避免了個體之間關(guān)聯(lián)性差導致算法陷入停滯的問題。

在具體問題中信息素按照如下方式進行初始化：以所要到達的終點為圓心，距離終點越遠其信息素濃度越低，這樣可以防止在迭代初期由于信息素相同導致算法盲目搜索。終點圓心處設(shè)置的信息素濃度為D，離圓心最遠處設(shè)置的濃度為Ds，期間根據(jù)距離遠近以等差為d2數(shù)列逐漸降低信息素濃度，其二維平面示意圖如圖5所示。

D-2d2D-2d2D-2d2D-2d2D-2d2D-2d2D-d2D-d2D-d2D-2d2D-2d2D-d2DD-d2D-2d2D-2d2D-d2D-d2D-d2D-2d2D-2d2D-2d2D-2d2D-2d2D-2d2

Figure 5 Two-dimensional plan view of initial pheromone

圖5 初始信息素二維平面圖

圖5中的D為終點信息素濃度(第4節(jié)中，D=2000)，圍繞終點，信息素濃度隨著與起點的距離增大而不斷降低，而等差數(shù)列的等差項d2則如式(23)所示:

(23)

其中,Ds為以終點為圓心可搜索區(qū)域內(nèi)最外圈各點的信息素濃度，在圖5中即為D-2d2(第4節(jié)中，Ds=1000);ks為按照圖5方式，在整個搜索域內(nèi)圍繞終點的最大層數(shù)，例如在圖5中，整個區(qū)域內(nèi)圍繞終點的最大層數(shù)為2，所以ks=2。將其擴展到三維空間中時也遵循此規(guī)則，只不過圍繞終點的外層平面空間變成了包圍終點空間的立體殼層空間，每一層外殼的信息素濃度也按照等差數(shù)列遞減。

EDACO算法流程圖如圖6所示。

Figure 6 Flow chart of EDACO algorithm圖6 EDACO算法流程圖

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

假設(shè)存在4個不同的受災山區(qū),空間大小均為1000×1000×1000 m3，可通行，安排無人機向這4個山區(qū)的居民運送必須的生活用品。

設(shè)螞蟻個體數(shù)N=100，最大迭代次數(shù)tmax=100，將山區(qū)空間區(qū)域看作1000×1000×1000 m3共109個位置點，無人機長寬高分別為a=0.5 m,b=0.6 m,h=0.5 m，最大飛行高度Hmax=1000 m,途中最小飛行高度Hmin=10 m。其他的參數(shù)設(shè)置如表1所示。

Table 1 Parameter table

設(shè)定4個山區(qū)的起點分別為(1,5,0)，(0,5,0)，(2,9,0)，(0.5,3.5,0),4個山區(qū)的終點分別為(10,5,0)，(10,5,0)，(10,0.5,0)，(9.5,9.5,0)，設(shè)終點信息素濃度D=2000，區(qū)域內(nèi)最遠處信息素濃度Ds=1000。由于已知4個山區(qū)的終點坐標，所以在4個山區(qū)中，ks的值分別為999，999，999，999。

為了驗證第3節(jié)提出的精英策略和擴散策略對算法各方面性能有顯著提升作用，選擇1號山區(qū)作為驗證環(huán)境，分別將單獨加入了精英策略的蟻群優(yōu)化EACO(Elite Ant Colony Optimization)算法和單獨加入擴散策略的蟻群優(yōu)化DACO(Diffusion Ant Colony Optimization)算法與傳統(tǒng)蟻群算法運用到該問題中求解，求解得到的路徑圖如圖7所示。

Figure 7 Three-dimensional path diagram of three algorithms in No 1 mountain area圖7 3種算法在1號山區(qū)的三維路徑圖

從圖7中可以看到，單獨加入精英策略和單獨加入擴散策略后的蟻群算法得到的路徑與傳統(tǒng)蟻群算法得到的路徑有很大的區(qū)別，3種算法的最終路徑長度隨著迭代次數(shù)變化的過程如圖8所示。

Figure 8 Iterative diagram of three algorithms in No.1 mountain area圖8 3種算法在1號山區(qū)的迭代圖

根據(jù)圖8可知，單獨引入精英策略的蟻群算法(EACO)，其最終路徑長度相對于傳統(tǒng)蟻群算法減少了5.8%，提升效果并不是特別顯著，但其迭代速度卻得到了大幅度提升，在30次左右就達到最優(yōu)；而單獨引入擴散策略的蟻群算法(DACO)，其路徑長度相對于傳統(tǒng)蟻群算法減少了18.5%，效果顯著，且其迭代速度也有小幅度的提升。由此測試可以看出，精英策略和擴散策略能夠提升蟻群算法的收斂速度和精度等性能，表明上述精英策略、擴散策略的改進是有效的。

將上述參數(shù)代入到算法中，用精英擴散蟻群優(yōu)化算法、傳統(tǒng)蟻群算法、遺傳算法和螢火蟲算法計算得到4個山區(qū)的無人機派送路徑如圖9所示。

根據(jù)圖9中4個山區(qū)的無人機派送圖可以看出，改進的蟻群算法(EDACO)都能找到飛行高度更低、平滑度更好的路徑。

3種對比基礎(chǔ)算法得到的4個山區(qū)的無人機派送路徑長度對比數(shù)據(jù)如表2所示。表2中的Min表示最優(yōu)結(jié)果的路徑長度，Time表示迭代算法獲得最優(yōu)解的時間。蟻群算法在計算時存在運行常數(shù)階O(1)、找尋最大值的線性階O(n)和快速排序的對數(shù)階O(nlogn)，所以傳統(tǒng)蟻群算法的時間復雜度最高階為對數(shù)階O(nlogn)。改進的蟻群算法加入的精英策略和擴散策略只是在每次迭代結(jié)束后根據(jù)公式對信息素矩陣進行加減運算，僅僅增加了常數(shù)階和線性階復雜度，并沒有再增加傳統(tǒng)蟻群算法最高階對數(shù)階的運算，所以整體來說它們的時間復雜度相近，EDACO算法所用計算時間可能會略長一點。Rate表示個體收斂率,即收斂到最優(yōu)結(jié)果的個體占總個體的比例。根據(jù)表2中3種基礎(chǔ)算法的數(shù)據(jù)，從求解的精度、迭代時間和粒子的收斂率3個指標綜合評價來看，蟻群算法的效果要更為優(yōu)秀，對問題的適應性更好。因此改進蟻群算法可以得到最好的優(yōu)化效果。

蟻群算法和精英擴散蟻群優(yōu)化算法(EDACO)的結(jié)果數(shù)據(jù)如表3所示。從表3可以看出，EDACO算法在求解精度、迭代收斂速度、粒子收斂率上相對傳統(tǒng)蟻群算法都有了明顯提升，性能更加優(yōu)秀，對比于文獻[6～8]中改進的蟻群算法，解決了因螞蟻個體之間關(guān)聯(lián)性差而導致的收斂速度慢，以及對無人機和環(huán)境有較多限制的問題。本文EDACO算法適用環(huán)境更廣且更適合用于復雜環(huán)境下的大型無人機系統(tǒng)之中。理論上只要能夠建立環(huán)境模型，都可以采用本文所提出的EDACO算法解決問題。選取其中的1號山區(qū)為例子，各算法迭代情況如圖10所示。根據(jù)圖10可以看出，相對于傳統(tǒng)的蟻群算法，EDACO算法在迭代40次左右就達到收斂值，其收斂速度更快、精度更高，能夠根據(jù)地形情況快速響應為無人機提供最優(yōu)路徑，滿足無人機在復雜地形下對反應速度和精度的要求。EDACO算法對無人機三維路徑分配問題有著更好的適應性。

Figure 9 UAV’s delivery path diagram of four algorithms in four mountain areas圖9 4種算法在4個山區(qū)的無人機派送路徑圖

山區(qū)編號ACOMin/km Time/s Rate/%GAMin/km Time/s Rate/%FAMin/km Time/s Rate/%11.484 767.59441.634 582.21321.495 584.702921.410 359.14551.533 877.76431.433 269.243731.591 063.12472.059 969.85451.739 673.153641.715 259.93491.564 170.04341.651 864.3735

Table 3 Comparison of algorithm results

Figure 10 Iteration diagram of four algorithms in No.1 mountain area圖10 4種算法在1號山區(qū)的迭代圖

5 結(jié)束語

針對受災山區(qū)運輸物資的無人機三維路徑規(guī)劃問題，本文提出了一種精英擴散蟻群算法，首先通過極值限定策略限制信息素的最大、最小范圍，防止算法陷入局部最優(yōu)；而后采用精英策略改進信息素濃度公式，加強優(yōu)質(zhì)個體對種群的影響，以加快算法收斂；最后通過擴散策略加大距離較近個體之間的交流合作，防止種群獨立搜索而陷入停滯。將精英擴散蟻群算法EDACO、傳統(tǒng)蟻群算法、遺傳算法和螢火蟲算法用于4個山區(qū)無人機運送物資的實例中，結(jié)果表明改進的算法在各方面擁有更優(yōu)秀的性能，對無人機三維路徑規(guī)劃問題有著良好的適應性。

值得注意的是，通過表3可以看出，雖然本文算法在路徑長度和安全度等各方面都有著很大的優(yōu)勢，但這一切都必須建立在對飛行環(huán)境準確建模的基礎(chǔ)上，如果對于飛行環(huán)境的建模不夠準確，可能會導致路徑障礙判斷失誤而造成無人機撞擊墜毀事故，這對于環(huán)境的分析與建模是一個不小的挑戰(zhàn)。除此之外，本文算法較對比算法對物體碰撞的判斷要更加“嚴苛”，雖然“嚴苛”的判斷會提升無人機的飛行效率，有利于規(guī)劃出更加優(yōu)秀的路徑，但在一定程度上也會影響到無人機路徑規(guī)劃選擇的空間。后續(xù)將研究如何將該算法與其他算法融合以進一步提高算法的性能，擴大應用范圍，并盡量降低建模和搜索所需時間和難度，使得算法的應用范圍更廣、限制更少。