基于灰狼優(yōu)化算法的軍用運(yùn)輸機(jī)航路規(guī)劃方法

魏燕明，甘旭升，劉 飛，孫靜娟

（1.西京學(xué)院，西安 710123；2.空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051）

0 引言

軍用運(yùn)輸機(jī)擔(dān)負(fù)著重要的運(yùn)輸任務(wù)，在軍事行動中的地位舉足輕重。而運(yùn)輸機(jī)的航路規(guī)劃是指在綜合考慮各種因素影響的前提下，從航圖中規(guī)劃出起飛和降落機(jī)場間的最短航路。在大量航路中，選擇科學(xué)的規(guī)劃方法，尋找起點(diǎn)到終點(diǎn)的最短航路，是一個復(fù)雜的過程，故可將運(yùn)輸機(jī)航路規(guī)劃問題歸結(jié)為最短路徑問題。

現(xiàn)有航路規(guī)劃方法通?？蓺w納為3 類：一是傳統(tǒng)方法，例如Voronoi 圖法［1］、柵格法［2］等；二是智能優(yōu)化算法，例如遺傳算法［3］、粒子群優(yōu)化算法［4］等；三是其他算法，例如動態(tài)規(guī)劃算法［5］等。傳統(tǒng)算法對障礙物的要求較為理想化，實(shí)際地形對規(guī)劃出的結(jié)果影響很大。智能優(yōu)化算法的特點(diǎn)是不受函數(shù)求導(dǎo)的限制，在全局搜索和穩(wěn)定性方面具有優(yōu)勢，但也存在效率低、速度慢、無法適用動態(tài)地圖的缺點(diǎn)。其他算法，如動態(tài)規(guī)劃算法，在局部路徑上可以達(dá)到最優(yōu)值，也適用于動態(tài)地圖，但是無法確保全局最優(yōu)。相比較而言，灰狼優(yōu)化（Grey Wolf Optimization，GWO）算法［6］能在迭代中通過不斷調(diào)整收斂因子，實(shí)現(xiàn)種群的局部尋優(yōu)和全局尋優(yōu)，并通過多個基準(zhǔn)測試函數(shù)進(jìn)行測試，從結(jié)果上驗證了該算法的可行性，并在對基準(zhǔn)測試函數(shù)的求解精度和穩(wěn)定性上優(yōu)于遺傳算法、粒子群優(yōu)化算法與差分優(yōu)化算法等。因此，GWO 算法在最優(yōu)無功電力調(diào)度、表面波數(shù)優(yōu)化、多輸入多輸出系統(tǒng)優(yōu)化、直流電機(jī)最優(yōu)控制、無人機(jī)航路規(guī)劃等工程問題上得到了廣泛應(yīng)用。

鑒于最短路徑問題是圖論中的經(jīng)典問題，本文提出基于圖論知識構(gòu)建航空網(wǎng)絡(luò)，并在此基礎(chǔ)上提出了基于一種非線性調(diào)節(jié)參數(shù)的GWO 算法的航路規(guī)劃方法。

1 基于圖論的航空網(wǎng)絡(luò)模型

航空網(wǎng)絡(luò)主要有3 種典型網(wǎng)絡(luò)結(jié)構(gòu)［7］：1）點(diǎn)對點(diǎn)結(jié)構(gòu)。該結(jié)構(gòu)容易設(shè)置，但存在航線資源閑置問題。2）線型跳躍結(jié)構(gòu)。該結(jié)構(gòu)的飛機(jī)利用率明顯提高，其存在飛機(jī)頻率低、飛機(jī)時刻難以安排、規(guī)模小等問題。3）軸輻式結(jié)構(gòu)。該結(jié)構(gòu)是指選擇流量大、經(jīng)濟(jì)發(fā)達(dá)的城市作為樞紐機(jī)場，與其他大中型城市之間設(shè)置航空干線，大中型城市與其附近中小型城市之間設(shè)置航空支線形成的航空網(wǎng)絡(luò)模型。當(dāng)前的航空網(wǎng)絡(luò)往往是樞紐輻射結(jié)構(gòu)的混合型網(wǎng)絡(luò)。

