基于遺傳算法的區(qū)域防空部署應(yīng)用

潘永強(qiáng) 吳凱 董詩音 姜鴻儒 雷建杰

防空部署是對兵力作戰(zhàn)效能的有效利用,部署的好壞程度將直接影響整個(gè)防空作戰(zhàn)結(jié)果,在當(dāng)前復(fù)雜多變的敵情和有限兵力資源情況,如何將防空部署效能做到更優(yōu)是防空作戰(zhàn)研究的重點(diǎn)與難點(diǎn)[1?3],目前,國內(nèi)防空部署的研究成果大致如下幾點(diǎn),一是根據(jù)部署方案的相關(guān)特征,建立并計(jì)算部署方案的貼近度,從而得到部署方案的改進(jìn)策略[4],此方法需要融入大量人為評價(jià)因素,部署優(yōu)化程度有待提高;二是在防空部署權(quán)重不確定時(shí)采用多屬性決策方法(MAMD),考慮不同因素權(quán)重,使得計(jì)算得到的防空部署方案更加科學(xué)可靠[5?7],但由于考慮的因素較多且差異性較大,該方法實(shí)際應(yīng)用過程較為復(fù)雜;三是通過層次分析法建立防空部署評價(jià)指標(biāo)體系,采用正態(tài)云擬合算法選出最優(yōu)防空部署方案[8],該方法實(shí)現(xiàn)了定性到定量的合理轉(zhuǎn)化,在單個(gè)武器系統(tǒng)防空部署優(yōu)化計(jì)算上效率較高,但對于多武器系統(tǒng)防空部署的優(yōu)化計(jì)算難度則因考慮因素的復(fù)雜程度增大而增大;四是考慮來襲目標(biāo)和本武器系統(tǒng)殺傷性能等要素,建立仿真評估系統(tǒng),模擬仿真防空作戰(zhàn)過程,優(yōu)化部署[9?11],此方法僅考慮了單武器系統(tǒng)防空部署仿真,暫未對多武器系統(tǒng)的防空部署進(jìn)行仿真;五是通過建立多目標(biāo)防空部署模型,得到考慮多目標(biāo)因素的目標(biāo)函數(shù),采用遺傳算法求解防空部署優(yōu)化模型[12],遺傳算法能很好地解決多目標(biāo)優(yōu)化收斂問題,是一種簡單有效處理防空部署優(yōu)化問題的實(shí)用方法,但目前為止防空部署優(yōu)化模型僅考慮了單點(diǎn)防空部署,而并未考慮到整個(gè)防空區(qū)域的區(qū)域性部署效能.

通過以上研究發(fā)現(xiàn),采用遺傳算法優(yōu)化防空部署方案不失為一個(gè)好方法,2003年,國內(nèi)就已經(jīng)嘗試并探索遺傳算法在防空兵火力分配上的應(yīng)用[13],在建立遺傳算法模型的基礎(chǔ)上仿真運(yùn)算,得到具有一定參考價(jià)值的分配方案,在戰(zhàn)役方向兵力優(yōu)化分配方面,建立防空部署分配的數(shù)學(xué)規(guī)劃模型,改進(jìn)遺傳算法[14],并最終得到單個(gè)防空武器在對抗典型目標(biāo)下的部署方案,而未考慮到多武器系統(tǒng)防空部署優(yōu)化問題,且涉及到多種武器混合部署下的優(yōu)化模型較為復(fù)雜[15],是防空部署優(yōu)化研究的重點(diǎn).

從防空部署區(qū)域的角度來考慮,區(qū)域性防空部署更能有效地反映整個(gè)防空部署的性能,將更有效的作戰(zhàn)資源部署在更加需要保衛(wèi)的要地中心,同時(shí)能夠兼顧保護(hù)在防空區(qū)域內(nèi)其他非重點(diǎn)保護(hù)的要地,做到合理利用武器資源、合理部署.所以,如何做到在考慮多目標(biāo)多類型兵力資源的基礎(chǔ)上,有效利用對保衛(wèi)要地的區(qū)域性管理,得到最優(yōu)化的防空部署方案,是目前防空部署研究上的難點(diǎn),本文就防空部署問題進(jìn)行了較為深入的分析,提出從單點(diǎn)要地防空轉(zhuǎn)為區(qū)域性要地防空,建立了防空區(qū)域的設(shè)計(jì)模型,并設(shè)計(jì)防空區(qū)域的兵力部署數(shù)學(xué)模型,將遺傳算法應(yīng)用于區(qū)域防空部署模型的求解,得到了較為理想的結(jié)果.

