改進(jìn)鏈?zhǔn)蕉喾N群遺傳算法的防空火力任務(wù)分配

唐俊林，張 棟，王孟陽(yáng)，劉亮亮

(1.西北工業(yè)大學(xué) 航天學(xué)院，西安 710072；2.空天飛行器設(shè)計(jì)陜西省重點(diǎn)實(shí)驗(yàn)室(西北工業(yè)大學(xué))，西安 710072)

防空火力任務(wù)分配是防空指揮的重要環(huán)節(jié)，是決定作戰(zhàn)效果的關(guān)鍵因素之一[1]。其目的是最大化武器裝備作戰(zhàn)效能，尋求敵方目標(biāo)逃脫概率最小的方案[2]。

目前的研究中，防空火力任務(wù)分配模型考慮的重要因素包括目標(biāo)的威脅程度和火力單元對(duì)目標(biāo)的殺傷概率。文獻(xiàn)[3]從分配控制條件、彈目相對(duì)距離和飛行時(shí)間3個(gè)方面，歸納了火力單元對(duì)目標(biāo)的攔截可行性判斷邏輯。文獻(xiàn)[4]細(xì)化了防空火力任務(wù)分配通用模型，從多個(gè)方面評(píng)估目標(biāo)威脅程度，構(gòu)建殺傷區(qū)、發(fā)射區(qū)模型和單發(fā)導(dǎo)彈殺傷概率模型。因此，制定詳細(xì)的威脅程度評(píng)估方法和可攔截性判斷對(duì)防空火力任務(wù)分配的實(shí)際應(yīng)用具有重要意義。

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

針對(duì)目前防空火力任務(wù)分配模型以及智能優(yōu)化算法所面臨的問(wèn)題，本文構(gòu)建了一種改進(jìn)的防空火力任務(wù)分配模型。模型細(xì)化目標(biāo)威脅程度的評(píng)估方法，并將可攔截性約束條件簡(jiǎn)化。此外，進(jìn)一步提出鏈?zhǔn)蕉喾N群遺傳算法(Chainlike multi-population genetic algorithm, CMPGA)，運(yùn)用鏈?zhǔn)蕉喾N群環(huán)、多樣性保持、分層選擇、去頂操作等策略，加快收斂速度并提高全局搜索能力。

1 防空火力任務(wù)分配模型

1.1 作戰(zhàn)場(chǎng)景與決策變量

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

(1)

1.2 目標(biāo)函數(shù)

最大化作戰(zhàn)效能的目標(biāo)函數(shù)建立如下:

(2)

1.3 約束條件

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

1)每個(gè)火力單元最多分配μi個(gè)目標(biāo)，μi為火力單元i的打擊通道數(shù)，即

(3)

2)每個(gè)目標(biāo)最少分配1個(gè)火力單元，最多分配λj個(gè)火力單元，即

(4)

1.4 目標(biāo)威脅程度模型

威脅程度的評(píng)估如下：

1)目標(biāo)飛行高度威脅因子。當(dāng)敵方來(lái)襲目標(biāo)在低空出現(xiàn)時(shí)，攻擊意圖明顯，己方的防御時(shí)間短促，威脅程度顯著增強(qiáng)。目標(biāo)飛行高度威脅因子為[15]

(5)

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

2)目標(biāo)飛行速度威脅因子。飛行速度越快的目標(biāo)一定程度上擁有更強(qiáng)的機(jī)動(dòng)能力和作戰(zhàn)能力，己方攔截更加困難，威脅程度也更大。目標(biāo)飛行速度威脅因子為[15]

μv=1-e-αv

(6)

式中α=0.001 5。

