郭拉克，李文生，韓帥濤

(中國洛陽電子裝備試驗中心，河南洛陽 471000)

0 引言

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

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

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

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

定義1:如果可行個體p至少有一個目標函數比可行個體q的好，而且個體p的所有目標都不比個體q的差，即:

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

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

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

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

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

假設無人機航路規(guī)劃過程以航路長度、航路安全性、航路隱蔽性為效能目標函數。包括起始點和目標點在內共有N個航路點，分別記為P(n)，n={1，2，…，N}，一條完整的航路記為P。則:

航路總長度:

其中:dis為空間兩點間的歐氏距離。

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

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

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

航路隱蔽性以航路點的平均高度衡量:

其中:Pnz為第n個航路點的飛行高度。

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

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

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

3 無人機多目標航路規(guī)劃的NSGA－Ⅱ算法

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

3.1 編碼設計

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

3.2 種群初始化

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

3.3 精英選擇

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

3.4 交叉操作

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

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

3.5 變異操作

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

3.6 快速非支配排序

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

3.6.1 np和Sp計算

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

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

3.6.2 非支配分級

非支配分級用于劃分種群中個體的非支配層級。

Step 1:初始化非支配層級數i=1。

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

Step3:i=i+1，重復Step 2，直至種群中所有個體都已經被劃分層級。

3.6.3 擁擠度計算

用于表示目標空間內同一非支配層級內染色體周圍個體的密度。初始化該非支配層級內所有個體擁擠度Pd=0。對非支配層級內所有個體按目標函數向量的第m個分量進行升序排序，假設非支配層級內有染色體個數k，排序為i的個體當前擁擠度為P，其目標函數向量的第m個分量值為fm［i］，則染色體擁擠度計算為:

其中:fmmax和fmmin分別為層級內目標函數向量的第m個分量的最大值和最小值。排序邊緣個體直接賦予極大擁擠度，即依次遍歷航路長度、航路安全性、航路隱蔽性3個目標函數分量，計算染色體擁擠度。

3.6.4 最優(yōu)解排序

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

3.7 終止條件

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

4 仿真算例

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

表1 無人機性能約束參數

表2 敵方火力威脅參數

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

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

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

圖1 航跡長度收斂曲線

圖2 航路威脅度收斂曲線

圖3 航路隱蔽性收斂曲線

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

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

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

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

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

5 結語

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

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