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

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

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

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

1 引言

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

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

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

2.1 規(guī)劃空間

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

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

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

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

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

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

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

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

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

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

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

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

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

離散度φ的定義如下：

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

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

δ為n-1個(gè)解的方差：

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

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

（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個(gè)種群有9種排列組合情況，結(jié)果如表1。

（2）動(dòng)作

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

（3）獎(jiǎng)賞

本文對(duì)獎(jiǎng)賞值的設(shè)置主要是為了搜索最好的遷徙參數(shù)m(t)、φi(t)和φi0(t)分別為第i個(gè)種群第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ī)劃路線(xiàn)的起點(diǎn)和終點(diǎn)。

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

圖1（b）三種群三維路線(xiàn)圖

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

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

圖2 種群Pareto前沿解分布

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

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

圖3（a）航跡隱蔽性收斂曲線(xiàn)比較

圖3（b）航跡威脅性收斂曲線(xiàn)比較

圖3（c）航跡長(zhǎng)度收斂曲線(xiàn)比較

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

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

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

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

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

（5）多樣性分析

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

圖4 遷徙代為6代時(shí)種群多樣性比較

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

5 結(jié)束語(yǔ)

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

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