郭拉克，李文生，韓帥濤

(中國(guó)洛陽(yáng)電子裝備試驗(yàn)中心，河南洛陽(yáng) 471000)

0 引言

無(wú)人機(jī)航路規(guī)劃是根據(jù)任務(wù)目標(biāo)，確定一條合理的最優(yōu)航路，該航路滿足無(wú)人機(jī)性能約束、任務(wù)要求和環(huán)境約束，并使無(wú)人機(jī)任務(wù)效能達(dá)到最優(yōu)?？尚泻铰返膬?yōu)劣評(píng)估受多項(xiàng)指標(biāo)因素的影響，傳統(tǒng)的思路是通過(guò)加權(quán)將多項(xiàng)指標(biāo)綜合成單指標(biāo)進(jìn)行處理，但該方法存在指標(biāo)間量綱不一致、過(guò)分依賴權(quán)重、主觀性強(qiáng)、優(yōu)度進(jìn)展不可控等固有缺陷。多目標(biāo)優(yōu)化 (向量?jī)?yōu)化)由于可以實(shí)現(xiàn)多個(gè)指標(biāo)的共同優(yōu)化，近年來(lái)受到學(xué)者們的廣泛關(guān)注，并產(chǎn)生了大量的研究成果，在多個(gè)領(lǐng)域得到了廣泛的應(yīng)用［1-5］。文獻(xiàn) ［6］提出了一種適用于多目標(biāo)優(yōu)化的非支配排序進(jìn)化算法NSGA，文獻(xiàn)［7］提出了其改進(jìn)算法NSGA－II，改進(jìn)了原來(lái)算法的不足之處，引入了精英策略，并提高了算法的運(yùn)算速度和魯棒性，同時(shí)保證了非劣最優(yōu)解的均勻分布。文獻(xiàn)［8］提出了一種新的排序和篩選策略，通過(guò)循環(huán)計(jì)算的刪除當(dāng)前擁擠距離最小的解，提高多目標(biāo)進(jìn)化的收斂性和多樣性。本文采用多目標(biāo)優(yōu)化思想，建立了無(wú)人機(jī)航路規(guī)劃的多目標(biāo)優(yōu)化模型，并給出了基于NSGA－Ⅱ的模型求解方法，為無(wú)人機(jī)航路規(guī)劃研究提供了新的思路和方法。

1 多目標(biāo)優(yōu)化問題模型

多目標(biāo)優(yōu)化問題，一般可以定義為在一定約束條件下，對(duì)多個(gè)目標(biāo)函數(shù)共同進(jìn)行優(yōu)化的最優(yōu)問題。當(dāng)效能受多個(gè)目標(biāo)影響時(shí)，多個(gè)目標(biāo)之間往往會(huì)出現(xiàn)沖突，即不存在使所有目標(biāo)同時(shí)達(dá)到最優(yōu)的解。一個(gè)目標(biāo)性能的改善，往往以降低其他一個(gè)或多個(gè)目標(biāo)性能為代價(jià)。以最小化問題為例，可以描述為如下標(biāo)準(zhǔn)形式［4］:

其中:fi(x)為目標(biāo)函數(shù);x為待優(yōu)化的決策變量;gi(x)≤0為變量x的線性不等式約束。滿足約束條件的決策變量稱為可行解或可行個(gè)體，所有可能的可行解的集合稱為決策空間，決策空間中所有可行解的像 (目標(biāo)函數(shù)向量)的集合稱為目標(biāo)空間。

定義1:如果可行個(gè)體p至少有一個(gè)目標(biāo)函數(shù)比可行個(gè)體q的好，而且個(gè)體p的所有目標(biāo)都不比個(gè)體q的差，即:

那么稱個(gè)體p支配個(gè)體 q，或者稱個(gè)體 q受個(gè)體 p支配，記為p＜q，反之記為p>q。

定義2:當(dāng)前決策集中，對(duì)于某個(gè)可行個(gè)體 p，如果不存在可行個(gè)體q，使得p>q，則稱可行個(gè)體p為多目標(biāo)優(yōu)化問題的非支配解或非劣解，又稱為Pareto最優(yōu)解。當(dāng)前決策集中的所有Pareto最優(yōu)解構(gòu)成Pareto前端，簡(jiǎn)稱前端。

