基于遺傳算法的面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題研究

郝　輝,李雪瑞,李亞雄

(第二炮兵工程大學(xué)，西安　710025)

?

基于遺傳算法的面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題研究

郝輝,李雪瑞,李亞雄

(第二炮兵工程大學(xué)，西安710025)

摘要：為解決面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題，在單彈打擊不規(guī)則面目標(biāo)毀傷面積計(jì)算的基礎(chǔ)上，給出了多彈打擊面目標(biāo)的毀傷面積計(jì)算模型和重復(fù)毀傷面積計(jì)算方法。建立了瞄準(zhǔn)點(diǎn)優(yōu)化模型，利用遺傳算法原理，對(duì)瞄準(zhǔn)點(diǎn)進(jìn)行編碼，確定了適應(yīng)度函數(shù)，設(shè)計(jì)了遺傳算子，并設(shè)計(jì)了不規(guī)則面目標(biāo)瞄準(zhǔn)點(diǎn)選擇計(jì)算實(shí)例。實(shí)例計(jì)算結(jié)果表明，該方法計(jì)算可信度較高，且具有一定的可操作性，軍事應(yīng)用價(jià)值較強(qiáng)。

關(guān)鍵詞：不規(guī)則面目標(biāo)；遺傳算法；毀傷面積；瞄準(zhǔn)點(diǎn)

本文引用格式：郝輝,李雪瑞,李亞雄.基于遺傳算法的面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題研究[J].兵器裝備工程學(xué)報(bào)，2016(1):128-131.

Citation format:HAO Hui，LI Xue-rui，LI Ya-xiong.Optimization of Area Target Aiming Point Based on Genetic Algorithm[J].Journal of Ordnance Equipment Engineering,2016(1):128-131.

現(xiàn)代高技術(shù)戰(zhàn)爭(zhēng)中，用多枚精確制導(dǎo)武器，如常規(guī)導(dǎo)彈打擊一個(gè)不規(guī)則目標(biāo)成為一種重要作戰(zhàn)樣式[1]。作戰(zhàn)運(yùn)用中，如何選擇各枚導(dǎo)彈的瞄準(zhǔn)點(diǎn)，以取得最佳打擊效果，是一個(gè)迫切需要解決的問(wèn)題。對(duì)于多枚導(dǎo)彈武器打擊遠(yuǎn)程面目標(biāo)，為達(dá)到最佳的效費(fèi)比，通常需要對(duì)瞄準(zhǔn)點(diǎn)進(jìn)行優(yōu)化選擇。而不規(guī)則面目標(biāo)瞄準(zhǔn)點(diǎn)的選擇首先需要確定一個(gè)合適的指標(biāo)作為最優(yōu)瞄準(zhǔn)點(diǎn)的判斷標(biāo)準(zhǔn)，然后依據(jù)指標(biāo)值進(jìn)行瞄準(zhǔn)點(diǎn)選擇模型的優(yōu)化，最終得出最優(yōu)的瞄準(zhǔn)點(diǎn)[2]。

1遺傳算法

常見(jiàn)的尋優(yōu)算法有很多，各有優(yōu)勢(shì)和不足。枚舉法易于實(shí)現(xiàn)，但要列出所有可能的結(jié)果，不利于求解大規(guī)模問(wèn)題；動(dòng)態(tài)規(guī)劃法用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題，但規(guī)劃模型建立較復(fù)雜；迭代法能較快地得到最優(yōu)解，但只適用于單值問(wèn)題，且易出現(xiàn)發(fā)散；分支定界法僅可用于解純整數(shù)或混合整數(shù)規(guī)劃問(wèn)題[3]；爬山法和禁忌搜索法極易陷入局部最優(yōu)不適用于多值問(wèn)題的求解[2]。

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來(lái)的隨機(jī)搜索方法。其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法從全局開(kāi)始搜索，運(yùn)用交叉，變異等算子進(jìn)行迭代尋優(yōu)，從理論分析以及實(shí)踐表明遺傳算法具有其他方法難以具備的全局尋優(yōu)特性[2]。

2不規(guī)則面目標(biāo)毀傷指標(biāo)計(jì)算模型