1 區(qū)域防空部署流程

隨著目前武器裝備升級換代速度的加快,現(xiàn)有武器裝備保衛(wèi)能力越來越強(qiáng),保衛(wèi)覆蓋范圍也越來越大,采用一個(gè)防空武器系統(tǒng)僅保衛(wèi)單個(gè)防空要地的方式已與目前防空武器的高速發(fā)展相矛盾,故本文在要地單點(diǎn)防空部署的基礎(chǔ)上,提出區(qū)域化的防空部署,使得一個(gè)防空武器系統(tǒng)可以同時(shí)保衛(wèi)多個(gè)防空要地,減少資源使用成本,實(shí)現(xiàn)更高效的防空部署,并基于區(qū)域化防空的特點(diǎn),建立區(qū)域防空部署模型,采用遺傳算法求解得出最優(yōu)的區(qū)域防空部署方案.

本文對區(qū)域防空部署應(yīng)用研究的流程如下:

1)要地單點(diǎn)防空區(qū)域化.

2)建立區(qū)域防空最優(yōu)部署目標(biāo)函數(shù).

3)基于遺傳算法解算區(qū)域防空最優(yōu)部署方案.

4)區(qū)域防空部署遺傳算法模型優(yōu)化分析.

流程圖如圖1所示.

圖1 基于遺傳算法的區(qū)域防空部署流程Fig.1 Regional air defense deployment process based on genetic algorithm

2 區(qū)域防空部署模型

2.1 要地單點(diǎn)防空區(qū)域化

防空部署,主要是為了最大化發(fā)揮各類防空武器的性能,以更高的效能來保衛(wèi)我方要地[16],為了建立區(qū)域化防空部署的數(shù)學(xué)模型,對部署條件抽象描述如下:

設(shè)防空部署可用的武器有m種,且第i(i=1,2,···,m)種武器有ni套,要地個(gè)數(shù)為r,要地的重要性系數(shù)為wj(j=1,2,···,r),保衛(wèi)性系數(shù)為eij.wj表示j要地的重要程度,eij表示i武器成功保衛(wèi)j要地的概率.

在防空部署過程中,在偵察來襲目標(biāo)運(yùn)動參數(shù)信息的基礎(chǔ)上,可推測出敵機(jī)的航線方向和最大攻擊距離d,設(shè)敵機(jī)飛行方向如圖2所示,則可以根據(jù)保衛(wèi)要地與敵相對位置信息,以局部要地為中心,d為半徑,將多個(gè)要地劃分為少量的防空區(qū)域,實(shí)現(xiàn)要地單點(diǎn)防空向區(qū)域防空的轉(zhuǎn)變.為此,建立如下防空區(qū)域作圖準(zhǔn)則:

1)wj為首要考慮因素,wj從大到小排序,先以重要的要地開始作圖,依次考慮次要要地.

圖2 防空區(qū)域的劃分Fig.2 Division of air defense zone

2)當(dāng)次要要地已在重要要地防空區(qū)域內(nèi),則不再對其進(jìn)行作圖.

3)在wj相同情況下,相對敵目標(biāo)位置更近的要地先作圖.

在完成以上作圖操作后,可以將多個(gè)單點(diǎn)要地劃分為少量的防空區(qū)域,記為S={S1,S2,...,Sk},而根據(jù)優(yōu)化算法將防空武器部署在各個(gè)防空區(qū)域的中心,既能最大火力地保衛(wèi)防空區(qū)域中心的重點(diǎn)要地,也能兼顧保衛(wèi)區(qū)域內(nèi)部的其他要地,實(shí)現(xiàn)防空效能的最大化,同時(shí)從多要地轉(zhuǎn)化為少防空區(qū)域的量化數(shù)據(jù)的減少更加有助于優(yōu)化算法的收斂.

2.2 建立區(qū)域防空最優(yōu)部署目標(biāo)函數(shù)

采用不同防空區(qū)域的重要性系數(shù)為Wj,保衛(wèi)性系數(shù)為Eij,其中Wj為j防空區(qū)域的重要程度,Eij為i武器對成功保衛(wèi)j防空區(qū)域的概率.

假設(shè)第j個(gè)防空區(qū)域包括多個(gè)要地,S j=為該防空區(qū)域中心要地,dpq為sp要地與sq要地之間的距離,dpt為sp要地與st要地之間的距離,則第j個(gè)防空區(qū)域的重要性系數(shù)Wj和第i種武器系統(tǒng)對第j個(gè)防空區(qū)域成功保衛(wèi)的概率Eij為:

防空部署可用矩陣X=(xij)m×k來描述,其中,xij為用于保衛(wèi)j防空區(qū)域的i武器數(shù)量.

最優(yōu)部署的目標(biāo)函數(shù)是對防空區(qū)域的保衛(wèi)效能指標(biāo)達(dá)到最大,該保衛(wèi)效能指標(biāo)以成功保衛(wèi)防空區(qū)域的數(shù)學(xué)期望為基礎(chǔ).

用一定數(shù)量的i武器成功保衛(wèi)j防空區(qū)域的概率可表示為:

所有m類武器成功保衛(wèi)j防空區(qū)域概率為:

數(shù)學(xué)期望為:

所以最優(yōu)化的目標(biāo)函數(shù)為:

約束條件如下:

2.3 遺傳算法解算最優(yōu)部署方案

根據(jù)遺傳算法理論[17],結(jié)合區(qū)域防空部署問題的特征,設(shè)計(jì)了區(qū)域防空部署模型的遺傳算法,為定量描述遺傳算法求解過程,下面以具體實(shí)例來進(jìn)行說明.

假設(shè)有A、B、C、D 4種型號的武器,共20個(gè)武器系統(tǒng)(A型數(shù)量n1為6個(gè),B型數(shù)量n2為4個(gè),C型數(shù)量n3為4個(gè),D型數(shù)量n4為6個(gè))用于保衛(wèi)6個(gè)目標(biāo)要地,保衛(wèi)要地的坐標(biāo)sj(=1,2,···,6)分別為s1(0,0),s2(?10,0),s3(0,15),s4(?40,40),s5(?50,40),s6(?50,0),其權(quán)重wj(=1,2,···,6)依次為(0.3,0.1,0.1,0.15,0.15,0.2);部署A型武器成功保衛(wèi)要地sj的概率e1j(=1,2,···,6)為(0.30,0.40,0.60,0.30,0.50,0.40);部署B(yǎng)型武器成功保衛(wèi)要地sj的概率e2j(=1,2,···,6)為(0.20,0.50,0.30,0.60,0.60,0.40);部署C型武器成功保衛(wèi)要地sj的概率e3j(=1,2,···,6)為(0.80,0.50,0.20,0.30,0.70,0.40);部署D型武器成功保衛(wèi)要地sj的概率e4j(=1,2,···,6)為(0.50,0.80,0.30,0.30,0.30,0.60),假設(shè)敵機(jī)來襲航線方向如圖3所示,敵機(jī)攻擊距離d為20 km,試求要地保衛(wèi)效能最優(yōu)時(shí)的區(qū)域防空部署方案.

首先根據(jù)要地分布情況、敵機(jī)攻擊距離以及作圖規(guī)則劃分出S1={s1,s2,s3}、S2={s4,s5}、S3={s6}3個(gè)防空區(qū)域,如圖3所示.

圖3 防空區(qū)域的劃分實(shí)例Fig.3 Example of the division of air defense zones

根據(jù)式(1)計(jì)算得出各防空區(qū)域Wj為

根據(jù)式(2)計(jì)算得出Eij為:

下面再利用遺傳算法優(yōu)化求解得出A、B、C、D 4種防空武器分別部署在S1、S2、S3的數(shù)量.

2.3.1 編碼

對xij進(jìn)行二進(jìn)制編碼,由于xij為非負(fù)整數(shù),設(shè)xij最大取值為R=max{ni},Q(R)為R轉(zhuǎn)化為二進(jìn)制數(shù)時(shí)的位數(shù),故每個(gè)部署方案所需串長為L=Q(R)×m×k,則第t個(gè)防空部署方案對應(yīng)染色體為:

在上例中,xij最大為6,故R=3,因此L=3×4×3=36.

2.3.2 初始種群

初始種群選擇的好壞影響算法的計(jì)算效率,所以,盡量將初始種群選在全局最優(yōu)解附近,故既可減少迭代次數(shù),又可更快得到滿意解,根據(jù)區(qū)域防空作戰(zhàn)部署的原則[18],提出根據(jù)要地重要性比例來產(chǎn)生初始種群的方法:

計(jì)算所有k個(gè)防空區(qū)域Wj的比例,根據(jù)式(1)計(jì)算結(jié)果,記為W1:W2:···:Wk.

計(jì)算相對重要程度.j防空區(qū)域的相對重要程度kWj為:

計(jì)算初始種群