定義3:如果某個(gè)可行個(gè)體在整個(gè)決策空間范圍內(nèi)不受任何其他可行個(gè)體支配，則稱該個(gè)體為全局Pareto最優(yōu)解。所有全局Pareto最優(yōu)解構(gòu)成全局Pareto前端。

多目標(biāo)優(yōu)化的目標(biāo)就是尋找這樣一組可行解，它包含盡可能多的非劣解，解集中的個(gè)體盡可能逼近問題的全局Pareto前端，且個(gè)體分布盡可能均勻。

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

假設(shè)無(wú)人機(jī)航路規(guī)劃過(guò)程以航路長(zhǎng)度、航路安全性、航路隱蔽性為效能目標(biāo)函數(shù)。包括起始點(diǎn)和目標(biāo)點(diǎn)在內(nèi)共有N個(gè)航路點(diǎn)，分別記為P(n)，n={1，2，…，N}，一條完整的航路記為P。則:

航路總長(zhǎng)度:

其中:dis為空間兩點(diǎn)間的歐氏距離。

航路安全性以無(wú)人機(jī)受敵方防御火力的威脅程度衡量:

其中:thri為第i個(gè)火力威脅在空間點(diǎn)的威脅度，i={1，2…M}，M 為戰(zhàn)場(chǎng)中威脅總數(shù)［9］。

其中:dmaxi為第i個(gè)火力威脅的最大威脅半徑，dmaxi為絕對(duì)威脅半徑 (該距離內(nèi)威脅恒定為最大值)，θ為視線仰角，θmini為攻擊下界角。

航路隱蔽性以航路點(diǎn)的平均高度衡量:

其中:Pnz為第n個(gè)航路點(diǎn)的飛行高度。

航路約束條件包括最小飛行高度約束、最大拐彎角約束和最大爬升/俯沖角約束。

綜上，無(wú)人機(jī)多目標(biāo)航路規(guī)劃問題可以描述為:

其中:P(n)·h為第n個(gè)航路點(diǎn)處的地形高度，θpn，φpn為該航路點(diǎn)處的拐彎角和爬升/俯沖角，safeh，θmax，?min，?max分別為無(wú)人機(jī)最小安全離地高度、最大拐彎角和最大爬升和最大俯沖角。

3 無(wú)人機(jī)多目標(biāo)航路規(guī)劃的NSGA－Ⅱ算法

NSGA－Ⅱ算法具有運(yùn)行速度快，收斂性好，解集分布均勻，魯棒性強(qiáng)等優(yōu)點(diǎn)，是目前應(yīng)用最廣的多目標(biāo)進(jìn)化算法 (MOEA)，該算法包括編碼設(shè)計(jì)、種群初始化、精英選擇、交叉操作、變異操作和快速非支配排序幾個(gè)步驟。本文將該算法應(yīng)用于無(wú)人機(jī)多目標(biāo)航路規(guī)劃問題的求解，具體步驟如下［5］:

3.1 編碼設(shè)計(jì)

無(wú)人機(jī)航路點(diǎn)在空間中表現(xiàn)為離散點(diǎn)，因此采用正整數(shù)編碼。首先將戰(zhàn)場(chǎng)空間柵格化，得到NX×NY×NZ的搜索空間。則代表一條航路的染色體為P=(P1，P2…PN)，N為航路點(diǎn)總數(shù)。Pi=(Pix，Piy，Piz)為該航路第i個(gè)航路點(diǎn)坐標(biāo)。其中Pix∈ {1，2…NX}，Piy∈ {1，2…NY}，Piz∈{1，2…NZ}。

3.2 種群初始化

