用混合蛙跳算法的智能防空火力分配

韓占朋， 王玉惠， 姜長生， 吳慶憲

(南京航空航天大學自動化學院，南京 210016)

0 引言

在防空作戰中，由于空襲目標數量眾多，威脅等級各異，飛行諸元繁雜，己方防空武器種類、數量眾多，作戰范圍多變，火力優化歷來都是其難點之一。因此，開展防空火力分配問題的研究是十分必要且具有實際意義的?；鹆Ψ峙涫且粋€離散的、帶約束的組合優化問題，屬N－P問題［1］。近十幾年來，智能算法的出現及蓬勃發展為解決這一問題提供了更強有力的工具，如人工免疫算法［2］、基于遺傳的人工魚群算法［3］、改進的粒子群算法［4］、禁忌搜索與粒子群算法的混合優化策略算法［5］、蟻群算法［6］等都比較好地解決了火力優化問題，但同時也有各自不足之處。本文引入一種新的智能計算方法——混合蛙跳算法，該算法具有概念簡單、參數少、計算速度快、全局搜索能力強、易于實現的優點［7］。根據算法原理，通過特殊的編碼方式更新青蛙位置，加入了一個變區間步長σ，逐步得到全局最優方案。

1 火力分配建模

假設我方有m組不同的防空武器，每組防空武器的數量為vk，k=1，2，…，m。預警系統發現有n批不同目標，數量為 qk，k=1，2，…，n。n 批目標的威脅系數用 wj表示，j=1，2，…，n。

為使分配的火力單元能有效打擊目標，首先定義防空武器的火力單元條件約束總矩陣R。在武器系統的有效作用區域和組間最大轉火時間內，同組內的武器單元由于作用區域差異及敵機飛臨特征，能有效打擊的目標各不相同。因此建立防空武器單元對n批目標開火的約束矩陣為

式中:Rmn表示第m組防空武器的第n個火力單元的目標分配約束陣。rij表示該火力單元對第i批目標的第j個目標的條件約束，屬二值變量，由該火力單元的作用區域、彈藥裝載量、轉火時間、武器的自身屬性及目標特點決定。

注1 單獨考慮武器及目標類型因素時，煙幕彈對F－16戰斗機基本沒有作用，則rij=0，但對AGM－137 TSSAM 巡航導彈的毀傷可達到 0.804［8］，rij=1。rij=1時表示可以分配，否則為零，不可分配。

假定同批內目標的類型及威脅系數相同，防空武器打擊相同類型目標的毀傷概率相同，只需確定武器系統分配給每批目標的數量即可得到火力決策陣。則毀傷矩陣P與火力決策矩陣X分別為

pij表示第i組防空武器對第j批目標分配一個火力單元后對目標的毀傷概率;xij表示第i組防空武器對第j批目標分配的火力單元數。

為了最大限度地殺傷空襲目標，將總的防空火力單元的殺傷概率作為目標函數，使殺傷達到概率最大值。即

上述模型能夠真實地模擬打擊情況，在全局分配的同時兼顧單個火力的狀態，與以往模型相比，提高了分配精度，可確定各組武器的每個單元的作戰對象。當面臨多批空中目標威脅時能最大限度地利用防空武器資源。下面根據模型，給出火力決策陣的關聯解陣。

為了直觀簡便，本文采用十進制編碼方式，每個解依照火力單元號排列，m組防空武器構成一個m維解矩陣。解值表示火力單元所分配到的目標。在滿足矩陣R的前提下，關聯解陣為

其中，s11代表第1組防空武器的第1個火力單元分配的目標。由解陣S可得到火力決策矩陣X，依照式(3)可計算解陣S的代表的適應值。

2 混合蛙跳算法

2.1 混合蛙跳算法

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是2001年 Muzaffar Eusuff和 Kevin Lansey為了解決水管網設計提出的一種基于青蛙覓食的群體智能搜索算法［9］?，F已經證明該算法滿足隨機搜索的全局收斂條件，能夠保證做到全局收斂［10］。

