改進鏈式多種群遺傳算法的防空火力任務分配

唐俊林，張 棟，王孟陽，劉亮亮

(1.西北工業大學 航天學院，西安 710072；2.空天飛行器設計陜西省重點實驗室(西北工業大學)，西安 710072)

防空火力任務分配是防空指揮的重要環節，是決定作戰效果的關鍵因素之一[1]。其目的是最大化武器裝備作戰效能，尋求敵方目標逃脫概率最小的方案[2]。

目前的研究中，防空火力任務分配模型考慮的重要因素包括目標的威脅程度和火力單元對目標的殺傷概率。文獻[3]從分配控制條件、彈目相對距離和飛行時間3個方面，歸納了火力單元對目標的攔截可行性判斷邏輯。文獻[4]細化了防空火力任務分配通用模型，從多個方面評估目標威脅程度，構建殺傷區、發射區模型和單發導彈殺傷概率模型。因此，制定詳細的威脅程度評估方法和可攔截性判斷對防空火力任務分配的實際應用具有重要意義。

隨著計算機技術的發展，智能優化算法已經成為解決防空火力任務分配等組合優化問題的重要方法。除了遺傳算法、粒子群算法等經典算法之外，布谷鳥搜索算法[5]、合同網拍賣算法[6]和博弈論[7]等方法也可以用于求解任務分配問題。文獻[8]通過控制初始種群中變量的取值范圍和改進變異策略來提高搜索效率。文獻[9]提出非支配排序算法(NSGA-Ⅲ)，引入具有良好收斂性和分布性的參考點來指導進化。面對極大的計算復雜性，文獻[10]提出一種基于改進遺傳算法的元啟發式算法來改善隨機任務分配問題的求解。文獻[11]提出針對具體問題的種群初始化方法，重新定義了配對限制和選擇操作。文獻[12]提出一種基于遺傳算法的anytime算法，引入元級控制，來確定算法的停機時刻。文獻[13]提出多種群遷移遺傳算法，利用種群間的遷移機制代替選擇算子的篩選機制，并改進交叉和變異算子等操作。文獻[14]提出一種基于ER網絡的多種群遺傳算法，研究子種群網絡結構對優勢基因在子種群間傳播速度以及算法性能的影響。防空火力任務分配的實時性要求很高，響應過慢則可能貽誤戰機。傳統智能優化算法及其改進算法，在種群規模和迭代次數受限時并不能穩定找到全局最優解。

針對目前防空火力任務分配模型以及智能優化算法所面臨的問題，本文構建了一種改進的防空火力任務分配模型。模型細化目標威脅程度的評估方法，并將可攔截性約束條件簡化。此外，進一步提出鏈式多種群遺傳算法(Chainlike multi-population genetic algorithm, CMPGA)，運用鏈式多種群環、多樣性保持、分層選擇、去頂操作等策略，加快收斂速度并提高全局搜索能力。

1 防空火力任務分配模型

1.1 作戰場景與決策變量

為保護防御要地，在其周圍部署m個位置不同的火力單元。假定空情顯示有n個目標從各個方向襲來，我方需快速作出響應，將來襲目標分配給各火力單元，以化解敵方空襲威脅。防空火力任務分配的方案用矩陣D={dij},i∈1,2,…,m,j∈1,2,…,n描述,矩陣D的各個元素為

(1)

1.2 目標函數

最大化作戰效能的目標函數建立如下:

(2)

1.3 約束條件

防空火力任務分配考慮的約束條件如下：

1)每個火力單元最多分配μi個目標，μi為火力單元i的打擊通道數，即

(3)

2)每個目標最少分配1個火力單元，最多分配λj個火力單元，即

(4)

1.4 目標威脅程度模型

威脅程度的評估如下：

1)目標飛行高度威脅因子。當敵方來襲目標在低空出現時，攻擊意圖明顯，己方的防御時間短促，威脅程度顯著增強。目標飛行高度威脅因子為[15]

(5)

式中高度的臨界值hc=1 500 m，衰減參數k1=10-11。

2)目標飛行速度威脅因子。飛行速度越快的目標一定程度上擁有更強的機動能力和作戰能力，己方攔截更加困難，威脅程度也更大。目標飛行速度威脅因子為[15]

