基于多智能體遺傳算法的戰(zhàn)術航段優(yōu)化

饒衛(wèi)平， 楊任農， 雷曉義， 柴毅哲

(空軍工程大學 航空航天工程學院，陜西 西安 710038)

?

基于多智能體遺傳算法的戰(zhàn)術航段優(yōu)化

饒衛(wèi)平， 楊任農， 雷曉義， 柴毅哲

(空軍工程大學 航空航天工程學院，陜西 西安 710038)

摘要:針對飛機戰(zhàn)術飛行要求和威脅規(guī)避目標的問題，采用優(yōu)勢函數和戰(zhàn)術規(guī)避相結合的原則，將戰(zhàn)術航段優(yōu)化問題轉化為路徑搜索問題，提出了基于多智能體遺傳算法來解決此問題。采用自適應交叉和變異算子，改進自學習算子獲取子代的算法，實現了全局最優(yōu)的結果。通過和傳統(tǒng)遺傳算法進行仿真比較，相比之下，基于多智能體的遺傳算法可以有效利用地形，實現戰(zhàn)術飛行。

關鍵詞：戰(zhàn)術優(yōu)化； 多智能體； 遺傳算法

0引言

飛機戰(zhàn)術飛行是飛機空戰(zhàn)和突防的重要內容。突防中的戰(zhàn)術飛行動作，是根據實時的飛行環(huán)境，在飛行員的判斷和戰(zhàn)術決策下，做出的符合戰(zhàn)術任務的動作，這些動作將使飛機盡可能處于自我保護狀態(tài)下，從而發(fā)射武器，打擊目標，以此來提高作戰(zhàn)能力的目的。

在飛行中，需要對戰(zhàn)術動作進行一定的決策，而這些決策動作是根據機動動作庫組合起來實現的，然后,基于這些戰(zhàn)術動作根據戰(zhàn)場環(huán)境對戰(zhàn)術進行優(yōu)化。戰(zhàn)術優(yōu)化的基本思想是建立優(yōu)化目標函數，利用機動動作庫，采用某種優(yōu)化方法，在一定的約束限制情況下尋求最佳的優(yōu)化設計。戰(zhàn)術優(yōu)化設計需滿足以下幾個特點：1)限制較多:由于突防情況所考慮的條件眾多，既要考慮飛機飛行要求，又要考慮戰(zhàn)場地形條件，還要規(guī)避威脅，使得優(yōu)化過程約束條件眾多。2)優(yōu)化評價函數必須滿足飛機速度、飛行高度、戰(zhàn)術動作，先進武器的發(fā)射以及規(guī)避威脅等因素。3)戰(zhàn)場環(huán)境復雜，對數據模型的建立比較困難。戰(zhàn)場環(huán)境瞬息萬變，敵人雷達火炮的不可預知，這些都加大了模型建立的難度[1]。

國內外對戰(zhàn)術優(yōu)化的方法已進行了大量的研究，如Voronoi圖法[2]、A*搜索法、微分進化法等。這些方法在解決復雜非線性戰(zhàn)術優(yōu)化問題上存在著一定的局限性，如無法得到最優(yōu)解、運算量巨大等。但是遺傳算法因其自身隱含的并行性和多目標優(yōu)化特點，適合于復雜、非線性的優(yōu)化問題，因而，受到越來越多的學者研究。由于傳統(tǒng)的遺傳算法具有初始種群隨機生成的特性，在進化過程中容易陷入局部最優(yōu)，因此，本文引入多智能體技術，采用自適應的交叉變異算子，將多智能體的優(yōu)點和遺傳算法的優(yōu)點結合，從而有效地解決了飛行戰(zhàn)術優(yōu)化的問題。

1戰(zhàn)術優(yōu)化問題的數學描述

對戰(zhàn)術航段的優(yōu)化是一個典型的多目標優(yōu)化問題。為了評價一段戰(zhàn)術航段的好壞應該從戰(zhàn)術要求、飛行狀態(tài)、環(huán)境條件進行詳細分析以此來判斷是否達到飛行器的最佳飛行指標和是否達到最佳的戰(zhàn)術意圖。飛行指標由飛行評價函數fRoute表示，其意義是戰(zhàn)斗機作為飛行器的一類，即戰(zhàn)斗機具有飛行屬性，這就需要其在飛行過程中盡可能達到距離約束Dr和高度約束Hr，以減少對裝備的損耗以及飛行中的油耗；戰(zhàn)術指標執(zhí)行的好壞則可以由戰(zhàn)術評價函數ftactic表示，其意義是戰(zhàn)斗機作為戰(zhàn)斗單元的一類，即戰(zhàn)斗機具有戰(zhàn)斗屬性，這就需要其在飛行過程中盡可能達到戰(zhàn)術指標，由攻擊條件決定，包括在敵目標區(qū)飛行時間tfly盡可能短，飛行高度hfly盡可能低，被敵威脅源探測的概率fthreat盡可能小，以及被鎖定時需進行盡可能劇烈的機動elock。