對(duì)于不規(guī)則面目標(biāo)，通常將其等效成多邊形目標(biāo)。為了簡(jiǎn)化計(jì)算，假定多邊形目標(biāo)為均勻面目標(biāo)，選取毀傷面積為毀傷效果指標(biāo)，導(dǎo)彈對(duì)目標(biāo)的毀傷能力用毀傷半徑來(lái)表示。于是，原問(wèn)題轉(zhuǎn)化為多邊形與圓相交面積計(jì)算問(wèn)題，相交部分的面積為毀傷效果指標(biāo)。

2.1單彈打擊不規(guī)則面目標(biāo)毀傷面積計(jì)算

文獻(xiàn)[4]給出了圓與任意有向三角形面目標(biāo)相交面積的快速解析計(jì)算方法，如圖1所示。

圖1　圓與三角形相交面積計(jì)算方法

對(duì)于多邊形目標(biāo)，可先將其簡(jiǎn)單分割成多個(gè)有向三角形，再應(yīng)用圓與三角形面目標(biāo)相交面積計(jì)算方法進(jìn)行計(jì)算。如圖2，多邊形ABCDE被簡(jiǎn)單分割成3個(gè)三角形，分別為△AOB、△BOC、△COD、△DOE、△EOA。若定義順時(shí)針為正，則△COD、△DOE、△EOA為正三角形，計(jì)算的相交面積為正值，△AOB、△BOC為負(fù)三角形，計(jì)算的相交面積為負(fù)值。

圖2　多邊形的劃分方法

該方法為解析計(jì)算方法，在計(jì)算過(guò)程中回避了計(jì)算交點(diǎn)坐標(biāo)這個(gè)影響精度的操作，減少了運(yùn)算次數(shù)，計(jì)算結(jié)果精度高，算法程序易于實(shí)現(xiàn)[4-6]。

2.2多彈打擊不規(guī)則面目標(biāo)重復(fù)毀傷面積計(jì)算

多彈打擊面目標(biāo)時(shí)，存在重復(fù)毀傷的情況，其計(jì)算過(guò)程相對(duì)復(fù)雜，通常使用像素法進(jìn)行求解[1]。像素法能有效解決重復(fù)毀傷面積計(jì)算問(wèn)題，但要提高精度，勢(shì)必呈平方地增加計(jì)算量。本研究基于單彈打擊面目標(biāo)毀傷面積解析計(jì)算方法，提出一種重復(fù)毀傷面積的解析計(jì)算方法，大大提高了精度。

在多彈打擊面目標(biāo)的實(shí)踐過(guò)程中，由于考慮到導(dǎo)彈的效費(fèi)比，通常會(huì)盡量節(jié)省彈量，在這種情況下，存在重復(fù)毀傷的情況并不多見(jiàn)[8-11]。在出現(xiàn)重復(fù)毀傷時(shí)，可先利用相交圓的交點(diǎn)連線，將原多邊形目標(biāo)分割成多個(gè)多邊形，如圖3所示，然后利用2.1節(jié)提供的方法分別求解相交部分面積，最后減去重復(fù)部分的面積。

圖3　重復(fù)毀傷面積計(jì)算方法

2.3毀傷指標(biāo)計(jì)算模型

對(duì)于任意形狀的多邊形目標(biāo)，毀傷指標(biāo)值為目標(biāo)區(qū)域的平均毀傷面積，作戰(zhàn)任務(wù)要求達(dá)到的最低毀傷值為Sr，有n頂點(diǎn)的多邊形目標(biāo)的坐標(biāo)值為(x1,x2,…,xn)和(y1,y2,…,yn)，m個(gè)導(dǎo)彈的CEP為(cep1,cep2,…,cepm)，毀傷半徑為(r1,r2,…,rm)，瞄準(zhǔn)點(diǎn)為(xa1,xa2,…,xam)和(ya1,ya2,…,yam)，采用蒙特卡洛模擬的方法來(lái)計(jì)算平均毀傷面積。

步驟1利用U(0,1)分布隨機(jī)數(shù)生成函數(shù)模擬導(dǎo)彈落點(diǎn)坐標(biāo)。

(1)

