異步并行螞蟻策略在網絡化艦艇編隊武器目標分配中的應用

李相民， 張元瀚， 代進進

(海軍航空工程學院，山東 煙臺 264001)

0 引言

在當前乃至未來的海戰(zhàn)中，由美國海軍首先提出的艦艇編隊網絡中心戰(zhàn)理論將成為主導。作戰(zhàn)平臺呈現扁平化、網絡化，形成一個整體與整體的對抗，但是這也導致了信息量的暴增，從發(fā)現目標到發(fā)射攔截導彈的過程中如果單以人力來處理這些信息，是遠遠不能滿足作戰(zhàn)需要的。如何合理利用編隊資源，有效、科學和經濟地進行防空作戰(zhàn)，對我編隊海上作戰(zhàn)具有重要意義［1］。

目前的各種武器目標分配(Weapon Target Assignment，WTA)方法很多，主要有遺傳算法以及改進的遺傳算法，微分對策模型和灰色局勢決策方法，這些方法實時性較弱，全局搜索能力不強，容易陷入局部最優(yōu);另外還有基于馬爾科夫鏈的動態(tài)分配，但是預測需要過去的信息，隨著時間的推移和目標的大量出現，計算工作量也將無法滿足實戰(zhàn)作戰(zhàn)需求［2］。

本文給出了一種基于蟻群算法的異步并行螞蟻策略。利用蟻群系統的并行性和正反饋快速收斂性等優(yōu)點，對艦艇編隊武器目標分配進行了研究，文章引入了綜合毀傷閾值和綜合毀傷矩陣Em的概念，前者在有大量目標數和武器節(jié)點數的情況下，能夠大大減少計算量;后者在突發(fā)情況發(fā)生之后能保證分配繼續(xù)正常進行，很大程度上滿足了實戰(zhàn)性的需要。

1 網絡平臺介紹

多Agent系統(Multi-Agent System，MAS)的引入為網絡中心戰(zhàn)中的編隊系統提供了一個動態(tài)的分布式的網絡，作為平臺發(fā)揮作用。MAS中的Agent概念，源于人工智能理論，它的特性主要是具有反應性、自主性和社會性。而每個Agent不僅要求自身具備一定的處理和解決問題的能力，更要求各個Agent之間具有互相協作、共同完成某個任務的能力，這與編隊內成員的功能和地位不謀而合。“網絡中心戰(zhàn)”中的作戰(zhàn)艦艇，具備指控系統、武器系統和傳感器，具備獨立作戰(zhàn)能力，而數據網絡奠定了各艦之間協作的基礎［3］。

在網絡中，指控系統之間通過廣播模塊和接收模塊實現資源和信息的共享和指揮協商的功能;通過公共訪問服務節(jié)點來進行網外單位的進入和網內單位的退網，實現動態(tài)網絡的重組。圖1是MAS的主要結構功能圖。

圖1 艦艇編隊MAS結構功能圖Fig.1 The function structure of warship fleet MAS

2 基于MAS的WTA模型

2.1 約束條件

在目標分配之前，有幾點必須統一。首先所有網內成員必須以整體效益最大為最高優(yōu)先和最終目標;其次從威脅判斷開始到目標分配所運用的算法必須一致，否則會產生計算結果的不同步和時序上的混亂;第三每個單一的成員在系統中的邏輯結構是一致的;最后，網絡中的每個Agent都遵守該網絡定義的語義和規(guī)則［4］。

在此基礎上，由于編隊作戰(zhàn)條例和客觀條件約束限制，編隊武器節(jié)點在獲得來襲目標數據之后，必須進行目標協商，防止資源沖突或無效分配的出現［5］。

假設我方編隊成員數目為M，每個成員所擁有的武器節(jié)點為Nl(1≤l≤M)，來襲目標有A個。

1)武器節(jié)點的目標協商。

判別來襲目標的航路捷徑經過哪些武器節(jié)點的協同殺傷區(qū)，即確定由參加攔截該目標的武器節(jié)點。目標j相對于武器節(jié)點i的航路捷徑為pij，當pij小于最大航路捷徑要求maxpi時，即pij≤maxpi，該武器節(jié)點能夠攔截目標。

確定武器節(jié)點自身的工作狀態(tài)，是否進入正常備戰(zhàn)狀態(tài)，該狀態(tài)包括:武器節(jié)點是否損壞，能否正常工作，是否有可用導彈等，經過檢查后，通過網絡通報給其他武器節(jié)點，確定能夠參與攔截的武器節(jié)點。為武器節(jié)點工作狀態(tài)［6］:

其中:1≤m≤M;1≤i≤Nl;1≤j≤A。

2)目標分配的約束條件。

對于給出的可能分配方案來說，需要滿足一定的約束條件，才能符合最終的要求。