其中,Dr為飛行航路的限制約束，則其可以表示為

(1)

式中dxi,xi-1為航跡點xi到xi+1的距離，dmin為開始規(guī)劃點到目標點的直線距離。

飛行高度Hr的設置是為了更好地跟隨地形飛行，提高掩護效果[3]，其表達為

(2)

式中hi為戰(zhàn)術航段點i高度，hmax為飛行最大高度。

以雷達或導彈為中心，其周邊處于不同的位置的點所感知的信息是不同，這些信息將影響飛機所受到的威脅程度，其信息感知范圍可以分為四類：通信范圍RC,偵察范圍RS，作戰(zhàn)范圍RT，行動范圍RM，如圖1所示，顯然有RC>RS>RT>RM[4]。這些感知范圍對于飛機的威脅也是不同的，其構成了一個多環(huán)的威脅模型，飛機處于不同的“環(huán)”其所受威脅程度是不一樣的，在同一環(huán)內其威脅值可以簡單地認為只與飛機與威脅源的距離成比例，那么被敵探測概率可以表示為式(3)

圖1　信息感知多環(huán)示意圖Fig 1　Diagram of multi-cyclic of information perception

(3)

式中TM,TT,TS,TC分別為飛機進入RM,RT,TS與RC環(huán)的懲罰值，顯然有TM>TT>TS>TC，Rl為飛機到威脅源的水平距離，R5為飛機可被威脅的最大距離。

機動劇烈程度評價函數elock與飛機機動時過載的變化率有關，但是劇烈的機動不能有太大的速度v，一般不高于0.7MH，即約等于210m/s，那么在某一區(qū)域的停留時間Δti必然大于以最大速度通過的時間ti min=li/vi max，且劇烈的機動通常會帶來航段長度l的增加與飛行高度hi的損失，可見兩個目標是互相沖突的。對于規(guī)避防空導彈來說，一般可以得到elock的數學表達式為

(4)

即在某一時刻飛機的控制量變化越劇烈就認為其更可能不被鎖定或更容易脫鎖，其中wlock1,wlock2與wlock3為加權系數，根據具體機動的情況而定，與基本機動動作相對應。通過以上分析，已經可以給出此多目標優(yōu)化問題的數學描述，其中一個目標是我方戰(zhàn)機的飛行代價froute(x)最小，另一個目標是戰(zhàn)機的戰(zhàn)術代價floxk(x)最小，如式(5)

(5)

就躲避防空導彈攻擊而言,需要考慮借助地形進行規(guī)避，那么高度指標可以放寬些，即w2可以設置的小一些。具體的加權系數應根據上級指揮信息系統(tǒng)給出的具體任務的交戰(zhàn)規(guī)則得出，仿真一般按照：首先保存自己、其次完成任務的邏輯對加權系數做以限定，即系數w5，w6最高，下來是w3，w4兩個參數，而w1，w2最小。

2多智能體遺傳算法求解戰(zhàn)術優(yōu)化問題

智能體是物理或者虛擬的實體，具有自治性、反應性、主動性和適應性等特點，因此，可以描述多變復雜的環(huán)境[5]。由若干智能體為了相同的目的而相互協同作用形成的計算系統(tǒng)就構成了多智能體系統(tǒng)。將戰(zhàn)場環(huán)境轉換為三維網格，由網格點所組成的一個戰(zhàn)術航路代表一個智能體，這樣不同的戰(zhàn)術航路所組成的集合就構成了智能體網格，記為L，網格的大小為Lsize×Lsize，其中,Lsize為整數。每個智能體固定在一個格子點上，則第i行、第j列的智能體為Li,j，i,j=1,2,…,Lsize，每個智能體不能移動，只能和鄰域發(fā)生作用。

智能體網格如圖2所示，每個圓圈表示一個智能體，圈中的數字表示該智能體在網格中的位置，而有連線的兩個智能體才能發(fā)生相互作用[6]。

圖2　智能體網格Fig 2　Agent lattice

基于以上定義，給出具體算法過程如下：

1)初始化基因編碼

