喻世軼,張 亮,周學廣

(1.海軍工程大學,湖北 武漢 430033;2.中國人民解放軍91642部隊,海南 三亞 572000)

武器目標分配(Weapon-target Assignment,WTA)是指依據(jù)作戰(zhàn)目的、可使用武器的技戰(zhàn)術性能、目標威脅等級等約束條件,結合戰(zhàn)場態(tài)勢信息,合理快速地分配武器資源,確定最佳武器目標分配方案,以實現(xiàn)最佳的協(xié)同作戰(zhàn)效果或最佳的作戰(zhàn)目的。武器-目標分配問題作為作戰(zhàn)指揮決策過程中的一個關鍵環(huán)節(jié),一直以來都受到研究人員的高度關注。如何快速高效地給出武器目標分配方案,對于縮短指揮員的決策時間,提升指揮決策效能具有重要意義。

武器-目標分配問題屬于NP完全問題,求解WTA問題的計算量較大,隨著決策變量的維度增加，計算量呈指數(shù)增長,因此,目前，國內(nèi)外的學者通常采用智能優(yōu)化算法進行求解,常用的有遺傳算法[1]、粒子群算法[2]、匈牙利算法[3]、人工魚群算法[4]、差分進化算法[5]等。其中,遺傳算法因具有較強的全局搜索能力被廣泛應用,并且針對其易早熟，搜索效率低,受參數(shù)影響較大的弱點,提出的改進算法也很多[6-10]。本文針對遺傳算法在求解武器目標分配時計算時間較長的問題,利用蛙跳算法的快速計算性能[11],借鑒基于非支配等級和擁擠度因子的精英選擇策略[12],改善初始種群的多樣性和均勻度,提高了算法搜索最優(yōu)解的質(zhì)量,同時，計算時間相對遺傳算法較短。

1 受空間約束的武器目標分配模型

1.1 問題描述及分配原則

假設我水面艦艇編隊通過預警偵察體系發(fā)現(xiàn)有n批來襲空中目標,水面艦艇有m種不同型號的防空武器可供使用,在作戰(zhàn)過程中的某一時刻,每類武器系統(tǒng)可使用的武器資源為ci(i=1,2,…，m),第i種防空武器對第j類目標的命中概率為pij(i=1,2,…，m,j=1,2,…，n)。

水面艦艇編隊防空作戰(zhàn)的武器目標分配原則如下:

1)每類武器可以對多個目標進行分配,同時每個目標可以被分配多個武器系統(tǒng);

2)每種型號的防空武器在作戰(zhàn)時間內(nèi)分配的武器資源不能超過該防空武器系統(tǒng)的武器資源總數(shù);

3)為確保不遺漏任何目標,每個目標至少被分配一個型號的武器;

4)根據(jù)防空武器使用的一般原則——避免資源浪費,每一類型的防空武器對同一個目標分配的最大武器資源數(shù)為3,且每個目標被分配的武器資源總數(shù)也不超過3;

5)由于每類防空武器都有射擊條件,最簡單的就是空間約束,因此,不能保證每類防空武器都能對每個來襲目標進行攔截;

6)分配的目標是為了獲取最大作戰(zhàn)效能,即毀傷目標的數(shù)學期望最大,同時消耗武器的成本最小。

1.2 武器目標分配模型

假設編隊內(nèi)有m種不同型號的防空武器,每種防空武器的資源總數(shù)為ci(i=1,2,…，m),每種防空武器的成本為ei(i=1,2,…，m),來襲空中目標為n批,目標的威脅度系數(shù)為dj(j=1,2,…，n),第i種防空武器對第j類目標的毀傷概率為pij(i=1,2,…，m,j=1,2,…，n),則武器目標分配的決策方案為

(1)

其中,xij(i=1,2,…，m,j=1,2,…，n)表示第i類武器對第j類目標分配的武器資源數(shù),當xij>0時，表示第i類武器對第j類目標分配xij個武器資源,反之表示不分配武器資源。

