改進(jìn)蛙跳算法求解武器目標(biāo)分配問題

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

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

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

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

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

1.1 問題描述及分配原則

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

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

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

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

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

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

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

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

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

假設(shè)編隊(duì)內(nèi)有m種不同型號(hào)的防空武器,每種防空武器的資源總數(shù)為ci(i=1,2,…，m),每種防空武器的成本為ei(i=1,2,…，m),來襲空中目標(biāo)為n批,目標(biāo)的威脅度系數(shù)為dj(j=1,2,…，n),第i種防空武器對(duì)第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類武器對(duì)第j類目標(biāo)分配的武器資源數(shù),當(dāng)xij>0時(shí)，表示第i類武器對(duì)第j類目標(biāo)分配xij個(gè)武器資源,反之表示不分配武器資源。

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

(2)

其中,yij(i=1,2,…，m,j=1,2,…，n)表示為第i類武器對(duì)第j類目標(biāo)是否能分配武器的判斷變量,當(dāng)yij=1時(shí)表示第i類武器對(duì)第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è)解對(duì)應(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 基于非支配等級(jí)和擁擠度因子優(yōu)選的改進(jìn)蛙跳算法求解武器目標(biāo)分配問題

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

3.1 解的編碼

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

3.2 初始解的生成

蛙跳算法(SFLA)的初始解通常是隨機(jī)生成的,其多樣性和均勻性不可控,借鑒文獻(xiàn)[13]的思想,對(duì)初始解進(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)系等級(jí),假設(shè)某個(gè)個(gè)體不被其他任何個(gè)體支配,則該個(gè)體的非支配等級(jí)為1,將種群中所有非支配等級(jí)為1的個(gè)體挑選出來,剩下的個(gè)體再進(jìn)行一次非支配關(guān)系排序,挑選出來的非支配個(gè)體等級(jí)為2,依次類推,直到所有的個(gè)體都被賦予非支配等級(jí),其流程圖如圖1所示。

圖1 非支配等級(jí)排序

圖2 擁擠度因子算法流程

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

3.3 更新策略

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

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

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

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

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

每個(gè)目標(biāo)的威脅等級(jí)系數(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對(duì)算法進(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,對(duì)應(yīng)的最優(yōu)決策變量為

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

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

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

5 結(jié)束語

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