郭昱普，蔡 飛，潘志強

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

0 引言

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

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

其次，隨著敵我飛行器數(shù)量種類的增加，需要執(zhí)行的任務(wù)規(guī)模也隨之?dāng)U大，將大批量的任務(wù)分配給大批量的飛行器會導(dǎo)致組合爆炸。因此即便是擁有較長的規(guī)劃周期，對于實現(xiàn)全局最優(yōu)規(guī)劃也是十分棘手的[4]。

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

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

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

1 空中作戰(zhàn)任務(wù)規(guī)劃框架

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

圖1 空中作戰(zhàn)任務(wù)規(guī)劃框架Fig.1 Frame of air combat mission planning

在給出的空中任務(wù)規(guī)劃框架中，通過作戰(zhàn)仿真的方式對方案進行評估。為了迅速完成規(guī)劃，采用低保真的作戰(zhàn)模擬環(huán)境。

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

2 多目標(biāo)進化算法概述

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

搜索算法必須在有沖突的2個目標(biāo)之間取得平衡?；旌蠁l(fā)式算法的設(shè)計具有控制這種平衡的能力[9]。本文提出的搜索自適應(yīng)多目標(biāo)進化算法將工作擴展到連續(xù)搜索領(lǐng)域，開發(fā)了一種混合進化算法，并且在多目標(biāo)進化算法的框架下集成了一組自適應(yīng)的搜索策略。本算法從不同搜索操作的協(xié)作和一體化中取得了良好的效果，同時，還能夠根據(jù)現(xiàn)有問題選擇合適的搜索策略。

2.1 基本概念和定義

如果沒有一般性約束，多目標(biāo)優(yōu)化問題可以寫作

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

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

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

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

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

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

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

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

2.2 遺傳操作

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

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

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

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

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

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

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

2.3 差分進化算法

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

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

3 基于搜索自適應(yīng)的多目標(biāo)優(yōu)化算法

3.1 算法表述

根據(jù)第2節(jié)的基本概念，把空中任務(wù)規(guī)劃多目標(biāo)優(yōu)化問題轉(zhuǎn)化成以下數(shù)學(xué)表達式

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

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

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

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 實驗結(jié)果

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

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

圖2 實驗結(jié)果圖Fig.2 Experimental results diagram

4 規(guī)劃框架的具體應(yīng)用

使用文中所提出的空中任務(wù)規(guī)劃框架，做了幾個具體場景下的應(yīng)用，設(shè)計了幾個決策支持的工具。第一個解決了空中動態(tài)目標(biāo)的打擊問題，隨后將該框架擴展到情報偵察領(lǐng)域，并且嘗試著將其推廣到無人機任務(wù)規(guī)劃領(lǐng)域。

4.1 動態(tài)目標(biāo)打擊任務(wù)

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

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

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

3)戰(zhàn)機攜帶哪些彈藥可以成功地實現(xiàn)對目標(biāo)的打擊；

4)方案會達到什么樣的效果，以及如何處理級聯(lián)效應(yīng)。

這個過程往往發(fā)生在戰(zhàn)機正在空中執(zhí)行日常巡航任務(wù)的過程中，所以必須在幾分鐘之內(nèi)做出決策。因此，使用自動化輔助決策系統(tǒng)可以極大地提高效率。

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

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

圖3 動態(tài)任務(wù)規(guī)劃表示Fig.3 Dynamic targeting mission plan genetic representation

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

該方法給動態(tài)目標(biāo)規(guī)劃領(lǐng)域提供了一個可行的方案，這樣的方式同樣可以應(yīng)用到武器規(guī)劃部門，用于分析武器裝備開發(fā)過程中潛在新興目標(biāo)的影響。這個動態(tài)分配任務(wù)的框架被用于支持建模和基于模擬的實驗。

4.2 情報偵察任務(wù)規(guī)劃

目標(biāo)打擊任務(wù)是空中行動的重要環(huán)節(jié)，但是不能孤立的運作。指揮中心下設(shè)的情報偵察部門負責(zé)向決策者提供準確、相關(guān)和及時的情報，在此基礎(chǔ)上形成情報預(yù)測能力和態(tài)勢感知能力。與打擊任務(wù)相似，情報偵察部門也需要規(guī)劃人員制定偵察巡航計劃，利用我方裝備所攜帶的傳感器和偵察平臺，對目標(biāo)區(qū)域進行偵察探測以滿足情報需求。在情報偵察領(lǐng)域，同樣可以使用空中作戰(zhàn)任務(wù)規(guī)劃框架。

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

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

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

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

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

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

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

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

5 結(jié)論

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

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