另外,根據(jù)分配原則5),不是每類武器都能對所有目標進行攔截,假設分配禁忌決策為

(2)

其中,yij(i=1,2,…，m,j=1,2,…，n)表示為第i類武器對第j類目標是否能分配武器的判斷變量,當yij=1時表示第i類武器對第j類目標可分配武器,反之則表示不能分配,用來作為生成初始決策種群的約束條件。

根據(jù)分配原則6)可建立防空武器目標分配模型如式(3)所示:

(3)

式(3)是一個多目標優(yōu)化問題,為利于算法求解,通常將多目標轉化為單目標進行求解,因此,本文將實現(xiàn)最大的防空作戰(zhàn)效果和最小的武器消耗成本兩個目標變?yōu)橐粋€目標,即求解單位成本內(nèi)取得的最大防空作戰(zhàn)效果,則該模型變?yōu)?/p>

(4)

2 蛙跳算法原理

蛙跳算法是2003年提出的一種仿生學智能優(yōu)化算法[13],適用于組合優(yōu)化問題,參數(shù)少，計算速度快,具有全局尋優(yōu)的特點。其主要思想:假設濕地有一群青蛙,可通過在濕地中不同的石頭上跳躍來尋找食物。每只青蛙代表組合優(yōu)化問題的一個解,且有自己的文化,個體之間通過文化來交換信息。初始時,將青蛙分成若干個子群,在子群中每個個體之間通過文化相互影響,隨著子群的不斷進化,實現(xiàn)局部搜索。當子群進化到一定階段后,各子群之間再進行文化信息交換,實現(xiàn)全局搜索。重復上述過程,直到滿足停止條件。

其算法模型可描述為:首先隨機產(chǎn)生規(guī)模為N(維數(shù)為l)的初始種群P={X1,X2,…,XN},其中Xi=[xi1,xi2,…xil]表示問題的一個解。再根據(jù)目標函數(shù)計算每個解對應的適應度值,并進行降序排序。然后將初始種群分為m個子群,每個子群中有n個青蛙,即N=m×n,具體的分配方法:總群中第1只青蛙分配給第1個子群,第2只分配給第2個子群,直到第m只分配給第m個子群,第m+1只青蛙分配給第1個子群,依次類推,直到全部分配完畢。將每個子群中青蛙的最優(yōu)適應度值和最差適應度值個體記為Xb、Xw,其相應的適應度值記為vb、vw,然后，在每個子群中按照式(4)進行局部搜索:

(5)

3 基于非支配等級和擁擠度因子優(yōu)選的改進蛙跳算法求解武器目標分配問題

本文針對傳統(tǒng)蛙跳算法(SFLA)全局尋優(yōu)質(zhì)量不高的問題進行改進,在兼顧計算時間的前提下,通過基于非支配等級和擁擠度因子的精英選擇策略改進初始種群的生成,提高初始種群的多樣性和均勻性,以期在有限的迭代次數(shù)中獲得相對較優(yōu)的最優(yōu)解。

3.1 解的編碼

在基于改進的蛙跳算法求解武器目標分配問題中,需要對決策變量進行變換,將多維矩陣決策變量變?yōu)橐痪S矩陣,即X=[x11,x12,…，x1n,x21,x22,…，x2n,…,xm1,xm2,…,xmn],有利于蛙跳算法的更新計算。

3.2 初始解的生成

蛙跳算法(SFLA)的初始解通常是隨機生成的,其多樣性和均勻性不可控,借鑒文獻[13]的思想,對初始解進行預處理,假設算法中參與迭代計算的種群規(guī)模為N,則先隨機生成數(shù)倍于N的種群規(guī)模,設為mul*N。

