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

郝　輝,李雪瑞,李亞雄

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

?

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

郝輝,李雪瑞,李亞雄

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

摘要：為解決面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問題，在單彈打擊不規(guī)則面目標(biāo)毀傷面積計(jì)算的基礎(chǔ)上，給出了多彈打擊面目標(biāo)的毀傷面積計(jì)算模型和重復(fù)毀傷面積計(jì)算方法。建立了瞄準(zhǔn)點(diǎn)優(yōu)化模型，利用遺傳算法原理，對瞄準(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)用價值較強(qiáng)。

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

本文引用格式：郝輝,李雪瑞,李亞雄.基于遺傳算法的面目標(biāo)瞄準(zhǔn)點(diǎn)尋優(yōu)問題研究[J].兵器裝備工程學(xué)報，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)爭中，用多枚精確制導(dǎo)武器，如常規(guī)導(dǎo)彈打擊一個不規(guī)則目標(biāo)成為一種重要作戰(zhàn)樣式[1]。作戰(zhàn)運(yùn)用中，如何選擇各枚導(dǎo)彈的瞄準(zhǔn)點(diǎn)，以取得最佳打擊效果，是一個迫切需要解決的問題。對于多枚導(dǎo)彈武器打擊遠(yuǎn)程面目標(biāo)，為達(dá)到最佳的效費(fèi)比，通常需要對瞄準(zhǔn)點(diǎn)進(jìn)行優(yōu)化選擇。而不規(guī)則面目標(biāo)瞄準(zhǔn)點(diǎn)的選擇首先需要確定一個合適的指標(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遺傳算法

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

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

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

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

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

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

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

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

圖2　多邊形的劃分方法

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

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

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

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

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

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

對于任意形狀的多邊形目標(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個導(dǎo)彈的CEP為(cep1,cep2,…,cepm)，毀傷半徑為(r1,r2,…,rm)，瞄準(zhǔn)點(diǎn)為(xa1,xa2,…,xam)和(ya1,ya2,…,yam)，采用蒙特卡洛模擬的方法來計(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)的選擇首先要確定一個合適的指標(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]。對目標(biāo)的攻擊，要選擇合適的彈型，用最小的，獲利最大的毀傷效果，不違背限制條件，實(shí)現(xiàn)對目標(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)組成的染色體或個體，二進(jìn)制編碼是目前遺傳算法中最常用的編碼方法。針對本問題而言，對于m枚導(dǎo)彈，瞄準(zhǔn)點(diǎn)坐標(biāo)為

則該組值的編碼為

x1y1x2y2…xmym

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

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

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

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

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

(3)

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

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

1) 選擇操作

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

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

(4)

2) 交叉操作[2]

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

(5)

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

3) 變異操作

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

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

設(shè)有一多邊形打擊目標(biāo)，目標(biāo)在一長200 m，寬100 m的矩形區(qū)域內(nèi)，現(xiàn)有5枚導(dǎo)彈對其進(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++程序，通過搜索計(jì)算，最終得出結(jié)果如表1所示。

從程序運(yùn)行的結(jié)果來看，利用遺傳算法求出來的其中一組瞄準(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é)果來看，其瞄準(zhǔn)點(diǎn)的分布還是相對比較合理的，但是對于此類問題，它是沒有唯一最優(yōu)解的，而我們這里計(jì)算出來的也并不是一個最優(yōu)解，只能說是局部最優(yōu)或是比較合理的解，一方面這與導(dǎo)彈的參數(shù)有關(guān)，另一方面是由于計(jì)算機(jī)的計(jì)算誤差，然而其計(jì)算結(jié)果是完全可以接受的。

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

[13]張信啟,黃銳,范陽濤.常規(guī)導(dǎo)彈火力運(yùn)用的優(yōu)化[J].四川兵工學(xué)報,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

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

中圖分類號：TP391.9

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

doi:10.11809/scbgxb2016.01.031

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

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