郝　輝,李雪瑞,李亞雄

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

?

基于遺傳算法的面目標瞄準點尋優(yōu)問題研究

郝輝,李雪瑞,李亞雄

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

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

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

本文引用格式：郝輝,李雪瑞,李亞雄.基于遺傳算法的面目標瞄準點尋優(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ī)則目標成為一種重要作戰(zhàn)樣式[1]。作戰(zhàn)運用中，如何選擇各枚導(dǎo)彈的瞄準點，以取得最佳打擊效果，是一個迫切需要解決的問題。對于多枚導(dǎo)彈武器打擊遠程面目標，為達到最佳的效費比，通常需要對瞄準點進行優(yōu)化選擇。而不規(guī)則面目標瞄準點的選擇首先需要確定一個合適的指標作為最優(yōu)瞄準點的判斷標準，然后依據(jù)指標值進行瞄準點選擇模型的優(yōu)化，最終得出最優(yōu)的瞄準點[2]。

1遺傳算法

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

2不規(guī)則面目標毀傷指標計算模型

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

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

文獻[4]給出了圓與任意有向三角形面目標相交面積的快速解析計算方法，如圖1所示。

圖1　圓與三角形相交面積計算方法

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

圖2　多邊形的劃分方法

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

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

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

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

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

2.3毀傷指標計算模型

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

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

(1)

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

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

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

(2)

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

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

3.1模型編碼

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

則該組值的編碼為

x1y1x2y2…xmym

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

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

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

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

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

(3)

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

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

1) 選擇操作

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

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

(4)

2) 交叉操作[2]

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

(5)

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

3) 變異操作

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

4應(yīng)用實例

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

圖4　多邊形目標初始瞄準點

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

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

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

圖5　多邊形目標瞄準點計算結(jié)果

序號坐標瞄準點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ī)則面目標，并給出導(dǎo)彈打擊面目標的平均毀傷面積計算模型；利用遺傳算法對瞄準點尋優(yōu)問題進行求解驗證。實例計算表明，該算法能有效地解決瞄準點尋優(yōu)問題，為此類問題的解決提供了一種解決方案。算法還可用于導(dǎo)彈火力分配問題和發(fā)射彈量計算等多目標決策問題，有很高的軍事應(yīng)用價值。

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

[13]張信啟,黃銳,范陽濤.常規(guī)導(dǎo)彈火力運用的優(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

文獻標識碼：A

doi:10.11809/scbgxb2016.01.031

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

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