周 晶 林 眾 盧一鳴 何應(yīng)強

（海軍大連艦艇學(xué)院作戰(zhàn)軟件與仿真研究所 大連 116018）

1 引言

對空防御作戰(zhàn)是海上編隊的重要作戰(zhàn)樣式，其典型特征是戰(zhàn)斗節(jié)奏快，影響決策因素多，反應(yīng)時間短［1～2］。任務(wù)分配問題是編隊對空防御中核心問題之一，在有限的時間內(nèi)完成科學(xué)有效任務(wù)分配問題是編隊進行對空防御的關(guān)鍵［3］。任務(wù)分配問題中要考慮敵方威脅程度、完成任務(wù)收益、任務(wù)執(zhí)行時間和資源消耗等多種因素制約，因此編隊對空防御中的任務(wù)分配問題是一個典型的多目標(biāo)優(yōu)化問題（Multi-Objective Optimization Problem，MOOP）。多目標(biāo)優(yōu)化問題求解已被證明是NPH問題，當(dāng)任務(wù)規(guī)模增加時，求解難度呈幾何增長。除了優(yōu)化目標(biāo)多，任務(wù)分配問題還需要考慮涉及時間、空間、兵力能力和執(zhí)行順序等大量的約束條件。目前已有一些算法用于多目標(biāo)任務(wù)分配。早期最常見的方法是采用集中式方式進行求解，完成求解后將分配方案指派給各執(zhí)行兵力［4］，但這類方法存在單點失效問題和容錯性較差等問題，且無法解決大規(guī)模問題。近年來，分布式多任務(wù)分配方法被提出，大致可分為以下幾類：分布式完全搜索算法、分布式局部搜索算法、基于拍賣機制的算法和分布式蟻群算法等［5～7］。分布式完全搜索算法能確保解最優(yōu)，但各節(jié)點間需要較大的通信和計算成本，在單節(jié)點計算或通信資源有限的情況下難以適用；分布式局部搜索算法則大量減少了通信和計算的代價，各個節(jié)點在本地搜索最適合自己的任務(wù)分配方案，然后通過通信來實現(xiàn)全局任務(wù)分配的統(tǒng)一和協(xié)同，但這類方法通常難以保證解的質(zhì)量，求解的效果依賴于具體的應(yīng)用場景；分布式蟻群算法則將節(jié)點視為螞蟻，模擬螞蟻覓食的群體行為，來求解最優(yōu)的任務(wù)分配方案。這類方法利用智能啟發(fā)式優(yōu)化策略具有資源消耗小的優(yōu)勢，但分布式蟻群算法難以處理大量約束條件的問題，且容易陷入局部最優(yōu)。

演化算法是應(yīng)用最廣泛的智能優(yōu)化算法之一，具有與蟻群算法相當(dāng)?shù)膬?yōu)化能力［8］。近年來，分布式演化算法得到了廣泛的應(yīng)用［9］，但基于分布式演化算法用于多目標(biāo)任務(wù)分配、且在大量約束條件的研究較少。針對以上問題，本文提出一種基于NS?GA3的分布式多目標(biāo)演化算法（以下簡稱為D-NS?GA3算法），將編隊對空防御中的約束條件轉(zhuǎn)換為優(yōu)化目標(biāo)，與原有的目標(biāo)函數(shù)一起協(xié)同優(yōu)化，通過種群演化收斂得到滿足約束條件的全局最優(yōu)解。

2 任務(wù)分配問題分析與建模

為便于后續(xù)的演化算法實現(xiàn)，首先給出編隊任務(wù)分配問題的形式化描述，以下分別定義編隊中任務(wù)分配的各要素。

1）任務(wù)：為實現(xiàn)編隊總體作戰(zhàn)任務(wù)，通常需要對任務(wù)進行分解，直到分解為可以單個兵力獨立完成的原子任務(wù)為止，表示為V=｛v1…vn｝，其中，n為任務(wù)的數(shù)目。在實際應(yīng)用場景中，每個任務(wù)具有時間限制，假定每個任務(wù)在時間上限定了最早可執(zhí)行的時間和最晚可開始執(zhí)行的時間，則定義任務(wù)的可開始執(zhí)行時間范圍TV=｛［low1，up1］…［lown，upn］｝，其中l(wèi)owi為任務(wù)vi最早可執(zhí)行的時間，upi為任務(wù)vi最晚可開始執(zhí)行的時間，當(dāng)時間超過最晚時間時，任務(wù)將失效。［lowi，upi］為任務(wù)vi可開始執(zhí)行的時間范圍。執(zhí)行任務(wù)所需花費的時間表示為W=｛w1…wn｝，其中wi為執(zhí)行任務(wù)vi所需花費的時間。任務(wù)的位置信息是任務(wù)分配中需重點考慮的隱私，因此定義當(dāng)前位置為LV=｛lv1…lvn｝，其中l(wèi)vi（i=1…n）表示任務(wù)vi的當(dāng)前位置。