初始化所有染色體的首個(gè)航路點(diǎn)為起始點(diǎn)，末位航路點(diǎn)為目標(biāo)點(diǎn)，此兩點(diǎn)不參與交叉變異操作。約束范圍內(nèi)隨機(jī)產(chǎn)生其余航路點(diǎn)。NSGA－Ⅱ算法中每個(gè)染色體P都有兩個(gè)重要屬性:非支配排序Prank和擁擠度Pd。前者表示染色體所屬的非支配層級(jí)，層級(jí)數(shù)小的染色體相對(duì)于其他層級(jí)染色體，處于非支配地位，因而更優(yōu)秀。后者用于表示目標(biāo)空間內(nèi)同一非支配層級(jí)內(nèi)染色體周圍個(gè)體的密度，擁擠度越大，染色體代表性越強(qiáng)，染色體更優(yōu)秀。染色體的非支配排序Prank和擁擠度Pd均通過(guò)快速非支配排序獲得，因此對(duì)于初始種群，參與選擇操作前，需要額外進(jìn)行一次快速非支配排序。

3.3 精英選擇

精英策略就是保留父代中的優(yōu)良個(gè)體進(jìn)入子代，防止已獲得的Pareto最優(yōu)解丟失，并逐漸提高種群所代表的解的質(zhì)量。NSGA－Ⅱ算法采用錦標(biāo)賽機(jī)制產(chǎn)選擇出與父代種群大小相同的新群體，用于進(jìn)行后續(xù)的遺傳操作。從父代種群中隨機(jī)選擇任意兩個(gè)染色體p和q。首先比較其非支配排序，如果prank＜qrank，則染色體p勝出，反之染色體q勝出;如果prank=qrank，則比較其擁擠度，如果pd＞qd，則染色體p勝出，反之染色體q勝出，勝出染色體加入新群體。反復(fù)從父代種群選擇個(gè)體進(jìn)行錦標(biāo)賽，直至滿足新種群規(guī)模。

3.4 交叉操作

對(duì)通過(guò)選擇的群體，進(jìn)行概率為Pc的交叉操作。從通過(guò)選擇的群體中隨機(jī)選擇任意兩個(gè)染色體進(jìn)行配對(duì)，隨機(jī)設(shè)定交叉位置n，使配對(duì)個(gè)體交換序號(hào)n及其以后的航路點(diǎn)編碼信息。為防止交叉位置航路發(fā)生突變，需要檢測(cè)交叉處航路點(diǎn)的最大拐彎角約束和最大爬升/俯沖角約束，如果不滿足約束條件，則進(jìn)行平滑處理:

如果原始染色體為可行解，則變異操作后染色體亦可保證為可行解。

3.5 變異操作

對(duì)通過(guò)交叉的群體，進(jìn)行概率為Pm的變異操作。從通過(guò)交叉的群體中隨機(jī)選擇任意染色體進(jìn)行變異，隨機(jī)設(shè)定變異位置n，對(duì)變異個(gè)體序號(hào)為n的航路點(diǎn)位置進(jìn)行隨機(jī)擾動(dòng)。為防止變異位置航路發(fā)生突變，需要檢測(cè)交叉處航路點(diǎn)的最大拐彎角約束和最大爬升/俯沖角約束，如果不滿足約束條件，則進(jìn)行平滑處理。如果原始染色體為可行解，則變異操作后染色體亦可保證為可行解。

3.6 快速非支配排序

選擇出的群體經(jīng)過(guò)交叉和變異操作，形成子代群體。將子代群體和父代群體合并，形成種群規(guī)模為的混合種群，對(duì)混合種群進(jìn)行快速非支配排序，選出最優(yōu)的dnanum個(gè)染色體，即為新的父代種群?？焖俜侵渑判蚪Y(jié)束后，重新返回錦標(biāo)賽選擇環(huán)節(jié)，進(jìn)行下一次迭代，直至算法結(jié)束。

3.6.1 np和Sp計(jì)算

快速非支配排序中，種群中每個(gè)個(gè)體p都有兩個(gè)參數(shù)np和Sp，其中np為種群中支配個(gè)體p的個(gè)體數(shù)，即比個(gè)體p優(yōu)的個(gè)體數(shù);Sp為種群中被個(gè)體p支配的個(gè)體的集合。

