陳 昊

(中國(guó)航空工業(yè)集團(tuán)公司 洛陽電光設(shè)備研究所，河南 洛陽471009)

0 引 言

空戰(zhàn)火力分配是研究現(xiàn)代空戰(zhàn)中有關(guān)火力運(yùn)用和作戰(zhàn)決策的一個(gè)重要課題。空戰(zhàn)火力分配問題是指在超視距多機(jī)協(xié)同多目標(biāo)攻擊空戰(zhàn)環(huán)境中，我方空戰(zhàn)指揮控制系統(tǒng)根據(jù)敵方多架飛機(jī)的威脅權(quán)重值，及時(shí)有效地將我方機(jī)載空空導(dǎo)彈分配到導(dǎo)彈攻擊區(qū)內(nèi)的多個(gè)目標(biāo)，以最大限度地消除敵方目標(biāo)的威脅。目前，已經(jīng)證明空戰(zhàn)火力分配問題屬于完全非確定多項(xiàng)式(non－deterministic polynomia，NP)問題［1］，傳統(tǒng)的求解方法通常具有指數(shù)階的時(shí)間復(fù)雜度，當(dāng)我機(jī)數(shù)目、導(dǎo)彈數(shù)目和目標(biāo)數(shù)目都很大時(shí)，將發(fā)生組合爆炸，進(jìn)而在有限決策時(shí)間內(nèi)難以求得問題最優(yōu)解，滿足不了空戰(zhàn)決策實(shí)時(shí)性要求。

蟻群算法具有并行性計(jì)算、正反饋機(jī)制、啟發(fā)式搜索、求解精度高、算法操作簡(jiǎn)單等特點(diǎn)，自2002 年以來，已被很多學(xué)者用來求解火力分配問題［2～6］，并取得很好的成果。然而，當(dāng)分配問題規(guī)模較大時(shí)，傳統(tǒng)的蟻群算法難以在有效時(shí)間內(nèi)求得問題的最優(yōu)解。為了提高算法在求解大規(guī)?；鹆Ψ峙鋯栴}時(shí)的時(shí)效性，以滿足指揮決策實(shí)時(shí)性的要求，學(xué)者們開始將研究?jī)?nèi)容轉(zhuǎn)向蟻群算法的并行優(yōu)化［7～9］。

傳統(tǒng)的協(xié)同空戰(zhàn)火力分配大都采用一次性分配的靜態(tài)火力分配模型。而在空戰(zhàn)實(shí)際中，整個(gè)分配過程是動(dòng)態(tài)的，敵我雙方多個(gè)編隊(duì)根據(jù)空戰(zhàn)戰(zhàn)術(shù)，執(zhí)行多個(gè)階段協(xié)同作戰(zhàn)。目前，動(dòng)態(tài)火力分配尚未得到實(shí)質(zhì)上的解決，根據(jù)文獻(xiàn)［10］中的“動(dòng)靜結(jié)合”的觀點(diǎn)，動(dòng)態(tài)火力分配中的某一特定階段，可以作為靜態(tài)分配為題進(jìn)行處理?；诖怂枷?，針對(duì)空戰(zhàn)中第一階段，建立了一種帶毀傷概率門限的火力分配模型，在求得對(duì)目標(biāo)機(jī)群最大毀傷效果的同時(shí)盡量節(jié)約導(dǎo)彈武器資源，以應(yīng)對(duì)下一階段的火力分配，并借鑒粗粒度并行策略，采用OpenMP 并行優(yōu)化技術(shù)對(duì)蟻群系統(tǒng)(ant colony system，ACS)中最耗時(shí)的循環(huán)迭代、循環(huán)賦值和禁忌表更新等部分進(jìn)行并行化處理，并通過各種規(guī)模的火力分配問題的仿真實(shí)驗(yàn)驗(yàn)證火力分配模型和算法的有效性。

1 協(xié)同空戰(zhàn)火力分配模型的建立