2）抗擊兵力：表示為A=｛a1…am｝，其中m為兵力的數(shù)目。兵力的位置信息為LA=｛la1…lam｝，其中l(wèi)ai（i=1…m）表示兵力ai的當(dāng)前經(jīng)緯度信息。

3）分配關(guān)系：用于表述作戰(zhàn)兵力與原子任務(wù)之間的分配關(guān)系，P={π1…πn}，其中設(shè)定πi為任務(wù)vi的分配，當(dāng)πi=vi→aj表示任務(wù)vi分配給兵力ai執(zhí)行，πj=vj→?表示任務(wù)vj未被有效分配給任一兵力。為便于后續(xù)描述，將πi=vi→ai和πj=vj→?分別簡化為πi=ai和πj=?。為了簡化問題模型，假設(shè)一個兵力在一個時間點只能完成一個任務(wù)，一個任務(wù)僅需要一個兵力執(zhí)行并完成，即不存在需要多個兵協(xié)同合作執(zhí)行才能完成的任務(wù)元，且時間是離散化的，以秒為單位。

4）執(zhí)行序列：Q=｛q1…qm｝，其中qi=｛qi1…qik｝為節(jié)點ai所需要執(zhí)行的k（不同節(jié)點的k值可能不同）個任務(wù)序列，例如qi=｛v1，v3，v5｝，表示任務(wù)v1，v3，v5分配給了節(jié)點ai，且節(jié)點ai按次序執(zhí)行這三個任務(wù)。

3 基于D-NSGA3算法的多目標(biāo)任務(wù)分配方法

3.1 NSGA3演化算法

NSGA3算法是由Deb等人于2013年提出的，NSGA3算法是在NSGA-2算法的基礎(chǔ)上改進而來，主要提升了NSGA-2算法以解決高維優(yōu)化問題（即當(dāng)目標(biāo)數(shù)目大于3）時的優(yōu)化能力［10～11］。其最大的差別點在于選擇操作，NSGA2算法采用基于參考點的選擇操作代替NSGA2算法中擁擠距離的選擇操作來保持非支配解的多樣性。主要包括以下四點：確定超平面上的參考點、規(guī)范化目標(biāo)函數(shù)、關(guān)聯(lián)操作和小生境保持操作。NSGA3的算法框架如表1所示。

表1 NSGA3算法

3.2 基于Master-Slave模型的D-NSGA3算法

在水面艦艇編隊中，編隊指揮所作為Master節(jié)點來負責(zé)NSGA-III的種群初始化、演化迭代、雜交、變異和選擇操作等。由于環(huán)境隨時可能發(fā)生變化，進而導(dǎo)致任務(wù)相關(guān)的指標(biāo)和信息（如執(zhí)行任務(wù)所需的能耗和完成任務(wù)的收益等）發(fā)生變化，最終導(dǎo)致評估任務(wù)分配策略的好壞也會發(fā)生變化。另一方面，由通信速度和覆蓋范圍受限，單個艦艇往往只能感知到其周圍的環(huán)境信息，因此，它只負責(zé)評估任務(wù)分配策略中涉及這些信息的部分。因此，本文將一條艦或擔(dān)負區(qū)域防控的多個艦艇作為一個Slave節(jié)點。Master節(jié)點會根據(jù)每個Slave節(jié)點的評估能力對任務(wù)分配方案進行分割與分發(fā)，Slave節(jié)點將接收到的基因片段進行評估，將評估結(jié)果返回給Master節(jié)點。

文中提出的算法流程如下：1）Master節(jié)點首先隨機初始化生成大小為N的初始種群作為父代；2）Master節(jié)點依據(jù)每個Slave節(jié)點所掌握的信息對種群個體基因進行分割劃分，并將基因片段發(fā)送給對應(yīng)的Slave節(jié)點；3）Slave節(jié)點接收到Master節(jié)點發(fā)送的基因片段后進行評估，并將評估函數(shù)的計算結(jié)果返回給Master節(jié)點；4）Master節(jié)點收集所有Slave節(jié)點返回的評估結(jié)果后，計算個體的整體評估值；5）Master節(jié)點通過雜交、變異算子產(chǎn)生子代種群；6）Master節(jié)點和Slave節(jié)點再對子代個體進行評估；7）Master節(jié)點對父代種群和子代種群進行非支配排序形成H個非支配層F1…FH；8）Master節(jié)點找出前h個非支配層的個體；9）Master節(jié)點通過選擇操作決定下一代種群，若，則直接選出前h層的個體作為下一代種群，否則通過參考點方法從臨界層Fh中選擇與F1…Fh-1層的個體一起作為下一代種群；迭代以上5）～9）步直至種群收斂或超過最大迭代次數(shù)。

3.3 染色體編碼、初始化、雜交、變異及評估