式中：xbi,ybi為導(dǎo)彈落點(diǎn)坐標(biāo)；η1,η2為服從U(0,1)分布隨機(jī)數(shù)；σi為導(dǎo)彈落點(diǎn)散布的標(biāo)準(zhǔn)差，σi=cepi/1.177 41。

步驟2利用2.2節(jié)的方法計(jì)算毀傷面積Sj,j=1,2,…,N。

步驟3重復(fù)步驟1和步驟2，統(tǒng)計(jì)計(jì)算平均毀傷面積。

(2)

3基于遺傳算法的瞄準(zhǔn)點(diǎn)尋優(yōu)模型

瞄準(zhǔn)點(diǎn)的選擇首先要確定一個(gè)合適的指標(biāo)作為最優(yōu)瞄準(zhǔn)點(diǎn)的判斷標(biāo)準(zhǔn)，然后依據(jù)指標(biāo)值進(jìn)行瞄準(zhǔn)點(diǎn)選擇模型的優(yōu)化，最終得出最優(yōu)的瞄準(zhǔn)點(diǎn)[12-13]。對(duì)目標(biāo)的攻擊，要選擇合適的彈型，用最小的，獲利最大的毀傷效果，不違背限制條件，實(shí)現(xiàn)對(duì)目標(biāo)的毀傷意圖。要實(shí)現(xiàn)上述要求，必須科學(xué)選擇瞄準(zhǔn)點(diǎn)位，即最優(yōu)瞄準(zhǔn)點(diǎn)。

3.1模型編碼

遺傳算法不能直接處理有關(guān)空間的參數(shù)，而必須把它們轉(zhuǎn)換成遺傳空間的基因，并按一定結(jié)構(gòu)組成的染色體或個(gè)體，二進(jìn)制編碼是目前遺傳算法中最常用的編碼方法。針對(duì)本問(wèn)題而言，對(duì)于m枚導(dǎo)彈，瞄準(zhǔn)點(diǎn)坐標(biāo)為

則該組值的編碼為

x1y1x2y2…xmym

3.2群體規(guī)模及初始群體的選取

群體中個(gè)體的個(gè)數(shù)稱為群體的規(guī)模。群體的規(guī)模越大，其代表性越廣泛，最終進(jìn)化到最優(yōu)解的可能性越大。但規(guī)模大的群體勢(shì)必造成計(jì)算時(shí)間的增加，這又是不希望看到的，所以應(yīng)適當(dāng)選取初始群體規(guī)模K。

初始群體若是隨機(jī)選取，容易遍歷所有的狀態(tài)，達(dá)到全局最優(yōu)解，但是無(wú)疑增加了計(jì)算時(shí)間。若利用其他的啟發(fā)式算法得到初始解，可能使種子缺乏代表性，因而可能出現(xiàn)早熟現(xiàn)象而達(dá)不到全局最優(yōu)。本文初始群體的選取采用均勻布點(diǎn)法。

3.3適應(yīng)度函數(shù)的設(shè)計(jì)

遺傳算法在進(jìn)化搜索過(guò)程中要求以非負(fù)的最大值形式來(lái)反映個(gè)體的生存能力，即個(gè)體的適應(yīng)度。根據(jù)遺傳算法中適應(yīng)度函數(shù)的構(gòu)造原理，結(jié)合最優(yōu)瞄準(zhǔn)點(diǎn)問(wèn)題的特性，取適應(yīng)度為所選取的毀傷指標(biāo)值，即

(3)

3.4遺傳算子的設(shè)計(jì)

遺傳算法的遺傳操作包括以下3個(gè)基本遺傳算子：選擇；交叉；變異。

1) 選擇操作

目前遺傳算法中常用的選擇算子有以下幾種：適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。其中輪盤(pán)賭選擇法(roulette wheel selection)是最簡(jiǎn)單也是最常用的選擇方法。在該方法中，各個(gè)個(gè)體的選擇概率和適應(yīng)度值成比例。

針對(duì)本問(wèn)題，個(gè)體i的適應(yīng)度為fi，則i被選擇的概率為

(4)

2) 交叉操作[2]