假設(shè)在某次空戰(zhàn)中的第一階段，我方機(jī)群R 由M 架我機(jī)組成，分別記為 Rr(r =1，2，…，M);敵方機(jī)群 B 由 N 架敵機(jī)組成，分別記為Bj(j =1，2，…，N)。載機(jī) Rr所掛載的空空導(dǎo)彈數(shù)目為dr，且導(dǎo)彈類型不完全一致。機(jī)群R 所掛載的總導(dǎo)彈數(shù)為Z，且Z ＞N。Z 枚空空導(dǎo)彈構(gòu)成武器集合W，記為 W=(i，i=1，2，…，Z)。當(dāng) W 中的第 r 枚導(dǎo)彈剛好是Rr所掛載的dr枚導(dǎo)彈中的第i 枚導(dǎo)彈時(shí)，r 與l 的對(duì)應(yīng)關(guān)系如式(2)所示

設(shè)機(jī)群R 所分配的導(dǎo)彈對(duì)目標(biāo)Bj的聯(lián)合毀傷概率為pj，則有

其中，pij為導(dǎo)彈i 對(duì)目標(biāo)j 的毀傷概率，與導(dǎo)彈性能和具體空戰(zhàn)態(tài)勢(shì)等有關(guān)。xij為決策變量，若分配導(dǎo)彈i 攻擊目標(biāo) j，則 xij=1;否則，xrj=0。

在以往的靜態(tài)火力分配數(shù)學(xué)模型中，目標(biāo)j 必須被攻擊，且至少分配一枚導(dǎo)彈進(jìn)行攻擊，具體分配數(shù)目由指控系統(tǒng)根據(jù)實(shí)際情況給出。本文采取優(yōu)先選擇毀傷概率高的導(dǎo)彈優(yōu)先攻擊價(jià)值系數(shù)高的目標(biāo)的“雙優(yōu)分配原則”，針對(duì)特定目標(biāo)j 設(shè)定一個(gè)毀傷概率門限值ptj，只有當(dāng)分配給目標(biāo)j的聯(lián)合毀傷概率高于此門限值時(shí)才分配導(dǎo)彈，以避免對(duì)目標(biāo)j 毀傷概率很低的導(dǎo)彈被分配，造成不必要的武器浪費(fèi)。從而可將某些將被用來攻擊當(dāng)前階段處于導(dǎo)彈攻擊區(qū)以外，或者當(dāng)前時(shí)刻導(dǎo)彈難以命中毀傷的目標(biāo)的導(dǎo)彈，放到下一階段里再分配，節(jié)約了本階段的武器彈藥。因此，在本文中，目標(biāo)j 根據(jù)具體情況可不分配導(dǎo)彈攻擊。

目標(biāo)j 的價(jià)值系數(shù)用vj表示。多機(jī)協(xié)同的空戰(zhàn)主要是為了爭(zhēng)奪制空權(quán)的空戰(zhàn)，因此，假設(shè)參戰(zhàn)雙方機(jī)種均為戰(zhàn)斗機(jī)，此時(shí)目標(biāo)價(jià)值系數(shù)可用目標(biāo)對(duì)我機(jī)的威脅系數(shù)thjr衡量。由此建立一種帶有毀傷概率門限的火力分配數(shù)學(xué)模型為

其中，pij為目標(biāo)j 的毀傷概率門限。式(5)表示在一個(gè)火力分配方案中，如果目標(biāo)j 的聯(lián)合毀傷概率pj小于ptj，則認(rèn)為是無效分配，式(7)表示一枚導(dǎo)彈只能攻擊一個(gè)目標(biāo)。該數(shù)學(xué)模型的意義在于，在滿足毀傷概率門限的前提下，將目標(biāo)相對(duì)我機(jī)的威脅、我機(jī)導(dǎo)彈對(duì)目標(biāo)的毀傷概率以及導(dǎo)彈武器資源的消耗3 個(gè)因素綜合考慮，通過比較各種導(dǎo)彈對(duì)目標(biāo)的組合對(duì)火力分配目標(biāo)函數(shù)值的貢獻(xiàn)來進(jìn)行導(dǎo)彈的優(yōu)化分配，從而達(dá)到在獲得最大火力分配效能的同時(shí)，節(jié)省武器資源，且能保證威脅度大的目標(biāo)被優(yōu)先攻擊。

2 并行蟻群算法求解火力分配問題