染色體的編碼、雜交和變異策略是演化算法中的核心問題，直接影響種群進化的速度和多樣性和求解的質(zhì)量。染色體編碼策略如下：每個染色體表述為x=x1…xm，其中xi表示兵力ai可執(zhí)行的任務(wù)的工作序列。此外，針對ai的功能約束，表示ai將按照xi指定的順序依次考慮執(zhí)行任務(wù)，倘若任務(wù)執(zhí)行后，ai無法在約束條件下執(zhí)行當(dāng)前任務(wù)時，則ai將跳過該任務(wù)繼續(xù)執(zhí)行下一個任務(wù)。對于染色體x，如果ai按照xi能在滿足約束條件的情況下執(zhí)行任務(wù)vj，那么后續(xù)的兵力ai+1…am將不再考慮執(zhí)行vj任務(wù)。假定存在2兵力和5個任務(wù)，由于存在功能約束，兵力a1可執(zhí)行任務(wù)v1、v2、v3，兵力 a2可執(zhí)行任務(wù)v3、v4、v5，那么，染色體 x=3 1 2 4 3 5 表示兵力 a1將按照順序考慮執(zhí)行任務(wù)v3、v1、v2，a2將按照順序考慮執(zhí)行任務(wù) v4、v3、v5，若 a1執(zhí)行完 v3和 v1后無法在資源約束或時間約束內(nèi)成功執(zhí)行任務(wù)v2，那么最終a1可成功執(zhí)行2個任務(wù)；而由于v3已經(jīng)分配給a1執(zhí)行，a2僅需按順序考慮執(zhí)行v4和v5。該編碼方式的優(yōu)點是所有個體編碼長度固定，無需在評估個體時考慮功能約束，簡化了評估過程，且易于對個體進行初始化、交叉、變異等操作。

初始化種群采用隨機方式，然后根據(jù)編碼方式，Master節(jié)點依據(jù)每個兵力ai的功能約束得到它們可執(zhí)行的任務(wù)集合，然后生成的隨機排列，作為初始化個體x的第i部分。雜交方式采用經(jīng)典的單點雜交算子，對于兩個父代個體x=x1…xm和y=y1…ym，Master節(jié)點隨機生成一個1～m間的數(shù)k，交換x和y的前k個序列得到子代個體和。在變異算子中采用參數(shù)mutPr來控制個體變異的概率。依據(jù)概率選出個體的第i個序列xi做變異，Master節(jié)點將生成一個的隨機排列替換原有的xi。

4 實驗結(jié)果及分析

為了驗證算法有效性和執(zhí)行效率，將文中的算法與全局搜索算法進行比較，通過設(shè)置相同的初試數(shù)據(jù)和環(huán)境變更信息的條件下，兩種算法進行對比實驗。實驗采用基于Tsung-Che Chian的NSGA-III的版本進行二次開發(fā)［10］，默認設(shè)置演變迭代次數(shù)設(shè)為200次，雜交概率為1.0，突變率設(shè)為0.2。實驗環(huán)境為：操作系統(tǒng)為Windows 7 64位Professional，CPU i7 7600主頻2.80GHz，內(nèi)存8G，編程環(huán)境為Visual Studio2010。

選擇4組參數(shù)分別為：1）m=5，n=5；2）m=5，n=10；3）m=5，n=20；4）m=10，n=20。當(dāng)（m=5，n=20）與（m=10，n=20）時，采用完全搜索策略的算法在1 h未能完成計算，而文中提供的算法在5 min內(nèi)完成求解。通過不同的閾值進行過濾顯示，結(jié)果如表格2～3所示。

表2 對比試驗結(jié)果當(dāng)m=5，n=10

表3 對比試驗結(jié)果當(dāng)m=10，n=10

通過比較本文算法和完全搜索策略下的計算結(jié)果，發(fā)現(xiàn)本文提供的算法可以搜索到接近全局搜索策略下最優(yōu)解。當(dāng)m=5且n=5時，兩者搜索到的最優(yōu)解相差僅為0.008；當(dāng)m=5且n=10時，平均差值為0.0408，而最大的偏差量也僅為0.231，最小偏差值為0；當(dāng)m=10且n=10時，平均差值為0.14，而最大的偏差量也僅為0.225，最小偏差值為0.003。盡管全局搜索策略可獲得最優(yōu)解，但求解時間較長，只能限于在較小的問題規(guī)模下使用。而本文算法在m≥100，n≥800時，仍可以有效尋求最優(yōu)解，因此該算法具有較好的實用性和推廣性。

5 結(jié)語

本文針對水面艦艇任務(wù)分配問題中優(yōu)化目標(biāo)多、約束條件苛刻的問題，提出了一種基于分布式演化算法的多目標(biāo)任務(wù)分配方法，實驗結(jié)果表明：相比于分布式局部搜索算法，本文的算法能在消耗更少的時間和通信代價下得到接近全局最優(yōu)的任務(wù)分配方案。