μv=1-e-αv

(6)

式中α=0.001 5。

3)目標射程威脅因子。在區域防空作戰中，來襲目標可能是飛機或者導彈。導彈的射程直接反映導彈的殺傷威力。短程、中程導彈射程短，殺傷力有限。遠程、洲際導彈搭載核彈頭，破環性極強。當目標類型為導彈時，目標射程威脅因子為[4]

(7)

式中L為導彈的射程，km。

4)目標距離威脅因子。目標距離己方防御要地中心的距離r也反映目標的威脅程度。目標距離己方防御要地中心的距離r越小，威脅程度越大。目標距離威脅因子為

(8)

式中rmax為己方相對于防御要地中心的最大可探測距離。

綜上所述，目標威脅系數由各威脅因子及其權重加權求和得到：

Wj=whμh+wvμv+wLμL+wrμr

(9)

式中wh、wv、wL、wr分別為目標飛行高度威脅因子、目標飛行速度威脅因子、目標射程威脅因子和目標距離威脅因子的權重，均由專家經驗給出。

1.5 可攔截性判斷模型

具體判斷過程如下：

1)若火力單元i不滿足對目標j的可攔截性條件，則令Pij=0。如此處理可將一些約束條件融入殺傷概率的計算中，有利于約束條件的簡化。目標可攔截性判斷如下[3]：如圖1所示，點A為目標的位置，點B為火力單元的位置，以點B為圓心的圓是火力單元的殺傷區。

圖1 火力單元與目標的相對位置Fig.1 Relative position of fire unit and target

①航路捷徑約束。航路捷徑LBC為目標速度矢量與火力單元的最短距離，即

LBC=LABsin∠EAB

(10)

火力單元無法攔截航路捷徑大于其殺傷半徑Ri的目標，即

LBC>Ri→Pij=0

(11)

②最大攔截速度約束。火力單元無法攔截速度超過其最大可攔截速度vmax i的目標，即

vj>vmax i→Pij=0

(12)

③目標飛離時間約束。火力單元無法攔截即將飛離其殺傷區的目標。若目標j的預估飛離時間TAE小于火力單元i的準備時間Tri和其防空導彈的預估飛行時間Tfi之和，則目標j不滿足火力單元i的攔截條件，即：

Tri+Tfi>TAE→Pij=0

(13)

(14)

(15)

式中：vj為目標j的飛行速度，vi為火力單元i攔截導彈的飛行速度。

④攔截高度約束。火力單元的可攔截高度應介于其殺傷區高低界之間，即:

hj

(16)

hj>himax→Pij=0

(17)

式中：hj為目標j的飛行高度，himin、himax分別為火力單元i的殺傷區低界與高界。

2)若火力單元i滿足對目標j的可攔截性條件，即航路捷徑約束、最大攔截速度約束、目標飛離時間約束、攔截高度約束、殺傷概率取經驗值Pij。

2 基于鏈式多種群遺傳算法的防空火力任務分配

針對上文所建防空火力任務分配模型，提出一種鏈式多種群遺傳算法(CMPGA)。首先提出傳統遺傳算法的改進措施，包括多樣性保持、分層選擇、去頂操作。在此基礎上提出鏈式多種群環結構，既讓多種群共享當前最優解，又一定程度上保留單個種群進化的獨立性。

2.1 改進型遺傳算法

2.1.1 編碼方式

采用二進制編碼，即表示防空火力任務分配方案的矩陣D={dij},i∈1,2,…,m,j∈1,2,…,n。

2.1.2 適應度評價

適應度表征個體的優劣程度。適應度越大，個體越優秀。適應度函數取目標函數的倒數:

(18)

2.1.3 分層選擇

按輪盤賭策略從父種群中選擇與父種群規模相同的N個個體，等待完成交叉變異操作后生成子種群。輪盤賭策略根據個體的適應度確定被選擇的概率，個體適應度越高，被選擇的概率越大。種群中適應度為f(Dk)的第k個個體被選擇的概率為

(19)

式中N為種群規模。

