基于多目標算法的空中作戰任務規劃框架研究

郭昱普，蔡 飛，潘志強

(國防科技大學信息系統工程重點實驗室，長沙 410073)

0 引言

空中作戰任務規劃是一個很復雜的過程，首先要通過聯合作戰空中評估流程將指揮員的意圖轉化為聯合空中作戰計劃，聯合指揮中心的計劃人員必須通過準確分析戰場空間信息來提高態勢感知能力[1]。制訂作戰計劃時，決策人員根據所需要執行的任務清單來制訂合理的聯合空中作戰計劃，飛行員負責聽從指令完成任務[2]。空中作戰任務規劃給規劃任務帶來了非常大的挑戰，其主要難度體現在以下幾個方面：

首先，空中作戰是一個動態的過程[3]，戰場態勢變化迅速，這就是一個很強的時間限制。以觀察-判斷-決策-行動(Observation-Orientation-Decision-Action, OODA)環為例，完成從偵察到打擊的過程本身就需要很長的時間，其中留給規劃決策的時間更是緊迫。

其次，隨著敵我飛行器數量種類的增加，需要執行的任務規模也隨之擴大，將大批量的任務分配給大批量的飛行器會導致組合爆炸。因此即便是擁有較長的規劃周期，對于實現全局最優規劃也是十分棘手的[4]。

第三，有效的任務規劃服從某些強制性的約束。在空間上，可能表現為打擊目標不能突破某些禁飛區；在時間上，我方飛行器可能無法在特定的時間窗口到達打擊區域；在其他飛行器能力方面，如燃料、攜帶彈藥、速度等，都可能成為限制任務完成的潛在因素，所以可行域是不連續的。因此，大部分基于梯度的搜索方法能力明顯不足。

第四，目標函數的設置不確定性強。在打擊目標的任務中，更看重對目標最大限度毀傷的可能性；在情報偵察監視的任務中，更看重最大限度地覆蓋目標區域。魚和熊掌不能兼得，不同的優化目的可能本身是相互沖突的，例如，如果追求毀傷目標的最大可能性，可能意味著我方戰機需要較長的追擊距離，這就增加了我方戰機自身被摧毀的可能性。

有限的決策時間、龐大的任務規模、復雜的可行域以及相互間存在矛盾的目的函數給空中任務規劃帶來了巨大的壓力。空中作戰任務規劃可以看作多目標優化問題，其特點是規模大、存在多個相互沖突的目標。進化算法被廣泛應用于尋找多目標優化問題的最優解，在設計全局搜索方法時，多樣化和集約化是2個主要的問題。多樣化是指在搜索空間中訪問多個不同區域的能力，而集約化是指在這些區域內獲得高質量解決方案的能力。本文在算法層面提出了一種多目標進化算法，也從頂層設計了空中作戰任務規劃框架，并且給出了2個具體決策的例子。

1 空中作戰任務規劃框架

在信息戰條件下，為了解決空中作戰任務規劃的問題，僅通過規劃者和指揮人員的辛苦工作是遠遠不夠的。本文提出了空中作戰任務規劃的工作流程框架,需要借助許多輔助決策的信息工具:例如將實際問題轉化成數學模型的數學建模工具,用于解決多目標優化問題的進化算法的程序和軟件以用于評估方案，預測可能導致的情況的作戰仿真的工具等。本節提出的規劃架構如圖1所示。

圖1 空中作戰任務規劃框架Fig.1 Frame of air combat mission planning

在給出的空中任務規劃框架中，通過作戰仿真的方式對方案進行評估。為了迅速完成規劃，采用低保真的作戰模擬環境。

文中采用的是一種基于agent的仿真方法，每一個作戰單元都可以看作是一個動態的agent，將agent看作是一個智能體，每個agent有自己的運行規則，甚至可以有自己的博弈策略。近年來，隨著計算機計算能力的提高，基于agent的仿真方法得到了更加廣泛的接受。此外，與經典的戰爭數學模型(如蘭徹斯特方程)[5]相比，它具有能夠直接對系統中實體進行建模的顯著優勢。這允許從不同實體的低級交互中產生系統級的影響，在對較為復雜的情況進行建模時，這可能是有利的[6-8]。

