支持強(qiáng)化學(xué)習(xí)RNSGA-II算法在航跡規(guī)劃中應(yīng)用

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

1.長安大學(xué) 工程機(jī)械學(xué)院，西安710064

2.長安大學(xué) 理學(xué)院，西安710064

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

1 引言

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

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

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

2.1 規(guī)劃空間

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

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

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

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

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

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

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

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

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

3 支持強(qiáng)化學(xué)習(xí)RNSGA-II算法在航跡規(guī)劃中的應(yīng)用

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

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

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

離散度φ的定義如下：

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

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

δ為n-1個解的方差：

3.2 強(qiáng)化學(xué)習(xí)模型及組成元素

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

（1）狀態(tài)

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

（2）動作

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

（3）獎賞

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

表1 強(qiáng)化學(xué)習(xí)狀態(tài)集合

3.3 支持強(qiáng)化學(xué)習(xí)NSGA-II算法應(yīng)用步驟

綜上所述，支持強(qiáng)化學(xué)習(xí)的RNSGA-II算法應(yīng)用步驟如下：

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

步驟2初始化種群1、種群2，采用三維坐標(biāo)編碼，控制坐標(biāo)的隨機(jī)性，使兩個種群的初始化結(jié)果具有多樣性。

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

（2）目標(biāo)空間的非支配前沿解集

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

圖2 種群Pareto前沿解分布

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

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

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

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

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

（4）算法對比結(jié)果分析

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

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

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

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

（5）多樣性分析

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

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

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

5 結(jié)束語

圖6 Q學(xué)習(xí)對種群2的影響

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