3)目標(biāo)射程威脅因子。在區(qū)域防空作戰(zhàn)中，來(lái)襲目標(biāo)可能是飛機(jī)或者導(dǎo)彈。導(dǎo)彈的射程直接反映導(dǎo)彈的殺傷威力。短程、中程導(dǎo)彈射程短，殺傷力有限。遠(yuǎn)程、洲際導(dǎo)彈搭載核彈頭，破環(huán)性極強(qiáng)。當(dāng)目標(biāo)類型為導(dǎo)彈時(shí)，目標(biāo)射程威脅因子為[4]

(7)

式中L為導(dǎo)彈的射程，km。

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

(8)

式中rmax為己方相對(duì)于防御要地中心的最大可探測(cè)距離。

綜上所述，目標(biāo)威脅系數(shù)由各威脅因子及其權(quán)重加權(quán)求和得到：

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

(9)

式中wh、wv、wL、wr分別為目標(biāo)飛行高度威脅因子、目標(biāo)飛行速度威脅因子、目標(biāo)射程威脅因子和目標(biāo)距離威脅因子的權(quán)重，均由專家經(jīng)驗(yàn)給出。

1.5 可攔截性判斷模型

具體判斷過(guò)程如下：

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

圖1 火力單元與目標(biāo)的相對(duì)位置Fig.1 Relative position of fire unit and target

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

LBC=LABsin∠EAB

(10)

火力單元無(wú)法攔截航路捷徑大于其殺傷半徑Ri的目標(biāo)，即

LBC>Ri→Pij=0

(11)

②最大攔截速度約束?；鹆卧獰o(wú)法攔截速度超過(guò)其最大可攔截速度vmax i的目標(biāo)，即

vj>vmax i→Pij=0

(12)

③目標(biāo)飛離時(shí)間約束?；鹆卧獰o(wú)法攔截即將飛離其殺傷區(qū)的目標(biāo)。若目標(biāo)j的預(yù)估飛離時(shí)間TAE小于火力單元i的準(zhǔn)備時(shí)間Tri和其防空導(dǎo)彈的預(yù)估飛行時(shí)間Tfi之和，則目標(biāo)j不滿足火力單元i的攔截條件，即：

Tri+Tfi>TAE→Pij=0

(13)

(14)

(15)

式中：vj為目標(biāo)j的飛行速度，vi為火力單元i攔截導(dǎo)彈的飛行速度。

④攔截高度約束?；鹆卧目蓴r截高度應(yīng)介于其殺傷區(qū)高低界之間，即:

hj

(16)

hj>himax→Pij=0

(17)

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

2)若火力單元i滿足對(duì)目標(biāo)j的可攔截性條件，即航路捷徑約束、最大攔截速度約束、目標(biāo)飛離時(shí)間約束、攔截高度約束、殺傷概率取經(jīng)驗(yàn)值Pij。

2 基于鏈?zhǔn)蕉喾N群遺傳算法的防空火力任務(wù)分配

針對(duì)上文所建防空火力任務(wù)分配模型，提出一種鏈?zhǔn)蕉喾N群遺傳算法(CMPGA)。首先提出傳統(tǒng)遺傳算法的改進(jìn)措施，包括多樣性保持、分層選擇、去頂操作。在此基礎(chǔ)上提出鏈?zhǔn)蕉喾N群環(huán)結(jié)構(gòu)，既讓多種群共享當(dāng)前最優(yōu)解，又一定程度上保留單個(gè)種群進(jìn)化的獨(dú)立性。

2.1 改進(jìn)型遺傳算法

2.1.1 編碼方式

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

2.1.2 適應(yīng)度評(píng)價(jià)

適應(yīng)度表征個(gè)體的優(yōu)劣程度。適應(yīng)度越大，個(gè)體越優(yōu)秀。適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù):

(18)

2.1.3 分層選擇

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

(19)

式中N為種群規(guī)模。

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

圖2 種群分層Fig.2 Population stratification

2.1.4 單點(diǎn)交叉操作

對(duì)父代兩個(gè)任務(wù)分配矩陣的每一行執(zhí)行單點(diǎn)交叉操作。對(duì)第i行，隨機(jī)生成區(qū)間(0,1)的數(shù)r1，若r1