考慮到航空網(wǎng)絡(luò)空間結(jié)構(gòu)整體顯現(xiàn)規(guī)則網(wǎng)絡(luò)特征、局部顯現(xiàn)不規(guī)則特征及核心邊緣結(jié)構(gòu)的特點(diǎn)，本文采用圖論的相關(guān)知識，對特定區(qū)域航空網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行描述。由此，建立基于圖論的航空網(wǎng)絡(luò)模型共分為以下3 個步驟［8］：

1）網(wǎng)絡(luò)節(jié)點(diǎn)的確定。在構(gòu)建航空網(wǎng)絡(luò)模型時，通常把機(jī)場作為網(wǎng)絡(luò)節(jié)點(diǎn)。2）確定邊權(quán)。將兩機(jī)場之間的距離作為邊權(quán)。3）建立鄰接矩陣，繪制航空網(wǎng)絡(luò)模型圖。

2 運(yùn)輸機(jī)的航路規(guī)劃問題

軍用運(yùn)輸機(jī)的航路規(guī)劃就是在一定條件下最短路徑的求解問題，主要有Dijkstra 算法［9］和Floyd算法［10］等，這兩種算法是當(dāng)前較為成熟的求解最短路徑的方法，但是這兩種算法求解速度較慢，歷時較長，并不適合軍用運(yùn)輸機(jī)的航路規(guī)劃問題，因此，本文試圖探索一種更快求解軍用運(yùn)輸機(jī)航路規(guī)劃問題的方法。

2.1 目標(biāo)函數(shù)

通常情況下，軍用運(yùn)輸機(jī)的航路規(guī)劃問題主要考慮以下3 個因素：

1）距離。對于航路規(guī)劃問題，距離因素最重要。從航空網(wǎng)絡(luò)模型可以看出每個航線點(diǎn)之間的距離，沒有航線的航線點(diǎn)之間用0 表示。由于距離的數(shù)值較大，如果使用這一數(shù)值，其他約束條件的影響將會微乎其微，所以要對所有參數(shù)進(jìn)行統(tǒng)一。在真實(shí)數(shù)據(jù)的基礎(chǔ)上，將距離的數(shù)值限定在（0，1］之內(nèi)，故其表達(dá)式為

式中，S 為距離約束條件，s 為兩航線點(diǎn)間的真實(shí)距離，max 為航線點(diǎn)間的最大距離。

2）天氣。由于天氣因素對飛行有較大影響，在解決航路規(guī)劃問題時一定要考慮天氣因素。天氣較為復(fù)雜，本文將天氣分為：對飛行沒有影響（記為0）、對飛行影響較?。ㄓ洖?.2）、對飛行影響適中（記為0.5）、對飛行影響較大（記為0.8）、對飛行影響很大（記為1）。在求解過程中，上述5 種情況隨機(jī)產(chǎn)生，記為t。當(dāng)t=1 時，天氣對飛行器飛行的影響很大，為避免天氣因素影響飛行，在規(guī)劃航路時，就不能經(jīng)過這一導(dǎo)航點(diǎn)。

3）飛行器密度。航線上能承載的飛行器數(shù)量是有限的，當(dāng)航線上飛行器過多時，可能導(dǎo)致飛行器間的距離過近，引發(fā)飛行事故。所以，在解決航路規(guī)劃問題時，一定要考慮航線上的飛行器密度ρ=x/N，其中，x 為航線上已有飛行器數(shù)量，N 為航線承載飛行器上限。當(dāng)ρ=1 時，航線上飛行器密度對飛行影響很大，易引起相撞，為防止相撞，規(guī)劃航路時，就不能經(jīng)過該導(dǎo)航點(diǎn)。

根據(jù)不同因素對航路規(guī)劃的不同影響程度，對考慮的不同因素進(jìn)行加權(quán)，當(dāng)ti≠1 且ρi≠1 時