首先，要求一個目標只能被一個防空單位分配，禁止重復分配，即

其中:1≤m≤M;1≤i≤Ni;1≤j≤A。

其次，計算后給出的武器節(jié)點數量不得超過實際給定的最大武器節(jié)點數量，Nr≤Nmax。

2.2 模型建立過程

在目標綜合毀傷矩陣建立之前，應依照威脅評估算法和我方單位對目標毀傷能力數據，給出威脅度值和協同毀傷概率值，并得到綜合毀傷值，具體步驟如下。

1)由指控網中的指控節(jié)點通過威脅評估算法得出來襲目標的威脅度值，進行排序，歸一化處理，統一量綱，得到來襲目標威脅度值(T1，T2，T3，…，TA)。

2)各指控節(jié)點根據自身武器裝備性能，結合編隊其他成員的技、戰(zhàn)術指標，給出m艦武器節(jié)點i對目標j的聯合毀傷概率，即:

式中:Rg為獲取目標信息的能力;Mc為通信能力;Rs為搜索跟蹤目標的能力;Mt為傳輸信息的能力;Pd為導彈的自導能力;Pf為導彈捕捉目標的概率;Ph為導彈對目標的殺傷概率。從而給出我方武器節(jié)點在協同制導下對目標的聯合毀傷概率矩陣，1≤m≤M，1≤i≤Ni，1≤j≤A。

4)經過廣播模塊把Em發(fā)送給其他Agent，同時通過接收模塊得到其他Agent的綜合毀傷矩陣，綜合可以得到編隊綜合毀傷矩陣E:

5)建立目標函數［7］:

6)運用最優(yōu)分配算法——異步并行螞蟻策略算法進行目標分配，求取目標函數最大的目標分配方式。

在實時作戰(zhàn)中，如果發(fā)生某成員被毀傷或數據鏈路被破壞而導致的該成員綜合毀傷矩陣無法發(fā)送至網絡時，算法可以不受影響地繼續(xù)通過其他成員的綜合毀傷矩陣進行多目標分配，也就是說，綜合毀傷矩陣的引入使該算法能夠實時進行多目標分配，即使編隊中只剩幾個甚至一個成員時，也能繼續(xù)使用和運行，大大滿足了實戰(zhàn)的需要。

由于某個目標的威脅度或者防空武器對其毀傷效果明顯過小將會導致其綜合毀傷值過小，但是程序對這個明顯不會被選擇的值，仍然會分配時間對其進行判斷和計算，這樣就造成了一定的時間浪費，這里將引入一個“綜合毀傷閾值”的概念，首先判斷某綜合毀傷值是否有被選擇的資格，不超過綜合毀傷閾值的綜合毀傷值將不被蟻群中的螞蟻搜索。即:

而這個閾值初始化由最初的專家系統給出，隨著打擊后的目標殺傷效果評估來對閾值進行修正。

3 異步并行螞蟻系統

并行螞蟻系統，又稱并行螞蟻，是以著名的主人/奴隸方法為基礎的，適用于當前流行的MIMD體系結構處理器并行蟻群策略之一［8］。這個方法的主要思路在于:對于每一個指控節(jié)點，分配一個或多個奴隸螞蟻，每個螞蟻從自身作戰(zhàn)成員出發(fā)，開始構建解決方案，而主人處理器由某一個處理能力最強的指控節(jié)點擔任，對于全局的信息素進行更新和輸出，以確定整個系統在一個實時的同步更新的狀態(tài)下工作，而局部信息素的更新由奴隸所在的指控節(jié)點完成，這是區(qū)別同步并行螞蟻的地方，同步并行螞蟻中由主處理器完成局部和全局的信息素更新，通信量較大。另外，主人處理器也可以同時擔當被分配到奴隸螞蟻的工作，以保證更高效地執(zhí)行。

不妨設開始時有螞蟻k在城市r上，它選擇下一個城市的準則是:

這里，q是一個在0和1之間的統一的隨機數，q0是一個參數，而螞蟻已經訪問過的城市將禁止再次訪問，螞蟻還可以訪問的城市形成一個集合Gk(r)，這里的參數β選擇為正數，這樣路徑越長越受歡迎。上式表示下一個城市的選擇受到當前路徑上的信息量和距離影響，距離越長，信息量越多，越優(yōu)先選擇該城市，下式表示通過概率選擇下一個城市。局部更新規(guī)則為

式中:ρ是局部信息素衰減系數且0＜ρ＜1;τ0是各條邊上的初始信息素量。而當所有螞蟻完成一次行程后，在構成當前最長路徑上的信息素更新為

式中:γ是全局信息素衰減系數0＜γ＜1;Δτ(r，s)是增加的信息素，確定如下:

式中:X是常數，不妨設為100;L是當前最長路徑長度。

