基于量子分布估計(jì)算法的火力分配問題研究

張 毅， 楊秀霞， 周紹磊

(海軍航空工程學(xué)院控制工程系，山東煙臺 264001)

0 引言

火力分配問題是根據(jù)武器攻擊的任務(wù)，合理進(jìn)行目標(biāo)配對決策，并向武器裝訂相應(yīng)的決策指令，使攻擊效率最高，其屬于NP難問題。傳統(tǒng)的求解算法，如非線性網(wǎng)絡(luò)流法、搜索樹法等，都基于圖論搜索的思想，具有指數(shù)級的時間復(fù)雜度，當(dāng)武器及目標(biāo)數(shù)目增加時很難求解［1］。目前，一些學(xué)者采用智能優(yōu)化算法如遺傳算法［2］、粒子群算法［3－4］、蟻群算法［5］等對火力分配問題進(jìn)行了研究，但算法的收斂速度仍然較慢，且難以保證解的精度。為滿足實(shí)戰(zhàn)需求，只能降低最優(yōu)性要求，求得滿意解。針對這一問題，本文在綜合考慮武器作戰(zhàn)效能和防御效能的基礎(chǔ)上，建立了一種用于多武器對抗多目標(biāo)的火力分配模型，提出了基于量子分布估計(jì)算法的火力優(yōu)化分配方法，并引入一種適于問題求解的編碼方法，這種方法可以根據(jù)武器目標(biāo)的數(shù)目決定具體的編碼方式，同時將模型的約束條件與解的編碼結(jié)合到一起，提高了算法的運(yùn)算效率。分布估計(jì)算法以全局概率估計(jì)模型實(shí)現(xiàn)種群的進(jìn)化，其具有良好的全局優(yōu)化性能，且進(jìn)化速度比較快，而量子進(jìn)化算法的局部尋優(yōu)能力很強(qiáng)，能夠提高搜索精度［6］，本文提出的量子分布估計(jì)算法將兩種算法的優(yōu)點(diǎn)相結(jié)合，以提高算法的收斂速度及精度，同時給出了自適應(yīng)量子進(jìn)化操作算子，提出一種基于量子分布估計(jì)算法的火力分配問題求解方法。

1 火力分配的數(shù)學(xué)模型

1)戰(zhàn)術(shù)背景:假設(shè)有W個火力單位對T個目標(biāo)進(jìn)行打擊，每個火力單元只能打擊一個目標(biāo)，每個目標(biāo)可以分配多個火力單元，目標(biāo)特征用毀傷概率Kij描述，Kij表示分配第i個武器到第j個目標(biāo)的殺傷概率。

2)分配矩陣:用 R=(Rij)w×T描述，Rij為第 i個火力單元對第j個目標(biāo)的分配，0為不分配，1為分配。

3)毀傷價值:V(j)為第j個目標(biāo)將對打擊目標(biāo)產(chǎn)生的期望損傷值。

4)分配期望:最優(yōu)分配的目標(biāo)函數(shù)是使對目標(biāo)的摧毀價值指標(biāo)達(dá)到最大。

假設(shè)火力單元數(shù)目大于目標(biāo)數(shù)目，即W＞T，以最小化目標(biāo)對系統(tǒng)的損傷為目標(biāo)函數(shù)，要求所有的火力單元必須分配給目標(biāo)，每個目標(biāo)至少分配一個武器攻擊，則得到多火力單元任務(wù)分配模型(N)為

式(1)中，X表示可行的分配方案。

這是一個典型的組合優(yōu)化問題，且為0－1分配的NP難問題。對于模型(N)，可有(m+1)n種分配方案，在問題規(guī)模較大的情況下，采用枚舉法得到問題的最優(yōu)解是不現(xiàn)實(shí)的，因此，分配算法對求解的質(zhì)量和速度要求很高［5］。

2 基于量子分布估計(jì)算法的火力分配求解算法

2.1 量子進(jìn)化算法

