基于PSGA的岸基導彈火力分配研究*

汲萬峰，王光源，章堯卿，孫鈞正

(海軍航空工程學院，山東 煙臺 264001)

0 引言

遺傳算法(genetic algorithna，GA)作為一種基于生物自然選擇與遺傳機理的隨機搜索算法，因其在優化求解方面具有較強的優越性[1]，因而在航跡規劃問題中得到了廣泛的應用[2-4]。但GA存在2個不容忽視的缺陷，分別是未成熟收斂和遺傳后期的收斂遲滯[5]。主要原因是：一方面，為了保證算法的全局收斂性，就要維持種群中個體的多樣性和搜索的有效性，避免有效基因的丟失；另一方面，為了加快收斂速度，就要使種群較快地向最優狀態轉移，這又會降低群體的多樣性，容易陷入局部最優。如何較快地找到最優解并防止早熟收斂問題是GA的一個較難權衡的問題。

許多學者對GA的改進方法進行了研究，主要集中在2個方面：①對于GA自身過程算子或控制參數的不斷完善和改進。如：分層遺傳、自適應遺傳、小生境、并行遺傳等[6]。②引入其他優化思想或智能技術，發揮互補優勢[7-8]。文獻[7]將禁忌搜索與遺傳算法配合，在利用遺傳算法求解配送中心選址問題的同時，設計禁忌搜索規則來解決配送中心選址所涉及的路線安排問題。文獻[8]研究了模擬退火算法與遺傳算法融合的混合遺傳方式，有一定的指導意義，但是在實際應用實現中還需針對問題具體分析。

本文設計了一種基于PS(predatory search)的改進遺傳算法，來提高算法的綜合搜索能力，并進一步研究了基于改進遺傳算法的飛行器航跡規劃問題。

1 GA簡介

GA是根據生物的進化思想啟發而得出的一種全局優化算法，通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優解的自適應搜索過程。GA主要執行以下步驟[9]：

(1) 依據編碼方式生成初始種群

編碼是GA要解決的首要問題，通過編碼將解空間的數據表示成基因串數據，按照相應的編碼方案隨機產生指定種群大小的個體。

(2) 適應度分配

GA在搜索過程中用適應度來評估個體的優劣，并作為后續遺傳操作的依據，個體的適應度越大則被遺傳到下一代的概率就越大。

(3) 選擇操作

選擇操作是根據各個個體的適應度值，按照“適者生存”的規則，從上一代群體中選擇出一些優良的個體遺傳到下一代群體中。GA進行選擇的原則是適應性強的個體為下一代貢獻的概率大，則被保留到下一代的概率也大。

(4) 交叉操作

交叉操作是GA最主要的遺傳操作，通過交叉操作可以得到新一代個體，新個體組合了父輩個體的特性。簡單的交叉操作是按照交叉概率隨機選擇若干對染色體并隨機選取交叉點實行相應位置的基因交換，得到新的染色體。

(5) 變異操作

變異操作是對于群體中的任一個體，以一定的概率隨機改變串結構中某個串的值，即對群體中的個體，以某一概率改變某一個或一些基因座上的基因值。

(6) 重插入操作

通過以上遺傳環節所生成的子代個體，通過基于適應度的再選擇機制被保留并插入父代種群中，同時父代中相應位置的個體被淘汰，從而產生新的參與下一代進化的種群。

2 PSGA算法的實現

2.1 PSGA算法的改進方法