根據(jù)以上表達(dá)式，對GWO 算法求解航路規(guī)劃問題的權(quán)值進(jìn)行重新規(guī)劃；當(dāng)ti=1 或ρi=1時，這一導(dǎo)航點(diǎn)不能使用。

2.2 約束條件

在運(yùn)輸機(jī)的航路規(guī)劃過程中，存在限制整個規(guī)劃的約束條件［11］。具體包括：

1）油耗。運(yùn)輸飛機(jī)載物時由于其最大起飛重量的限制、跑道承重限制以及最低空載重量的限制，燃油的攜帶量都是經(jīng)過精準(zhǔn)計算。要根據(jù)具體油量來規(guī)劃合理的飛行距離；

2）任務(wù)時間要求。運(yùn)輸飛機(jī)必須在規(guī)定時間內(nèi)完成運(yùn)輸和支援任務(wù)；

3）航路距離。飛行的航路距離必須少于同等負(fù)重條件下的運(yùn)輸飛機(jī)的最大飛行距離，受到燃油限制和飛行時間限制；

4）途經(jīng)點(diǎn)。在執(zhí)行飛行任務(wù)時必須飛過的一些航路點(diǎn)。

出于簡化問題需要，本文沒有考慮禁飛點(diǎn)、地形的限制以及飛機(jī)自身性能的限制。

3 灰狼優(yōu)化算法

根據(jù)前面對軍用運(yùn)輸機(jī)航路規(guī)劃問題的分析，可知該問題是一類多約束、非線性復(fù)合最優(yōu)化問題，其難點(diǎn)在于對約束條件的處理，尤其是對任務(wù)約束的處理，而GWO 算法由于采取領(lǐng)導(dǎo)層級機(jī)制，在處理約束條件時，不與適應(yīng)度函數(shù)直接關(guān)聯(lián)，能夠有效解決多約束問題，并且不影響算法的尋優(yōu)性能［12-13］。雖然GWO 算法得到了廣泛的應(yīng)用，但也存在收斂速度不高、全局搜索能力弱、易陷入局部最優(yōu)的缺點(diǎn)，據(jù)此，本文針對所建模型的具體特點(diǎn)，引入一種非線性調(diào)節(jié)參數(shù)增強(qiáng)其全局搜索性能和精度。

3.1 標(biāo)準(zhǔn)算法

灰狼處于自然界中食物鏈的頂端，喜歡群居生活，并且具有嚴(yán)格的社會等級制度，將群體劃分為4個等級，呈金字塔結(jié)構(gòu)，處于頂端的為領(lǐng)導(dǎo)層，稱為Alpha（α）狼，它是整個灰狼群體的核心，對捕食、休整等問題擁有決策權(quán)；第二級為Beta（β）狼，主要輔助Alpha（α）狼作決策，并負(fù)責(zé)向下加強(qiáng)貫徹該決策；第三級為Delta（δ）狼，負(fù)責(zé)貫徹執(zhí)行Alpha（α）狼與Beta（β）狼的決定，并且擔(dān)負(fù)警衛(wèi)、照顧受傷灰狼和幼小灰狼的任務(wù)；處于底層的為Omega（ω）狼，主要跟隨前3 個層級的狼捕食和休整。具體捕食時，灰狼群體在Alpha（α）狼的帶領(lǐng)下，搜尋獵物并逐漸接近，待確定獵物具體位置后，形成包圍圈并逐漸縮小，最后實(shí)施攻擊。

為了模擬灰狼的捕食機(jī)制，以解決問題的優(yōu)劣程度來模擬劃分灰狼的社會等級，最佳解決方案視為α 狼，第2 和第3 最佳解決方案分別命名為β 狼和δ 狼，其他解決方案均被假定為ω 狼。

在GWO 算法中，設(shè)定灰狼包圍獵物時，灰狼與獵物之間的距離為

3.2 改進(jìn)策略