首先，根據(jù)公式 (3－6)，計(jì)算種群中個(gè)體適應(yīng)度，為盡快淘汰非可行解，可以將非可行解的目標(biāo)函數(shù)值設(shè)為極大 (適應(yīng)度極小)。然后，初始化每個(gè)個(gè)體的np=0，Sp=?，通過(guò)循環(huán)遍歷，對(duì)種群中任意兩個(gè)個(gè)體p和q進(jìn)行支配性判定 (定義1)，如果p＜q，則nq=nq+1，Sp=Sp∪q;反之np=np+1，Sq=Sq∪p。

3.6.2 非支配分級(jí)

非支配分級(jí)用于劃分種群中個(gè)體的非支配層級(jí)。

Step 1:初始化非支配層級(jí)數(shù)i=1。

Step 2:找到種群中所有np=0的個(gè)體，令其Prank=i。從種群中移除np=0的個(gè)體，并遍歷np=0個(gè)體的Sp，對(duì)任意 q∈Sp，令 nq=nq－1。

Step3:i=i+1，重復(fù)Step 2，直至種群中所有個(gè)體都已經(jīng)被劃分層級(jí)。

3.6.3 擁擠度計(jì)算

用于表示目標(biāo)空間內(nèi)同一非支配層級(jí)內(nèi)染色體周圍個(gè)體的密度。初始化該非支配層級(jí)內(nèi)所有個(gè)體擁擠度Pd=0。對(duì)非支配層級(jí)內(nèi)所有個(gè)體按目標(biāo)函數(shù)向量的第m個(gè)分量進(jìn)行升序排序，假設(shè)非支配層級(jí)內(nèi)有染色體個(gè)數(shù)k，排序?yàn)閕的個(gè)體當(dāng)前擁擠度為P，其目標(biāo)函數(shù)向量的第m個(gè)分量值為fm［i］，則染色體擁擠度計(jì)算為:

其中:fmmax和fmmin分別為層級(jí)內(nèi)目標(biāo)函數(shù)向量的第m個(gè)分量的最大值和最小值。排序邊緣個(gè)體直接賦予極大擁擠度，即依次遍歷航路長(zhǎng)度、航路安全性、航路隱蔽性3個(gè)目標(biāo)函數(shù)分量，計(jì)算染色體擁擠度。

3.6.4 最優(yōu)解排序

基于精英策略的最優(yōu)解排序就是選取父代子代混合種群的最優(yōu)個(gè)體作為新的父代，使得原父代中的優(yōu)良個(gè)體得以保留，從而防止Pareto最優(yōu)解。具體方法是，先按非支配排序Prank從小到大將非支配層級(jí)整體選入新父代，直到如果將某非支配層級(jí)完全選入新父代會(huì)超過(guò)規(guī)定的父代種群規(guī)模。此時(shí)按擁擠度從大到小，依次將非支配層級(jí)擁擠度最大的若干個(gè)個(gè)體選入新父代，使其滿足規(guī)定種群規(guī)模，此時(shí)的新父代即為混合種群中的最優(yōu)個(gè)體集合。

3.7 終止條件

當(dāng)種群多目標(biāo)進(jìn)化算法的運(yùn)行時(shí)間達(dá)到最大允許值或者種群迭代次數(shù)達(dá)到事先規(guī)定的上限，則進(jìn)化結(jié)束，取當(dāng)前最優(yōu)Pareto最優(yōu)解集為輸出結(jié)果，通過(guò)解碼得到備選方案集，并根據(jù)作戰(zhàn)目標(biāo)和指戰(zhàn)員意圖，從中選擇最合適的規(guī)劃結(jié)果。

4 仿真算例

假設(shè)無(wú)人機(jī)約束參數(shù)如表1，戰(zhàn)場(chǎng)環(huán)境為1 000 m×1 000 m×500 m，戰(zhàn)場(chǎng)敵方地面火力威脅數(shù)量為3，威脅參數(shù)如表2，其中火力威脅高度直接取所處位置的地形高度。

表1 無(wú)人機(jī)性能約束參數(shù)

表2 敵方火力威脅參數(shù)

設(shè)定染色體長(zhǎng)度為50，種群規(guī)模為60，最大迭代次數(shù)為100。采用NSGA－Ⅱ算法，仿真結(jié)果如下圖。