本文設計一種基于PS[10-12]的改進遺傳算法。主要基于2個理由：① GA的收斂主要取決于交叉算子和變異算子，交叉算子提供了全局搜索能力，而變異算子則提供了局部搜索能力。進化初期，應確保種群在大范圍內搜索，進行全局進化以避免過早收斂；進化后期，種群成熟度較高，個體更加逼近最優解，種群應該在局部范圍內搜索，盡可能提高搜索精度[10]。因此，交叉概率和變異概率的取值需綜合考慮，平衡選擇。② PS是一種模擬動物捕食行為的空間搜索策略[11]，能夠有效地平衡全局探索能力和局部開發能力。PS的基本思想是：動物在捕食過程中，當沒有發現獵物或獵物跡象時，在整個捕食空間沿著一定的方向以很快的速度尋找獵物；一旦發現獵物或發現獵物跡象，它們就放慢步伐，在發現獵物或存在獵物跡象的區域進行集中搜索，以期望找到獵物；如果尋找一段時間后而沒有找到獵物，捕食動物將放棄這種集中的區域，而繼續在整個捕食空間尋找獵物。

借鑒PS思想，改進的PSGA(predatory search genetic algorithms)算法采取以下原理：算法運行時，首先以較大的交叉概率Pc1和較小的變異概率Pm1進行全局搜索；一旦發現一個較好的解，則改變為以較大的變異概率Pc2和較小的交叉概率Pm2進行局部搜索；如果在局部搜索過程中最優解得不到改善，則再以較大的交叉概率Pc1和較小的變異概率Pm1進行全局探索。在整個算法運行過程中，不斷地根據搜索解的情況自適應地調整交叉概率和變異概率的取值。

本文設計的PSGA算法的具體方法為：在進化過程中，根據適應度的變化來調整交叉和變異概率，以平衡全局搜索和局部開發。以最小化適應度為目標，設歷代最好適應度為gbest，當代最好適應度為fbest，以兩者的比值g=fbest/gbest來改變交叉和變異概率。設定一個小于1的正數k，比較g值和k值的大小，如果g≤k，則進行局部開發，優化代數為num代，交叉概率和變異概率分別取為Pc2和Pm2；如果g>k，則以Pc1和Pm1來更新交叉和變異概率。

這里k的取值對PSGA算法的性能有較大的影響，k可以取常量，也可以取變量。當k取常量時，若k值取得過大，則使得不同代數個體間的最優適應度值差異不明顯時就進行局部尋優，可能會圍繞一些非較優解進行局部搜索，從而影響算法的全局搜索性能；若k值取得過小，則使得不同代數個體間的最優適應度值具有較大差異時才進行局部尋優，可能會忽略掉進化過程中搜索到的一些較優解，從而影響算法的局部搜索性能。當k取變量時，考慮到遺傳算法在進化過程中，進化初期個體的差異性較大，不同個體間適應度值的差異相應較大，進化后期個體的差異性較小，不同個體間適應度值的差異也相應較小，因此k的值可以根據進化代數的增加逐漸遞增。

對于Pc1和Pm1的取值，采用自適應交叉和變異，Pc1和Pm1將隨著進化代數動態地改變。

Pc1=Pc1_max-(Pc1_max-Pc1_min)i/M，

Pm1=Pm1_min+(Pm1_max-Pm1_min)i/M，

(1)

式中：i為進化代數；M為總進化代數；Pc1_max，Pc1_min分別為最大、最小交叉概率；Pm1_max，Pm1_min分別為最大、最小變異概率。

對于Pc2和Pm2的取值，采取式(2)的方法：

Pc2=P0g，
Pm2=P1/g，

(2)

式中：P0，P1為固定值。

對于num的取值，采取方法為

num=「n/g?，

(3)

式中：“「·?”表示向上取整函數，如「3.4?=4；n為固定值。

改進的PSGA算法的具體步驟如下：

(1) 初始化種群，根據式(1)對交叉概率Pc1和變異概率Pm1取值。

(2) 計算種群中個體的適應度，并根據本代最佳適應度和歷代最佳適應度的比值g確定交叉和變異概率。如果g≤k，則根據式(2)進行局部優化num代；否則以Pc1和Pm1更新交叉和變異概率進行進化。

(3) 選擇。根據個體適應度的大小按輪盤賭方法選擇個體，并采用精英保留策略保留最優個體。