目前量子計(jì)算理論與進(jìn)化算法相結(jié)合的量子進(jìn)化算法的研究引起越來越多的學(xué)者關(guān)注，并被成功地用于背包問題、數(shù)值優(yōu)化等多個領(lǐng)域［7－8］。量子進(jìn)化算法可看作是一類特殊的分布估計(jì)算法(Estimation of Distribution Algorithm，EDA)［9］，其采用量子比特概率幅來構(gòu)建概率模型，通過該模型對問題解空間中可能存在最優(yōu)解的區(qū)域進(jìn)行估計(jì)和描述，并指導(dǎo)搜索。與大多數(shù)EDA算法不同，量子進(jìn)化算法采用多個量子概率模型并行演化搜索，每個概率模型都可以作為一個獨(dú)立的搜索單元。在量子進(jìn)化算法中，概率模型的學(xué)習(xí)是否全面、充分，對算法的探索能力有著重要的影響。量子概率模型學(xué)習(xí)越充分，量子進(jìn)化算法對復(fù)雜優(yōu)化問題的尋優(yōu)能力可能越強(qiáng)。

一個量子位染色體由一個量子位串組成。如前面所述，一個量子位可以表示為一對復(fù)數(shù)，當(dāng)一個量子位染色體量子位長度為m時，它可以表示為

式(3)所描述的是解空間中各個解的取值概率分布，其作用相當(dāng)于EDA算法中的單變量概率模型。在量子力學(xué)中，量子比特的狀態(tài)還可用相角θ來表示，因此，式(3)所描述的量子概率模型可表示為

量子進(jìn)化算法實(shí)現(xiàn)的基本步驟如下:

1)設(shè)進(jìn)化代數(shù)t=0，對種群Q(t)進(jìn)行初始化;

2)由Q(t)的觀測狀態(tài)產(chǎn)生新的個體P(t)，并對P(t)進(jìn)行適應(yīng)度評價，將最優(yōu)解保存于個體B(t)中;

3)判斷終止條件是否滿足，若滿足，則輸出優(yōu)化結(jié)果，否則，令t=t+1，使用量子門更新種群Q(t)，然后轉(zhuǎn)移到步驟2)。

式中，α′i、β′i(i=1，2，…，n)表示采用量子旋轉(zhuǎn)門更新操作后量子位染色體的取值。采用式(5)的模型編碼，旋轉(zhuǎn)算子可簡化為

式中，Δθi表示量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度，其大小和方向一般由一個事先設(shè)計(jì)的調(diào)整策略決定，由查表獲得。在算法實(shí)現(xiàn)時需要多個條件判斷指令，且必須逐位計(jì)算，不方便以向量或矩陣為單位的算法實(shí)現(xiàn)。因此，本文采用文獻(xiàn)［10］中的方法計(jì)算Δθi，即

2.2 分布估計(jì)算法

分布估計(jì)算法也是一種概率種群進(jìn)化方法，其主要操作算子為種群的概率估計(jì)模型，省去了遺傳算法等優(yōu)化算法的交叉、變異等操作，因此進(jìn)化速度比較快。

標(biāo)準(zhǔn)分布估計(jì)算法的步驟為:

1)初始化種群P(t)和進(jìn)化代數(shù)t=0;

2)選擇優(yōu)勢群體構(gòu)建概率估計(jì)模型ρ;

3)根據(jù)概率估計(jì)模型ρ生成新種群;

4)算法終止條件判斷，如果滿足終止條件，則算法結(jié)束，并保存當(dāng)前的最優(yōu)解，否則繼續(xù)算法;

5)進(jìn)化代數(shù)增加，t=t+1，轉(zhuǎn)步驟2)。

可見，概率估計(jì)模型是EDA的核心，其通過概率估計(jì)模型來直接描述整個群體的進(jìn)化趨勢。但其是對生物進(jìn)化“宏觀”層面上的數(shù)學(xué)建模，對局部搜索能力較差，因此提出將EDA與量子進(jìn)化算法相結(jié)合的量子分布估計(jì)算法。