遺傳算法中，適應度相近的個體經過交叉變異后更有可能產生比父代優秀的子代個體，所以采用分層選擇策略能加快種群的進化速度。所分層數根據種群大小確定，以3層為例說明。除初代種群以外，父種群中的個體已按適應度從優到劣排列，可以直接采取如下操作：從父種群的0～N/2個體中選擇N/3個個體進入子種群，從父種群的N/2+1～N個體中選擇N/3個個體進入子種群，從整個父種群中選擇N/3個個體進入子種群。對父種群的分層如圖2所示。

圖2 種群分層Fig.2 Population stratification

2.1.4 單點交叉操作

對父代兩個任務分配矩陣的每一行執行單點交叉操作。對第i行，隨機生成區間(0,1)的數r1，若r1

圖3 交叉操作Fig.3 Cross operation

2.1.5 變異操作

對任務分配矩陣的每個基因位，以Pmu的變異概率將0置為1，或將1置為0。為了增強遺傳算法的局部尋優能力，每個基因位變異后都對任務分配矩陣進行沖突消解，并計算個體的適應度，若適應度大于該基因位變異前的適應度，則不對該個體后續的基因位執行變異操作。

2.1.6 多樣性保持策略

借鑒NSGA-Ⅱ的思想，將子種群與父種群合并，從中選擇結構不同的個體組成新的父種群[16]。將經過交叉變異的子種群和父種群合并，對合并種群的2N個個體按適應度從優到劣進行排序，依次選擇結構不同的N個個體組成新一代的父種群。

為避免迭代后期種群同質化嚴重，在合并種群中從優到劣依次選擇個體進入新父種群時，同一結構的個體最多只能有Nsi個進入新父種群。這使得新父種群中同一適應度的個體不超過Nsi，從而能持續維持種群的多樣性，降低算法陷入局部極值的概率。對合并種群的2N個個體進行排序后，結構相同的個體適應度也相同，往往集中在一起。每次從合并種群中將待選個體加入新父種群前，需計算新父種群中與當前個體適應度相同的個數，若小于Nsi時，將待選個體加入，若等于Nsi時，舍棄當前個體。當Nsi=2時，從合并種群中選擇個體的過程如圖4所示。

圖4 多樣性保持的選擇過程Fig.4 Selection process of diversity maintenance

2.1.7 去頂操作

在合并種群中從優到劣依次選擇個體進入新父種群前，需判斷合并種群的最優個體相較于前代是否改變。若最優個體連續Ga代未發生改變，說明該種群可能陷入了局部最優。為跳出局部最優，采用后退的思維方式，將已經搜尋到的一部分最優秀的個體刪除，即將局部最優解刪除，剩余個體繼續參與后續的遺傳操作，重新搜尋最優解。若最優個體連續Ga代未改變，跳過前面的Nj個個體，從第Nj+1個個體開始依次選擇個體加入新父種群；否則，從第1個個體開始選擇。若去頂操作后種群多樣性不足，生成隨機個體補全新父種群。當Nj=10時，對合并種群的去頂操作如圖5所示。

圖5 去頂操作Fig.5 Topping operation

2.2 基于CMPGA的防空火力任務分配

基于上述改進型遺傳算法，利用多種群并行搜索的思想提出CMPGA算法。一般多種群進化算法每次迭代完成后都會將當前最優解在所有種群范圍內共享[17]。這樣多種群間的信息共享過于頻繁，并不能充分發揮多種群的優勢。本文所提算法每隔數代才會出現當前最優解的傳遞，并且每次只有一個種群將移民算子傳遞給其后一個種群。當間隔代數達到Gr時，將種群Pf的當前最差解替換為種群Pl的當前最優解。

(20)

(21)

式中：G為當前迭代數,?·」為向下取整,Np為種群數；mod(·)為取余數。

以首尾相連的Np個種群為例，假設當前種群為Pi,i∈0,1,…,Np-1,間隔代數達到Gr時，將種群Pi+1的最差解替換為種群Pi的當前最優解；當間隔代數再次達到Gr時，將種群Pi+2的最差解替換為種群Pi+1的當前最優解，如此循環往復。當前種群為PNp-1時，其最優解傳遞給種群P0。當種群Pi將