蟻群算法本質(zhì)上是一種并行算法，具有很高的并行性［8］?，F(xiàn)實(shí)中的螞蟻是并行地搜尋食物，并逐漸形成一條從蟻穴到食物的最短路徑，蟻群算法繼承了真實(shí)螞蟻的這種并行機(jī)制。蟻群算法在求解問題的每一次迭代過程中，每只螞蟻根據(jù)當(dāng)前路徑上的信息素量和問題的啟發(fā)函數(shù)，彼此獨(dú)立地構(gòu)建問題的解，螞蟻之間通過信息素進(jìn)行間接通信。蟻群算法所具有的這種天然的并行性為算法的并行實(shí)現(xiàn)提供了良好的基礎(chǔ)。因此，把串行蟻群算法改造為并行蟻群算法是可行的。

論文提出的并行蟻群系統(tǒng)(parallel ant colony system，PACS)的思想可以描述為:利用PC 計(jì)算機(jī)多核的優(yōu)勢(shì)和粗粒度的并行策略，將串行蟻群系統(tǒng)(serial ant colony system，SACS)算法中的整個(gè)蟻群分為多個(gè)子蟻群(子蟻群個(gè)數(shù)等于計(jì)算機(jī)核的個(gè)數(shù))，每個(gè)子蟻群螞蟻個(gè)數(shù)相等。將每個(gè)子蟻群分配給一個(gè)線程處理，每個(gè)子蟻群分別進(jìn)行解的搜索，根據(jù)并行策略在適當(dāng)時(shí)機(jī)進(jìn)行子蟻群之間的通信。每個(gè)子蟻群根據(jù)從其他子蟻群獲取的有關(guān)信息，對(duì)本子蟻群的信息素矩陣和禁忌表進(jìn)行修改。當(dāng)達(dá)到算法的終止條件時(shí)，由其中1 個(gè)線程收集各子蟻群的最優(yōu)解，比較各個(gè)最優(yōu)解值的大小，從而得出算法最優(yōu)解，輸出所找到的全局最優(yōu)解。

2.1 火力分配方案

設(shè)武器集合為W={i|i=1，2，…，Z}，目標(biāo)集合為 T ={j|j=1，2，…，N}。本文選擇把武器分配給目標(biāo)的分配策略，一種火力分配方案就是從T 到W 的一個(gè)二元關(guān)系。在蟻群算法中，一個(gè)解就是一種火力分配方案，解成分就是序偶〈j，i〉。對(duì)于目標(biāo)j，從可選武器集(尚未被分配的武器所構(gòu)成的集合)中按序偶選擇規(guī)則選出一件武器i 分配給該目標(biāo)。

2.2 序偶選擇規(guī)則

q 是一個(gè)在區(qū)間［0，1］上呈均勻分布的隨機(jī)數(shù)，q0(0≤q0≤1)是算法參數(shù)。當(dāng)q≤q0時(shí)，螞蟻k 按先驗(yàn)知識(shí)選擇序偶〈j，i〉

其中，τji(t)為序偶〈j，i〉在 t 時(shí)刻對(duì)應(yīng)的信息素;α 表征信息素在選擇概率上的相對(duì)重要性;ηji為序偶〈j，i〉對(duì)應(yīng)的啟發(fā)式函數(shù)值，本文中ηji=thjrpij;β 表征啟發(fā)式函數(shù)值在選擇概率上的相對(duì)重要性;allowed(t)是當(dāng)前允許分配的武器集合。

2.3 信息素更新規(guī)則

信息素更新規(guī)則分為局部信息素更新規(guī)則和全局信息素更新規(guī)則。局部信息素更新在螞蟻k 選擇一個(gè)序偶〈j，i〉后進(jìn)行。局部更新的目的是適當(dāng)降低螞蟻所經(jīng)過的序偶的信息素強(qiáng)度，以避免搜索過度集中而導(dǎo)致搜索停止。局部更新規(guī)則表示如下

其中，τ0為信息素初始值;ρ(0 ＜ ρ ＜ 1)為局部更新規(guī)則的信息素?fù)]發(fā)因子。全局信息素更新在一次迭代完成后進(jìn)行

