逆轉(zhuǎn)變異蟻群算法在CGF多目標分配中的應(yīng)用

張 媛， 張立民， 劉文彪， 陳 潔

(海軍航空工程學(xué)院，a.4系;b.7系;c.3系，山東 煙臺 264001)

0 引言

目標選擇屬于組合優(yōu)化的NP問題，其目的是通過目標排序，確定目標的優(yōu)先級，將優(yōu)化目標分配給各友機，以便各CGF(Computer Generated Forces)實體采取有針對性的應(yīng)對措施。虛擬空戰(zhàn)仿真中的目標分配是許多CGF作戰(zhàn)飛機行為決策的基礎(chǔ)，它模擬的準確性直接影響其他CGF實體行為和實體模擬的真實性。

近年來，在多機協(xié)同目標分配決策仿真中，文獻［1－5］采用遺傳算法解決最優(yōu)目標的分配問題。雖然遺傳算法能夠在可行時間內(nèi)得到較大問題規(guī)模的滿意解，但是其交叉算子的合適選擇是十分困難的，而且還存在著所謂的“基因漂移”現(xiàn)象，從而使算法容易陷入局部最優(yōu)。隨著蟻群算法在解決離散組合優(yōu)化問題方面的良好性能體現(xiàn)［6］，黃樹采首先將基本蟻群算法應(yīng)用于防空C3I系統(tǒng)的目標分配問題研究中［7］，隨后文獻［8－11］根據(jù)各自仿真要求對基本蟻群算法進行了改進，實現(xiàn)了超視距空戰(zhàn)條件下協(xié)同空戰(zhàn)的目標分配問題。但是蟻群算法收斂速度一般比較慢并且易于陷入局部最優(yōu)狀態(tài)［12］的缺點仍沒有很好地得到解決。

受文獻［13］中對預(yù)警機指揮引導(dǎo)下多機協(xié)同空戰(zhàn)目標選擇方案的優(yōu)化求解啟發(fā)，本文將遺傳算法的逆轉(zhuǎn)變異算子融入蟻群算法中，對蟻群算法問題解空間搜索策略以及信息素強度更新規(guī)則進行改進和設(shè)計，提高了CGF實體指揮決策過程中目標選擇方案的搜索效率。

1 多機協(xié)同目標選擇問題描述

假定有m架藍方戰(zhàn)機與n架紅方戰(zhàn)機進行空戰(zhàn)，在預(yù)警機指揮引導(dǎo)下，空中指揮員已獲得紅藍雙方的飛行態(tài)勢。根據(jù)文獻［14］中關(guān)于超視距協(xié)同空戰(zhàn)整體威脅態(tài)勢的計算方法，建立藍機Bj對紅機Ri(j=1，2，…，m)的態(tài)勢優(yōu)勢矩陣 s=［sij］，i=1，2，…，n，j=1，2，…，m，目標分配的最優(yōu)解指標取分配戰(zhàn)機打擊全部目標的優(yōu)勢函數(shù)最大。取決策變量xij，xij表示第i個火力單元(戰(zhàn)機平臺)是否打擊第j個來襲目標，有

根據(jù)文獻［13，15－17］建立目標分配優(yōu)化函數(shù)表達式為

式中:J表示一輪具體目標分配后分配紅方編隊飛機迎擊全部目標的最小不利因素函數(shù);sij為紅方第i架飛機對藍方第j架飛機的綜合態(tài)勢優(yōu)勢函數(shù)值;Rj表示第j架藍機的戰(zhàn)役價值;d1和d2為加權(quán)系數(shù)，根據(jù)作戰(zhàn)任務(wù)的不同而定。如要進行要地防空任務(wù)時，取d1=0.4，d2=0.6;純空空格斗時可選取 d1=1，d2=0;對于藍方戰(zhàn)機數(shù)大于紅方戰(zhàn)機最大攻擊能力時，選取d1=0.6，d2=0.4。

2 目標優(yōu)化選擇模型設(shè)計

蟻群算法是意大利學(xué)者Macro Dorigo最早在國際上提出的［18］，并用該算法求解TSP等問題，取得了較好的效果。應(yīng)用蟻群算法求解協(xié)同目標分配問題，根據(jù)協(xié)同目標分配的特點，對蟻群算法進行如下改進:

1)將分配紅方戰(zhàn)機打擊全部藍方目標的優(yōu)勢函數(shù)最大作為最優(yōu)解指標;

