支持強化學習RNSGA-II算法在航跡規(guī)劃中應用

封 碩，鄭寶娟，陳文興，張婷宇

1.長安大學 工程機械學院，西安710064

2.長安大學 理學院，西安710064

3.武漢大學 數(shù)學與統(tǒng)計學院，武漢430072

1 引言

在戰(zhàn)場環(huán)境中要為無人機規(guī)劃出合理的路徑需要考慮多方面的因素，如無人機本身的性能、地形因素、威脅，隱蔽性等，使其能夠以更低風險和更廉價費用得到一個最優(yōu)的路徑，是一個NP完全問題，是無人機任務規(guī)劃系統(tǒng)研究的難點之一。遺傳算法作為智能優(yōu)化算法的一種，具有很好的魯棒性、并行性、全局收斂性優(yōu)點[1]。將遺傳算法應用于無人機路徑規(guī)劃目前已有大量研究成果：文獻[2]介紹了三種路徑規(guī)劃方法：貪婪啟發(fā)式、遺傳算法和多種群遺傳算法，證明了貪婪啟發(fā)式算法與遺傳算法相結合是解決無人機緊急著陸問題的有效策略。文獻[3]提出一種主從并行矢量評估遺傳算法（MSPVEGA）來解決航跡規(guī)劃問題。MSPVEGA利用先進的計算能力并行處理多個遺傳算法從而實現(xiàn)了無人機的自動化。然而，隨著工程的發(fā)展，解決多個優(yōu)化目標算法逐漸引起了學者的關注。傳統(tǒng)的多目標優(yōu)化算法利用權重線性組合目標函數(shù)，其中，權重的確定往往依賴于經(jīng)驗，往往不能很好地解決優(yōu)化問題。針對多目標的遺傳算法，文獻[4]改進了非支配排序遺傳算法（NSGA），提出了復雜度更低，更能保持種群多樣性，具有Pareto占優(yōu)的NSGA-II算法，已被越來越廣泛地應用于解決多目標優(yōu)化問題[5-9]，文獻[10]將NSGA-II算法成功應用于無人機航跡規(guī)劃，但是算法雖然設置了擁擠距離保持解之間的距離，然而當解陷入局部最優(yōu)時還是很難跳出。為解決這個缺陷，文獻[11]提出了一種雙種群遺傳粒子群算法，設置兩個不同種群，每隔一定代數(shù)在兩個種群之間進行精英的遷徙，驗證了該算法比單一種群得到的解更具有分布性和多樣性，然而種群之間遷徙參數(shù)是人為確定，不能很好地逼近最優(yōu)解。文獻[12]首次提出用強化學習來優(yōu)化種群之間的遷徙參數(shù)，但是算法是基于單目標優(yōu)化問題設計強化學習三要素，對多目標問題暫未考慮。文獻[13]在文獻[12]的基礎上將種群劃分為三類子種群從而實現(xiàn)各自遷徙，能有效地解決算法的收斂速度和全局收斂的矛盾，但是算法優(yōu)化的目標函數(shù)只有一個且未應用驗證有效性。

為了有效解決以上算法在收斂精度和航跡規(guī)劃應用方面的不足，本文嘗試用NSGA-II算法來解決三維戰(zhàn)時環(huán)境下無人機路徑規(guī)劃問題。首先，建立兩個不同種群，每隔一定代數(shù)對兩個種群進行遷徙，避免單一種群解陷入局部最優(yōu)。遷徙參數(shù)利用強化學習動態(tài)確定，強化學習的目的是優(yōu)化種群多樣性，使種群能自主保持多樣性，從而加快算法收斂，提高收斂精度和速度。

2 無人機多目標路徑規(guī)劃模型

2.1 規(guī)劃空間