(4) 交叉。隨機配對交叉產生新個體。

(5) 變異。對種群中個體進行變異。

(6) 進化終止條件判斷，如滿足條件，則停止計算，輸出最佳結果；否則，執行(2)。

2.2 仿真測試

(1) 測試函數

對本文改進的PSGA算法的仿真測試采用2個經典函數，分別為一元多極值函數f1和多元多峰函數f2(Shubert函數)。

f1：f(x)=xsin(12πx)+2.0,x∈[-3.54]，

(4)

(5)

式中：f1為周期震蕩函數，在當前限定域中，當x=3.958 5時取得極小值-1.958 4；f2為一個多峰值多極值函數，在其定義域內總共有760個局部最小點，其中有18個是全局最小點，全局最小值為13.269 1。

(2)k值的確定

本文改進的PSGA算法對k的取值分為3種情況進行測試：k=0.8，k=0.99，k=0.8+0.19i/M，i為進化代數，M為總進化代數。測試結果如表1所示。表1中，算法的種群規模為80，針對每個函數，在每個k值和不同的最大設定代數情況下分別運行30次。收斂是指算法終止時，優化結果與理論最優值之間的誤差在0.001以內。

從表1可以看出：k取3種不同的值，當運行代數超過100代時，針對2個函數f1和f2，算法均收斂到理論最優解，顯示該算法具有較強的尋優能力。當運行代數為50代時，對f1，k=0.8和k=0.99時算法收斂性能稍好；對f2，k=0.8+0.19i/M時算法收斂性能稍好。可見k值的選擇要根據具體情況來確定。考慮到航跡規劃目標函數是一個復雜多極值函數，本文根據k=0.8+0.19i/M取值。

(3) 不同算法的比較

為了說明改進的PSGA算法的搜索性能，現將改進的PSGA算法與其他一些算法進行仿真測試比較，參與對比測試的算法為：基本遺傳算法(SGA)、自適應遺傳算法(AGA)及本文的PSGA算法。遺傳操作方式采取單點交叉和基本位變異。

GA算法中Pc=0.7，Pm=0.05。

AGA算法中自適應概率調整為

(6)

式中：fmax為種群中最大的適應度值；favg為每代種群的平均適應度值；f′為要交叉的2個個體中較小的適應度值；f為要變異個體的適應度值；Pc1=0.85；Pc2=0.5；Pm1=0.06；Pm2=0.03。

PSGA算法中，Pc1_max=0.85，Pc1_min=0.5，Pm1_max=0.06，Pm1_min=0.03，另P0=0.3，P1=0.06，n=5，k=0.8+0.19i/M。

仿真測試時，各算法的種群規模均為80，每個算法分別在不同的最大迭代代數設置下運行30次。測試的所有數據和結果都在同一計算環境上(即同一臺計算機、同一個操作系統和同一段時間內)運算所得。表2表示各算法針對不同的最大迭代代數設置分別運行30次的數據統計結果。

從表2中可以看出：

(1) 對函數f1,f2測試的結果數據中，最大迭代代數為50代時，PSGA算法稍不如AGA，主要原因是PSGA算法在發現較好解之后要進行局部搜索，由此降低了交叉概率，從而使種群中產生較好新個體的可能性變小，這在一定程度上影響了算法的收斂速度。尤其在進化早期，對算法的影響較大。

(2) 最大迭代代數設置為100，200，300代時，無論從平均適應度值、收斂次數，還是收斂到理論最優值的次數，PSGA算法均略優于GA，AGA，表明隨著迭代代數的增加，PSGA算法具有更高的收斂精度和收斂率，這說明PSGA算法在提高算法的搜索精度和防止陷入局部最優方面起到了很好的效果。

(3) 從表2的平均運行時間比較來看，對于算法的改進帶來程序在執行效率上的略微降低，但是，相對于達成優化目標而言，這種損失是必然的和可以接受的。