圖1～圖3為當(dāng)前種群航路長(zhǎng)度、航路安全性、航路隱蔽性最優(yōu)值與最差值隨著迭代次數(shù)的收斂曲線，可以看到迭代過(guò)程中，3個(gè)航路指標(biāo)的表現(xiàn)出了共同進(jìn)化的特征，且最優(yōu)值與最差值的收斂代數(shù)均不超過(guò)30代，表現(xiàn)出了良好的收斂性，證明了NSGA－Ⅱ算法的優(yōu)越性。

為抵消不同指標(biāo)項(xiàng)量綱帶來(lái)的影響，將Pareto解適應(yīng)度向量的各個(gè)分量與種群中該分量的最優(yōu)值 (最小值)的比值稱為相對(duì)適應(yīng)度。通過(guò)快速非支配排序從最終種群中選取10個(gè)最優(yōu)Pareto解，圖4為其相對(duì)適應(yīng)度向量在目標(biāo)空間的分布，可以看出Pareto前端的空間散布非常均勻，說(shuō)明獲得的Pareto最優(yōu)解具有良好的代表性。表3列出了最優(yōu)Pareto解的相對(duì)適應(yīng)度。

圖1 航跡長(zhǎng)度收斂曲線

圖2 航路威脅度收斂曲線

圖3 航路隱蔽性收斂曲線

從圖4和表3可以看出，經(jīng)過(guò)迭代收斂，種群中的最優(yōu)Pareto解普遍達(dá)到了較優(yōu)秀水平，但并不存在各方面都優(yōu)于其他Pareto解的絕對(duì)最優(yōu)解，而是體現(xiàn)出了一定的多樣性，即不同的Pareto解都具有各自的優(yōu)勢(shì)，分別適應(yīng)不同的任務(wù)需求。在復(fù)雜多變的戰(zhàn)場(chǎng)環(huán)境中，指揮人員可以根據(jù)不同任務(wù)需求的傾向性，選擇當(dāng)前最合適的方案，而不必依賴于應(yīng)變能力很差的固定指標(biāo)權(quán)重，體現(xiàn)出了良好的靈活性和適應(yīng)性。更重要的是，多元化的解集在空間均勻分布，各個(gè)最優(yōu)Pareto解不僅相互競(jìng)爭(zhēng)，而且互為備份，指揮人員不必?fù)?dān)心面臨，由于指標(biāo)權(quán)重或量綱等問題產(chǎn)生出某方面具有“短板”的劣質(zhì)最優(yōu)解，導(dǎo)致無(wú)合適方案可用的尷尬情況。這是多目標(biāo)優(yōu)化區(qū)別于加權(quán)單目標(biāo)優(yōu)化的重要特征，也是多目標(biāo)優(yōu)化的最大優(yōu)勢(shì)。

圖4 最優(yōu)Pareto解目標(biāo)空間分布

表3 最優(yōu)Pareto解相對(duì)適應(yīng)度

假設(shè)指揮人員決定采用冒險(xiǎn)策略發(fā)起一次快速隱蔽的打擊，并愿意承擔(dān)一定的風(fēng)險(xiǎn)，則其可能會(huì)選擇航路方案10，圖5和圖6分別為其三維路線圖和二維俯視圖。圖中同心圓的外圈表示敵方火力威脅的最大威脅半徑，內(nèi)圈為絕對(duì)威脅半徑。

圖5 最優(yōu)航路三維圖

5 結(jié)語(yǔ)

本文建立了無(wú)人機(jī)航路規(guī)劃問題的多目標(biāo)優(yōu)化模型，并給出了基于NSGA－Ⅱ的求解方法。相比于傳統(tǒng)加權(quán)單目標(biāo)優(yōu)化，該方法能夠兼顧無(wú)人機(jī)航路規(guī)劃的多個(gè)不同指標(biāo)要求，更加符合無(wú)人機(jī)作戰(zhàn)的實(shí)際特點(diǎn)，并具有很強(qiáng)的靈活性和適應(yīng)性。仿真算例表明了該方法解決無(wú)人機(jī)航路規(guī)劃問題的可行性和有效性，為無(wú)人機(jī)航路規(guī)劃研究提供了新的思路［1013］。

圖6 最優(yōu)航路二維俯視圖