模型假設無人機處于山谷中，受到雷達的偵測，航跡規(guī)劃問題需要綜合考慮路徑長度、威脅性及隱蔽性等眾多因素作為優(yōu)化的目標函數(shù)。雷達所形成的威脅區(qū)用圓形環(huán)表示[14]，其中內(nèi)環(huán)區(qū)域為絕對威脅區(qū)，在本區(qū)域內(nèi)飛行處于絕對危險狀態(tài)，此時無人機絕對會被雷達偵測到，外環(huán)區(qū)域為最大威脅區(qū)，在此區(qū)域內(nèi)飛行處于有一定威脅狀態(tài)，此時無人機有被偵測到的可能性。確定無人機的飛行起始點和終點，航跡規(guī)劃結果就是包括起點和終點在內(nèi)的N個航跡點。本算法的任務是：確定出無人機航跡，包括起點和終點在內(nèi)的N個航跡點。

2.2 優(yōu)化目標及約束條件

航跡長度代價f1由以下優(yōu)化函數(shù)表示，其中l(wèi)i為路徑中第i段相鄰兩點移動的歐氏距離：

雷達的能量是隨著其傳播距離平方衰減的，假設無人機截面受到雷達的威脅后反射相同的能量，則航跡中的威脅值是航跡點到雷達中心的距離四次方：

式中，Thrj(i)為航跡點受到雷達的威脅[8]，j表示雷達的個數(shù)，j={1,2,…,M}

其中，d max j，d min j為第j個雷達的最大威脅半徑和絕對威脅半徑，θ為視線仰角，θmin為攻擊下界角，無人機飛行過程中的隱蔽性代價f3由航跡所處的高度決定：

無人機飛行過程中還收到基本的約束條件，這些約束條件包括：最大拐彎角ψmax，最大爬升角φmax或俯沖角φmin，安全飛行高度約束hsafe等。

綜上，考慮三維山谷情形下一個無人機飛行模型，最優(yōu)目標需要考慮三方面因素，使得航跡長度代價、總威脅值、隱蔽性代價達到最小，約束條件，通俗的講受約束于飛行安全距離、拐彎角在可操作范圍內(nèi)、爬升與俯沖可在正?？煽胤秶?，具體建立的優(yōu)化模型如下：

約束條件中，zh為第i個航跡點所在位置的地形高度，ψi，φi為航路點的水平轉彎角和爬升角。

3 支持強化學習RNSGA-II算法在航跡規(guī)劃中的應用

在以上模型的基礎上運用支持強化學習RNSGA-II算法實現(xiàn)三維空間航跡規(guī)劃。RNSGA-II算法的基本思想如下：控制初始種群產(chǎn)生的隨機性，使用兩種隨機量產(chǎn)生兩個不同的初始種群，由于遺傳算法初期需要增加種群的多樣性避免解陷入早熟，所以在前50代設計遷徙規(guī)則讓兩個種群交換，具體遷徙為每隔一定代數(shù)令種群1的前m個精英群體與種群2隨機m個群體交換，交換后形成新的種群1和種群2，再分別運用NSGA-II算法各自獨立進化。把當前迭代過程中，選擇出來（或指定的）要進行交換的小群體個數(shù)占總群體個數(shù)的百分比定義為遷徙比例，然而不同的遷徙比例得到的效果不同，因此遷徙參數(shù)的設置對算法的效果起著非常重要的作用，由此引入了強化學習來自主確定遷徙比例，使算法自主保持種群多樣性的目的。

3.1 多目標優(yōu)化函數(shù)的多樣性衡量

傳統(tǒng)的多目標優(yōu)化問題大多轉化為單目標來衡量解的多樣性，所得到的多樣性值往往不夠精確，對多目標優(yōu)化函數(shù)解的多樣性的研究目前采用的辦法是評價具有Pareto性的前沿解的均勻離散分布程度，一般解分布得越均勻，說明得到解的多樣性效果越好，常用的多樣性衡量指標有[15]解間距度量、熵度量、網(wǎng)格度量、聚類度量、方差度量、離散度量等。本文采用離散度量的方法來衡量解的多樣性，結合強化學習動態(tài)確定遷徙參數(shù)。從而控制飛行路徑精度。

離散度φ的定義如下：

di表示的是解的歐式距離：

其中，|A|為具有Pareto性的前沿解的個數(shù)。