圖3 交叉操作Fig.3 Cross operation

2.1.5 變異操作

對(duì)任務(wù)分配矩陣的每個(gè)基因位，以Pmu的變異概率將0置為1，或?qū)?置為0。為了增強(qiáng)遺傳算法的局部尋優(yōu)能力，每個(gè)基因位變異后都對(duì)任務(wù)分配矩陣進(jìn)行沖突消解，并計(jì)算個(gè)體的適應(yīng)度，若適應(yīng)度大于該基因位變異前的適應(yīng)度，則不對(duì)該個(gè)體后續(xù)的基因位執(zhí)行變異操作。

2.1.6 多樣性保持策略

借鑒NSGA-Ⅱ的思想，將子種群與父種群合并，從中選擇結(jié)構(gòu)不同的個(gè)體組成新的父種群[16]。將經(jīng)過(guò)交叉變異的子種群和父種群合并，對(duì)合并種群的2N個(gè)個(gè)體按適應(yīng)度從優(yōu)到劣進(jìn)行排序，依次選擇結(jié)構(gòu)不同的N個(gè)個(gè)體組成新一代的父種群。

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

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

2.1.7 去頂操作

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

圖5 去頂操作Fig.5 Topping operation

2.2 基于CMPGA的防空火力任務(wù)分配

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

(20)

(21)

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

以首尾相連的Np個(gè)種群為例，假設(shè)當(dāng)前種群為Pi,i∈0,1,…,Np-1,間隔代數(shù)達(dá)到Gr時(shí)，將種群Pi+1的最差解替換為種群Pi的當(dāng)前最優(yōu)解；當(dāng)間隔代數(shù)再次達(dá)到Gr時(shí)，將種群Pi+2的最差解替換為種群Pi+1的當(dāng)前最優(yōu)解，如此循環(huán)往復(fù)。當(dāng)前種群為PNp-1時(shí)，其最優(yōu)解傳遞給種群P0。當(dāng)種群Pi將

最優(yōu)解傳遞給種群Pi+1后，需要相隔Gr×(Np-1)代，才會(huì)接受到來(lái)自種群Pi-1的最優(yōu)解。這樣既保留各種群自身進(jìn)化的獨(dú)立性，也能適時(shí)共享其他種群的最優(yōu)解。4個(gè)種群構(gòu)成的鏈?zhǔn)江h(huán)結(jié)構(gòu)如圖6所示。

圖6 鏈?zhǔn)蕉喾N群環(huán)結(jié)構(gòu)圖Fig.6 Structure of chainlike multi-population ring

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

圖7 鏈?zhǔn)蕉喾N群遺傳算法流程圖Fig.7 Flow chart of chainlike multi-population genetic algorithm

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

算法CMPGA算法求解任務(wù)分配問(wèn)題

Step1分別隨機(jī)初始化各個(gè)種群P0,P1,…,PNp-1，并計(jì)算個(gè)體的適應(yīng)度。

Step2若達(dá)到最大進(jìn)化代數(shù)，輸出所有種群的全局最優(yōu)解。否則，跳轉(zhuǎn)至step3。

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

Step4分別對(duì)各個(gè)子種群執(zhí)行交叉、變異操作。

Step5分別將各個(gè)子種群和對(duì)應(yīng)的父種群合并，并對(duì)合并種群的個(gè)體按適應(yīng)度從優(yōu)到劣排序。

Step6分別從各個(gè)合并種群中選擇結(jié)構(gòu)不同的N個(gè)個(gè)體組成新父種群。當(dāng)種群最優(yōu)解連續(xù)Ga代未變時(shí)，從合并種群的第Nj+1個(gè)個(gè)體開始依次選擇個(gè)體加入新父種群；否則，從合并種群的第1個(gè)個(gè)體開始依次選擇。

