基于DSGA的航空作戰平臺作戰聯盟形成策略

張 磊， 姚佩陽， 侯春雷， 張杰勇

(1.空軍工程大學信息與導航學院，西安 710077; 2.中國人民解放軍71901部隊，山東 聊城 252000)

0 引言

信息和網絡技術的迅猛發展及其在軍事領域的廣泛應用，使得未來戰場環境日趨復雜，作戰平臺日益多樣。戰爭對抗雙方為了獲取體系對抗的整體優勢，既要保證聚焦使用作戰力量，又必須根據戰場態勢能夠敏捷地調整配置作戰資源。單個平臺限于自身能力，往往難以獨立完成復雜的作戰任務，而傳統的多平臺作戰編組限于體制編制模式、作戰思維以及隨機處置的權限設置等問題，不適合分布式網絡化條件下實施敏捷作戰的要求。因此，具備不同作戰屬性的多作戰平臺根據任務的需要，快速而有效地組成作戰聯盟將是未來分布式網絡化戰爭一種重要的作戰樣式。多種作戰平臺根據作戰任務如何形成“作戰聯盟”成為指揮控制領域一個新問題。

在多 Agent系統(Multi－Aagent System，MAS)中，許多學者對任務聯盟形成方法和策略進行了系統深入的研究［1－7］，這為本文航空作戰平臺聯盟形成(Aerial Combat Platform Coalition Formation，ACPCF)問題的研究提供了重要理論技術和方法參考。但是，MAS中任務聯盟的形成與ACPCF問題存在幾點差異:一是MAS中Agent多是自私或是理性自私的，任務聯盟形成的本質是各Agent為獲取更多的個體利益而采取的博弈策略，如果將航空作戰平臺(ACP)看成Agent，該類型Agent屬于無私型的，為服務全局不計個體犧牲;二是MAS中Agent傾向于執行計算任務，任務一結束可立即加入下一任務中，任務聯盟穩定性較差，隨時可能進行聯盟重構，而ACP型的Agent完成一項任務后會有一定損耗，同時所形成的作戰聯盟必須具備一定的魯棒性。基于以上分析，本文在MAS任務聯盟形成理論基礎上，針對ACP的特點，分析建立ACPCF問題的數學模型，并針對該模型利用一種雙串編碼遺傳算法(Double Strings Genetic Algorithm，DSGA)對問題進行求解。

1 問題描述

1.1 作戰聯盟的相關概念

為了更好地描述ACP作戰聯盟的形成問題，首先給出該問題相關概念的基本定義。

定義1 作戰平臺(Combat Platform):在該問題中是指航空作戰平臺，是資源能力的載體，為執行作戰任務提供武器裝備、通信設施、偵察監視設備等資源，主要包括預警機、殲擊機、電子戰飛機等。在本文問題中，假設形成作戰聯盟可使用的作戰平臺集合為:P={P1，P2，…，Pj，…，PK－1，PK}，K 表示作戰平臺集合中平臺的數量;作戰平臺 Pj所擁有的資源能力向量PAj=(rj1，rj2，…，rjl，…，rjL－1，rjL)，rjl用于定量描述 Pj所具備的第l項類型的資源能力的大小。

定義2 作戰任務(Combat Task):是由ACP作戰的使命環境決定的，是作戰聯盟形成并進行所有活動的依據和目標，作戰任務通常是需要一定資源能力才能完成的活動。在本文問題中，假設需要完成的作戰任務為T;該作戰任務T的資源能力需求向量為RA=(R1，R2，…，Rl，…，RL－1，RL)，Rl用于定量描述成功處理任務T所需第l項類型的資源能力的大小。

定義3 作戰聯盟(Combat Coalition):是根據ACP所需執行的作戰任務需要，從可選擇的作戰平臺集合中挑選一定的平臺，按照一定的協議和規則組成的作戰平臺的聯合體，該聯合體可以通過有效的任務分配和計劃協調完成作戰任務中的各個作戰目標。作戰聯盟因作戰任務的存在而產生，也隨著作戰任務的完成而解散。在本文問題中，假設作戰聯盟C的資源能力向量為CA=(S1，S2，…，Sl，…，SL－1，SL)，Sl用于定量描述作戰聯盟CA所具備的第l項類型的資源能力的大小，其數值為

1.2 問題建模