δ為n-1個解的方差：

3.2 強化學習模型及組成元素

強化學習是一個環(huán)境交互式學習方式，如果Agent與環(huán)境交互的過程中某個動作得到了正的獎賞，則Agent會在以后的交互中更加趨于這個動作。Agent通過不斷地與環(huán)境交互達到目的狀態(tài)，且獲得最優(yōu)策略使期望折扣和最大。強化學習時最關注的是最終的滿意的狀態(tài)，即獲得最優(yōu)策略時其期望總值達到最大。本文中Agent學習程度可以通過與環(huán)境交互調(diào)整遷徙參數(shù)m來控制，當交互到種群1和種群2的多樣性都比初始狀態(tài)好時，認為當前的遷徙參數(shù)設定合理。強化學習的過程又可以細分為三個重要因素，其設計過程如下。

（1）狀態(tài)

狀態(tài)St( )t=1,2,…,9為當前種群多樣性與初始種群多樣性的比值，具體定義及表示的意義如表1所示，其中φ10、φ20為初始種群1和種群2的初始多樣性值，φ1i、φ2i為種群1和種群2的第i代多樣性值。種群狀態(tài)的意義常分為：減少、不變、增加，2個種群有9種排列組合情況，結果如表1。

（2）動作

式中，m(t)為第t代種群的遷徙參數(shù)，dnanum為種群的數(shù)量，A為動作矩陣，對動作的設定有三種，保持參數(shù)m(t)不變，增加m(t)和減少m(t)。

（3）獎賞

本文對獎賞值的設置主要是為了搜索最好的遷徙參數(shù)m(t)、φi(t)和φi0(t)分別為第i個種群第t代的多樣性值和初始種群i的多樣性值。

表1 強化學習狀態(tài)集合

3.3 支持強化學習NSGA-II算法應用步驟

綜上所述，支持強化學習的RNSGA-II算法應用步驟如下：

步驟1初始化參數(shù)，設置算法相關參數(shù)：種群迭代次數(shù)t，種群規(guī)模dnanum，交叉概率Pc，變異概率Pm，輸入所規(guī)劃的三維空間，設置雷達所在的位置及作用半徑，設置規(guī)劃路線的起點和終點。

步驟2初始化種群1、種群2，采用三維坐標編碼，控制坐標的隨機性，使兩個種群的初始化結果具有多樣性。

步驟3對種群采用一點交叉，一點變異，產(chǎn)生新的種群記做子代Qt。

步驟4將種群Pt與子代種群Qt合并，新的種群記為Rt，對Rt種群進行非支配排序，擁擠度計算，產(chǎn)生新的種群Pt+1。

步驟5判斷當前代是否為“遷徙”代，若是則執(zhí)行步驟6，否則執(zhí)行步驟3。

步驟6將種群1的前m個優(yōu)勢子代與種群2的隨機m個子代交換，交換的“遷徙”參數(shù)m用強化學習方法產(chǎn)生。

步驟7判斷種群是否達到最大迭代次數(shù)，如果達到，迭代結束，否則轉步驟3。

4 仿真分析

基于上述算法設計，在Matlab上進行仿真實驗，以某山區(qū)DEM[16]作為算例的實驗環(huán)境，戰(zhàn)時環(huán)境為1 000 m×1 000 m×1 000 m，設置種群1和種群2的最大迭代次數(shù)為100代，種群規(guī)模為50個染色體，交叉概率為0.8，變異概率為0.2。無人機和雷達的參數(shù)如表2和表3所示。

表2 無人機參數(shù)信息

表3 雷達參數(shù)信息

（1）路徑規(guī)劃結果

圖1（a）為三類種群中具有Pareto前沿的航跡俯視圖，其中種群1和種群2是相互遷徙的種群，種群3是經(jīng)傳統(tǒng)NSGA-II算法作用的種群。圖1（b）為三類種群的三維路線點。從圖中可以看出，三類種群都能成功規(guī)劃出效果較好的路線，且都規(guī)避了絕對威脅半徑。

