基于改進人工魚群優(yōu)化的蟻群算法無人機自主航路規(guī)劃

馬銘希，吳 軍，岳龍飛，閆孟達，余稼洋

(1.空軍工程大學 空管領航學院，西安 710051；2.空軍工程大學 裝備管理與無人機工程學院，西安 710051)

1 引言

蟻群算法(ant colony optimization，ACO)是于20世紀90年代意大利學者M.Dorigo等人受到螞蟻覓食和返巢等行為的啟發(fā)，提出的一種隨機搜索模擬進化算法。具有參數數目少，設置簡單，魯棒性較強等優(yōu)點，因此常被用于解決組合優(yōu)化問題、連續(xù)時間系統優(yōu)化問題等。相比于遺傳算法、模擬退火算法、人工勢場法、粒子群算法，蟻群算法有記憶性、更適于復雜問題求解、有明顯的正反饋機制的優(yōu)點。但是，在蟻群算法尋優(yōu)的過程中也存在一些不足。比如，蟻群算法的初始信息素值相同，因此選擇下一節(jié)點時采用隨機選擇，導致蟻群算法的收斂速度較慢；同時，蟻群算法容易陷入局部最優(yōu)甚至出現停滯現象；還有蟻群算法在種群多樣性與收斂速度上存在矛盾，當個體分布越均勻，種群多樣性就越好，但與此同時收斂速度就越慢，當其分布越集中時，收斂速度加快，但是不利于算法的全局尋優(yōu)。針對此類問題不少學者開展了相應的研究。

李靜等為了增加路徑的平滑程度，同時提高全局搜索能力，提出了用Logistic混沌擾動改進信息素的更新方式，但是該算法在初期階段，沒有對初始信息素濃度進行優(yōu)化，雖然豐富了全局搜索空間，但同時也造成了無效搜索，降低了收斂速度；王蘇彧等為加快蟻群算法的收斂速度與尋優(yōu)能力，提出了基于自適應導向的蟻群算法。但是，該算法在陷入局部最優(yōu)時并沒有適當的策略可以使螞蟻產生“逃逸”行為，跳出當前的局部陷阱；郭一聰等人利用改進勢場法對無人機在三維空間上的飛行路徑進行規(guī)劃，使得傳統人工算法中易陷入局部最小、局部路徑震蕩的問題得到了解決，但是無法避免人工勢場法對復雜地形環(huán)境不適用性。

因此，針對目前研究中存在的收斂速度慢和全局尋優(yōu)效果差的問題，本文提出了一種基于改進蟻群算法的無人機自主航路規(guī)劃方法。首先通過調整對初始信息素濃度的分配，來減少算法初期的無效搜索；而后提出利用人工魚群算法的視場機制與傳統蟻群算法相結合，改變傳統蟻群算法中僅依靠概率來選擇搜索方向的方式，并通過在路徑上添加“天敵”，使螞蟻跳出局部最優(yōu)的陷阱；利用Logistic混動擾動模型改進全局信息素搜索能力；再結合A算法改進傳統蟻群算法的啟發(fā)式函數，提升算法的搜索效率。最后，通過仿真實驗驗證算法的可行性。

2 路徑規(guī)劃地圖建模

當無人機在執(zhí)行任務時，為了簡化模型，可將其視為在一定高度上的二維平面中的運動，因此可以運用柵格模型對飛行空域進行構造。柵格法即離散化處理，有著易于實用，便于工程化落地的優(yōu)點。由于柵格法簡單有效，能夠適應較多的威脅模型，能夠大大降低環(huán)境建模的難度。因此，本文采用柵格法對無人機的飛行環(huán)境進行簡單仿真。將威脅存在范圍內的柵格視作不可行柵格，在仿真程序中用1表示；威脅沒有覆蓋的柵格視作自由柵格，在仿真程序中用0表示。為了進一步簡化計算，對威脅覆蓋范圍進行膨化，即將覆蓋區(qū)域未滿一個柵格的單元，將面積充滿。同時，采用序號法和二維直角坐標系對應來對柵格進行標示。如圖1所示，以10×10的柵格環(huán)境為例進行說明。

