基于量子遺傳算法的火力分配

李 閃，王新宇，麻志強(qiáng)，衛(wèi)景寵，田 杰

（北方自動控制技術(shù)研究所，太原 030006）

0 引言

多目標(biāo)防空中的火力分配問題是防空作戰(zhàn)中的研究重點(diǎn)［1］。現(xiàn)今防空作戰(zhàn)的整體環(huán)境正朝著聯(lián)合防空的方向發(fā)展，在進(jìn)行防空火力分配時應(yīng)充分考慮多平臺、多火力單元之間相互協(xié)同的特點(diǎn)，針對來襲目標(biāo)的武器數(shù)量、威脅度以及武器特點(diǎn)，完成多點(diǎn)對多點(diǎn)的火力分配任務(wù)。因此，火力分配是一個離散且具有一定約束條件的規(guī)劃求解問題，此類問題屬于典型的NP（非確定多項式）問題［2］，此類問題的求解難點(diǎn)在于當(dāng)防空武器和來襲目標(biāo)數(shù)量增加時，其解空間會以指數(shù)形式增長。

當(dāng)前普遍使用的遺傳算法在應(yīng)對這種復(fù)雜優(yōu)化問題時經(jīng)常因選擇、交叉、變異參數(shù)選擇不當(dāng)，而出現(xiàn)難以收斂和局部極值、求解結(jié)果差異性大等問題。文獻(xiàn)［3］對遺傳算法的收斂速度進(jìn)行了優(yōu)化，但是未能解決結(jié)果穩(wěn)定性的問題，解算的最優(yōu)值有所下降。文獻(xiàn)［4］將模擬退火算法與遺傳算法結(jié)合具有較好的全局搜索能力，但是耗時較長。文獻(xiàn)［5］使用的NSGA-II 算法在低維多目標(biāo)優(yōu)化問題中具有優(yōu)勢，但不適用高維多目標(biāo)問題。文獻(xiàn)［6］提出的NLPCGA 算法對遺傳算法作出了優(yōu)化，但是未能從根本上解決對參數(shù)選擇的依賴問題。量子遺傳算法（quantum genetic algorithm，QGA）就是將量子態(tài)與遺傳編碼相結(jié)合［7］，用量子門代替遺傳算法中選擇、交叉、變異的更新方法，實(shí)現(xiàn)種群基因的進(jìn)化，從而達(dá)到優(yōu)化求解的目的。量子遺傳算法在解決此類問題時，可以只依賴目標(biāo)函數(shù)的適應(yīng)度值在概率引導(dǎo)下進(jìn)行全局自適應(yīng)搜索［8］，并不局限于問題的特性、優(yōu)化形式等因素，具有可靠的穩(wěn)定性。量子態(tài)是量子計算中的基本信息單元，量子計算利用量子態(tài)的疊加、糾纏等性質(zhì)，可以實(shí)現(xiàn)許多難以處理的經(jīng)典NP 問題，這種方法可以取得很好的優(yōu)化結(jié)果，可以擺脫分配求解時算法參數(shù)的選擇依賴問題。

本文在建立火力資源及約束的基礎(chǔ)上，以毀傷效益為評價標(biāo)準(zhǔn)建立了火力分配模型，并利用量子遺傳算法對模型求解，通過仿真實(shí)驗對量子遺傳算法在此類問題上的可行性進(jìn)行分析，并與遺傳算法仿真結(jié)果相比較，體現(xiàn)了該算法在解決此類問題上的可行性和有效性。

1 火力分配模型

1.1 火力分配流程

火力分配是防空作戰(zhàn)的重要環(huán)節(jié)，現(xiàn)代防空作戰(zhàn)已基本形成了遠(yuǎn)中近結(jié)合、軟硬多武器平臺協(xié)同作戰(zhàn)的運(yùn)用原則［9］。作戰(zhàn)過程中防空火力分配需根據(jù)戰(zhàn)場態(tài)勢進(jìn)行機(jī)動調(diào)整，并優(yōu)先打擊對我方保衛(wèi)對象威脅度較高的目標(biāo)。依據(jù)來襲目標(biāo)的威脅度和防空武器系統(tǒng)的射擊有利度，進(jìn)行火力分配，流程如圖1 所示。