Step7當(dāng)間隔代數(shù)達(dá)到Gr時(shí)，將種群Pf的當(dāng)前最差解替換為種群Pl的當(dāng)前最優(yōu)解。當(dāng)間隔代數(shù)未達(dá)到Gr時(shí)，不進(jìn)行任何操作。跳轉(zhuǎn)至step2。

2.3 沖突消解策略

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

圖8 沖突消解Fig.8 Conflict resolution

為盡量不破壞個(gè)體的結(jié)構(gòu)，沖突消解策略可分為：

3 仿真結(jié)果

為了驗(yàn)證CMPGA算法的性能，本文選取3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，尋找它們的全局極小值。其后，在火力資源通道數(shù)大于來(lái)襲目標(biāo)數(shù)時(shí)，對(duì)中等規(guī)模算例進(jìn)行仿真，以驗(yàn)證防空火力任務(wù)分配模型的有效性。

3.1 算法性能測(cè)試

采用3種標(biāo)準(zhǔn)單目標(biāo)優(yōu)化測(cè)試函數(shù)對(duì)CMPGA算法進(jìn)行對(duì)比測(cè)試。

1)Schaffer函數(shù)。

(22)

-10≤x,y≤10

(23)

該函數(shù)有無(wú)數(shù)個(gè)極小值點(diǎn)，在(0,0)處取得最小值0，具有強(qiáng)烈振蕩的形態(tài)。

2)Shubert函數(shù)。

(24)

-10≤x,y≤10

(25)

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

3)Eggholder函數(shù)。

(26)

-512≤x,y≤512

(27)

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

針對(duì)以上3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，分別利用鏈?zhǔn)蕉喾N群遺傳算法(CMPGA)、多種群遺傳算法(Multi-population genetic algorithm,MPGA)[17]、遺傳算法(Genetic algorithm,GA)和二進(jìn)制離散粒子群算法(Binary discrete particle swarm optimization,BDPSO)求解全局極小值，均采用二進(jìn)制編碼和單點(diǎn)交叉策略，每種算法各運(yùn)行100次，進(jìn)行對(duì)比分析見表1～3。

由表1可知，CMPGA、MPGA、GA算法均能較為穩(wěn)定地求得Schaffer函數(shù)的全局極小值，BDPSO算法容易陷入局部極值。由表2可知，CMPGA算法能較為穩(wěn)定地求得Shubert函數(shù)的全局極小值，MPGA、BDPSO與GA算法均容易陷入局部極值。由表3可知，CMPGA算法仍能較為穩(wěn)定地求得Eggholder函數(shù)的全局極小值，MPGA和GA算法性能次之。BDPSO算法容易陷入局部極值。由以上3個(gè)測(cè)試函數(shù)的求解可知，從收斂的快速性和結(jié)果的穩(wěn)定性來(lái)看，CMPGA算法均能以較小的種群規(guī)模和進(jìn)化代數(shù)，較高的概率尋得全局最優(yōu)解，其性能明顯領(lǐng)先于MPGA、BDPSO和GA算法。

表1 4種算法求解Schaffer函數(shù)100次運(yùn)行結(jié)果對(duì)比Tab.1 Comparison of results of 100 runs of four algorithms for solving Schaffer function

表2 4種算法求解Shubert函數(shù)100次運(yùn)行結(jié)果對(duì)比Tab.2 Comparison of results of 100 runs of four algorithms for solving Shubert function

表3 4種算法求解Eggholder 函數(shù)100次運(yùn)行結(jié)果對(duì)比Tab.3 Comparison of results of 100 runs of four algorithms for solving Eggholder function

3.2 仿真算例

假設(shè)某次防空作戰(zhàn)中，己方部署8個(gè)位置不同的火力單元?；鹆卧獙?duì)目標(biāo)的經(jīng)驗(yàn)殺傷概率由[0.5,1.0]的隨機(jī)數(shù)生成，計(jì)算目標(biāo)威脅程度時(shí)，wh，wv，wL，wr均為0.25，己方防御中心位置為(0,0),其最大可探測(cè)距離rmax=90 000 m。各個(gè)火力單元及目標(biāo)的參數(shù)見表4、5。