表1 PSGA算法在不同k值和不同進化代數下的測試結果Table 1 Test results for PSGA algorithm in different k values and different evolution algebras

3 PSGA算法在岸基導彈火力分配中的應用

3.1 火力分配模型

對導彈火力分配問題的解決一般假設[13]：紅方有k種導彈的發射平臺，而且每種發射平臺只發射某一型導彈；打擊目標有n個，目標重要程度為Wj,j=1,2,…,n，可用表達式Wj=(a1,a2)(sj,wj)T來表示，其中sj表示目標j的價值因素，wj表示目標j的威脅度，a1，a2為權重系數，0

(7)

式中：xij為第i種發射平臺用于打擊第j個目標的導彈數目。

此問題的模型可描述為:尋找問題一組解X,滿足以下目標函數與約束條件，目標函數為

(8)

約束條件為

(9)

毀傷概率Pij可表示為[14]

i=1,2，…,n，j=1，2，…,m，

(10)

故構建艦艇毀傷效益最優火力分配模型為

(11)

約束條件為

3.2 仿真算例

3.2.1 戰場想定

岸導部隊接上級指揮機關命令，對藍方某具有重要戰略意義的島嶼實施海上封鎖。岸導部隊通過合理選擇發射陣地，可使封鎖海域處于其火力打擊范圍之內。

據上級情報：藍方一海上護航運輸船編隊試圖借助高海情的掩護，對該島嶼實施裝備物資保障(其中2艘均可發射箔條彈和釋放電磁干擾的運輸船，3艘均裝備有防空武器和電磁干擾設備的護衛艦)。

考慮到特殊戰場條件下，艦艇不便出航、飛機不便出動的特殊情況，紅方岸導部隊獨立遂行打擊該編隊的任務，破壞藍方作戰企圖。作戰岸導部隊編制為1個團，下轄2個營。假設紅方信息渠道通暢，部隊已機動到達某預設陣地待機，隨時等待發射命令。戰場敵我態勢如圖1所示。

圖1 戰場態勢圖Fig.1 Battlefield situation

各參數取值如下：

(1) 綜合考慮運輸船A，B，護衛艦C，D，E的政治價值、軍事價值和經濟價值得到其綜合價值分別為0.8，0.7，0.4，0.3，0.3。

(2) 根據作戰主要目的(對運輸船進行打擊)，通過層次分析法對艦艇綜合價值和威脅度的權重進行歸一化處理后得到a1為0.7，a2為0.3。

(3) 參數數值

查閱導彈相關數據，并由有關公式計算得參數數值如表3所示。

表3 參數數值表Table 3 Numerical value of parameters

(4) 紅方岸導團對藍方運輸船編隊實施集火打擊，由于新型岸艦導彈連續發射時間間隔小于4.5 s，經過合理的航路規劃后，可以使48枚導彈同時從不同方向打擊敵編隊。

(5) 藍方編隊采取獨立防御措施，每艘艦艇獨立完成防御任務。艦艇之間的間距合理，1枚導彈不會同時擊傷2艘艦艇。

(6) 藍方艦船的彈藥數量沒有限制，即只要其沒有被消滅，就可以一直對來襲導彈進行攔截。

(7) 藍方戰場信息資源豐富，可以有效地對紅方導彈進行不同程度地攔截。

(8) 紅方戰區信息保障充分，岸導部隊發射陣地在戰區防空火力范圍內能獲得有效的信息保障。

3.2.2 仿真計算與分析

根據模型(11)，采用遺傳算法進行仿真。仿真條件為：Matlab7.1，CPU Pentium 1.6G 內存2G。仿真得到火力分配方案如表4所示。

表4 火力分配方案Table 4 Fire distribution scheme