圖1 火力分配流程Fig.1 Flow chart of firepower distribution

1.2 模型假設(shè)

假定在某次防空作戰(zhàn)中，我方共有多組防空武器參與攔截，防空武器系統(tǒng)分解后，共有u 個可控火力單元，攔截預(yù)警系統(tǒng)發(fā)現(xiàn)的n 批空中來襲目標(biāo)，每批次包含多個可攔截目標(biāo)，數(shù)量為v。我方防空武器集合D={d1，d2，…，du}，空中目標(biāo)集合T={t1，t2，…，tv}?？罩心繕?biāo)對我方保衛(wèi)目標(biāo)的威脅度為W={w1，w2，…，wv}，其中可認(rèn)為同批次內(nèi)的同類型目標(biāo)威脅度相同。

1.3 模型建立

在對防空火力單元進(jìn)行分配前應(yīng)考慮火力單元的約束條件，建立其對空中目標(biāo)的約束向量Ri={ri1，ri2，…，riv}，Ri（i=1，2，…，u）表示防空武器第i 個火力單元對每個空中目標(biāo)的約束向量，火力單元對空中目標(biāo)的約束矩陣R：

Ri中元素均為0 或1 的二值變量，取值考慮該火力單元對某個空中目標(biāo)的狀態(tài)約束，可以分配為1，不可分配為0，如資源約束（已消耗為0，未消耗為1）、轉(zhuǎn)火時間（火力單元的轉(zhuǎn)火時間在分配環(huán)節(jié)時間要求取值1，不滿足取值0）、故障約束（火力單元狀態(tài)正常取值為1，故障狀態(tài)取值0）。

約束矩陣R 表征了火力單元對空中目標(biāo)的分配是否有效，只有滿足所有約束時，火力分配的結(jié)果才有意義。在火力分配前可根據(jù)武器單元狀態(tài)靈活調(diào)整約束矩陣。

針對來襲目標(biāo)，作出火力分配，火力分配決策矩陣Xf為：

期望獲得目標(biāo)毀傷的收益最大，目標(biāo)毀傷函數(shù)如式（1）所示。

式（1）中，qij為第i 個防空火力單元對第j 個空中來襲目標(biāo)的射擊有利度。

為實(shí)現(xiàn)最大限度攔截來襲目標(biāo)，需要確定模型的約束條件。多組防空武器系統(tǒng)分解為最小火力單元之后，每個火力單元只能分配一個目標(biāo)，在決策矩陣中體現(xiàn)為：

其取值由約束矩陣確定，如式（3）。若當(dāng)前某個火力單元對所有目標(biāo)均不滿足射擊條件，則退出此次分配。

面對空中來襲目標(biāo)時需保證我方最少有一個防空火力單元被分配用于攔截該目標(biāo)的襲擊，在決策矩陣中體現(xiàn)為：

在實(shí)際情況中，應(yīng)根據(jù)當(dāng)前時刻火力單元對空中目標(biāo)的狀態(tài)，隨時調(diào)整約束矩陣R。這樣可以在火力分配的同時充分考慮單個火力單元的狀態(tài)。

綜上所述：

可以看出多目標(biāo)火力分配是一個有條件約束的非線性混合整數(shù)多解尋優(yōu)問題，相比一般的非線性多解尋優(yōu)問題，對解算算法有著更高的要求。

2 量子遺傳算法的實(shí)現(xiàn)

運(yùn)用量子遺傳算法對防空火力規(guī)劃進(jìn)行求解，與遺傳算法的解算流程不同，量子遺傳算法在個體的編碼方式上采用量子比特編碼，在種群的進(jìn)化上利用量子門更新種群。

2.1 量子比特編碼

在量子遺傳算法中，引入量子比特來完成基因的存儲和表達(dá)。量子比特是量子信息中的概念，它與經(jīng)典比特不同，是因為它可以在同一時刻處于兩個狀態(tài)的疊加中［10］。一個兩態(tài)的基因使用一個量子比特編碼則有：