2 多目標進化算法概述

多目標進化算法是一種廣泛被應用在優化問題上的智能算法。進化算法的提出受到了達爾文進化論的啟發。在解決優化問題時先隨機地構建一些初始解，然后通過評價保留一些解、淘汰一些解，被保留的解通過進化隨機產生后代解，然后再進行評估。通過不斷迭代，相當對可行域進行了一個優勝劣汰的選擇，迭代的次數越多，獲得帕累托最優解的概率就越大。由于多目標優化問題在大多數情況下的梯度是不連續的，所以進化算法的表現要明顯優于基于梯度的算法。

搜索算法必須在有沖突的2個目標之間取得平衡。混合啟發式算法的設計具有控制這種平衡的能力[9]。本文提出的搜索自適應多目標進化算法將工作擴展到連續搜索領域，開發了一種混合進化算法，并且在多目標進化算法的框架下集成了一組自適應的搜索策略。本算法從不同搜索操作的協作和一體化中取得了良好的效果，同時，還能夠根據現有問題選擇合適的搜索策略。

2.1 基本概念和定義

如果沒有一般性約束，多目標優化問題可以寫作

MinimizeF(x)=(f1(x),f2(x),…,fm(x))
Subject to:x∈Ω

這里，F(x)是一個m維的目標向量，fi(x)是第i個優化的目標，x=(x1,…,xn)T是n維的決策變量，Ω是可行決策空間。

定義1：一個可行解是x優于另一個可行解y(定義為xy)，使得fi(x)≤fi(y)，?i∈{1,…,m}。

定義2：一個解是帕累托最優的充分條件是不存在y使得xy。

定義3：帕累托最優集(P*)是所有帕累托最優解的集合

P*={x∈Ω|?y∈Ω,y?x}

定義4：帕累托前沿(Pareto Front, PF)是帕累托最優集在目標空間的映射

PF={F(x)=(f1(x),…,fm(x)):x∈P*}

2.2 遺傳操作

交叉和突變是最有名的2個遺傳操作。交叉是交換父母的遺傳物質以產生新的后代的過程。而突變算子則用于保持種群在世代間的多樣性。下面主要介紹了模擬二進制交叉(Simulated Binary Crossover, SBX)、多親本交叉和多項式突變。

SBX在實際應用中得到了廣泛的應用。它在許多具有連續搜索空間的測試問題中都能很好地工作。對于一對父母節點xa和xb，SBX產生一個后代y如下

這里，p,u∈[0,1]是2個隨機數，ηc是分配指數。

目前在連續搜索領域提出了多種多父交叉，例如單純形交叉(Simplex Crossover, SPX)和父中心交叉(Parent-Centric Crossover, PCX)等。然而，本文中提出的算法使用了新多父交叉(Multi-Parent Crossover, MPC)。MPC從3個不同隨機選擇的父母中交叉構建了一個新的子女，公式如下

這里，β～N(μ,σ)是滿足高斯分布的隨機數，p∈[0,1]是均勻分布的隨機數。

在多項式變異中，在靠近父結點的地方生出一個子結點的概率大于在遠離父結點的地方生出一個子結點的概率。突變體后代

這里，uj∈[0,1]是滿足均勻分布的隨機數，分布指數ηm和突變指數pm是2個控制參數。aj和bj是xj的上限和下限。

2.3 差分進化算法

微分進化算法是一種簡單有效的搜索算子，主要用于求解連續域的優化問題。微分進化的成功依賴于微分突變，利用搜索域內的候選解來構建差分向量。每個差異向量被縮放并添加到另一個候選解中，生成所謂的突變向量;然后，微分進化將突變向量與父代解重新結合，生成新的子代;當子代具有同等或者更好的適應度時，才能取代父代。差分進化有一些控制參數如縮放因子F，用來縮放差分向量，以及交叉速率CR。給定N個個體的總體P，為每個目標個體隨機選擇3個不同的個體xa、xb、xc，目標個體xi∈P,?P∈{1,…，N}。突變體vi由下述公式生成。然后，將二項交叉應用于vi和vi，生成新的子代。

其中，rnd∈[0,1],jrnd∈{1,…，n}是一個隨機選擇的索引來確保至少有一個組件ui是由vi所提供，n是個體的長度，CR∈[0,1]。