表4 火力單元參數(shù)Tab.4 Fire unit parameters

表5 目標(biāo)參數(shù)Tab.5 Target parameters

3.3 仿真結(jié)果

防空火力任務(wù)分配問(wèn)題的搜索空間隨目標(biāo)和火力單元數(shù)量的增加而急劇增大。大多數(shù)文獻(xiàn)的仿真算例規(guī)模較小，易于求解。本文通過(guò)與二進(jìn)制離散粒子群算法(BDPSO)、遺傳算法(GA)和多種群遺傳算法(MPGA)的對(duì)比，來(lái)體現(xiàn)CMPGA算法能以更大的概率快速搜尋到最優(yōu)解。

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

BDPSO算法各參數(shù)取值為：最大進(jìn)化代數(shù)500，粒子群規(guī)模SN1=500，速度慣性因子w=1.0，學(xué)習(xí)因子c1=2，學(xué)習(xí)因子c2=2。

GA算法為：最大進(jìn)化代數(shù)500，遺傳種群規(guī)模SN2=500，交叉概率Pcro=0.6，變異概率Pmu=0.01。采用精英策略，將當(dāng)代適應(yīng)度排序前SN2/10個(gè)較優(yōu)解直接復(fù)制到下一代，防止已搜尋到的最優(yōu)解丟失。

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

4種算法各運(yùn)行100次的結(jié)果見表6和如圖9所示。

表6 4種算法100次運(yùn)行結(jié)果對(duì)比Tab.6 Comparison of results of 100 runs of four algorithms

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

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

表7 最優(yōu)分配方案Tab.7 Optimal allocation scheme

為具體說(shuō)明CMPGA算法快速收斂的性能，分別選取4種算法某次運(yùn)行中目標(biāo)函數(shù)的變化如圖10所示。

圖10 單次運(yùn)行結(jié)果對(duì)比Fig.10 Comparison of single run results

由圖10可知，CMPGA的收斂速度與MPGA相當(dāng)。BDPSO和GA的收斂速度較慢。4種算法的單次運(yùn)行時(shí)長(zhǎng)見表8。

表8 單次運(yùn)行時(shí)長(zhǎng)對(duì)比Tab.8 Comparison of single run duration

從單次運(yùn)算時(shí)長(zhǎng)來(lái)看，3種對(duì)比算法所需的種群規(guī)模和進(jìn)化代數(shù)較大，運(yùn)行時(shí)長(zhǎng)較長(zhǎng)。綜合考慮運(yùn)算時(shí)長(zhǎng)和尋優(yōu)性能，CMPGA算法為首選。

仿真表明，本文所提的CMPGA算法，通過(guò)多種策略的結(jié)合，同時(shí)具有收斂快速和全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)，能夠以極高的概率搜尋到最優(yōu)解。

4 結(jié) 論

1)本文提出改進(jìn)的防空火力任務(wù)分配模型，詳細(xì)介紹目標(biāo)威脅程度的計(jì)算，并將可攔截性判斷融入殺傷概率中，以簡(jiǎn)化模型的約束條件。本文使用有效的沖突消解策略，盡可能少地破環(huán)個(gè)體結(jié)構(gòu)，以保證算法易于尋優(yōu)。

2)綜合運(yùn)用鏈?zhǔn)蕉喾N群環(huán)、多樣性保持、分層選擇、去頂操作等策略，提出CMPGA算法，大幅提升遺傳算法的尋優(yōu)性能。為驗(yàn)證算法性能的優(yōu)越性，仿真選取3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和中等規(guī)模的任務(wù)分配算例。仿真結(jié)果表明，算法快速收斂的同時(shí)能有效跳出局部極值。