圖1 柵格坐標與標號關系圖Fig.1 Grid coordinate and label relationship

如圖1所示，空白柵格表示自由柵格，藍色柵格表示威脅覆蓋的不可行柵格。地圖按照從左至右的順序對柵格進行編碼，依次為1,2,3,…，一個編碼對應一個柵格，坐標與柵格的標號關系如式(1)所示：

(1)

式(1)中:為取余函數，為向后取整函數，為柵格編號，為每一列柵格的數量，由式(1)所求即為柵格中心點的位置坐標。

通過柵格模型的構建，無人機執(zhí)行任務進行的航跡規(guī)劃轉化為已知起始點E和目標點S，利用相關算法在自由柵格的集合中尋找有序排列的問題，而這些有序柵格的中心點坐標的連線段構成了無人機飛行的航跡。

3 蟻群算法的基本原理

3.1 基本原理

在自然界中，螞蟻在覓食的過程中總是能找到食物源和蟻巢之間的最短路徑，受到螞蟻這種行為的啟發(fā)，意大利學者M.Dorigo等首先提出了一種隨機搜索模擬進化算法——基本蟻群算法。它模擬了螞蟻在覓食和返回蟻巢途中“探索”的行為，即螞蟻將使用感知到之前螞蟻釋放并遺留在途中的信息素，按照一定的概率選擇接下來的路徑并釋放信息素。在這條路徑中的信息素將會影響之后的螞蟻。隨著每條路徑上的信息素積累、釋放和揮發(fā)，引導著一個個螞蟻進行路徑的選擇，而螞蟻也總是趨向于選擇信息素含量高的路徑，久而久之，在螞蟻覓食和返巢的路徑中將出現一條最短的路徑。

而意大利學者M.Dorigo正是利用這一行為特征，將其抽象形成了隨機搜索模擬進化算法。假設在出發(fā)點和目標點之前存在若干干擾因素，在算法伊始，將只螞蟻隨機的放到個地點，并為相關的路徑賦予信息素初值(0)=，每只螞蟻將按照信息素含量和啟發(fā)式信息獨立的選擇接下來的目標。在時刻，第只螞蟻位于節(jié)點，它將以輪盤賭模型的方式選擇下一目標節(jié)點，其狀態(tài)轉移概率為

其中:allowed為螞蟻可以在下一步選擇的節(jié)點集合；為路徑(,)的信息素值；為信息素激勵因子，它反映了信息素濃度對路徑選擇的重要性，的大小與重要性成正比；是預期的啟發(fā)因子，它反映了啟發(fā)式信息在路徑上的重要性。越大則螞蟻越傾向于選擇最短路徑；()為啟發(fā)式值，表示螞蟻從節(jié)點轉移到目標節(jié)點的期望程度，如下式所示：

其中表示從節(jié)點到節(jié)點的歐氏距離。同時，每個螞蟻在選擇的路徑行進的過程中也會釋放出信息素，從而形成信息素的累計，為了防止信息素過多，導致啟發(fā)信息泛濫，進而導致算法快速結束或者陷入局部最優(yōu)。因此，在每個螞蟻完成一次循環(huán)后，選擇對信息素進行更新，更新公式如下所示：

(+1)=(1-)()+Δ

()

其中：為信息素的揮發(fā)系數，1-為信息素殘留因子，Δ()為循環(huán)路徑中的信息素增量，其計算方式如下：

其中：為螞蟻在本次循環(huán)路徑中路線的總長度，為循環(huán)一周的信息素總量。

在自然界中，魚往往能夠自行或者尾隨其他魚找到營養(yǎng)物質多的地方，人工魚群算法(artificial fish swarms algorithm，AFSA)正是利用這一現象，創(chuàng)造了這一尋優(yōu)算法。在人工魚中封裝了自身數據和一系列行為，它能夠受到環(huán)境的刺激而做出反應。并且它是通過視覺來實現對外界的感知，在人工魚群模型中：

=+*()

的方式實現虛擬視覺的模擬。其中()為隨機函數，用來產生0～1之間的隨機數，為步長。主要模擬了魚類活動中覓食、群聚、追尾等行為，本文主要利用這3種行為中通過視覺探測進而選擇行動方向和躲避天敵這2種方式來對蟻群算法進行優(yōu)化。