為了準確描述ACPCF問題的數學模型，先對問題作如下假設。

假設1 假設作戰聯盟形成過程中，只考慮作戰平臺資源能力對作戰聯盟形成的影響，而忽略其他因素對其的影響。

假設2 假設作戰聯盟形成是在一個非超加性環境中(超加性是指對于任意兩個獨立的作戰聯盟，若將它們合并為一個作戰聯盟，其收益大于等于這兩個作戰聯盟收益之和)，否則，最大的作戰聯盟(包括所有作戰平臺)將是最有益的［8］。

1.2.1 目標函數

ACP形成作戰聯盟的基本要求:1)確保能夠完成作戰任務(即滿足作戰任務的資源能力需求);2)作戰聯盟的成本盡可能小。聯盟成本(OC)一般有兩部分組成:資源能力成本(FC)和平臺協作成本(CC)。

資源能力成本是組成作戰聯盟的所有作戰平臺總的資源能力折合的成本。資源能力成本通常也可以用作戰聯盟的資源能力的冗余來表示，即作戰聯盟所擁有的作戰平臺資源能力正好滿足作戰任務的資源能力需求時，該作戰聯盟的資源能力成本最小。即

平臺協作成本是在作戰聯盟形成過程中，期望減少作戰聯盟中作戰平臺在任務執行時不必要的協作，即如果某一作戰平臺的資源能力能滿足作戰任務的資源能力需求，就不用選擇多個作戰平臺來協作完成這一任務。因此，作戰聯盟中的作戰平臺的數量越多，該作戰聯盟中作戰平臺之間的協作成本就越大。在本文問題中，假設作戰聯盟形成問題的平臺協作成本與聯盟中平臺的數量的平方成正比。即

其中，N(C)表示作戰聯盟C中作戰平臺的數量。

因此，聯盟成本OC為資源能力成本FC和平臺協作成本CC的加權和。即:

其中，a和b為權系數，表示對應成本對總成本的影響。

ACPCF問題的目標函數就是極小化聯盟成本OC。

1.2.2 問題的約束條件

在本節假設條件的基礎上，ACPCF的約束條件只有一個，即作戰聯盟的資源能力要滿足作戰任務的資源能力需求，也就是說作戰聯盟的每一項類型的資源能力必須大于等于作戰任務對應項類型的資源能力需求，這也是作戰聯盟形成的必要條件。可以表示為

1.2.3 問題的數學描述

綜合上述ACPCF問題的目標函數和約束條件，該問題的數學描述為

2 問題求解

由式(5)可知，該問題實質上是一個復雜組合優化問題，即是一個非確定性多項式時間(Nondeterministic Polynomial，NP)問題。本文采用遺傳算法(GA)來求解以上問題模型。GA是由美國 Michigan大學的 J.Holland教授創建的一種概率搜索算法，它是利用某種編碼技術和遺傳運算機制來求解復雜的優化問題［9］。

2.1 染色體的編碼和解碼方式

為了簡化使用GA求解帶約束優化問題的難度，針對式(5)問題數學模型的特點，本文使用DSGA對染色體進行編碼［10］。如圖1所示。

圖中:Z(i)(i=1，2，…，K)表示作戰平臺的標號，取值范圍為{1，2，…，K}，對應可使用平臺集P中的作戰平臺，而序列［Z(1)，Z(2)，…，Z(K)］為1～K 的一個隨機序列;FZ(i)是標號為Z(i)的平臺所對應的狀態取值，取值范圍為{0，1}。

這種雙串結構的編碼方式，特定的解碼方式產生的原象總為可行解(在解碼過程中考慮問題模型的約束條件)，從而可以提高GA的進化效率，以下為這種雙串結構染色體的解碼方式。

2) 設解碼后產生的原象為(G1，…，Gj，…，Gk)(j=1，2，…，K)，Gj表示標號 j的作戰平臺的真實狀態。

3)設i=1。

4)如果 FZ(i)=1，則 GZ(i)=1，執行 6);如果FZ(i)=0，執行5)。

6) 如果?l∈{1，2，…，L} s.t.P'S≥Rl，則

l0;否則

7)i=i+1，假如 i＞ K，結束循環;否則，執行4)。

2.2 適應度函數

由式(5)可得，問題數學模型的目標函數為極小化作戰聯盟形成的聯盟成本OC，因此，本文設計的DSGA的適應度函數為聯盟成本OC的逆，即