3 基于搜索自適應的多目標優化算法

3.1 算法表述

根據第2節的基本概念，把空中任務規劃多目標優化問題轉化成以下數學表達式

miny=F(x)=(f1(x),f2(x),…,fk(x))

e(x)=(e1(x),e2(x),…,em(x))≤0,

x=(x1,x2,…,xn)∈X

X={(x1,x2,…,xn)|li≤xi≤ui,i=1,2,…,n}
L=(l1,l2,…,ln)
u=(u1,u2,…,un),y=(y1,y2,…,yk)∈Y

其中，x是決策變量，y是目標變量，X是決策變量空間，Y是目標函數變量空間，L和u分別是決策變量空間的下界和上界，e(x)是約束函數向量。把群體中的個體看作是相空間中的粒子，首先選出初始的一代，然后通過計算熵和自由能確定候選的父粒子，最后通過差分算法給出遺傳變異規則確定的后代。給出的算法過程如下：

步驟1：設置t=0，然后隨機生成初始種群P0={x1(t),x2(t),…,xN(t)}。

xi(t))-fj(t-1,xi(t-1))))(自由能的表達式)，然后利用下面的比較規則計算第i個粒子的秩函數值

if ((xiπxj)∨(xiπ=xj)∨(xi?xj∧si>

sj)∨(xi?xj∧si=sj∧pi(t,f(t)))<=

pj(t,f(t)))∨(xi～xj))

then Rank(xi(t))=Rank(xi(t))+1;

else Rank(xi(t))=Rank(xi(t))

步驟4：將新生成的l個粒子添加到種群Pt中從而形成新的種群Pt′。

3.2 實驗結果

實驗中，為了驗證該算法的計算性能，對四種典型的基準函數(ZDT1～ZDT4)[10]進行了測試。ZDT是一套測試優化算法的基準函數集，測試了該算法在不同情況下解決復雜的多目標優化問題的能力。結果如圖2所示。

從圖2可以看到,通過使用這種新算法不僅可以求解凸最優帕累托(ZDT1)和凹最優帕累托前沿(ZDT2),而且還可以求出離散最優帕累托前沿(ZDT3)；同時，該算法收斂速度(ZDT4)更快,性能優于傳統的多目標進化算法。

圖2 實驗結果圖Fig.2 Experimental results diagram

4 規劃框架的具體應用

使用文中所提出的空中任務規劃框架，做了幾個具體場景下的應用，設計了幾個決策支持的工具。第一個解決了空中動態目標的打擊問題，隨后將該框架擴展到情報偵察領域，并且嘗試著將其推廣到無人機任務規劃領域。

4.1 動態目標打擊任務

動態目標打擊任務是指敵方飛行器突然在我方領空出現時，我方利用一切可以利用的裝備資源盡最大可能將其毀傷。動態目標打擊小組的規劃人員必須快速生成并評估具有特定約束條件的打擊備選方案，需要考慮的問題有以下幾點[11]：

1)我方可以使用哪些裝備對目標進行打擊；

2)哪些武器裝備可以在時間窗口內到達打擊地域；

3)戰機攜帶哪些彈藥可以成功地實現對目標的打擊；

4)方案會達到什么樣的效果，以及如何處理級聯效應。

這個過程往往發生在戰機正在空中執行日常巡航任務的過程中，所以必須在幾分鐘之內做出決策。因此，使用自動化輔助決策系統可以極大地提高效率。

在打擊動態目標的任務中，任務規劃人員會根據上級的決心先確定行動希望達到的目的。所給框架中的目的子集包括：1)最大限度地提高敵方目標被毀傷的概率；2)最大限度地降低我方裝備被威脅的概率；3)最小化我方裝備被毀傷的概率；4)盡量使高優先級的目標被毀傷得最多。

由求解多目標優化問題得出的方案中包括負責執行任務的我方戰機以及其針對的目標。每次篩選要先根據限制條件確定可行解集，例如，一個已經消耗完彈藥的我方戰機不能再執行打擊另外一個目標的任務；在機會窗口結束之前無法到達的我方戰機不能被分配任務。其動態任務表示如圖3所示。