SFLA的原理是隨機得到k只青蛙構成初始種群，第 k 只青蛙用 Fk=(fk1，fk2，…，fks)表示，其中，s表示解的維數。之后，將種群內的青蛙按照適應度降序排列并劃分成l個模因組，每個組代表一個子群，內含有h個個體。在進化過程中，第1個解放入第1個子群，次第放入，直到第l個解放入第l個子群。然后，將第l+1個解再次放入到第1個子群，第l+2個解放入到第2個子群，循環分配，直到所有的解分配完畢。對每個子群而言，適應值最大的青蛙用Fb表示，適應值最小的青蛙用Fw表示，而整個種群中適應值最大的青蛙用Fg表示。之后對每個子群進行局部最優搜索并更新Fw。經過更新后，如果得到的青蛙Fw優于原來的青蛙Fw，則取代原來子群中的青蛙;否則，用Fg取代Fb，重新更新，如果仍然沒有改進，則隨機產生一個新蛙取代原來的Fw。重復上述操作。當完成局部搜索后，將所有的青蛙重新混合排序并劃分子群，再次進行局部搜索，如此反復直到滿足終止條件。

算法的框架是一致的，關鍵是青蛙的更新。為了使蛙跳算法適用于離散的火力分配問題，需改進其更新方式。下面介紹具體的改進方法:首先計算Fb與Fw(這里指最優、最差解陣S)的差異位置及其個數tmax(由Fb－Fw的值確定)，隨機得到相異的t個位置(t為隨機數)，用Fb相應位置上的數值更新Fw的相應位置。更新如下

首先在施工之前，項目部進行了實地考察和對當地建筑市場進行了解，并詳細研究招標文件對該幕墻工程的描述要求，制定了幕墻深化規劃設計的策劃方案，需要注意的：①在方案中明確規定了幕墻深化設計的標準和要求。②結合實地，分別對兩棟塔樓幕墻進行深化設計。③要求精確到每個螺絲釘的尺寸以及操作手法。④在繪制深化設計方案后，應當設置嚴格的會審流程，確定最終版本，積極向DEWAN監理公司工程師進行圖紙報批、溝通，減少深化設計的時間周期。⑤在施工過程中，要嚴格監督分包單位按照深化設計的施工圖紙以及各項專業的設計圖紙中規定尺寸和要求的來進行操作，保證施工質量。

式中:Rre表示首先計算Fb與Fw的差值矩陣，其解表征了兩者之間的差異，記錄非零元素所在位置;L表示兩者之間的差異位置集合。隨機抽取，得到差異位置，進行相應位置的更新。受雜草算法［12］的啟發引入一個可變步長σ來控制變異的個數t。

如果用 σinit，σfinal，σcur，imax，i以及 n 分別表示初始區間步長、最終步長、當前步長、最大迭代次數、當前迭代次數及非線性調節指數，則它們之間的關系為

然后根據N(0，σ2)隨機產生一個擴散值，即t(t＜tmax)的解。應用式(6)確保了算法在迭代過程中，t以非線性的方式逐漸減小，相當于遺傳算法中的交叉過程向變異過程轉變。在整個迭代過程中，從多點變異方式向單點變異方式轉變，最終在最優解的小范圍內擺動，試圖尋找全局最優解，因而整個尋優過程具有更強的魯棒性。

2.2 蛙跳算法分配火力

蛙跳算法步驟如下所述。

1)編碼初始化青蛙種群k=100。

2)按式(1)計算每只青蛙的適應度，并按降序排序。搜索出全局最優可行解Fg、各個子群中的最優可行解Fb和最差可行解Fw。

3)將種群劃分成10組，每組10個個體，子群進化，并按式(5)、式(6)更新最差可行解Fw得新解Fq。

4)如果 Fq優于 Fw，則令 Fw=Fq;否則，令 Fg取代Fb產生新的可行解F'q，如果F'q優于Fw，令Fw=F'w;否則隨即產生新解Fw。重復步驟3)，直到子群的最大迭代次數imax=5。

5)將所有的青蛙重新混合排序，重復步驟3)～5)。

6)達到種群的最大迭代次數Imax=20或精度要求停止，輸出Fg。

3 實例仿真