導彈發射總數為43枚。其中21枚導彈對運輸船A，B進行了打擊，由于A，B的價值差異，較多的導彈(12枚)射向了價值較大的A船；另有22枚導彈對護衛艦C，D，E進行了打擊，由于護衛艦C的威脅度較高，但同時C艦的攔截概率也較高，導致導彈在3個目標間的分配數目差別不大(僅為1枚)。對各目標的毀傷概率依次為：0.96，0.95，0.84，0.87，0.87，對目標的毀傷程度均為擊毀。結果符合作戰要求。

從仿真結果可以看出：

(1) 分配方案證明了模型的有效性

分配方案符合作戰要求。其中在打擊運輸船編隊任務中，主要作戰目的是對運輸船進行打擊。由于2艘運輸船A，B的綜合價值分別為0.8，0.7，分配方案中打擊A船的導彈數目多于B船，在相同威脅度和射擊有利度條件下，導彈分配偏向了價值大的運輸船。

在3艘護衛艦C，D，E中，C艦綜合價值高于D艦和E艦(綜合價值依次為0.4，0.3，0.3)。在威脅度方面，C艦高于D艦，D艦高于E艦(威脅度依次為0.6，0.55，0.5)。因此在射擊有利度差別不大的情況下，導彈在3個目標間的分配數目差別不大。

(2) 分配方案反映了模型特點

極大化毀傷效益模型偏重對目標的毀傷效益。如果擁有導彈數目較充裕，其所得分配方案發射彈數目很大(43枚)，作戰消耗較大。如果沒有對某一目標進行集火射擊的導彈數目0≤xj≤12,j=1,2，…,5這一約束，其結果必然是發射所有導彈以求得最大的效益。

(3) 權重系數的選擇更有利于達成作戰意圖

考慮到主要作戰目的是對運輸船A，B實施火力打擊，而運輸船的威脅度相對護衛艦有一定差距，為了使分配方案符合作戰意圖，利用層次分析法將艦艇綜合價值sj和威脅度wj系數進行歸一化處理后設定各自權重為：0.7，0.3。因此威脅度的“地位”相對艦艇價值有所降低，即岸艦導彈火力分配方案在2個參數間進行決策時將偏重于艦艇綜合價值這一參數的大小。如果沒有權系數的引入，那么威脅度與艦艇綜合價值地位“平等”，分配方案必然傾向于護衛艦。即：在相同的毀傷概率條件下，護衛艦C的價值和威脅度乘積明顯高于運輸船A，分配方案必然偏重于護衛艦C。根據首長要求和作戰意圖，合理地確定和調整權重系數，對導彈火力分配方案有明顯影響。

4 結束語

本文將動物捕食思想引入遺傳算法，設計了一種基于捕食策略的改進遺傳算法，通過實例測試表明，該算法與基本遺傳算法、自適應遺傳算法相比具有更好的綜合搜索能力。進一步研究了基于改進遺傳算法的岸基導彈對海上艦艇目標攻擊時的火力分配問題，構建了火力分配模型，通過仿真實驗驗證了模型及算法的有效性。

參考文獻：

[1] SZCZERBA R J,GALKOWSKI P G,LICKSTIN I S,et al.Robust Algorithm for Real-Time Route Planning[J].IEEE Transactions on Aerospace and Electronic Systems,2000,36(3):869-878.

[2] 姚毅.基于遺傳算法的戰斗機低空突防航路規劃研究[D].武漢:海軍工程大學,2007.

YAO Yi.Low-Altitude Penetration Path Planning Based on Genetic Algorithm[D]. Wuhan:Naval University of engineering, 2007

[3] 袁麟博,章衛國,李廣文.一種基于遺傳算法-模式搜索法的無人機路徑規劃[J].彈箭與制導學報,2009,29(3):279-282.

YUAN Lin-bo, ZHANG Wei-guo, Li Guang-wen.A UAV Path Planning Based on Genetic Algorithm-Pattern Searching[J].Journal of Missiles and Guidance, 2009,29(3): 279-282.