圖1（a）三種群航跡規(guī)劃俯視圖

圖1（b）三種群三維路線圖

（2）目標空間的非支配前沿解集

為了消除三個目標函數(shù)解的不同量綱的影響，對Pareto解集做了無量鋼化處理，即對每一個目標函數(shù)的解分量與其最優(yōu)值求比得到相對適應度。算法提取了非支配排序前10的非劣解，得到如圖2的Pareto前沿解集分布，從圖中可以看出種群1和種群2所得到Pareto的前沿解分布具有多樣性，且均勻分布在解集中。

圖2 種群Pareto前沿解分布

（3）目標函數(shù)收斂曲線比較

提取每次迭代過程中三個目標函數(shù)的最小值，得到各個目標函數(shù)的收斂曲線如圖3所示，可以看出在迭代的過程中，種群1和種群2所得到的最優(yōu)值比種群3結果更好，尤其是種群2所得到的結果最優(yōu)。支持強化學習RNSGA-II算法的能改善NSGA-II算法陷入局部早熟的缺點。

圖3（a）航跡隱蔽性收斂曲線比較

圖3（b）航跡威脅性收斂曲線比較

圖3（c）航跡長度收斂曲線比較

（4）算法對比結果分析

將經(jīng)典NSGA-II算法，文獻[16]提出的ENSGA-II算法，及本文提出的支持強化學習RNSGA-II算法所得到的結果進行對比分析，每種算法獨立執(zhí)行10次，將算法得到的最優(yōu)航跡的各個適應值函數(shù)規(guī)范化到區(qū)間[1，2]上，求規(guī)范化后的最大值、最小值、平均值，并將其作為評價算法性能指標，結果越小則算法取值越好。表4～6給出各個算法最優(yōu)適應度值的規(guī)范化統(tǒng)計。從表中可以看出，多次實驗RNSGA-II算法所得到的最小值最好，經(jīng)典NSGA-II算法和ENSGA-II算法都又陷入局部最優(yōu)，且RNSGA-II算法在多次實驗后得到的各個適應度平均值最小，性能最穩(wěn)定。

表4 NSGA-II所得最優(yōu)航跡各個適應度函數(shù)的規(guī)范化統(tǒng)計

表5 ENSGA-II所得最優(yōu)航跡各個適應度函數(shù)的規(guī)范化統(tǒng)計

表6 RNSGA-II所得最優(yōu)航跡各個適應度函數(shù)的規(guī)范化統(tǒng)計

（5）多樣性分析

圖4以遷徙代為6代為例，分析不同算法下種群的多樣性?？梢悦黠@看出種群1和種群2所得到的非劣解多樣性比種群3解的多樣性更好。設置不同的遷徙代，以種群2為例，比較不同遷徙代對種群多樣性的影響，從圖5中可以明顯看出，遷徙代為5代和6代所得到的種群多樣性效果較好。圖6以初始遷徙代為5代時Q學習對種群2多樣性的作用分析，可以看出加入Q學習后種群2的多樣性相對較好。

圖4 遷徙代為6代時種群多樣性比較

圖5 不同遷徙代種群2多樣性比較

5 結束語

圖6 Q學習對種群2的影響

本文針對NSGA-II算法容易陷入早熟，收斂速度慢等問題，提出了支持強化學習RNSGA-II算法并應用在了無人機路徑規(guī)劃問題中。實驗表明該算法提高了非支配解的多樣性和收斂性，得到的解比NSGA-II算法得到的解更精確，避免了早熟現(xiàn)象，通過與其他算法的對比RNSGA-II算法多次實驗得到的解依然最精確，且更穩(wěn)定。通過進一步分析，加入強化學習后得到的解的多樣性更好，且實驗得到最優(yōu)的遷徙代數(shù)是5代和6代。算法在提高多目標優(yōu)化問題解的多樣性和收斂性上效果顯著，能很快找到具有Pareto性的前沿解，且得到的解更精確，對優(yōu)化多目標無人機航跡規(guī)劃提供了一定的借鑒思路。