其中，ζ(0 ＜ζ ＜1)為全局更新規(guī)則的信息素?fù)]發(fā)因子，Y－best 是到目前為止的全局最優(yōu)解，f－best 是到目前為止的全局最優(yōu)解的目標(biāo)函數(shù)值。

2.4 算法的并行實(shí)現(xiàn)

OpenMP 是用于共享內(nèi)存并行系統(tǒng)的多線程程序設(shè)計(jì)的一種指導(dǎo)性注釋。OpenMP 提供了對(duì)并行算法的高層的抽象描述，程序員通過在源代碼中加入專用的pragma 來指明自己的意圖，由此編譯器可以自動(dòng)將程序進(jìn)行并行化，并在必要之處加入同步互斥和通信。對(duì)于很多循環(huán)來說，都可以在其開始之前插入一條編譯指導(dǎo)，使其以多線程執(zhí)行。開發(fā)人員只需要認(rèn)真考慮哪些循環(huán)應(yīng)該以多線程方式執(zhí)行和如何重構(gòu)算法以便在多核處理器上獲得更好的性能等問題［11］。當(dāng)使用OpenMP 將那些最耗時(shí)的循環(huán)以多線程執(zhí)行的時(shí)候，OpenMP 的能力就體現(xiàn)出來。

并行蟻群并行策略分為細(xì)粒度策略和粗粒度策略。粗粒度策略是指將每一個(gè)子蟻群分配到一個(gè)處理器上讓其并行，并在適當(dāng)時(shí)機(jī)彼此之間相互通信評(píng)出最優(yōu)解。研究表明:粗粒度的并行蟻群更有潛力［12］。串行蟻群算法運(yùn)算量最大的部分是循環(huán)迭代、循環(huán)賦值階段，且這些計(jì)算大部分都集中在for 循環(huán)中，便于利用OpenMP 的編譯指導(dǎo)語句實(shí)現(xiàn)程序的并行化。

采用OpenMP 和C + +語言來實(shí)現(xiàn)并行蟻群算法，仿真計(jì)算機(jī)具有4 核處理器，基于OpenMP 的并行蟻群算法的實(shí)現(xiàn)步驟如下:

1)Part A 程序初始化部分

a.初始化蟻群算法各項(xiàng)參數(shù)，輸入目標(biāo)威脅矩陣、導(dǎo)彈毀傷概率矩陣等;

b.設(shè)置每條路徑上的初始信息素強(qiáng)度τ0;

c.根據(jù)計(jì)算機(jī)核的個(gè)數(shù)設(shè)置線程數(shù)為S(S =4)，用于將原來的一個(gè)蟻群分為4 個(gè)子蟻群在多核機(jī)上并行求解;

d.各個(gè)子蟻群中的每只螞蟻被隨機(jī)地放置在武器節(jié)點(diǎn);

e.初始化信息素矩陣τij(t)和初始時(shí)刻每條邊上的信息素增量;

f.初始化用于存放最優(yōu)解的Y－best 矩陣。

2)Part B 循環(huán)部分

進(jìn)入并行區(qū)，用#pragma parallel omp for 語句對(duì)循環(huán)迭代和循環(huán)賦值部分進(jìn)行并行化。

a.將原始蟻群分為 4 個(gè)子蟻群(分別記為 s1，s2，s3和s4)，再分別交給4 個(gè)處理器處理使其在多核機(jī)上并行求解;

b.各子蟻群中每只螞蟻根據(jù)式(8)和式(9)選擇下一個(gè)將訪問的序偶〈j，i〉。然后將該螞蟻移動(dòng)到新的序偶，并把序偶〈j，i〉添加到該螞蟻的禁忌表中。每只螞蟻在構(gòu)建自己可行解后，按照式(10)進(jìn)行信息素的局部更新;

c.在一次循環(huán)中各個(gè)蟻群中的每只螞蟻完成一次周游，它們的禁忌表被填滿，分別計(jì)算出4 個(gè)子蟻群中的每只螞蟻求解出的目標(biāo)函數(shù)值，比較它們的大小，得出本次循環(huán)最優(yōu)目標(biāo)函數(shù)值和最優(yōu)解;