定義待優(yōu)化的有效段為一個染色體(即一個個體)，一個基因即為該段中的一個仿真點，可表示為Wi=〈xi,yi,zi,Vi,θi,ψi〉，且優(yōu)化航段起始點和終止點的狀態(tài)是不變的，那么其可行解為

X=[x1,y1,z1,V1,θ1,ψ1,…,xn,yn,zn,Vn,θn,ψn].

(6)

若設種群規(guī)模為N，則解的空間為

Xi=[xi1,yi1,zi1,Vi1,θi1,ψi1,…,xin,yin,zin,Vin,θin,

ψin],i=1,2,…,N.

(7)

2)初始化種群

由所有的基因編碼組成的一個可行解組成的集合就是初始化種群的一個個體，表示為X0=[x01,y01,z01,V01,θ01,ψ01,…,x0n,y0n,z0n,V0n,θ0n,ψ0n]，假設種群規(guī)模為100，則可將這些種群作為由100個智能體所組成的多智能體網格，對多智能體進行遺傳操作。

3)變異(mutation)

首先根據式(8)產生一個新的智能體muti,j=(e1,e2,ek…,en),其中

(8)

其中,G(0,1/t)為高斯分布的隨機數，t為進化的代數。然后用這個新生成的Muti,j來代替Li,j。這種變異算子采用了高斯變異算子，所以，只在Li,j上的某些分量上疊加了一個小的擾動。而pm可由下列函數表示為

(9)

式中f為變異個體的適應度值，而pm1和pm2分別為設定好的最大和最小的變異概率。利用這個式子可以達到自適應性的目的[7]。

4)交叉(crossover)

將變異后的個體Muti,j=(e1,e2,…，en)與目標個體Xi,j=(x1,x2,…,xn)進行雜交來產生新的個體Croi,j=(c1,c2,…,cn)，這里使用二元交叉

(10)

其中，rand是[0,1]之間的隨機數，j=rand(i)使得至少會有一個基因發(fā)生變化，保證了每次交叉都會有新個體產生。這里的Pc可以采用具有自適應功能的交叉算子[7]

(11)

式中f ′為需要交叉?zhèn)€體的適應度值，fmax和fave為種群的最大適應度和平均適應度值，而pc1和pc2分別為設定好的最大和最小的交叉概率。

5)選擇(selection)

接著對Croi進行適應度評價，若滿足式(12),則在下一代中用Croi替換Xi

(12)

其中，f(x)=froute(x)+ftactic(x),這里規(guī)定每產生一個Croi個體即馬上進行選擇，并參與后續(xù)的進化過程。

6)自學習

智能體可以通過自學習來提高求解能力，這里根據Li,j的信息構建一個小規(guī)模的多智能體遺傳算法[8]。在自學習算子中，首先需要生成一個智能體的網格，這里用SL表示，其大小定義為sLsize×sLsize，其上的所有智能體表示為sLi′,j′,i′,j′=1,2,…，sLsize，其由式(13)產生

(13)

在這里的Newi′,j′=(ei′,j′,1,ei′,j′,2,…,ei′,j′,n),而其中根據式(14)產生

ei′j′k=

(14)

這里面的sradius∈[0,1]表示搜索的半徑。由上面所產生的智能體經過變異、交叉，之后和上面的目標智能體進行比較，選出適應度最高的個體代替本代的最終智能體。

7)循環(huán)迭代

遍歷所有的種群，并進行循環(huán)迭代，直到滿足最大迭代次數結束。整個操作的流程如圖3所示。

圖3　多智能體遺傳算法流程圖Fig 3　Flow chart of multi-agent genetic algorithm

3仿真驗證

參數設置如下：wlock1=0.4,nxG=2,wlock2=0.3,nyG=6,wlock3=0.3,γG=π/4；加權系數w1=0.2，w2=0.2，w3=0.4，w4=0.4,w5=0.6，w6=0.6，在使用多智能體遺傳算法時所設置的仿真參數為：Lsize=10，pc1=0.4，pc2=0.7，pm1=0.01，pm2=0.05，sLsize=4，sradius=0.2得到仿真結果如圖4與圖5，仿真總用時124s。

圖4　優(yōu)化結果局部放大后的三維效果圖Fig 4　3D effect picture of amplifying optimized result

圖5　優(yōu)化結果俯視圖Fig 5　Top view of optimized result