交叉是產(chǎn)生新個(gè)體的主要手段，本文采用兩點(diǎn)交叉方法。對(duì)選中的兩個(gè)個(gè)體，隨機(jī)選擇交叉位置r1,r2(r1

(5)

將兩式交叉位置中間的每個(gè)浮點(diǎn)數(shù)取出來(lái)，產(chǎn)生新的數(shù)據(jù)，代替原來(lái)的數(shù)據(jù)，即得到兩個(gè)新的個(gè)體。

3) 變異操作

變異算子的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)，針對(duì)二進(jìn)制變異，其基本步驟如下：① 對(duì)群中個(gè)體以事先設(shè)定的變異概率判斷是否進(jìn)行變異；② 對(duì)進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異。

4應(yīng)用實(shí)例

設(shè)有一多邊形打擊目標(biāo)，目標(biāo)在一長(zhǎng)200 m，寬100 m的矩形區(qū)域內(nèi)，現(xiàn)有5枚導(dǎo)彈對(duì)其進(jìn)行打擊，導(dǎo)彈精度指標(biāo)為σx=σy=50，初始瞄準(zhǔn)點(diǎn)坐標(biāo)為(25.0,50.0)，(75.0,50.0)，(50.0,100.0)，(25.0,150.0)，(75.0,150.0)，如圖4所示。

圖4　多邊形目標(biāo)初始瞄準(zhǔn)點(diǎn)

根據(jù)遺傳算法的計(jì)算流程，選取群體規(guī)模K=100，計(jì)算200代，編制C++程序，通過(guò)搜索計(jì)算，最終得出結(jié)果如表1所示。

從程序運(yùn)行的結(jié)果來(lái)看，利用遺傳算法求出來(lái)的其中一組瞄準(zhǔn)點(diǎn)的坐標(biāo)分別為(52.30，115.74)，(30.30,153.67)，(78.10,167.74)，(67.35,56.89)，(35.29,46.04)，如圖5所示。

從圖5的結(jié)果來(lái)看，其瞄準(zhǔn)點(diǎn)的分布還是相對(duì)比較合理的，但是對(duì)于此類問(wèn)題，它是沒(méi)有唯一最優(yōu)解的，而我們這里計(jì)算出來(lái)的也并不是一個(gè)最優(yōu)解，只能說(shuō)是局部最優(yōu)或是比較合理的解，一方面這與導(dǎo)彈的參數(shù)有關(guān)，另一方面是由于計(jì)算機(jī)的計(jì)算誤差，然而其計(jì)算結(jié)果是完全可以接受的。

圖5　多邊形目標(biāo)瞄準(zhǔn)點(diǎn)計(jì)算結(jié)果

序號(hào)坐標(biāo)瞄準(zhǔn)點(diǎn)12345適應(yīng)度1x42.3393.3571.7583.8728.15y66.86146.6342.82123.1721.518462.242x2.0588.2737.3496.2949.27y63.7398.73161.6820.9258.468764.933x90.8143.0132.2633.7278.40y17.40147.21143.11123.1772.638830.544x52.3030.3078.1067.3535.29y115.74153.67167.7456.8946.0410429.965x61.0065.1013.3948.0027.57y44.77108.90105.96169.542.1310048.106x42.4224.6374.1022.6881.43y17.4021.31128.053.3296.777569.07

5結(jié)束語(yǔ)

在比較分析常見(jiàn)優(yōu)化算法的基礎(chǔ)上，提出了遺傳算法的優(yōu)勢(shì)；采用多邊形區(qū)域簡(jiǎn)化不規(guī)則面目標(biāo)，并給出導(dǎo)彈打擊面目標(biāo)的平均毀傷面積計(jì)算模型；利用遺傳算法對(duì)瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題進(jìn)行求解驗(yàn)證。實(shí)例計(jì)算表明，該算法能有效地解決瞄準(zhǔn)點(diǎn)尋優(yōu)問(wèn)題，為此類問(wèn)題的解決提供了一種解決方案。算法還可用于導(dǎo)彈火力分配問(wèn)題和發(fā)射彈量計(jì)算等多目標(biāo)決策問(wèn)題，有很高的軍事應(yīng)用價(jià)值。