2)紅方每攻擊一架藍方飛機后，應(yīng)對原來的態(tài)勢優(yōu)勢函數(shù)矩陣進行修正;

3)信息素強度采用全局修正規(guī)則進行信息更新;

4)借鑒遺傳算法的變異操作思路，當蟻群算法中目標分配的優(yōu)化解在一次循環(huán)內(nèi)沒有明顯改進時，可對此時獲得的解進行逆轉(zhuǎn)變異操作，可以提高目標分配的全局策略。

2.1 目標分配策略

為了避免目標分配在搜索的一開始就以較大的概率集中于局部幾個優(yōu)勢函數(shù)較大的目標上，進而失去目標解的多樣性，改進算法中設(shè)置一個信息量刺激閾值p0，只有當信息量的刺激趨于閾值p0時，螞蟻才在信息量的刺激下趨于信息量較大的路徑，以獲取多樣性的解，將分配的目標放入目標分配矢量π中，π=(T1，T2，…，Tm)。π(i)=Tj表示紅方第 i架飛機攻擊藍方目標 Tj，Tj∈R，j=1，2，…，m。那么處在目標節(jié)點r的第k只螞蟻依據(jù)方程(3)可選擇所要轉(zhuǎn)移的目標單元節(jié)點j為

式中:p0∈(0，1);r是(0，1)中均勻分布的隨機數(shù);τij是節(jié)點i和j之間的信息素強度;ηij是螞蟻搜索時的啟發(fā)信息值，取啟發(fā)式信息值ηij=d1sij+d2Rj;α≥0是軌跡的相對重要性;β≥0是螞蟻搜索時的啟發(fā)式信息值。

由上式可知，螞蟻在選擇路徑時盡可能選擇目標綜合優(yōu)勢大而且信息素強度趨于閾值p0的方向，在一定程度上削弱了蟻群陷入局部最優(yōu)的趨勢。

2.2 信息量的全局修正

隨著進化時間的推移，以前留下的信息逐漸消逝，用參數(shù)(1－ρ)表示信息消逝程度，經(jīng)過n個時刻，螞蟻完成一次循環(huán)，信息素強度全局更新規(guī)則表示為

其中，

式中:Δτij=表示第k只螞蟻發(fā)現(xiàn)本次循環(huán)中的最短路徑;Q為比例系數(shù)，影響算法的收斂速度;Ek表示第k只螞蟻在本次循環(huán)中獲得的紅方飛機打擊藍方飛機的不利因素函數(shù)值。

通過式(4)可以看出，只有構(gòu)成全局最優(yōu)路徑的邊才有機會增加信息素水平，其他邊的信息素則由于揮發(fā)作用逐漸降低而使搜索的目的性大大增強。

2.3 引入逆轉(zhuǎn)變異方式

為了克服蟻群算法計算時間較長的缺陷，借鑒遺傳算法的變異操作思路，當蟻群算法獲得的目標選擇優(yōu)化解在一次循環(huán)內(nèi)沒有明顯改進時，則對該最優(yōu)解進行逆轉(zhuǎn)變異操作，可以提高目標選擇的全局搜索能力，明顯改善整體的性能。

逆轉(zhuǎn)變異操作是從一次循環(huán)中的最優(yōu)解個體中隨機挑選兩個逆轉(zhuǎn)點，再將兩個逆轉(zhuǎn)點間的基因交換，逆轉(zhuǎn)變異過程表示為變異前A'取2 4 1 3 5 7，變異后A″取2 5 1 3 4 7。

定義逆轉(zhuǎn)變異條件為

其中:i0i1i2…i(n－1)，(i0，i1，i2，…，i(n－1)∈{0，1，2，…，n －1})表示某個個體所走路徑。s1，s2∈{0，1，2，…，n－1}，符號“/”表示整除符號。進行操作 inversion(s1，s2，solutioni)，函數(shù) inversion()的功能是把個體solutioni的s1+1和s2這一段路徑顛倒過來進行變異，變異的次數(shù)是隨機的。這一過程涉及的運算比蟻群算法中的循環(huán)過程要簡單得多，因此只需要較短的時間便可完成相同次數(shù)的運算。經(jīng)過這種變異算子作用后，這一代解的性能會明顯改善，也大大改善了整個群體的性能，從而減少計算時間，提高搜索效率。

2.4 仿真步驟

基于變異蟻群算法求解協(xié)同目標選擇步驟分7步實現(xiàn):