最優解傳遞給種群Pi+1后，需要相隔Gr×(Np-1)代，才會接受到來自種群Pi-1的最優解。這樣既保留各種群自身進化的獨立性，也能適時共享其他種群的最優解。4個種群構成的鏈式環結構如圖6所示。

圖6 鏈式多種群環結構圖Fig.6 Structure of chainlike multi-population ring

在CMPGA算法中，種群數量的增加對性能的提升十分顯著。算法流程圖如圖7所示。

圖7 鏈式多種群遺傳算法流程圖Fig.7 Flow chart of chainlike multi-population genetic algorithm

基于CMPGA算法的防空火力任務分配具體步驟如下。

算法CMPGA算法求解任務分配問題

Step1分別隨機初始化各個種群P0,P1,…,PNp-1，并計算個體的適應度。

Step2若達到最大進化代數，輸出所有種群的全局最優解。否則，跳轉至step3。

Step3采用輪盤賭策略和分層選擇策略分別對各個種群執行選擇操作，生成待交叉變異、與父種群規模相同的子種群。

Step4分別對各個子種群執行交叉、變異操作。

Step5分別將各個子種群和對應的父種群合并，并對合并種群的個體按適應度從優到劣排序。

Step6分別從各個合并種群中選擇結構不同的N個個體組成新父種群。當種群最優解連續Ga代未變時，從合并種群的第Nj+1個個體開始依次選擇個體加入新父種群；否則，從合并種群的第1個個體開始依次選擇。

Step7當間隔代數達到Gr時，將種群Pf的當前最差解替換為種群Pl的當前最優解。當間隔代數未達到Gr時，不進行任何操作。跳轉至step2。

2.3 沖突消解策略

本文采用沖突消解策略以使算法獲得滿足約束條件的解，結構如圖8所示。

圖8 沖突消解Fig.8 Conflict resolution

為盡量不破壞個體的結構，沖突消解策略可分為：

3 仿真結果

為了驗證CMPGA算法的性能，本文選取3個標準測試函數，尋找它們的全局極小值。其后，在火力資源通道數大于來襲目標數時，對中等規模算例進行仿真，以驗證防空火力任務分配模型的有效性。

3.1 算法性能測試

采用3種標準單目標優化測試函數對CMPGA算法進行對比測試。

1)Schaffer函數。

(22)

-10≤x,y≤10

(23)

該函數有無數個極小值點，在(0,0)處取得最小值0，具有強烈振蕩的形態。

2)Shubert函數。

(24)

-10≤x,y≤10

(25)

此函數存在760個局部極小值，極難找到全局最優解，在(-1.425 13,0.800 32)處取得最小值-186.730 9。

3)Eggholder函數。

(26)

-512≤x,y≤512

(27)

此函數多峰值,在(x,y)=(512,404.231 9)處取得全局最小值-959.640 7。

針對以上3個標準測試函數，分別利用鏈式多種群遺傳算法(CMPGA)、多種群遺傳算法(Multi-population genetic algorithm,MPGA)[17]、遺傳算法(Genetic algorithm,GA)和二進制離散粒子群算法(Binary discrete particle swarm optimization,BDPSO)求解全局極小值，均采用二進制編碼和單點交叉策略，每種算法各運行100次，進行對比分析見表1～3。

由表1可知，CMPGA、MPGA、GA算法均能較為穩定地求得Schaffer函數的全局極小值，BDPSO算法容易陷入局部極值。由表2可知，CMPGA算法能較為穩定地求得Shubert函數的全局極小值，MPGA、BDPSO與GA算法均容易陷入局部極值。由表3可知，CMPGA算法仍能較為穩定地求得Eggholder函數的全局極小值，MPGA和GA算法性能次之。BDPSO算法容易陷入局部極值。由以上3個測試函數的求解可知，從收斂的快速性和結果的穩定性來看，CMPGA算法均能以較小的種群規模和進化代數，較高的概率尋得全局最優解，其性能明顯領先于MPGA、BDPSO和GA算法。

表1 4種算法求解Schaffer函數100次運行結果對比Tab.1 Comparison of results of 100 runs of four algorithms for solving Schaffer function