α 與β 是概率幅常數(shù)且取值滿足式（7）。

φ 不再表達(dá)一個確定的信息，可以為“0”態(tài)也可以為“1”態(tài)，成為一個擁有表達(dá)二者可能的信息。

對多目標(biāo)的火力分配這一數(shù)學(xué)模型，則需要引入多量子比特的編碼。因為空中目標(biāo)具有多批次、多數(shù)量的特點(diǎn)，每個防空火力單元的打擊決策也具有多種可能。使用n 個量子比特編碼對種群中1 個個體的m 個參數(shù)的基因進(jìn)行編碼：

使用量子比特編碼的染色體可認(rèn)為是多個狀態(tài)的疊加，具有表達(dá)所有基因的可能性，對該基因的任意一個操作會影響到其所表示的所有可能信息，因此，與經(jīng)典遺傳算法相比可以獲得更好的多樣性特征。隨著種群的不斷演化，|α|2或|β|2會趨于0或1，最終收斂到一個確定狀態(tài)。

2.2 量子旋轉(zhuǎn)門更新

2.2.1 量子旋轉(zhuǎn)門

量子門是算法中實(shí)現(xiàn)演化的重要步驟。量子門的選擇直接決定了種群能否演化成功和演化的方向［11］。根據(jù)火力分配的計算特點(diǎn)，這里選擇量子旋轉(zhuǎn)門作為種群的進(jìn)化策略。θi為旋轉(zhuǎn)角，則量子旋轉(zhuǎn)門的調(diào)整操作為：

更新方法：

［αiβi］T是第i 個量子比特在經(jīng)過量子旋轉(zhuǎn)門操作前的概率幅常數(shù)，其經(jīng)過更新后：

2.2.2 更新方法

先調(diào)整策略，確定旋轉(zhuǎn)角θi，在對當(dāng)前個體u 進(jìn)行更新時需要對比當(dāng)前種群中最優(yōu)個體best 確定旋轉(zhuǎn)角方向s（αi，βi）。計算當(dāng)前個體測量值的適應(yīng)度f（u）與當(dāng)前種群中最優(yōu)個體的適應(yīng)度f（best）。如果f（u）＞f（best）則改變u 中的對應(yīng)的量子比特，引導(dǎo)概率幅常數(shù)αi，βi向著有利于個體u 產(chǎn)生的方向進(jìn)化，如果f（u）＜f（best）同樣改變u 中對應(yīng)的量子比特，引導(dǎo)概率幅常數(shù)αi，βi向著有利于個體best 產(chǎn)生的方向進(jìn)化。

2.3 量子遺傳算法的實(shí)現(xiàn)流程

量子遺傳算法計算步驟：

1）將防空火力單元對空中目標(biāo)的火力決策矩陣作為種群個體，隨機(jī)生成以多個量子比特為編碼的染色體，并對染色體中的全部基因進(jìn)行初始化，種群中個體的全部基因（αi，βi）均初始化為（，），同時按照種群大小生成初始化種群Q（t0）。這樣生成的初始種群的基因表達(dá)每個可能狀態(tài)的概率都是相等的。

2）利用測量函數(shù)對初始種群的所有個體進(jìn)行一次測量，得出一組解，它不是火力分配的決策矩陣而是一個長度為n 的二進(jìn)制編碼P={p1，p1，…，pn}，其中，pj是該代種群中的第j 個個體的測量值。然后進(jìn)行適應(yīng)度評估并找出最佳適應(yīng)度個體，以此作為下一代種群的進(jìn)化方向。

3）算法開始循環(huán)迭代，在迭代中，每次都需要對種群進(jìn)行測量以得出一組解P（t）并計算相應(yīng)的適應(yīng)度值，利用量子旋轉(zhuǎn)門和旋轉(zhuǎn)角方向調(diào)整進(jìn)化方向，使種群的解不斷向最優(yōu)解收斂。

算法實(shí)現(xiàn)流程如圖2 所示。

圖2 量子遺傳算法實(shí)現(xiàn)流程Fig.2 Implementation flow chart of quantum genetic algorithm