依據上述模型，用改進的SFLA算法進行仿真。仿真環境為:P4 2.4 G/512 M微機，Windows操作系統，VC++6.0開發平臺。假定發現7批目標將在相鄰時刻到達，其間隔小于我方武器轉火間隔，假定每批目標數量都為5個(其數量對仿真無影響)。我方防空武器有6組，每組的火力單元數量分別為 8、6、7、6、5、8 個?；鹆卧獙δ繕说臍怕始澳繕送{如表1所示。

表1 火力單位對目標的殺傷概率Table 1 Kill probability of fire unit to target

依照2.2節中的蛙跳算法步驟及參數，仿真運行，得到最優解為

目標適應度函數值為23.5。

為對算法進行縱向比較，設定子群迭代5次，分別就整個種群迭代 20、50、100、200、500 次仿真，分別隨機運行50次取均值，結果如表2所示。

表2 結果比較Table 2 Comparison of the simulation result

上述結果表明，當迭代20次時，結果均值已經到達最優值23.5的87.98%，同500次仿真結果均值相差0.224，差異很小。由此說明蛙跳算法能快速收斂。

為了對仿真結果進行橫向比較，同時采用遺傳算法及其改進算法對該戰例進行了計算(群體大小100、交叉率0.6、變異率0.01，迭代次數50次)，由其50次獨立實驗的結果得到的目標函數值及時間均值與蛙跳算法比較如表3所示。

表3 毀傷比較Table 3 Comparison of kill probability

由上表可以看出，利用蛙跳算法進行火力分配在縮短運行時間的同時可以得到較好的效果，此外，當結果趨于穩定時，GA、IGA迭代次數明顯高于SFLA，也間接證明了SFLA能快速收斂。究其原因在于族群中的局部模因進化與族群間的混合交流交替進行，使群體信息更加豐富的同時也大大提高了算法的收斂速度，此外，可變步長σ使得解總是穩定在最優附近，防止算法在最終階段出現下滑現象，該結果也證明了模型的正確性。

4 結束語

火力分配歷來都是提高防空效率，打擊目標保證己方生存能力的關鍵環節。本文就混合蛙跳算法在解決防空作戰中火力分配問題的應用進行了初步探索。通過一個可變步長因子σ使整個過程具有更強的魯棒性。應用實例仿真得到理想的結果，通過橫向與縱向比較，證實了蛙跳算法具有很快的收斂速度及較高的精度。同時也表明了模型的正確性，為防空火力分配優化提供了一種新的有效方案。

［1］ 阮旻智，李慶民，劉天華.編隊防空火力分配建模及其優化方法研究［J］.兵工學報，2010，31(11):1525－1529.

［2］ 趙振鋒，吳慶憲，姜長生.基于遺傳的人工魚群優化之武裝直升機對地攻擊火力分配決策［J］.電光與控制，2011，18(3):31－33.

［3］ 丁鑄，馬大為，張學鋒，等.基于改進微粒群算法的火力分配［J］.彈箭與制導學報，2006，26(1):575－580.

［4］ 丁鑄，馬大為，于存貴，等.基于禁忌搜索與微粒群優化算法的混合優化策略算法在目標分配問題上的應用［J］.兵工學報，2007，28(9):1127－1131.

［5］ 嚴建鋼，鄭保華，黃晅，等.防空火力分配問題的螞蟻算法模型［J］.火力與指揮控制，2008，33(8):91－93.

［6］ 李英海，周建中，楊俊杰，等.一種基于閾值選擇策略的改進的混合蛙跳算法［J］.計算機工程與應用，2007，43(35):19－21.

［7］ 趙玲.防御陣地智能火控及指揮決策系統研究［D］.南京:南京航天航空大學，2010:36－38.

［8］ EUSUFF M M，LANSEY K E.Water distribution network design using the shuffled frog leaping algorithm［C］//World Water Congress，2001:1－8.

［9］ 駱劍平，李霞，陳泯融.混合蛙跳算法的Markov模型及其收斂性分析［J］.電子學報，2010，38(12):2875－2880.

［10］ MEHRABIAN A R，LUCAS C.A novel numerical optimization algorithm inspired from weed colonization［J］.Ecological Informatics，2006，1:355－366.