根據(jù)上述方法得到的初始種群需滿足作為約束條件的式(7).

對于A型武器部署在3個(gè)防空區(qū)域的數(shù)量x1j來講,其變化范圍為0～6,同時(shí)再考慮到A型武器成功保衛(wèi)j防空區(qū)域的概率,分配其作戰(zhàn)單元數(shù)分別為3,2,1,轉(zhuǎn)化為初始種群為011010001,同理可得B型武器對防空區(qū)域部署的初始種群為010001001,C型武器對防空區(qū)域部署的初始種群為010001001,D型武器對防空區(qū)域部署的初始種群為011010001,最終得到第1 組初始種群01101 0001 010001001 010001001 011010001,同理,可生成第2～4 組初始種群,4 組初始種群分別為:

第1組初始種群 011010001 010001001 010001001 011010001.

第2組初始種群 100000010 011001000 100000000 100010000.

第3組初始種群 100010000 000000100 001000011 001000101.

第4組初始種群 001000101 000000100 100000000 100001001.

2.3.3 適應(yīng)值

將區(qū)域防空部署優(yōu)化模型中的目標(biāo)函數(shù)值作為適應(yīng)值,計(jì)算公式如下:

計(jì)算結(jié)果如表1所示.

表1 初始種群及其相關(guān)數(shù)據(jù)Table1 Initial population and related data

2.3.4 選擇

按照部署方案的適應(yīng)值F進(jìn)行選擇,每個(gè)個(gè)體的選擇概率為通過隨機(jī)方法來選擇部署方案[19],被選中的部署方案(染色體)添入下一代染色體種群中,初始種群選擇情況如表1所示.

2.3.5 交叉

交叉是產(chǎn)生新個(gè)體的重要方式,且是實(shí)現(xiàn)全局收斂的重要保障[20],為滿足交叉操作可行性要求,采用單點(diǎn)交叉方法如下:

設(shè)Tp與Tq為配對交叉,其染色體分別為

交叉點(diǎn)選擇在第s位,則交叉結(jié)果如下:

本例交叉點(diǎn)選擇在第18位和第19位之間,確保交叉結(jié)果有效,根據(jù)選擇結(jié)果,分別將1和2、1和3配對,交叉后新種群結(jié)果如表2所示.

表2 交叉運(yùn)算結(jié)果Table2 Crossover operation result

2.3.6 變異

設(shè)定變異概率為P,對染色體隨機(jī)一位進(jìn)行變異操作,若變異后的染色體符合可行性要求,則填入下一代種群中.

按照以上步驟運(yùn)行遺傳算法程序,輸出不同迭代次數(shù)下的最優(yōu)解及其適應(yīng)值.

2.4 遺傳算法模型優(yōu)化分析

實(shí)際遺傳算法模型設(shè)計(jì)時(shí),有很多因素影響了迭代結(jié)果的收斂速度和收斂質(zhì)量,故本文從不同的影響因素角度來分析針對區(qū)域防空遺傳算法的最優(yōu)化因素組合.

從不同變異概率的角度來分析,分別取變異概率為P變異= 0.01、0.05、0.1、0.2、0.3,交叉概率為P交叉=0.6,迭代次數(shù)為ger=1 000,初始種群適應(yīng)值為F初始=0.7,仿真結(jié)果如圖4所示,可以看出,隨著變異概率逐漸增加,結(jié)果越快收斂且收斂值越高,但當(dāng)變異概率為0.2后,若繼續(xù)增加變異概率,因變異趨勢無法控制,收斂效果出現(xiàn)下降,因此,本文采用變異概率P變異=0.2 作為區(qū)域防空遺傳算法的最優(yōu)化變異概率因素.

圖4 不同變異概率下適應(yīng)值Fig.4 Fitness value under different mutation probability

從不同交叉概率角度來分析,分別取交叉概率為P交叉=0.2、0.4、0.6、0.8,變異概率為P變異=0.2,迭代次數(shù)為ger=1 000,初始種群適應(yīng)值為F初始=0.7,仿真結(jié)果如圖5所示,可以看出,隨著交叉概率逐漸增加,結(jié)果越快收斂且收斂值越高,但當(dāng)交叉概率為0.6后,若繼續(xù)增加交叉概率,因交叉趨勢無法控制,收斂效果出現(xiàn)下降,因此,本文采用交叉概率P交叉=0.6 作為區(qū)域防空遺傳算法的最優(yōu)化交叉概率因素.

圖5 不同交叉概率下適應(yīng)值Fig.5 Fitness value under different crossover probability