2.3 遺傳算子

1)交叉算子。

對于這種雙串結構的染色體編碼方式，如果采用傳統的單點或多點交叉方式進行交叉運算，在產生的子代染色體中的序列［Z(1)，Z(2)，…，Z(K)］一般不為1～K的隨機序列(一般會出現相同的作戰平臺標號)，使得子代染色體的編碼方式不可行。因此，針對雙串結構的染色體編碼方式，本文采用部分匹配交叉(Partially Matched Crossover，PMX)［11］進行交叉運算，以下為這種雙串染色體編碼方式使用PMX進行交叉操作的具體過程。

① 初始化，設種群規模為SD，并設i=1。

②從父代染色體種群中任意選擇兩個染色體X和 Y，同時令 X'=X，Y'=Y。

③ 產生一個隨機數 ra，ra∈［0，1］，如果 ra≤Pc(Pc為交叉概率)，執行④ ;否則，執行⑨ 。

④ 從序列(1，2，…，K)中隨機產生兩個交叉點u和v(u≠v)，令 d=u，首先對 X'和 Y執行⑤ ～⑦的操作。

⑤ 令j=((d－1)%K)+1(其中(d－1)%K表示整數(d－1)除以整數 K的余數)，尋找 j'，使得ZX'(j')=ZY(j)，交換(ZX'(j)，FZX'(j))T和(ZX'(j')，FZX'(j'))T，d=d+1。

⑥ 如果u＜v，當d＞v時，執行⑦;當d≤v時，執行⑤;如果 u＞v，當 d＞(v+K)時，執行⑦;當 d≤(v+K)時，執行⑤。

⑦ 如果 u＜v，使 FZX'(j)=FZY(j)(u≤j≤v)，執行⑧;如果 u ＞ v，使 FZX'(j)=FZY(j)(1≤j≤v，u≤j≤K)，執行⑧。

⑧ 同樣，對Y'和X執行⑤～⑦的操作。

⑨ 得到的X'和Y'就是兩個父代染色體X和Y的子代。

⑩ i=i+1，假如 i≤SD，執行①;否則，停止。

初始種群通過交叉算子可以得到規模為2·SD的新的種群，稱這個新的種群為交叉種群。

圖2為PMX的一個例子，描述了X'和Y的交叉過程。

2)變異算子。采用均勻變異(Uniform Mutation，UM)的方法進行變異操作，具體步驟如下。

① 設i=1。

② 設j=1。

③ 產生一個隨機數 ra，ra∈［0，1］，如果 ra≤Pm(Pm為變異概率)，執行④;否則，執行⑤。

④ 如果FZ(j)=1，則令 FZ(j)=0;如果 FZ(j)=0，則令FZ(j)=1。

⑤ j=j+1，如果j≤K，執行③ ;否則，執行⑥。

⑥ i=i+1，如果i≤SD，執行① ;否則，停止。

初始種群通過變異算子可以得到規模為SD的新的種群，稱這個新的種群為變異種群。

3)選擇算子。

常用的GA的選擇算子較多，如精英策略(Elitism)、賭輪選擇(Roulette Wheel Selection)、期望值選擇(Expected Value Selection)等。本文將原始種群、交叉種群和變異種群中的個體合并為一個種群，這個種群的規模為4·SD，稱這個種群為合并種群。采用2.2節中計算適應值的方法，使用精英策略和賭輪選擇相結合的方法對合并種群進行選擇操作。包括兩方面:精英主義和賭輪選擇。

精英策略:如果上一代種群中的個體的適應度大于這一代種群中的每一個個體，則將它保留到這一代種群中。

賭輪選擇:個體的選擇概率與其適應性成比例，對新一代種群中的另外SD－1個個體通過對合并種群進行SD－1次輪盤賭選擇的方式產生。

4)停止準則。

本文的停止準則采用最大迭代數進行判斷，即判斷迭代的代數是否達到要求，如果群體進化已趨于穩定，則選擇最優的染色體個體作為該問題模型的優化解輸出。

2.4 算法步驟

DSGA的流程如圖3所示。

圖3 DSGA的基本流程圖Fig.3 Basic flow chart of DSGA

3 算例分析