3.2 改進蟻群算法

為了縮短基本蟻群算法搜索最優(yōu)路徑的時間，提高搜索路徑的質量并且避免蟻群算法出現陷入局部最優(yōu)的情況，本文對基本蟻群算法做出如下改進。

初始信息素的設定

基本蟻群算法在初始狀態(tài)下信息素呈現均勻分布的狀態(tài)，這就使得蟻群算法在搜索路徑伊始可能出現與目標點反向的搜索路徑，由此導致算法的搜索時間，迭代速度慢。為了解決算法在初期搜索的盲目性，縮短搜索時間，對路徑進行預規(guī)劃。首先，連接初始點E與目標點S，作為預規(guī)劃路徑，如圖2所示，但是由于不可行柵格的存在，最優(yōu)規(guī)劃路徑會在該直線附近波動，初始信息素濃度以預規(guī)劃路徑為中心向兩邊呈現出高斯分布，如圖3所示。

圖2 初始規(guī)劃路徑L0圖Fig.2 Initial planning path L0

圖3 初始信息素濃度分布示意圖Fig.3 Schematic diagram of initial pheromone concentration distribution

初始信息素矩陣為，依據Toeplitz規(guī)律，沿對角線向兩側呈現正態(tài)分布。公式如下：

其中:為調整系數，的取值范圍是[,+100]，為方差。由圖可知，全局最優(yōu)路徑往往是在起始點與目標點連線附近波動的，因此，信息素濃度的不均勻分配能夠減少螞蟻的盲目搜索，有利于縮短迭代時間。

融合人工魚群算法的搜索策略和信息素更新原則

1)搜索策略。當前蟻群算法及其優(yōu)化算法在選擇行動方向時僅僅取決于與當前位置相鄰點的信息素濃度，這種做法不利于螞蟻的快速覓食，同時降低了算法的收斂速度。

因此，結合人工魚群算法的視覺特性以及覓食方式，提出新的覓食選擇機制即視場搜索，該機制如圖4所示。

圖4 視場搜索機制示意圖Fig.4 Schematic diagram of the field of view search mechanism

如圖4所示，賦予每個螞蟻一定半徑的視場范圍，可以使得螞蟻在接下來的動作中沒有障礙的到達下一目標節(jié)點。在二維空間內，距離可以用歐式距離來衡量，即：

其中:為螞蟻現在所處的位置，為螞蟻下一時刻可以選擇的位置。在覓食階段，每只螞蟻在各自的視場范圍內探測是否存在食物或者同伴占據過的更好地位置，一但發(fā)現，將采取如下行為：

=+*()

其中:表示螞蟻的視場半徑，()表示產生(0,1)之間的隨機數。

2)局部優(yōu)化。為了解決蟻群算法具有陷入局部最優(yōu)解的缺點，在算法中設置迭代閾值，并賦予合適的范圍，當迭代次數未超過，而路徑長度卻沒有變化時，人工在螞蟻視場范圍內引入“天敵”。當天敵出現時，螞蟻的視場變大(選用原視場的2倍)，加速逃離原視場范圍，其數學模型如下：

≤(,)≤2

融合logistic混沌模型的全局信息素篩選

蟻群系統中，螞蟻對于行動路線的選擇在很大程度上是由路徑上信息素濃度大小決定的。它的迭代過程對于初始狀態(tài)較為敏感，初始信息素濃度的分布，直接影響了后續(xù)螞蟻行動路線的選擇。因此，蟻群系統可以被稱為混沌系統。

混沌是來自與非線性動力系統，通過確定性方程獲得運動狀態(tài)的運動過程稱為混沌，它是一種既普遍又復雜的現象。Logistic映射是簡單的一維混沌映射，其解析式如下：

+1=**(1-)

其中，=0,1,2,…，∈[0,4]稱為Logistic參數，{X|i=0,1,2,…}為初始X∈[0,1]時產生的序列。圖5給出了不同初值和logistic參數條件的映射序列。