另外算法存在不足之處，如收斂速度慢和搜索方法單一，后續(xù)研究中考慮在計(jì)算過(guò)程中加入約束條件，并對(duì)算法進(jìn)行優(yōu)化，同時(shí)結(jié)合其他算法，提高收斂速度，增強(qiáng)算法的實(shí)用性。

參考文獻(xiàn)：

[1]畢義明,張紅文,黃超會(huì),等.多枚導(dǎo)彈打擊不規(guī)則面目標(biāo)瞄準(zhǔn)點(diǎn)的遺傳算法優(yōu)化[C]//中國(guó)系統(tǒng)工程學(xué)會(huì)第十四屆學(xué)術(shù)年會(huì)論文集.廈門(mén):[出版者不詳],2006.

[2]王小亮,王運(yùn)吉,關(guān)愛(ài)杰,等.基于遺傳算法的不規(guī)則區(qū)域瞄準(zhǔn)點(diǎn)選擇優(yōu)化[C]//第八屆中國(guó)青年運(yùn)籌信息管理學(xué)者大會(huì)論文集.桂林:[出版者不詳],2006.

[3]《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué) [M].3版.北京:清華大學(xué)出版社,2005.

[4]郝輝,李雪瑞,舒健生,等.導(dǎo)彈打擊三角形目標(biāo)毀傷面積的一種解析計(jì)算方法[J].火力與指揮控制,2013(6):143-145.

[5]康璞,畢義明,鄭重.導(dǎo)彈武器對(duì)體系目標(biāo)毀傷的反向分析方法[J].四川兵工學(xué)報(bào),2012(11):24-28.

[6]楊曉段,劉曙云,蔣心曉,等.基于遺傳算法的炮兵火力計(jì)劃方案模型分析[C]//2009年中國(guó)智能自動(dòng)化會(huì)議論文集.南京:[出版者不詳],2009.

[7]楊維芳.兩個(gè)復(fù)雜多邊形求交的矢量算法[J].蘭州鐵道學(xué)院學(xué)報(bào),2002(1):108-110.

[8]朱英貴,趙建江.基于剩余穿深理論選擇瞄準(zhǔn)點(diǎn)研究[J].火力與指揮控制,2006(10):77-79.

[9]李軍華.基于知識(shí)和多種群進(jìn)化的遺傳算法研究[D].南京:南京航空航天大學(xué),2009.

[10]駱軼姝,陳立今,樂(lè)嘉錦.基于遺傳算法多目標(biāo)決策的應(yīng)用[C]//MSE 2010.武漢:[出版者不詳],2010.

[11]曹偉華,焦紅革,魏建輝.遺傳算法在武器目標(biāo)分配中的應(yīng)用[J].四川兵工學(xué)報(bào),2008(5):119-121.

[12]姚躍亭,趙建軍,王毅,等.WTA問(wèn)題遺傳算法的混沌改進(jìn)[C]//第二十九屆中國(guó)控制會(huì)議論文集.北京:[出版者不詳],2010.

[13]張信啟,黃銳,范陽(yáng)濤.常規(guī)導(dǎo)彈火力運(yùn)用的優(yōu)化[J].四川兵工學(xué)報(bào),2009(8):57-59.

(責(zé)任編輯楊繼森)

【信息科學(xué)與控制工程】

Optimization of Area Target Aiming Point

Based on Genetic Algorithm

HAO Hui， LI Xue-rui， LI Ya-xiong

(The Second Artillery Engineering University, Xi’an 710025, China)

Abstract:In order to solve the aiming point optimization problem, a calculation method of multi-missile striking target damage area and repeated damage area were proposed on the basis of single missile striking irregular surface target damage area. Aiming point optimization model was established. By the principle of genetic algorithm, the aiming points were encoded, the fitness function was determined, the genetic operator was designed and irregular surface target aiming point selection and calculation example was given. The result shows that the method has good reliability and operability. It has strong value of military application.

Key words：irregular area target; genetic algorithm; damage area; aiming point

文章編號(hào)：1006-0707(2016)01-0128-04

中圖分類號(hào)：TP391.9

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.11809/scbgxb2016.01.031

作者簡(jiǎn)介：郝輝(1980—)，男，碩士，講師，主要從事軍事運(yùn)籌學(xué)研究。

收稿日期：2015-06-01；修回日期：2015-07-09