從不同迭代次數(shù)的角度來分析,分別取迭代次數(shù)為ger=10、100、300、600、1 000、10 000,變異概率為P變異=0.2,交叉概率為P交叉=0.6,初始種群適應(yīng)值為F初始=0.7,仿真結(jié)果如圖6所示,可以看出,隨著迭代次數(shù)的逐漸增加,結(jié)果越快收斂且收斂值越高,但當(dāng)?shù)螖?shù)為1 000后,若繼續(xù)增加迭代次數(shù),因遺傳算法模型已到達(dá)收斂峰值,收斂效果明顯變化,因此,本文采用迭代次數(shù)ger=1 000 作為區(qū)域防空遺傳算法的最優(yōu)化迭代次數(shù)因素.

從不同初始種群適應(yīng)值的角度來分析,分別取初始種群適應(yīng)值F初始=0.3、0.4、0.5、0.7,變異概率為P變異= 0.2,交叉概率為P交叉= 0.6,迭代次數(shù)為ger=1 000,仿真結(jié)果如圖7所示,可以看出,隨著初始種群適應(yīng)值逐漸增加,結(jié)果收斂越快,當(dāng)初始種群適應(yīng)值為0.7 時(shí),只需要迭代計(jì)算86次即可完成遺傳算法模型的收斂,因此,本文采用初始種群適應(yīng)值F初始=0.7 作為區(qū)域防空遺傳算法的最優(yōu)化變異概率因素.

圖6 不同迭代次數(shù)下適應(yīng)值Fig.6 Fitness value under different iteration times

圖7 不同初始種群適應(yīng)值下收斂效果Fig.7 Convergence effect under different initial population fitnes

綜上分析所述,區(qū)域防空遺傳算法的最優(yōu)化因素組合為變異概率P變異= 0.2,交叉概率為P交叉= 0.6,迭代次數(shù)為ger=1 000,初始種群適應(yīng)值為F初始= 0.7,對于本例,經(jīng)過1 000次迭代優(yōu)化,可得最終結(jié)果為:X=(x11,x12,x13,x21,x22,x23,x31,x32,x33,x41,x42,x43)=(0,0,6,0,4,0,3,0,1,1,0,5),最大適應(yīng)值為maxF=0.799 9,即第1個(gè)防空區(qū)域S1部署C型武器3個(gè)單元和D型武器1個(gè)單元,第2個(gè)防空區(qū)域S2部署B(yǎng)型武器4個(gè)單元,第3個(gè)防空區(qū)域S3部署A型武器6個(gè)單元、C型武器1個(gè)單元和D型導(dǎo)彈5個(gè)單元.

值得注意的是,對于本實(shí)例,如果前期沒有將多個(gè)要地轉(zhuǎn)化為少量的防空區(qū)域來減少計(jì)算量,將大大增加遺傳算法的可編程性和最優(yōu)解求解效率,且如果在初始種群中的選擇不合適的話,可能無法迭代得到全局最優(yōu)解,由于約束條件的存在使得染色體個(gè)體在選擇交叉點(diǎn)、交叉方法和變異方式上都受到制約,為了避免這個(gè)問題,一方面可以在設(shè)計(jì)產(chǎn)生初始種群時(shí),可以根據(jù)先驗(yàn)知識而不是通過隨機(jī)方式來產(chǎn)生,另一方面可以適當(dāng)增大初始種群中染色體個(gè)體的數(shù)量,將各染色體個(gè)體之間的差異明顯化,從而能更有效地達(dá)到全局最優(yōu)解.

3 結(jié)論

本文提出了一種將單點(diǎn)要地防空部署轉(zhuǎn)化為區(qū)域防空部署的方法,建立了區(qū)域防空部署方案的數(shù)學(xué)模型,并將遺傳算法應(yīng)用于區(qū)域防空部署的優(yōu)化求解,為該問題的解決提供了一個(gè)簡單有效的途徑.實(shí)例證明,該方法能夠取得良好的部署效能,在一定的時(shí)間內(nèi)即可搜索到全局或近似全局的最優(yōu)解,從而為我國區(qū)域防空部署的制定提供科學(xué)的、有效的支持.

在此,要特別感謝我的老師邱令存研究員,邱老師不辭辛勞,多次與我就論文中的核心問題展開細(xì)致入微地探討,并給我提出切實(shí)可行的建設(shè)性意見.“授人以魚,不如授之以漁”,請?jiān)试S我向尊敬的邱令存老師表示真摯的謝意.