1)nc←0(nc為迭代步數(shù)或搜索次數(shù))，給τij(i=1，2，…，n;j=1，2，…，m)矩陣賦相同的數(shù)值，給出 Q，ρ的值;

2)將S只螞蟻隨機放在S個初始目標節(jié)點上;3)對每個螞蟻按轉(zhuǎn)移概率Pkij選擇下一個節(jié)點;

4)計算本次分配的不利函數(shù)的和E，比較出最好的結(jié)果(E最小)，并記錄此次循環(huán)中最好結(jié)果的最優(yōu)路徑;

5)根據(jù)式(6)進行最優(yōu)解空間的逆轉(zhuǎn)變異條件判斷，若變異后路徑長度小于變異前，就保留這次最優(yōu)分配方案，否則維持原值;

6)按更新方程(4)修改信息強度，nc←nc+1;

7)若nc大于規(guī)定的循環(huán)次數(shù)，記錄當前螞蟻的位置(當前的解)，停止運行，輸出最好的解，否則轉(zhuǎn)第3)步。

3 算法實驗

假設(shè)紅方有8架A型截擊機A1～A8(各帶1枚可迎頭攻擊的某型中程空空導(dǎo)彈:射程為75 km，使用高度22000 m，Ma數(shù)為4)，使用高度22000 m。藍方參戰(zhàn)飛機為兩架B型(B1、B2)和兩架 C型(C3、C4)戰(zhàn)機(各帶兩枚可全向攻擊的某兩型遠程空空導(dǎo)彈，射程分別為70 km和80 km，使用高度分別為18000 m和20000 m，Ma數(shù)均為3)，使用高度為18000 m。藍機的機型為F－16D和F－15E，其雷達最大跟蹤距離分別為130 km和140 km。紅機的雷達最大跟蹤距離Ri=120 km。在某一時刻紅方機群坐標為A1(－30 km，190 km，10 km)，A2(20 km，200 km，12 km)，A3(－20 km，190 km，10 km)，A4(20 km，200 km，12 km)。藍方機群坐標為 B1(－42 km，260 km，7 km)、B2(10 km，276 km，11 km)、C3(－20 km，265 km，10 km)、C4(30 km，270 km，10 km)，將上述參數(shù)帶入文獻［14］關(guān)于超視距協(xié)同空戰(zhàn)整體優(yōu)勢態(tài)勢的計算公式中，計算出超視距協(xié)同空戰(zhàn)態(tài)勢數(shù)據(jù)，如表1所示。

表1 態(tài)勢矩陣Table 1 The situation matrix

根據(jù)文獻［14］中關(guān)于總體態(tài)勢威脅評估函數(shù)的定義，由表1可知，A7對B1的優(yōu)勢最小，優(yōu)勢值為0.1021，故紅方應(yīng)派出相應(yīng)的飛機對B1進行攻擊;同理可得，B2對A5，C3對A6以及C4對A2均具有很大的威脅。因此，為避免紅方兵力的殲滅，預(yù)警機應(yīng)采取相應(yīng)的目標分配方案來引導(dǎo)紅方戰(zhàn)機進行空戰(zhàn)。

設(shè)置藍方飛機4個目標的戰(zhàn)役價值向量R為(0.8，0.8，0.6，1.0)，按照參數(shù)的最優(yōu)選擇原則［19］，經(jīng)反復(fù)參數(shù)設(shè)置實驗，目標分配RAACA算法參數(shù)設(shè)置為 Q=1000，α =0.1，β =1.5，ρ=0.1，p0=0.8，利用Matlab在相同條件下對本例進行仿真，得出目標分配運算結(jié)果π，如式(7)和表2所示。

求得最優(yōu)解時，E=0.2636，J=6.0032。

表2 目標分配優(yōu)化方案Table 2 The optimal method for the target assignment

為了進一步驗證RAACA算法在多機協(xié)同空戰(zhàn)仿真中目標選擇問題的效果，在相同的仿真環(huán)境下分別采用RAACA算法和基本蟻群算法對該實例各進行10次仿真實驗，每次迭代運算均為100代終止。

在實驗中，RAACA算法均能在循環(huán)30代以內(nèi)獲得最優(yōu)解，而采取基本蟻群算法最好情況需循環(huán)70代左右才能獲得最優(yōu)解。兩種算法的最優(yōu)結(jié)果比較如圖1所示，其中RAACA表示逆轉(zhuǎn)變異蟻群算法，ACA表示基本蟻群算法。

