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

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

1 引言

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

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

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

1）任務(wù)：為實(shí)現(xiàn)編隊(duì)總體作戰(zhàn)任務(wù)，通常需要對(duì)任務(wù)進(jìn)行分解，直到分解為可以單個(gè)兵力獨(dú)立完成的原子任務(wù)為止，表示為V=｛v1…vn｝，其中，n為任務(wù)的數(shù)目。在實(shí)際應(yīng)用場景中，每個(gè)任務(wù)具有時(shí)間限制，假定每個(gè)任務(wù)在時(shí)間上限定了最早可執(zhí)行的時(shí)間和最晚可開始執(zhí)行的時(shí)間，則定義任務(wù)的可開始執(zhí)行時(shí)間范圍TV=｛［low1，up1］…［lown，upn］｝，其中l(wèi)owi為任務(wù)vi最早可執(zhí)行的時(shí)間，upi為任務(wù)vi最晚可開始執(zhí)行的時(shí)間，當(dāng)時(shí)間超過最晚時(shí)間時(shí)，任務(wù)將失效。［lowi，upi］為任務(wù)vi可開始執(zhí)行的時(shí)間范圍。執(zhí)行任務(wù)所需花費(fèi)的時(shí)間表示為W=｛w1…wn｝，其中wi為執(zhí)行任務(wù)vi所需花費(fèi)的時(shí)間。任務(wù)的位置信息是任務(wù)分配中需重點(diǎn)考慮的隱私，因此定義當(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è)一個(gè)兵力在一個(gè)時(shí)間點(diǎn)只能完成一個(gè)任務(wù)，一個(gè)任務(wù)僅需要一個(gè)兵力執(zhí)行并完成，即不存在需要多個(gè)兵協(xié)同合作執(zhí)行才能完成的任務(wù)元，且時(shí)間是離散化的，以秒為單位。

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

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

3.1 NSGA3演化算法

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

表1 NSGA3算法

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

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

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

3.3 染色體編碼、初始化、雜交、變異及評(píng)估

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

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

4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法有效性和執(zhí)行效率，將文中的算法與全局搜索算法進(jìn)行比較，通過設(shè)置相同的初試數(shù)據(jù)和環(huán)境變更信息的條件下，兩種算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)采用基于Tsung-Che Chian的NSGA-III的版本進(jìn)行二次開發(fā)［10］，默認(rèn)設(shè)置演變迭代次數(shù)設(shè)為200次，雜交概率為1.0，突變率設(shè)為0.2。實(shí)驗(yàn)環(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）時(shí)，采用完全搜索策略的算法在1 h未能完成計(jì)算，而文中提供的算法在5 min內(nèi)完成求解。通過不同的閾值進(jìn)行過濾顯示，結(jié)果如表格2～3所示。

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

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

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

5 結(jié)語

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