圖3 動態任務規劃表示Fig.3 Dynamic targeting mission plan genetic representation

通過這種直接的兩點交叉的編碼方式，采用均勻變異的標準遺傳算子來動態地更新可行解集。有時可行解是將一個任務同時分配給2個裝備，可能會在實際情況中產生沖突或矛盾。

該方法給動態目標規劃領域提供了一個可行的方案，這樣的方式同樣可以應用到武器規劃部門，用于分析武器裝備開發過程中潛在新興目標的影響。這個動態分配任務的框架被用于支持建模和基于模擬的實驗。

4.2 情報偵察任務規劃

目標打擊任務是空中行動的重要環節，但是不能孤立的運作。指揮中心下設的情報偵察部門負責向決策者提供準確、相關和及時的情報，在此基礎上形成情報預測能力和態勢感知能力。與打擊任務相似，情報偵察部門也需要規劃人員制定偵察巡航計劃，利用我方裝備所攜帶的傳感器和偵察平臺，對目標區域進行偵察探測以滿足情報需求。在情報偵察領域，同樣可以使用空中作戰任務規劃框架。

目標打擊任務是在盡可能保全自身的同時追求最大限度地殺傷敵人，在情報偵察領域目的產生了新的變化，目的子集包括：1)最小化每一個裝備所走的總距離；2)最大化對時間窗口要求的服從；3)最大化覆蓋盡可能廣的地理范圍。

任務計劃包括將可用的偵察裝備分配給可觀察站點的有序集合，每個可用裝備都配有一組傳感器，保證其能夠收集信息。每個可觀察站點都有一組與情報收集類型相匹配的相關情報需求。

最初表示收集計劃的方法是采用多層遺傳表示。在這種表示方法中，個體由一個或多個裝備路由基因組成，其中每個裝備路由基因包含一組裝備探測的路徑點。圖4展示了其中一個示例，小寫字母是觀察站點的標識符；D表示倉庫，是裝備的初始位置，倉庫可以用作模擬加油，并且具有產生多條路線的附加效果；N是一個無操作指示符，用于模擬可變長度的遺傳表示。

圖4 偵察探測任務計劃遺傳表示Fig.4 ISR mission plan genetic representation

遺傳變異算子在個體水平和基因水平上都起作用(如圖5)交叉操作采用單點交叉，從一個親本中選取一個完整的裝備路徑基因子集，并與另一個親本互補的基因結合。在基因層面，每個偵察探測裝備在2個候選計劃之間執行額外的單點交叉，交換部分裝備路由的各個部分，然后執行均勻突變，選擇一個可行的收集點并替換當前路徑點。

圖5 偵察探測任務計劃多層次遺傳變異Fig.5 ISR mission plan multi-tiered genetic variation

在使用這種遺傳表示的實驗中，該方案其實是對合作共同進化算法的一種近似[14]。在合作共同進化算法中，每個種群都包含代表更大解決方案的一個組件的個體。這些種群的進化是并行進行的，相互作用只是為了獲得適應性。

該改進的算法是為每個可用的偵察探測裝備形成一個子填充，其中的個體構成該資產的個體收集計劃，然后通過從每個子填充中選擇單個成員形成一個完整的收集計劃。交叉和變異是在種群水平上進行的，是一個標準的進化算法。為了進行評估，群體中的一個成員與上一代最優秀的成員相互協作，形成一個完整的候選解決方案。

5 結論

通過以上理論分析和實驗分析得出結論，構造的新的多目標進化算法明顯提高了傳統多目標任務規劃的性能。原因是這種新算法結合了自由能最小化和粒子系統的熵增加定律相空間,然后驅動所有粒子參與交叉和變異的所有時間,以便快速準確地獲得帕累托解。

空中任務規劃是一個非常復雜的過程，隨著武器裝備數量和種類的增加，任務規劃也將越來越復雜[15]。通過規劃希望達到多個最優的目標，提出了一種基于多目標任務規劃算法和作戰仿真相結合的框架用于輔助決策。研究了該框架在空中作戰領域的幾個部分，包括動態目標打擊、情報偵察探測和無人機任務規劃。在進化算法的研究領域，還可以做很多改進。希望這些工作能夠被應用于實踐，極大地幫助任務規劃者。