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

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

(1)

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

飛行高度Hr的設(shè)置是為了更好地跟隨地形飛行，提高掩護(hù)效果[3]，其表達(dá)為

(2)

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

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

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

(3)

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

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

(4)

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

(5)

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

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

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

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

圖2　智能體網(wǎng)格Fig 2　Agent lattice

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

1)初始化基因編碼

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

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

(6)

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

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

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

(7)

2)初始化種群

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

3)變異(mutation)

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

(8)

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

(9)

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

4)交叉(crossover)

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

(10)

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

(11)

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

5)選擇(selection)

接著對(duì)Croi進(jìn)行適應(yīng)度評(píng)價(jià)，若滿足式(12),則在下一代中用Croi替換Xi

(12)

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

6)自學(xué)習(xí)

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

(13)

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

ei′j′k=

(14)

這里面的sradius∈[0,1]表示搜索的半徑。由上面所產(chǎn)生的智能體經(jīng)過變異、交叉，之后和上面的目標(biāo)智能體進(jìn)行比較，選出適應(yīng)度最高的個(gè)體代替本代的最終智能體。

7)循環(huán)迭代

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

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

3仿真驗(yàn)證

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

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn):

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

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

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

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

[5]余斌.Multi-Agent 研究與應(yīng)用[D].合肥：安徽大學(xué)，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]王健.基于遺傳算法的無人機(jī)飛行器航跡規(guī)劃研究與實(shí)現(xiàn)[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2011.

[8]饒衛(wèi)平，楊任農(nóng)，雷曉義，等. 基于多智能體遺傳算法的無人機(jī)突防航線規(guī)劃[J].計(jì)算機(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

中圖分類號(hào)：TP 18

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

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

作者簡(jiǎn)介:

饒衛(wèi)平(1990-)，男，陜西商洛人，碩士研究生，主要研究領(lǐng)域?yàn)槿蝿?wù)規(guī)劃。

楊任農(nóng),通訊作者，E—mail:857805523@qq.com。