由前述可知，基于航空網(wǎng)絡(luò)的航路規(guī)劃能否滿足約束條件，直接關(guān)系到任務(wù)的成敗，目前對約束處理的方法主要有特殊算子法［14］、隨機(jī)排序法［15］、可行性準(zhǔn)則［16］和懲罰函數(shù)。而懲罰函數(shù)的方法簡單、復(fù)雜度低，適用于多種優(yōu)化問題，故采用懲罰函數(shù)來處理模型中約束。當(dāng)滿足約束條件時，則懲罰因子為0，否則令其為負(fù)無窮。

3.3 算法優(yōu)化流程

在航空網(wǎng)絡(luò)基礎(chǔ)上實(shí)現(xiàn)軍用運(yùn)輸機(jī)的航路規(guī)劃，采用改進(jìn)灰狼算法優(yōu)化計算步驟如下：

1）明確目標(biāo)，對航空網(wǎng)絡(luò)內(nèi)的飛行路徑進(jìn)行編碼；

2）設(shè)定種群數(shù)目N、最大迭代次數(shù)tmax、維數(shù)以及上下界；

3）初始化種群、根據(jù)適應(yīng)度函數(shù)及約束條件，找到最優(yōu)的前3 個計算備選解，令t=1；

5）按照式（8）～式（10）與式（14），更新各個灰狼個體的位置；

6）令t=t+1；

7）適應(yīng)度函數(shù)計算每個灰狼個體的適應(yīng)度值，保存最優(yōu)的前3 個計算備選解，判斷是否達(dá)到最大迭代次數(shù)，若是，則算法結(jié)束，輸出最佳飛行路徑，否則返回第4 步；

8）輸出所規(guī)劃的航路。

4 仿真分析

4.1 人造網(wǎng)絡(luò)的航路規(guī)劃

首先，使用較為簡單的人造網(wǎng)絡(luò)對算法進(jìn)行驗證，如圖1 所示。改進(jìn)GWO 算法的參數(shù)設(shè)置：初始種群個數(shù)為50，最大迭代次數(shù)為50，c1=1，在Matlab2014a 上運(yùn)行50 次。

圖1 人造網(wǎng)絡(luò)

該人造網(wǎng)絡(luò)有15 個節(jié)點(diǎn)，27 條連邊，每條連邊長度如上圖。該人造網(wǎng)絡(luò)的帶權(quán)鄰接矩陣為

通過GWO 算法求解人造網(wǎng)絡(luò)中節(jié)點(diǎn)1-節(jié)點(diǎn)11 的最短路徑，結(jié)果如下頁圖2 所示?？梢钥闯?，用GWO 算法求解最短路徑，結(jié)果收斂很快，當(dāng)?shù)降?1 代時，結(jié)果穩(wěn)定，不再變化，最短路徑長度為6。僅考慮權(quán)值，得到仿真結(jié)果如表1 所示。

圖2 GWO 算法求解結(jié)果

表1 求解結(jié)果對比

當(dāng)使用GWO 算法求解從1-11 的最短路徑時，首先得到的是距離18，路徑為1-3-6-10-9-12-8-11，繼續(xù)迭代得到距離為14，路徑為1-5-14-12-8-11，繼續(xù)迭代得到距離為10，路徑為1-5-14-11，繼續(xù)迭代得到距離為6，路徑為1-5-8-11，繼續(xù)迭代結(jié)果不變表明，1-11 最短路徑為1-5-8-11，距離為6。

不難看出，通過GWO 算法求解最短路徑得出的答案和Floyd 算法、Dijkstra 算法求解得到的答案是一致的，利用其求解航路規(guī)劃問題是可行的。

4.2 北京地區(qū)航空網(wǎng)絡(luò)的航路規(guī)劃

通過人造網(wǎng)絡(luò)的求解已經(jīng)得到了GWO 算法求解最短路徑的可行性及可靠性，下面在以北京為樞紐的航空網(wǎng)絡(luò)模型229 個節(jié)點(diǎn)的基礎(chǔ)上，使用GWO算法，求解以北京為起點(diǎn)的某兩個網(wǎng)絡(luò)節(jié)點(diǎn)間的最短距離及最短路徑。表2 為截取的部分節(jié)點(diǎn)連通情況及節(jié)點(diǎn)間距離。

