逆轉變異蟻群算法在CGF多目標分配中的應用

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

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

0 引言

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

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

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

1 多機協同目標選擇問題描述

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

根據文獻［13，15－17］建立目標分配優化函數表達式為

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

2 目標優化選擇模型設計

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

1)將分配紅方戰機打擊全部藍方目標的優勢函數最大作為最優解指標;

2)紅方每攻擊一架藍方飛機后，應對原來的態勢優勢函數矩陣進行修正;

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

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

2.1 目標分配策略

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

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

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

2.2 信息量的全局修正

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

其中，

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

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

2.3 引入逆轉變異方式

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

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

定義逆轉變異條件為

其中: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)，函數 inversion()的功能是把個體solutioni的s1+1和s2這一段路徑顛倒過來進行變異，變異的次數是隨機的。這一過程涉及的運算比蟻群算法中的循環過程要簡單得多，因此只需要較短的時間便可完成相同次數的運算。經過這種變異算子作用后，這一代解的性能會明顯改善，也大大改善了整個群體的性能，從而減少計算時間，提高搜索效率。

2.4 仿真步驟

基于變異蟻群算法求解協同目標選擇步驟分7步實現:

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

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

4)計算本次分配的不利函數的和E，比較出最好的結果(E最小)，并記錄此次循環中最好結果的最優路徑;

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

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

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

3 算法實驗

假設紅方有8架A型截擊機A1～A8(各帶1枚可迎頭攻擊的某型中程空空導彈:射程為75 km，使用高度22000 m，Ma數為4)，使用高度22000 m。藍方參戰飛機為兩架B型(B1、B2)和兩架 C型(C3、C4)戰機(各帶兩枚可全向攻擊的某兩型遠程空空導彈，射程分別為70 km和80 km，使用高度分別為18000 m和20000 m，Ma數均為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)，將上述參數帶入文獻［14］關于超視距協同空戰整體優勢態勢的計算公式中，計算出超視距協同空戰態勢數據，如表1所示。

表1 態勢矩陣Table 1 The situation matrix

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

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

求得最優解時，E=0.2636，J=6.0032。

表2 目標分配優化方案Table 2 The optimal method for the target assignment

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

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

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

4 結論

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

［1］劉付顯，邢清華.基于混合遺傳算法的目標優化分配［J］.系統工程理論與實踐，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］馮杰.遺傳算法及其在導彈火力分配上的應用［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］羅德林，吳順祥，段海濱，等.無人機協同多目標攻擊空戰決策研究［J］.系統仿真學報，2008，20(24):677-678.

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

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

［8］羅德林，段海濱，吳順詳，等.基于啟發式蟻群算法的協同多目標攻擊空戰決策研究［J］.航空學報，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］于雷，任波，魯藝.自適應蟻群算法的多機協同空戰目標分配方法［J］.火力與指揮控制，2008，33(6):49-51.

［11］陳中起，張斌，任波.隨機優化蟻群算法在空戰決策中的應用［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］趙磊，李仁松，常國任.預警機引導戰斗機空戰目標分配模型［J］.指揮控制與仿真，2008，30(5):34-36.

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

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

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

［17］李永賓，張鳳鳴，李俊濤.多機協同攻擊決策邏輯的蟻群算法研究［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］詹士昌，徐婕，吳俊.蟻群算法中有關算法參數的最優選擇［J］.科技通報，2003，19(1):381-186.