2.3 基于量子分布估計(jì)算法的火力分配問題求解

1)問題編碼。

在求解武器目標(biāo)分配問題的各種進(jìn)化算法中，可以采用以基因位表示武器所對應(yīng)的目標(biāo)來編碼，也可以采用分配給目標(biāo)的武器編號為編碼，由于武器數(shù)目W一般大于目標(biāo)數(shù)目T，因此采用前一種方式編碼。編碼時，根據(jù)武器數(shù)目W的最大值，對各武器設(shè)置二進(jìn)制基因位數(shù)。

問題解的表達(dá)形式如圖1所示，圖中，ti表示基因位。每一個個體由長度為m的0－1編碼表示，m=W*(int(lb W)+1)。

圖1 問題解的個體基因表達(dá)Fig.1 Expression of the solution individual

2)適應(yīng)度函數(shù)的確定。

由于費(fèi)用函數(shù)變化比較平緩，其對適應(yīng)值的貢獻(xiàn)值采用冪函數(shù)形式，即 f=f′n，設(shè) f′=C(X)(C(X)為費(fèi)用函數(shù))即n為大于1的冪函數(shù)定標(biāo)參數(shù)，則

3)個體基因位的更新概率。

算法的關(guān)鍵是計(jì)算各基因位的更新概率。采用包含m個分量的概率向量 p(tj)=［p(t1)，p(t2)，…，p(tm)］，表示某個體 xi(i=1，2，…，n)各基因位 tj的更新概率，為了充分利用EDA的全局搜索能力及量子進(jìn)化算法的局部尋優(yōu)能力，考慮其中的p(tj)(j=1，2，…，m)的算式為

式中:pE(tj)為EDA各基因位的分布估計(jì)概率;pQ(tj)為量子進(jìn)化算法中各基因位的更新概率，根據(jù)式(6)、式(7)得到;α(0＜α＜1)為調(diào)節(jié)因子。

根據(jù)上述設(shè)計(jì)，采用量子分布估計(jì)算法進(jìn)行火力分配問題優(yōu)化求解的步驟為:

1)初始化概率向量p(t);

2)對p(t)進(jìn)行隨機(jī)采樣，產(chǎn)生n個個體;

3)計(jì)算各個體的適應(yīng)值;

4)選擇最好的N個個體計(jì)算種群的分布估計(jì)概率pE(tj);

5)對特定個體，產(chǎn)生0～1之間的隨機(jī)數(shù)α，計(jì)算量子更新概率pQ(tj)，結(jié)合pE(tj)，利用式(9)進(jìn)行個體更新，并保留最優(yōu)個體;

6)判斷終止條件是否滿足，若滿足，則輸出優(yōu)化結(jié)果;否則，轉(zhuǎn)步驟2)。

3 基于量子分布估計(jì)算法的火力分配問題求解實(shí)例

對8個目標(biāo)、15個火力單元的系統(tǒng)進(jìn)行仿真，每個火力單元可單獨(dú)迎擊目標(biāo)，其中，迎擊武器的單發(fā)命中概率及目標(biāo)對財產(chǎn)的期望損傷值隨機(jī)給定，見表1及表2。分別采用分布估計(jì)算法(EDA)、量子進(jìn)化算法(QEA)及量子分布估計(jì)算法(QEDA)求解武器－目標(biāo)的分配，各算法均隨機(jī)運(yùn)行30次，統(tǒng)計(jì)結(jié)果見表3，最優(yōu)結(jié)果的進(jìn)化曲線列在圖2中。

圖2 QEA、EDA與QEDA的進(jìn)化曲線比較Fig.2 The evolution curves of QEA，EDA and QEDA

仿真試驗(yàn)中，參數(shù)的設(shè)定對求解影響很大，而本文提出的量子分布估計(jì)算法的需設(shè)置參數(shù)比較少，可減小參數(shù)設(shè)置對結(jié)果的影響。取種群數(shù)n=100，最大進(jìn)化代數(shù)G=100，最優(yōu)個體取N=40，初始時p(t)在0～1之間隨機(jī)產(chǎn)生。