d.經(jīng)過n 次循環(huán)后，所有螞蟻均完成可行解的構(gòu)建并通過通信比較得出當(dāng)前最優(yōu)解后，由式(11)和式(12)進(jìn)行信息素的全局更新;

e.將所有螞蟻的禁忌表清空;一次循環(huán)結(jié)束，進(jìn)入下次循環(huán);

f.上述過程不斷循環(huán)重復(fù)，最優(yōu)解序偶上的信息素得到加強(qiáng)，直到達(dá)到循環(huán)結(jié)束條件，求出最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值，輸出程序結(jié)果。

3 算例仿真驗(yàn)證與分析

算例1 為了驗(yàn)證火力分配模型的有效性，假設(shè)我方4 架戰(zhàn)斗機(jī)與敵方6 架戰(zhàn)斗機(jī)在某空域進(jìn)行超視距條件下的空戰(zhàn)，我方每架戰(zhàn)斗機(jī)均攜帶型號(hào)不完全相同的4 枚空空導(dǎo)彈。我方機(jī)群采用協(xié)同空戰(zhàn)戰(zhàn)術(shù)對(duì)進(jìn)入聯(lián)合攻擊區(qū)內(nèi)的6 個(gè)目標(biāo)進(jìn)行攻擊。目標(biāo)j 對(duì)我機(jī)r 的威脅值thjr由空戰(zhàn)態(tài)勢(shì)評(píng)估系統(tǒng)給出，目標(biāo)威脅函數(shù)值矩陣如表1 所示。我機(jī)16 枚空空導(dǎo)彈對(duì)6 個(gè)目標(biāo)的毀傷概率矩陣如表2 所示。設(shè)定目標(biāo)j 的毀傷概率門限ptj均為0.80。目標(biāo)j 可最多分配2 枚導(dǎo)彈同時(shí)進(jìn)行攻擊。最終最優(yōu)火力分配方案如表3所示，表中“0”表示導(dǎo)彈未對(duì)該目標(biāo)進(jìn)行火力分配。圖1給出了PACS 最優(yōu)目標(biāo)函數(shù)值收斂曲線。

表1 目標(biāo)威脅函數(shù)值矩陣Tab 1 Target threat function value matrix

表2 導(dǎo)彈對(duì)目標(biāo)的毀傷概率矩陣Tab 2 Damage probability matrix of missile against target

表3 最優(yōu)火力分配方案Tab 3 The best weapon-target assignment solution

由表3 數(shù)據(jù)看出:采用本文提出的帶毀傷概率門限的火力分配模型進(jìn)行火力分配，并未一次性將16 枚導(dǎo)彈全部分配給6 個(gè)目標(biāo)，而僅僅分配7 枚導(dǎo)彈便能完成空戰(zhàn)任務(wù)，為我機(jī)編隊(duì)節(jié)約了9 枚導(dǎo)彈。而按照以往的靜態(tài)火力分配模型，本階段中所有導(dǎo)彈都得分配給相應(yīng)目標(biāo)，這很不符合空戰(zhàn)實(shí)際情況。

圖1 PACS 收斂曲線Fig 1 PACS convergence curve

算例2 為檢驗(yàn)基于OpenMP 的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配的時(shí)效性，分別采用提出的并行蟻群算法和串行ACS 對(duì)各種規(guī)模的火力分配問題各進(jìn)行20 次仿真實(shí)驗(yàn)，每次均迭代300 代。實(shí)驗(yàn)所用 PC 計(jì)算機(jī)性能為Pentium(R)32 bit Four－Core PC，4G RAM，算法參數(shù)設(shè)置如下 α =1，β =2，m=20，ρ=0.25，ζ =0.20，q0=0.90，τ0=5。實(shí)驗(yàn)結(jié)果如表4 所示，圖2 給出了規(guī)模分別為M =50，N =75，Z=200 和 M =100，N =150，Z =400 時(shí)，PACS 和 SACS最優(yōu)目標(biāo)函數(shù)值收斂曲線。

表4 SACS 和PACS 算法性能比較Tab 4 Performance comparison of SACS and PACS algorithms