圖5 Logistic映射分叉圖Fig.5 Logistic map bifurcation graph

在經典蟻群算法中，當所有螞蟻走完以后算法會把所有路徑上的信息素進行更新，但是有些路徑過長，會成為系統中的干擾因素，造成螞蟻的無效搜索，因此要對路徑上的信息素進行有選擇的更新。

當螞蟻完成一次覓食后將這次路徑記錄下來，而后將所有螞蟻完成得路徑按照長度從小到大進行排序，并求出其平均值。對于小于平均值的路徑上的信息素進行直接更新；大于平均值的路徑進行處理后更新其路徑上的信息素。

假設是大于平均路徑長度的路徑個數，在中任意一條路徑上的信息素濃度是，=1,2,3，…，，那么定義混沌變量：

代入Logistic混沌模型的迭代公式中：

+1=**(1-)，=0,1,2,…，

其中:和是條路徑中信息素濃度的最大值和最小值，是混沌迭代次數。得到混沌序列：

=(,,,…,)

那么得到新的信息素為

,new=+(-)

因此，結合Logistic混沌模型后蟻群算法的全局信息素更新方式為

啟發(fā)函數融合A算法

A算法是一種啟發(fā)式遍歷算法，它的估價函數構造為：初始狀態(tài)到狀態(tài)的實際代價與狀態(tài)到目標狀態(tài)的預估代價之和，數學表達式為

()=()+()

其中:()為從初始狀態(tài)到目標狀態(tài)的總代價；()為初始狀態(tài)到狀態(tài)的真實代價；()為狀態(tài)到目標狀態(tài)的預估代價。

經典蟻群算法的啟發(fā)式函數中只考慮了當前節(jié)點到下一節(jié)點的路徑作為真實代價，只考慮了局部求解，不利于在全局中尋找最優(yōu)解。因此，在經典蟻群算法中引入A算法的估價函數，對蟻群算法的啟發(fā)式函數進行改進。將當前節(jié)點與下一節(jié)點的距離代價作為真實代價以及下一節(jié)點與目標節(jié)點的距離作為預估代價，這二者之和構成了A算法的估價函數。以這一函數代替蟻群算法的啟發(fā)式函數，同時引入平衡因子，得到改進啟發(fā)式函數如下：

其中:為當前節(jié)點到下一節(jié)點的距離，為下一節(jié)點到目標節(jié)點的距離。通過這種改進方式，增強了蟻群算法的搜索效率，提高了全局尋優(yōu)能力，有效避免陷入局部最優(yōu)。

改進算法流程如圖6所示。

圖6 改進蟻群算法流程框圖Fig.6 Improved ant colony algorithm flow chart

4 實驗數據分析

為了驗證算法的性能，以及相關參數對算法性能的影響，在二維柵格地圖模型上進行仿真驗證。因此，將整體實驗分為2個部分，實驗1通過固定地圖規(guī)模，調整參數的方式，進行對照實驗來驗證相關參數對算法性能的影響；實驗2通過改變地圖大小，分別采用不同的障礙物覆蓋率以及不同的障礙物形狀模擬實際飛行中可能存在的威脅來構建地圖環(huán)境。利用Matlab軟件進行仿真實驗的操作，通過實驗對比，分析路徑的優(yōu)劣，以此來判斷算法的性能。

實驗1：不同實驗參數對算法性能影響。

將本文改進的算法在20×20的柵格地圖模型中進行實驗，通過調整、和的取值來驗證不同參數對算法性能的影響，實驗結果如圖7所示。

圖7 不同參數對改進算法性能的影響曲線Fig.7 The influence of different parameters on the performance of the improved algorithm

由實驗1結果可知：改變算法的、和的取值對實驗的結果有較大影響，因此在考慮算法收斂速度和仿生學實際情況的基礎上，對算法參數的取值進行選擇，通過實驗結果選擇=1、=7、=04(雖然=08使得在該次實驗中算法的收斂速度以及精度都較高，但是從參數的實際意義考慮，取值過大，不利于算法在復雜環(huán)境下累積信息素，強化最優(yōu)路徑上信息素的迭代速率。

實驗2：不同地圖規(guī)模對算法性能影響對比。

將本文改進的算法與ACO算法分別在20×20，30×30，40×40的柵格地圖上進行對比實驗，并對實驗數據進行分析，檢驗算法性能。首先對算法的參數進行初始化設置，如表1所示。

表1 算法參數設置Table 1 Algorithm parameter settings

1)算法在20×20的柵格地圖上進行的實驗結果如圖8所示。