本文以一個航空兵突擊作戰的想定為案例，在Inter(R)Pentium(R)4 CPU 3.00 GHz計算機上進行仿真實驗。

案例想定中的假設作戰任務T為航空兵突擊任務，其所需的資源能力如表1所示。可使用的作戰平臺集P為{P1，P2，…，P15}，其資源能力屬性如表2所示。其中，表1和表2中的8維資源能力分別為{預警監視，指揮控制，電子干擾，空中通信，空中掩護，壓制防空，空中對抗，對地打擊}。

表1 作戰任務的屬性Table 1 Attribute of combat task

表1中Rl的取值表示任務T的第l項類型的資源能力需求的大小，其數值越大，能力需求越大;表2中Pj的取值表示作戰平臺所具備的第l項類型的資源能力的大小，其數值越大，完成該項類型任務的能力就越強。

針對以上仿真案例，作了以下仿真實驗。

仿真實驗1 設置DSGA中的參數SD=10，Pc=0.7，Pm=0.05，迭代次數為50次，設置模型中的參數a=3和b=1。使用本文設計的DSGA求解以上案例，得到的DSGA的收斂曲線，如圖4所示。

表2 作戰平臺資源的屬性Table 2 Attribute of combat platform resources

圖4 DSGA的收斂曲線Fig.4 Constringency curve of DSGA

由圖4可得，以上案例的最優的適應度值為Ffitness，best=0.0100。

對應的染色體的編碼和解碼方式分別如圖5中a和b所示，由案例的求解結果可得，最佳的作戰聯盟為

圖5 最佳的染色體編碼和解碼形式Fig.5 The optimum chromosome coding and decoding method

仿真實驗2 設置循環次數為60次，得到的結果如圖6所示;作戰平臺數量不同情況下的算法運行時間如表3所示。可以看出，算法具有較好的可靠性和時效性，實驗的結果比較滿意。

圖6 最佳適應度值變化曲線Fig.6 Change curve of optimal fitness value

表3 不同作戰平臺數量情況下的算法運行時間Table 3 Time cost of the algorithm with different quantity of combat platforms

4 結論

本文針對分布式網絡化戰爭中作戰資源可以自由組合、柔性配置度高等新特點，提出作戰聯盟的新作戰理念，并重點對聯盟形成策略進行了研究。從任務資源能力需求與平臺屬性能力優化匹配的角度建立了作戰聯盟形成問題模型，并利用改進的遺傳算法對模型進行求解。仿真實驗結果證明了算法能很好地解決聯盟形成問題，并且具有良好的可靠性和時效性。

［1］ 常勇，吳慶憲，張立珍，等.基于MAS的無人機縱向飛行控制［J］.電光與控制，2011，18(3):21－24.

［2］ 傅一峰，曹健，李明祿.面向復雜任務結構的Agent聯盟算法［J］.小型微型計算機系統，2011，32(3):402－406.

［3］ 許波，余建平.基于量子遺傳算法的多任務聯盟并行生成算法［J］.計算機應用研究，2010，27(6):2100－2102.

［4］ 蔣建國，吳瓊，夏娜.自適應粒子群算法求解Agent聯盟［J］.智能系統學報，2007，2(2):69－73.

［5］ ZHENG S F，HU S L，LAI X W，et al.Searching for agent coalition using particle swarm optimization and death penalty function［C］//LNCS 4681，Springer－Verlag，Heidelberg，2007:196－207.

［6］ 蔣建國，李勇，夏娜.一種求解單任務Agent聯盟生成的貪婪算法［J］.系統仿真學報，2008，20(8):1961－1964.

［7］ 夏娜，蔣建國，魏星，等.改進型蟻群算法求解單任務Agent聯盟［J］.計算機研究與發展，2005，42(5):734－739.

［8］ HARSANYI J C.A simplified bargaining model for n－person in games and social situations［M］.Cambridge University Press，1997.

［9］ 王瑋，程樹昌，張玉芝.基于遺傳算法的一類武器目標分配方法研究［J］.系統工程與電子技術，2008，30(9):1708－1711.

［10］ SAKAWA M，KATO K.Genetic algorithms with double strings for 0－1 programming problems［J］.European Journal of Operational Research，2003，144:581－597.

［11］ 王小平，曹立明.遺傳算法——理論、應用與軟件實現［M］.西安:西安交通大學出版社，2002:28－38.