[4] 馬云紅,周德云.一種無人機路徑規劃的混沌遺傳算法[J].西北工業大學學報,2006,24(4): 468-471.

MA Yun-hong, ZHOU De-yun. A UAV Path Planning Based on Chaos Genetic Algorithm[J]. Journal of Northwestern Polytechnical University, 2006,24(4): 468-471.

[5] 雷英杰,張善文,李繼武,等.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2005.

LEI Ying-jie, ZHANG Shan-wen, LI Ji-wu ,et al. Genetic Algorithm Toolbox and Its Application in MATLAB [M]. Xi’an: Xi’an Electronic and Science University Press, 2005.

[6] BAGLEY J D.The Behavior of Adaptive Systerm which Employ Genetic and Correlation Algorithm[J].Dissertation Abstricts International,1967,28(12):78-90.

[7] 胡大偉,陳誠.遺傳算法和禁忌搜索算法在配送中心選址和路線問題中的應用[J].系統工程理論與實踐,2007,9(9):171-176.

HU Da-wei, CHEN Cheng. Application of Genetic Algorithm and Tabu Search Algorithm in Distribution Center Location and Routing Problems[J].Systems Engineering Theory and Practice, 2007,9(9): 171-176.

[8] 王雪梅,王義和.模擬退火法與遺傳算法的結合[J].計算機學報,1997,20(4):381-384.

WANG Xue-mei, WANG Yi-he.Combining Simulated Annealing Algorithm with Genetic Algorithm[J].Chinese Journal of Computers, 1997,20(4): 381-384.

[9] 明亮.遺傳算法的模式理論及收斂理論[D].西安:西安電子科技大學,2006.

MING Liang.Schema Theory and Convergence Theory of Genetic Algorithm[D]. Xi'an: Xi'an Electronic and Science University, 2006.

[10] 張頂學,關治洪,劉新芝.基于捕食搜索策略的遺傳算法研究[J].計算機應用研究，2008,25(4): 1006-1007.

ZHANG Ding-xue,GUANG Zhi-hong,LIU Xin-zhi.Research on Genetic Algorithm of Predatory Search Strategy [J].Computer Application Research，2008,25(4): 1006-1007.

[11] LINHARES A.Preying on Optima:a Predatory Search Strategy for Combinatorial Problems[C]∥Proc of IEEE International Conference of Systems,Man and Cybernetics.Piscataway NJ, 1998: 2974-2978.

[12] LINHARES A.Synthesizing a Predatory Search Strategy for VLSI Layouts[J].IEEE Tran.On Evolutionary Computation,1999,3(2):147-152.

[13] 馮杰.遺傳算法及其在導彈火力分配上的應用[J].火力與指揮控制,2004,29(2):43-45.

FENG Jie.Genetic Algorithm and Its Application in Missile Fire Allocation[J].Fire Control and Command System,2004,29(2): 43-45.

[14] 楊飛,董朝陽. 實施飽和攻擊的反艦導彈武器火力分配[J].系統仿真學報，2011,23(2):316-320.

YANG Fei,DONG Zhao-yang.The Fire Allocation in Saturation Attack for Anti-Ship Missile[J].Journal of System Simulation，2011,23(2):316-320.

[15] 胡正東,丁洪波. 反艦導彈武器系統的火力分配方法研究[J].戰術導彈技術，2008,6(2):1-3.

HU Zheng-dong, DING Hong-bo.The Allocation Methods of Anti-Ship Missile Weapon System[J].Tactical Missile Technology，2008,6(2):1-3.

[16] 尤大德,徐德民.水面艦艇防空武器抗擊單枚反艦導彈的效能評估[J]. 火力與指揮控制,2010,16(10):81-83.

YOU Da-de, XU De-min.Effectiveness Evaluation of Warship Air Defense Weapons Against Single Anti-Ship Missile[J]. Fire Control and Command,2010,16(10):81-83.