圖2 不同規(guī)模下的PACS 和SACS 收斂曲線Fig 2 PACS and SACS convergence curves under different scale

由圖2 和表4 結(jié)果可看出:當(dāng)問題規(guī)模很小時(shí)，并行算法的求解時(shí)間比串行算法求解時(shí)間略長(zhǎng)，這是因?yàn)橛肙penMP 編寫的程序在運(yùn)行時(shí)會(huì)產(chǎn)生線程創(chuàng)建和銷毀的開銷。當(dāng)問題規(guī)模很小時(shí)，這個(gè)開銷將大于程序本身的執(zhí)行時(shí)間。隨著問題規(guī)模的增加，程序本身的執(zhí)行時(shí)間越來越長(zhǎng)，程序并行占的開銷在整個(gè)程序運(yùn)行時(shí)間中所占的比重越來越小。當(dāng)問題規(guī)模很大時(shí)，使用OpenMP 將那些最耗時(shí)的循環(huán)以多線程執(zhí)行時(shí)，并行蟻群算法的能力就體現(xiàn)出來。

4 結(jié) 論

本文針對(duì)空戰(zhàn)中第一階段，提出了一種帶毀傷概率門限的協(xié)同空戰(zhàn)火力分配模型，對(duì)傳統(tǒng)靜態(tài)火力分配模型進(jìn)行了改進(jìn)，在求得對(duì)目標(biāo)機(jī)群最大毀傷效果的同時(shí)盡量節(jié)約導(dǎo)彈武器資源，以應(yīng)對(duì)下一階段的火力分配。在此基礎(chǔ)上，根據(jù)粗粒度的并行策略，采用OpenMP 并行優(yōu)化技術(shù)，對(duì)蟻群系統(tǒng)中最耗時(shí)的循環(huán)迭代、循環(huán)賦值和禁忌表更新等部分進(jìn)行并行化處理，仿真結(jié)果表明:本文提出的火力分配模型符合空戰(zhàn)實(shí)際，基于OpenMP 并行優(yōu)化的蟻群能夠合理、快速的給出空戰(zhàn)目標(biāo)分配方案。

［1］ Lloyd S P，Witsenhausen H S.Weapons allocation is NP－complete［C］∥Proceedings of the IEEE Summer Simulation Conference，Reno，Vevada，1986:1054 － 1058.

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

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

［4］ 劉建新，宋以勝，盧厚清，等.改進(jìn)蟻群算法求解火力分配優(yōu)化［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39(20):92 －99.

［5］ 杜天軍，陳光禹，劉占辰.多目標(biāo)攻擊空戰(zhàn)決策WBG 模型及其蟻群算法［J］.系統(tǒng)工程與電子技術(shù)，2005，27(5):861 －865.

［6］ 高 堅(jiān)，佟明安.超視距多目標(biāo)攻擊排序及火力分配建模與解算［J］.火力與指揮控制，2004，29(3):9 －13.

［7］ Lee Zhejung，Su Shunfeng，Lee Chouyuan.Efficiently solving general weapon－target assignment problem by genetic algorithms with greed eugenics［J］.IEEE Journal on Systems，Man，and Cybernetics-part B:Cybernetics，2003，33(1):119 － 120.

［8］ 汪鵬飛.并行蟻群算法及其應(yīng)用研究［D］.成都:西南交通大學(xué)，2008.

［9］ Chen Song，He Jianhua，Liu Huaiyuan.Realization and simulation of parallel ant colony algorithm to solve WTA problem［C］∥2012 International Conference on Systems and Informatics，ICSAI 2012，2012:2458 －2461.

［10］ 劉傳波，邱志明，吳 玲，等.動(dòng)態(tài)武器目標(biāo)分配問題的研究現(xiàn)狀與展望［J］.電光與控制，2010，17(11):43 －48.

［11］劉向嬌，吳素萍，劉佳梅.基于OPENMP 求解旅行商問題的并行蟻群算法［J］.微電子學(xué)與計(jì)算機(jī)，2011，28(7):149 －155.

［12］ Ellabib I，Calamai P，Basir O.Exchange strategies for multiple ant colony system［J］.Information Sciences:An International Journal，2007，177(5):1248 － 1264.