基于分布式演化算法的編隊對空防御任務分配方法?

周 晶 林 眾 盧一鳴 何應強

（海軍大連艦艇學院作戰軟件與仿真研究所 大連 116018）

1 引言

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

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

2 任務分配問題分析與建模

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

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

2）抗擊兵力：表示為A=｛a1…am｝，其中m為兵力的數目。兵力的位置信息為LA=｛la1…lam｝，其中lai（i=1…m）表示兵力ai的當前經緯度信息。

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

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

3 基于D-NSGA3算法的多目標任務分配方法

3.1 NSGA3演化算法

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

表1 NSGA3算法

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

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

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

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

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

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

4 實驗結果及分析

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

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

表2 對比試驗結果當m=5，n=10

表3 對比試驗結果當m=10，n=10

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

5 結語

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