喻世軼,張 亮,周學(xué)廣

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

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

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

1 受空間約束的武器目標(biāo)分配模型

1.1 問題描述及分配原則

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

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

1)每類武器可以對多個(gè)目標(biāo)進(jìn)行分配,同時(shí)每個(gè)目標(biāo)可以被分配多個(gè)武器系統(tǒng);

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

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

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

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

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

1.2 武器目標(biāo)分配模型

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

(1)

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

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

(2)

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

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

(3)

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

(4)

2 蛙跳算法原理

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

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

(5)

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

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

3.1 解的編碼

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

3.2 初始解的生成

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

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

圖1 非支配等級排序

圖2 擁擠度因子算法流程

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

3.3 更新策略

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

圖3 基于改進(jìn)蛙跳算法的武器目標(biāo)分配流程圖

4 仿真計(jì)算及結(jié)果分析

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

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

每個(gè)目標(biāo)的威脅等級系數(shù)分別為{0.204 9,0.225 6,0.181 1,0.196 9,0.190 7},4型武器系統(tǒng)的價(jià)值分別為{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)的計(jì)算機(jī)上通過Matlab對算法進(jìn)行實(shí)現(xiàn),取參數(shù)為初始種群個(gè)數(shù)50,子群數(shù)5,子群個(gè)體10,子群迭代次數(shù)5,總?cè)旱螖?shù)50,計(jì)算的最優(yōu)目標(biāo)值為0.144 8,對應(yīng)的最優(yōu)決策變量為

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

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

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

5 結(jié)束語

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