通常情況下，機(jī)場在短期內(nèi)不會增加或減少，數(shù)量比較穩(wěn)定，而飛機(jī)有可能取消、延遲，并不穩(wěn)定，并且導(dǎo)航臺是固定在地面上的，不能移動。出于闡述問題需要，先以10 個有通航關(guān)系的導(dǎo)航臺為網(wǎng)絡(luò)節(jié)點(diǎn)。這些導(dǎo)航臺分別為：大王莊VOR 量（VYK），DOGAR，LADIX， 天 津 NDB（CG），P75，KALBA，PAMDA，ANRAT，IKENU，衡水NDB（HG），并分別表示為節(jié)點(diǎn)a，b，c，d，e，f，g，h，i，j。然后以兩個節(jié)點(diǎn)之間的距離作為邊權(quán)，進(jìn)而得到如下的帶權(quán)鄰接矩陣

對于以北京為樞紐的航空網(wǎng)絡(luò)包含229 個節(jié)點(diǎn)，其帶權(quán)鄰接矩陣比較龐大，在此基礎(chǔ)上對軍用運(yùn)輸機(jī)進(jìn)行航路規(guī)劃，其求解過程如下頁圖3所示。

表2 以北京為樞紐的航空網(wǎng)絡(luò)節(jié)點(diǎn)

圖3 GWO 算法求解結(jié)果

從圖中可看出，用GWO 算法求解最短路徑，收斂很快，當(dāng)?shù)降?5 代左右時，結(jié)果基本穩(wěn)定，不再變化，這時節(jié)點(diǎn)連成的路徑，即為最短路徑，路徑長度即為最短距離。表3 為綜合考慮距離、天氣、航路上飛機(jī)密度等因素時，GWO 算法、Dijkstra 算法和Floyd 算法得到的結(jié)果的對比。

由表可以看出，在綜合考慮距離-天氣-航空器密度等因素后，由于天氣和飛行器密度的影響，有一些距離較近的導(dǎo)航點(diǎn)不能使用，需考慮其他導(dǎo)航點(diǎn)。以北京到南陽為例：紫石口（RENOB）導(dǎo)航點(diǎn)因天氣原因不能使用，Dijkstra 算法和Floyd 算法時，只考慮距離因素，沒有考慮其他因素，得到的航路距離較短，但還是無法使用。而用GWO 算法求得的距離，相較于Dijkstra 算法和Floyd 算法的求解距離略大，不過由于考慮因素相對全面，能更好地進(jìn)行航路規(guī)劃供軍用運(yùn)輸機(jī)使用。

表3 求解結(jié)果對比

5 結(jié)論

現(xiàn)代戰(zhàn)爭對軍用運(yùn)輸機(jī)的航路規(guī)劃的要求越來越高。本文在航空網(wǎng)絡(luò)基礎(chǔ)上，采用GWO 算法對航路規(guī)劃進(jìn)行了研究。主要得出如下結(jié)論：

1）基于圖論相關(guān)知識構(gòu)建了航空網(wǎng)絡(luò)模型，收集相關(guān)數(shù)據(jù)，為后續(xù)的建模求解做鋪墊。2）在已構(gòu)建航空網(wǎng)絡(luò)基礎(chǔ)上，提出基于GWO 算法的軍用運(yùn)輸機(jī)航路規(guī)劃方法。結(jié)果表明GWO 算法用于軍用運(yùn)輸機(jī)航路規(guī)劃問題是可行的，能夠很好地完成軍航航路規(guī)劃的求解。3）采用本文方法對北京地區(qū)航空網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑求解，并與Dijkstra 算法和Floyd 算法進(jìn)行比較，驗證了方法的實(shí)用性和有效性。4）在未來的研究中，可考慮更多的對軍用運(yùn)輸機(jī)飛行有影響的因素，重新建立目標(biāo)函數(shù)，以科學(xué)、合理地進(jìn)行航路規(guī)劃。