圖8 路徑規(guī)劃結果示意圖Fig.8 Comparison of path planning results on a 20×20 map

由此可見，ACO算法在進行路徑規(guī)劃的過程中，出現無法收斂到全局最優(yōu)解的情況。因為在面臨有復雜障礙出現時，ACO算法中的螞蟻會在復雜障礙中反復前進后退，而本文改進的蟻群算法，利用了視場機制、逃出機制。有效減少了算法的迭代次數，提高了收斂精度。實驗數據結果如表2所示。

表2 算法在 的柵格地圖上的運行結果Table 2 Comparison of the running results of the two algorithms on a 20×20 grid map

2)算法在30×30的柵格地圖上進行的實驗結果如圖9所示。

圖9 基本蟻群算法路徑規(guī)劃結果示意圖Fig.9 ACO algorithm path planning results

由實驗2可知：ACO算法在對進行路徑規(guī)劃的時，隨著環(huán)境規(guī)模的增大，復雜障礙的出現，會出現在規(guī)定的迭代次數完成后無法獲得穩(wěn)定的規(guī)劃路徑，仍然會存在陷入障礙中無法尋得路徑的情況；并且，在這種情況下，基本蟻群算法必須通過增大迭代的次數，使得算法收斂，從而找到最優(yōu)路徑。因此對基本蟻群算法做出改進，得實驗結果如圖10和表3所示。

圖10 在30×30地圖上的路徑規(guī)劃結果示意圖Fig.10 Comparison of path planning results on a 30×30 map

表3 算法在30×30的柵格地圖上的運行結果Table 3 Comparison of the running results of the two algorithms on a 30×30 grid map

3)算法在40×40的柵格地圖上進行的實驗結果如圖11所示。由于地圖規(guī)模的擴大，搜索路徑的難度增大，為了更好地進行路徑規(guī)劃，獲得更加準確的結果，對迭代次數和螞蟻數量進行調整，參數調整如表4所示。

表4 算法在40×40的柵格地圖上的算法參數設置Table 4 Algorithm parameter settings on 40×40 grid map

圖11 在40×40地圖上的路徑規(guī)劃結果對比Fig.11 Comparison of path planning results on a 40×40 map

由實驗3可知，隨著實驗地圖規(guī)模的擴大，ACO算法在規(guī)定的迭代次數內無法搜索到最優(yōu)規(guī)劃路徑，暴露出ACO算法迭代收斂速度慢，在復雜環(huán)境下尋優(yōu)能力弱的現象；而本文由于引入了視場機制、逃逸策略、并且優(yōu)化了信息素的更新方式，搜索到全局最優(yōu)解，優(yōu)化了ACO算法的搜索能力。實驗數據結果如表5所示。

表5 算法在40×40的柵格地圖上的運行結果Table 5 Comparison of the running results of the two algorithms on a 40×40 grid map

5 結論

算法利用Toeplitz規(guī)律，使初始信息素沿著初始點與目標點的連線上呈現正態(tài)分布，有效的降低了螞蟻盲目搜索的概率；利用Logistic混沌模型優(yōu)化全局信息素更新方式；再引入視場機制和逃出策略，并改變啟發(fā)式函數，解決了螞蟻在搜索路徑過程中陷入局部最優(yōu)、甚至死解的情況，并通過Matlab進行仿真驗證。結果表明：相比于ACO的航路規(guī)劃，采用本文的改進算法能夠有效的提高收斂速度和精度，并且能夠解決在復雜地形環(huán)境中陷入局部最優(yōu)的情況，對無人機自主航跡規(guī)劃具有應用價值。

如何對算法進行進一步優(yōu)化，縮短算法的運行時間以及如何將其應用到動態(tài)障礙規(guī)避中，是下一步需要研究的內容。