從仿真結(jié)果的統(tǒng)計(jì)表2中可以看出，3種算法都收斂到了相同的最優(yōu)解，各目標(biāo)均有武器分配，有的目標(biāo)分配的武器數(shù)目多于1個。

由圖2可以看出，QEA的空間探索能力較強(qiáng)，EDA的全局進(jìn)化能力比較好，而本文提出的量子分布估計(jì)算法由于結(jié)合了二者的優(yōu)點(diǎn)，能充分利用進(jìn)化種群的全局信息及局部信息，對解空間能夠進(jìn)行充分搜索，因此其優(yōu)化性能很好，收斂速度最快，平均進(jìn)化代數(shù)大大減少，能最大限度減小財產(chǎn)的損失值，并且算法的調(diào)節(jié)參數(shù)少，易于控制。

表1 武器對目標(biāo)的損傷概率Table 1 Damage probability of the weapon to the target

表2 目標(biāo)對財產(chǎn)的期望損傷值Table 2 The expected demage value of the weapon to the target

表3 武器－目標(biāo)分配的仿真結(jié)果比較Table 3 Simulation results of the weapon-target assignment

4 結(jié)論

本文采用量子分布估計(jì)算法對火力分配問題進(jìn)行求解，其融合了分布估計(jì)算法的較強(qiáng)全局搜索能力及量子進(jìn)化算法適于局部尋優(yōu)的特點(diǎn)，提高了進(jìn)化效率。同時，本文采用了適合量子分布估計(jì)算法求解WTA問題的編碼方案及自適應(yīng)的量子進(jìn)化轉(zhuǎn)移算子，提高了算法的迭代效率和尋優(yōu)能力，仿真結(jié)果證明了算法的有效性。本文提出的算法中需要調(diào)節(jié)的參數(shù)較少，易于控制，可應(yīng)用于大規(guī)模的武器－目標(biāo)實(shí)時分配，另外，也可用于其他的組合優(yōu)化問題。

［1］SHIMA T，RASMUSSEN S.UAV cooperative decision and

control:Challenges and practical approaches［M］.Society for Industrial and Applied Mathematics，Philadelphia，2009.

［2］LU H Q，ZHANG H J，ZHANG X J，et al.An improved genetic algorithm for target assignment optimization of naval fleet air defense［C］//Proceedings of the 6th World Congression Intelligent Control and Automation，2006:3401－3405.

［3］高尚，楊靜宇.武器—目標(biāo)分配問題的粒子群優(yōu)化算法［J］.系統(tǒng)工程與電子技術(shù)，2005，27(7):1250－1252.

［4］陳華東，王樹宗，王航宇.基于混合粒子群算法的多平臺多武器火力分配研究［J］.系統(tǒng)工程與電子技術(shù)，2008，30(5):881－883.

［5］劉建新，宋以勝，盧厚清，等.改進(jìn)蟻群算法求解火力分配優(yōu)化［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識，2009，39(20):92－99.

［6］HAN K H，KIM J H.On the analysis of the quantuminspired evolutionary algorithm with a single individual［C］//2006 IEEE Congress on Evolutionary Computation，2006，7:9172－9179.

［7］王凌.量子進(jìn)化算法研究進(jìn)展［J］.控制與決策，2008，23(12):1321－1326.

［8］HAN K H，KIM J H.Quantum－inspired evolutionary algorithm for a class of combinatorial optimization［J］.IEEE Transactions on Evolutionary Computation，2002，6(6):580－593.

［9］PLATEL M D，SCHLIEBS S，KASABOV N.Quantuminspired evolutionary algorithm:A multimodel EDA［J］.IEEE Transactions on Evolutionary Computation，2009，13(6):1218－1232.

［10］譚立湘，郭立.基于全面學(xué)習(xí)的量子分布估計(jì)算法［J］.模式識別與人工智能，2010，23(3):314－319.