3 仿真結(jié)果及分析

假設(shè)我方偵察預(yù)警系統(tǒng)某次偵測到敵方有3批次空中目標(biāo)，每批次包含2 個同類型空中武器。我方在來襲方向的防御地帶上部署的防空武器系統(tǒng)經(jīng)分解后有10 個火力打擊單元?？找u武器對我方保衛(wèi)目標(biāo)的威脅度為：

各火力單元對空中目標(biāo)的射擊有利度為：

利用量子遺傳算法進(jìn)行火力分配，參數(shù)設(shè)置種群規(guī)模為40，進(jìn)化迭代次數(shù)為200。當(dāng)前個體基因的旋轉(zhuǎn)角和旋轉(zhuǎn)方向由其與最優(yōu)個體適應(yīng)度值的大小確定，量子旋轉(zhuǎn)門的旋轉(zhuǎn)角θi=Δθi·s（αi，βi），旋轉(zhuǎn)角度Δθi與方向s（αi，βi）的調(diào)整策略使用文獻(xiàn)［12］所提出的通用調(diào)整策略，如表1 所示。

表1 旋轉(zhuǎn)角調(diào)整策略Table 1 Adjustment strategy of rotation angle

使用式（5）所提出模型，以最大毀傷收益為目標(biāo)，火力單元對空中目標(biāo)的約束矩陣取R，得到火力決策矩陣X：

由決策矩陣，此次火力分配結(jié)果如表2 所示。

表2 火力分配結(jié)果Table 2 Fire distribution results

最大毀傷收益（最優(yōu)適應(yīng)度值）FQ=2.783 2，最優(yōu)適應(yīng)度值的收斂曲線如圖3 所示，即使陷入局部最優(yōu)之后，經(jīng)過一定次數(shù)迭代仍然可以跳出局部最優(yōu)。

圖3 最優(yōu)適應(yīng)度值的收斂曲線Fig.3 Comparison of optimal values of two kinds of algorithms

使用量子遺傳算法和遺傳算法分別求解50次，遺傳算法變異概率設(shè)置為0.1，其余參數(shù)均設(shè)置迭代次數(shù)100、種群規(guī)模50。計算最優(yōu)適應(yīng)度值的均值、極差和標(biāo)準(zhǔn)差，比較兩種算法的適用性和穩(wěn)定性，比較結(jié)果如表3 所示。

表3 兩種算法最優(yōu)值比較Table 3 Comparison of optimal values of two kinds of algorithms

由量子遺傳算法的火力分配結(jié)果可以看出，量子遺傳算法適用于解決多目標(biāo)防空的火力分配問題，并且與遺傳算法相比最優(yōu)適應(yīng)度的均值有所提升，同時保持極差和標(biāo)準(zhǔn)差較小。量子遺傳算法的分配結(jié)果與遺傳算法相比，在保持毀傷收益增加的同時還可以取得更好的穩(wěn)定性，避免某次分配結(jié)果極差的情況出現(xiàn)，體現(xiàn)了該算法的適用性、優(yōu)越性和穩(wěn)定性。

4 結(jié)論

針對空中目標(biāo)進(jìn)行火力分配時，將各平臺防空武器系統(tǒng)分解為可規(guī)劃的最小火力單元，利用火力單元對空中目標(biāo)的狀態(tài)約束矩陣加以限制，可以兼顧多武器系統(tǒng)的武器特點(diǎn)和使用情況，并且以最大毀傷收益為目標(biāo)函數(shù)，建立了多目標(biāo)的火力分配模型，針對遺傳算法的不足引入量子遺傳算法對模型進(jìn)行解算。為解決多武器平臺聯(lián)合防空作戰(zhàn)中對空中目標(biāo)的火力分配問題提供了一種新的解決辦法。仿真結(jié)果表明，量子遺傳算法適用于火力分配模型的解算，并且與遺傳算法相比，在毀傷收益上有一定程度的提升，在算法的穩(wěn)定性上也有較大幅度的改善，可以解決求解時算法參數(shù)的選擇依賴問題。