表2 4種算法求解Shubert函數100次運行結果對比Tab.2 Comparison of results of 100 runs of four algorithms for solving Shubert function

表3 4種算法求解Eggholder 函數100次運行結果對比Tab.3 Comparison of results of 100 runs of four algorithms for solving Eggholder function

3.2 仿真算例

假設某次防空作戰中，己方部署8個位置不同的火力單元。火力單元對目標的經驗殺傷概率由[0.5,1.0]的隨機數生成，計算目標威脅程度時，wh，wv，wL，wr均為0.25，己方防御中心位置為(0,0),其最大可探測距離rmax=90 000 m。各個火力單元及目標的參數見表4、5。

表4 火力單元參數Tab.4 Fire unit parameters

表5 目標參數Tab.5 Target parameters

3.3 仿真結果

防空火力任務分配問題的搜索空間隨目標和火力單元數量的增加而急劇增大。大多數文獻的仿真算例規模較小，易于求解。本文通過與二進制離散粒子群算法(BDPSO)、遺傳算法(GA)和多種群遺傳算法(MPGA)的對比，來體現CMPGA算法能以更大的概率快速搜尋到最優解。

CMPGA算法各參數取值為：最大進化代數200，種群數Np=5，種群規模N=80，共分為3層，交叉概率Pcro=0.9，變異概率Pmu=0.01，最大重復次數Nsi=1，傳遞間隔代數Gr=30，去頂代數Ga=65，去頂個數Nj=10。

BDPSO算法各參數取值為：最大進化代數500，粒子群規模SN1=500，速度慣性因子w=1.0，學習因子c1=2，學習因子c2=2。

GA算法為：最大進化代數500，遺傳種群規模SN2=500，交叉概率Pcro=0.6，變異概率Pmu=0.01。采用精英策略，將當代適應度排序前SN2/10個較優解直接復制到下一代，防止已搜尋到的最優解丟失。

MPGA算法為：最大進化代數500，種群數量3，各種群規模SN3=500，交叉概率Pcro=0.6，變異概率Pmu=0.01，采用上述精英策略。

4種算法各運行100次的結果見表6和如圖9所示。

表6 4種算法100次運行結果對比Tab.6 Comparison of results of 100 runs of four algorithms

圖9 4種算法100次仿真結果Fig.9 Simulation results of 100 runs of four algorithms

如表6和圖9可知，火力單元數大于目標數時，局部最優解較多，3種對比算法獲得最優解的概率均較低。本文所提CMPGA算法，以種群總規模400，200次的迭代仍有約97%的概率獲得全局最優。4種算法均求得此算例的最優解見表7。

表7 最優分配方案Tab.7 Optimal allocation scheme

為具體說明CMPGA算法快速收斂的性能，分別選取4種算法某次運行中目標函數的變化如圖10所示。

圖10 單次運行結果對比Fig.10 Comparison of single run results

由圖10可知，CMPGA的收斂速度與MPGA相當。BDPSO和GA的收斂速度較慢。4種算法的單次運行時長見表8。

表8 單次運行時長對比Tab.8 Comparison of single run duration

從單次運算時長來看，3種對比算法所需的種群規模和進化代數較大，運行時長較長。綜合考慮運算時長和尋優性能，CMPGA算法為首選。

仿真表明，本文所提的CMPGA算法，通過多種策略的結合，同時具有收斂快速和全局尋優能力強的優點，能夠以極高的概率搜尋到最優解。

4 結 論

1)本文提出改進的防空火力任務分配模型，詳細介紹目標威脅程度的計算，并將可攔截性判斷融入殺傷概率中，以簡化模型的約束條件。本文使用有效的沖突消解策略，盡可能少地破環個體結構，以保證算法易于尋優。

2)綜合運用鏈式多種群環、多樣性保持、分層選擇、去頂操作等策略，提出CMPGA算法，大幅提升遺傳算法的尋優性能。為驗證算法性能的優越性，仿真選取3個標準測試函數和中等規模的任務分配算例。仿真結果表明，算法快速收斂的同時能有效跳出局部極值。