一個螞蟻對應一個處理器，每個普通處理器都對自己的信息素矩陣留有副本保存。

編寫異步并行螞蟻策略的主人處理器和奴隸處理器的異步處理程序流程圖見圖2。

圖2 主人處理器和奴隸處理器異步處理程序流程Fig.2 Asynchronization processes of main processor and common processor

4 實例分析

在某時刻，由傳感器網信息采集和數據融合之后，通過威脅評估，這里運用灰色區(qū)間評估確定10枚來襲反艦導彈的威脅度值如表1所示。

表1 來襲目標威脅度值表(1×10－4)Table 1 The table of coming targets'threaten level

當武器控制系統根據雷達發(fā)送的目標精確數據，實時完成航路捷徑、殺傷區(qū)及發(fā)射區(qū)邊界、目標到達發(fā)射區(qū)近界和遠界的時間［9］等射擊諸元參數的計算后［10］，利用協同制導下防空導彈毀傷概率模型確定來襲目標在殺傷區(qū)內的遭遇點的毀傷概率，得到各武器節(jié)點對來襲目標的毀傷概率矩陣，如表2所示(為方便計算和表達明確，假設編隊中的武器節(jié)點數為3個，每個武器節(jié)點的火力通道數均為4個)。

表2 我武器節(jié)點對來襲目標的毀傷概率值Table 2 The damage probability of our weapon points to coming targets

最后，通過綜合計算得到編隊對該批目標的綜合毀傷矩陣(這里綜合毀傷閾值設為0.045)，可得:

其中:矩陣 e11=0.04104;e24=0.04383;e35=0.04064。小于綜合毀傷效能閾值，根據步驟直接賦0值。

經過Matlab編程實現和仿真運算，圖3為采用綜合毀傷閾值的并行螞蟻策略(實線)，不采用綜合毀傷閾值的并行螞蟻策略(點虛線)以及普通蟻群算法(虛線)的3種方式的效果顯示圖，結果表明該改進算法最好，并且隨著問題的規(guī)模越大，對比效果將越明顯。最后得出的分配結果為武器節(jié)點A的目標是{X4，X6，X9}武器節(jié)點 B 的目標是{X2，X5，X7，X8}，武器節(jié)點 C的目標是{X1，X3，X10}，最大綜合毀傷效能值 E=1.71761。

圖3 結果仿真圖Fig.3 The simulation of the result

5 結束語

本文在艦艇編隊的武器目標分配中引入了綜合毀傷閾值和綜合毀傷矩陣的概念，在算法上結合蟻群算法和并行網絡的特點，使用異步的方式，更適合于目前海上編隊網絡中心戰(zhàn)的作戰(zhàn)系統，本文對該方法進行了詳細的分析，并給出了簡要的例子予以驗證。不過，在艦艇編隊多目標分配中需要考慮更多的影響因素，比如防空導彈協同殺傷區(qū)和發(fā)射區(qū)，網絡的數據傳輸能力和編隊內擔任“螞蟻”的處理器個數等，這些因素對分配的影響，在今后的工作中，將進一步研究［11］。

［1］王劍飛，武文軍，范月強，等.“網絡中心戰(zhàn)”中的美國海軍C4ISR系統效能評估［J］.情報指揮控制系統和仿真技術，2005，27(5):15-20.

［2］張元瀚，李相民，代進進.艦艇編隊反導輔助決策系統分析［C］//火力與指揮控制2009年學術年會論文集，廈門，2009:171-173.

［3］楊軼.多Agent技術及螞蟻算法在制造網格系統中的應用［D］.武漢:武漢理工大學，2006.

［4］王祖典.網絡中心制導技術［J］.電光與控制，2005，12(4):38-39，43.

［5］PATTERSON W.A unified framework for solving multiagent target assignment problem［D］.Air Force Institute of Technology，2008.

［6］黃樹彩，李為民.超視距多目標攻擊排序問題中的蟻群算法［J］.人工智能及識別技術，2008，34(10):158-160.

［7］李士勇.蟻群算法及其應用［M］.哈爾濱:哈爾濱工業(yè)大學出版社，2004.

［8］程紅熙，任忠斌，何清華.馬爾可夫決策過程在動態(tài)WTA 中的應用［J］.電光與控制，2005，12(1):83-85.

［9］舒培貴，婁壽春.防空導彈混編火力群目標分配工程算法研究［J］.現代防御技術，2008，36(5):66-69.

［10］王步云，姜偉，徐建志.基于多Agent的編隊導彈攻擊火力分配的優(yōu)化研究［J］.指揮控制與仿真，2008，30(2):45-48.

［11］徐長江，王樂群.基于不確定多屬性決策的空中目標威脅評估技術［J］.現代防御技術，2009，37(2):5-9.