圖1 最佳實驗結(jié)果比較Fig.1 Comparison of the optimum experimental results

4 結(jié)論

由仿真實驗結(jié)果表明，基于變異的蟻群算法能夠有效解決預(yù)警機指揮引導(dǎo)下的多機協(xié)同空戰(zhàn)仿真中的目標選擇決策問題。該方法在蟻群算法中引入遺傳算法的逆轉(zhuǎn)變異算子對目標選擇構(gòu)造策略進行更新，并且改進和設(shè)計了信息素強度的更新規(guī)則，提高了空戰(zhàn)仿真中目標選擇方案的搜索效率，能夠在較短的迭代次數(shù)內(nèi)獲得最優(yōu)的目標選擇方案，很好地體現(xiàn)了現(xiàn)代空戰(zhàn)仿真中CGF實體目標選擇的實時性和真實性。

［1］劉付顯，邢清華.基于混合遺傳算法的目標優(yōu)化分配［J］.系統(tǒng)工程理論與實踐，2002，30(7):84-88.

［2］LEE Z J，SU S F，LEE C Y.Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Transactions on Systems，Man，and Cybernetics，2003，33(1):113-121.

［3］馮杰.遺傳算法及其在導(dǎo)彈火力分配上的應(yīng)用［J］.火力與指揮控制，2004，29(2):43-46.

［4］LUO Delin，SHEN Chunlin，WANG Biao，et al.Air combat decision-making for cooperative multiple target attack:An approach of hybrid adaptive genetic algorithm［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2006，23(3):382-388.

［5］羅德林，吳順祥，段海濱，等.無人機協(xié)同多目標攻擊空戰(zhàn)決策研究［J］.系統(tǒng)仿真學(xué)報，2008，20(24):677-678.

［6］柳長安，李為吉，王和平.基于蟻群算法的無人機航路規(guī)劃［J］.空軍工程大學(xué)學(xué)報:自然科學(xué)版，2004，5(2):9-12.

［7］黃樹采，李為民.目標分配問題的蟻群算法研究［J］.系統(tǒng)工程與電子技術(shù)，2005，27(1):79-80.

［8］羅德林，段海濱，吳順詳，等.基于啟發(fā)式蟻群算法的協(xié)同多目標攻擊空戰(zhàn)決策研究［J］.航空學(xué)報，2006，23(6):1166-1170.

［9］GAO S.Solving weapon-target assignment problem by a new ant colony algorithm［C］∥Proceedings of the 6th World Congress on Intelligent Control and Automation.2008:221-224.

［10］于雷，任波，魯藝.自適應(yīng)蟻群算法的多機協(xié)同空戰(zhàn)目標分配方法［J］.火力與指揮控制，2008，33(6):49-51.

［11］陳中起，張斌，任波.隨機優(yōu)化蟻群算法在空戰(zhàn)決策中的應(yīng)用［J］.電光與控制，2008，15(6):54-57.

［12］GAMBARDELLA L M，DORIGOM.Ant-Q:A reinforcement learning approach to the traveling salesman problem［C］//Proceedings of the 12th International Conference on MachineLearning，1995:252-260.

［13］趙磊，李仁松，常國任.預(yù)警機引導(dǎo)戰(zhàn)斗機空戰(zhàn)目標分配模型［J］.指揮控制與仿真，2008，30(5):34-36.

［14］滕鵬，劉棟，張斌，等.超視距協(xié)同空戰(zhàn)態(tài)勢評估方法研究［J］.電光與控制，2008，15(10):47-50.

［15］付新華，王健.多機協(xié)同多目標攻擊的目標分配和攻擊排序［J］.火力與指揮控制，2006，31(3):75-78.

［16］高堅，佟明安.超視距多目標攻擊排序及火力分配建模與解算［J］.火力與指揮控制，2004，29(3):9-12.

［17］李永賓，張鳳鳴，李俊濤.多機協(xié)同攻擊決策邏輯的蟻群算法研究［J］.電光與控制，2006，13(6):43-45.

［18］DORIGO M，MANIEZZO V，COLORNI A.The ant system:Optimization by a colony of cooperating agents［J］.IEEE Trans.on Systems，Man and Cybernetics，Part-B，1996，26(1):1-13.

［19］詹士昌，徐婕，吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇［J］.科技通報，2003，19(1):381-186.