首先，根據(jù)帕累托支配關系給初始種群進行非支配關系排序,并給每個解賦予一個非支配關系等級,假設某個個體不被其他任何個體支配,則該個體的非支配等級為1,將種群中所有非支配等級為1的個體挑選出來,剩下的個體再進行一次非支配關系排序,挑選出來的非支配個體等級為2,依次類推,直到所有的個體都被賦予非支配等級,其流程圖如圖1所示。

圖1 非支配等級排序

圖2 擁擠度因子算法流程

最后,按照精英選擇策略從mul*N個個體中挑選N個作為參與迭代計算的初始種群,具體算法思想是:根據(jù)個體的兩個屬性值——非支配等級pareto_rank和擁擠度因子flog_crowi,所有個體按照非支配等級由低到高的順序進行排序,從支配等級低的個體開始,依次將非支配等級對應的全體變量放入初始種群Pt,直到當某一非支配等級pareto_ranki對應的個體大小超出了種群N為止,然后對非支配等級為pareto_ranki的個體集合Ci按照擁擠度因子由大到小的順序排序,擁擠度因子大的優(yōu)先選入Pt,直到Pt的個體數(shù)量達到N為止。通過此種方法生成的初始種群相對隨機生成種群具有較好的多樣性和均勻度。

3.3 更新策略

搜索策略采用傳統(tǒng)蛙跳算法(SFLA)的更新策略,基于非支配等級和擁擠度因子的精英選擇策略改進蛙跳算法求解武器目標分配問題的算法流程如圖3所示。

圖3 基于改進蛙跳算法的武器目標分配流程圖

4 仿真計算及結果分析

假設有5批從不同方位來襲的目標,水面艦艇編隊有4型防空武器系統(tǒng),每種武器擁有的資源總數(shù)和毀傷概率如表1所示(其中，有相同型號的武器系統(tǒng)和相同型號的來襲目標)。

表1 武器系統(tǒng)基本參數(shù)

每個目標的威脅等級系數(shù)分別為{0.204 9,0.225 6,0.181 1,0.196 9,0.190 7},4型武器系統(tǒng)的價值分別為{1.2,1.0,1.2,0.6}。每型武器受射界的限制,其分配禁忌決策如表2所示,該決策可作為生成初始決策種群的約束條件。

表2 武器分配禁忌表

在內(nèi)存8 G,處理器為Intel(R)Core(TM)i5-5700 CPU @3.40GHz,64位操作系統(tǒng)的計算機上通過Matlab對算法進行實現(xiàn),取參數(shù)為初始種群個數(shù)50,子群數(shù)5,子群個體10,子群迭代次數(shù)5,總群迭代次數(shù)50,計算的最優(yōu)目標值為0.144 8,對應的最優(yōu)決策變量為

其最優(yōu)適應度值變化曲線如圖4所示。

本文將該算法與傳統(tǒng)蛙跳算法、遺傳算法進行多次運算比對分析,每種算法都運行10次,運行結果如表3所示。

由表3可以看出,改進蛙跳算法相對傳統(tǒng)蛙跳算法其尋優(yōu)時間變長,但最優(yōu)適應度值明顯變優(yōu),且時間的增加幅度不大;改進蛙跳算法相對傳統(tǒng)遺傳算法的最優(yōu)適應度值較小,但其尋優(yōu)時間相對遺傳算法要減少很多。而水面艦艇編隊防空作戰(zhàn)時,對時效性要求較高,改進后的蛙跳算法在時間增加相對較少的前提下,使最優(yōu)度值有了較大的改善,是解決編隊防空作戰(zhàn)時武器目標分配問題的一個不錯的選擇。

5 結束語

本文針對空間受限的水面艦艇編隊防空武器目標分配問題,提出一種基于擁擠度因子和非支配排序的改進蛙跳算法,大大改善了初始種群的多樣性和均勻度,相對傳統(tǒng)蛙跳算法提高了最優(yōu)解的質(zhì)量,相對傳統(tǒng)遺傳算法大大減少了尋優(yōu)時間,對于防空作戰(zhàn)這種實時性要求很高的武器目標分配來說是一個不錯的選擇。