圖5圓圈中標示出的兩條黑色線條即經過多智能體遺傳算法優(yōu)化出的戰(zhàn)術軌跡，分別記為優(yōu)化后的戰(zhàn)術軌跡段1和優(yōu)化后的戰(zhàn)術軌跡段2，可以看出:軌跡段考慮了一定的地形因素并做出了一定的戰(zhàn)術機動，為了更清楚地觀察優(yōu)化結果，將使用多智能體遺傳算法優(yōu)化和普通遺傳算法的結果放在一起進行比較如圖6所示。

圖6　多智能體遺傳算法和普通遺傳算法對戰(zhàn)術軌跡段1與戰(zhàn)術軌跡段2優(yōu)化俯視對比圖Fig 6　Topview comparison of optimization of tactical route 1and tactical route 2 using multi-agent genetic algorithm andtraditional genetic algorithm

圖6(a)為通過多智能體遺傳算法和普通遺傳算法對戰(zhàn)術軌跡段1優(yōu)化俯視對比圖，圖6(b)為通過這兩種方法對戰(zhàn)術軌跡段2優(yōu)化的俯視對比圖，其中黑色線條為多智能體遺傳算法所優(yōu)化的不同部分，灰色為普通話遺傳算法所優(yōu)化的情況，從中可以清晰地看出多智能體遺傳算法優(yōu)化的軌跡(黑色表示)對地形有較明顯的回避，且曲線較為平滑，結果較為滿意。

4結論

本文將多智能體改進的遺傳算法引進到突防戰(zhàn)術優(yōu)化中，建立了合適的評價函數，尤其是對威脅進行分環(huán)分析，使用網格形式存儲智能體，并對遺傳算法進行自適應的交叉因子和變異因子改進，極大改進了傳統(tǒng)遺傳算法容易陷入局部收斂的情況。通過引進多智能體系統(tǒng)，尤其是自學習算子，有效地將自學習自適應的特點體現出來。仿真結果顯示：此算法有效優(yōu)化戰(zhàn)術航段，具有很好的實用價值。

參考文獻:

[1]周德云，李峰，蒲小勃，等.基于遺傳算法的飛機戰(zhàn)術飛行動作決策[J].西北工業(yè)大學學報，2002,20(1)：109-112.

[2]McLainTW,ChandlePR,RasmussenS,etal.CooperativecontrolofUAVrendezvous[C]∥Proceedingsofthe2001AmericanControlConference,2001:2309-2314.

[3]巴海濤.無人機航跡規(guī)劃研究[D].西安：西北工業(yè)大學，2006.

[4]劉勝.基于Agent的機動通信戰(zhàn)術規(guī)劃的研究[D].杭州：浙江大學，2006.

[5]余斌.Multi-Agent 研究與應用[D].合肥：安徽大學，2006.

[6]Peng Zhihong,Wu Jinping,Chen Jie.Three-dimensional multi-constraint route planning of unmanned aerial vehicle low-altitude penetration based on coevolutionary multi-agent genetic algorith-m[J].Journal of Central South University of Technology,2011,18(5):1502-1508.

[7]王健.基于遺傳算法的無人機飛行器航跡規(guī)劃研究與實現[D].長沙：國防科技大學，2011.

[8]饒衛(wèi)平，楊任農，雷曉義，等. 基于多智能體遺傳算法的無人機突防航線規(guī)劃[J].計算機仿真，2015,32(4)：39-43.

Tactical optimization based on multi-agent genetic algorithm

RAO Wei-ping, YANG Ren-nong, LEI Xiao-yi, CHAI Yi-zhe

(College of Aeronautics and Astronautics Engineering,Air Force Engineering University,Xi’an 710038,China)

Abstract:Aiming at demand of tactical flight and problem of threating avoidance target in airplane route planning,using principle combining advantage function with tactics avoidance,tactical segment optimization problem is turned into path searching issue,propose a tactical segment optimization method based on multi-agent genetic algorithm.By adopting self-adaptive crossing and mutation operator, improve algorithm which acquirs next-generation by self-learning operator ,achieve global optimal result.Simulation results show that compared with traditional ones the improved genetic algorithm can effectively use terrain to fulfill tactical flight tasks.

Key words:tactical optimization; multi-agent; genetic algorithm

DOI:10.13873/J.1000—9787(2016)03—0040—04

收稿日期：2015—07—16

中圖分類號：TP 18

文獻標識碼：A

文章編號：1000—9787(2016)03—0040—04

作者簡介:

饒衛(wèi)平(1990-)，男，陜西商洛人，碩士研究生，主要研究領域為任務規(guī)劃。

楊任農,通訊作者，E—mail:857805523@qq.com。