基于改進(jìn)人工魚群算法的反TBM目標(biāo)分配策略*

王 楠 ，戴江斌 ，韓 鈞

（1.西安體育學(xué)院，西安 710068；2.空軍工程大學(xué)，西安 710051）

0 引言

反TBM（Tactical Ballistic Missile）的目標(biāo)分配，是為應(yīng)對大規(guī)模TBM進(jìn)攻，將來襲的TBM合理分配至防空反導(dǎo)攔截系統(tǒng)，以實現(xiàn)對要地區(qū)域的防護(hù)。反TBM目標(biāo)分配問題模型的有效性，算法的時效性決定了整個防空反導(dǎo)作戰(zhàn)的效能，是指揮決策的核心內(nèi)容之一。

反TBM目標(biāo)分配問題屬于NP完全問題，隨著戰(zhàn)場環(huán)境的日益復(fù)雜，參戰(zhàn)兵力兵器和來襲TBM目標(biāo)的增大，使得時間和空間復(fù)雜度呈指數(shù)級增長，傳統(tǒng)求解算法（如分支定界法、匈牙利法、整數(shù)規(guī)劃法等）已很不適宜，目前主要利用智能優(yōu)化算法進(jìn)行求解，如遺傳算法［1］、禁忌搜索算法［2］、粒子群算法［3］、蟻群算法［4］及模擬退火算法［5］等，雖發(fā)展顯著，但也普遍存在著早熟停滯現(xiàn)象，易陷入局部最優(yōu)，且收斂速度較慢，無法滿足當(dāng)前防空反導(dǎo)快速實時要求。本文在考慮攔截效益和時空等約束的基礎(chǔ)上建立了反TBM目標(biāo)分配模型，并設(shè)計了帶交叉變異算子的模擬退火人工魚群優(yōu)化策略，提升模型求解的速度精度，有效提高防空反導(dǎo)作戰(zhàn)效能。

1 反TBM目標(biāo)分配模型

1.1 目標(biāo)函數(shù)

考慮反TBM目標(biāo)分配攔截效益最大化，攔截TBM數(shù)量最大化，以及導(dǎo)彈消耗最小化的目標(biāo)，建立目標(biāo)函數(shù)模型為:

其中，F(xiàn)為攔截目標(biāo)的效益；pij為武器i對彈道導(dǎo)彈目標(biāo)j的攔截摧毀概率；wj為目標(biāo)j的威脅值；x=［xij］n×m為決策變量集合。Y 表示攔截目標(biāo)數(shù)；yj=1，表示目標(biāo)j受到武器的攔截，yj=0，表示目標(biāo)j未受到武器的攔截。R為武器總的攔截彈消耗數(shù)量。由于是多目標(biāo)決策，采用線性加權(quán)法進(jìn)行轉(zhuǎn)換，將其轉(zhuǎn)換為單目標(biāo)最大化問題:

1.2 約束條件

1.2.1 空間約束

反TBM作戰(zhàn)首先需要考慮攔截武器系統(tǒng)對來襲TBM在空間范圍內(nèi)是否構(gòu)成攔截可能，因而建立空間約束條件為:

其中，Rij為目標(biāo)j與武器i之間的直線距離，Rimax為武器i能攔截目標(biāo)的最大遠(yuǎn)界；Vj為目標(biāo)j的速度，Vimax為武器i能攔截目標(biāo)的最大速度；Hj為目標(biāo)j的高度，Himin和Himax分別為武器i能攔截目標(biāo)的最小和最大高度。

1.2.2 時間約束

TBM飛行速度快，武器系統(tǒng)對其攔截時效性要求高，必須滿足發(fā)射窗口的時間約束，且對應(yīng)不同目標(biāo)通道的武器系統(tǒng)，時間約束也不盡相同。

其中，tij為武器 i發(fā)射攔截彈時刻，tSij、tEij分別為目標(biāo)j到達(dá)武器i發(fā)射窗口最早、最晚發(fā)射點時間。

同時，對于單目標(biāo)通道武器系統(tǒng)，應(yīng)滿足:

對于多目標(biāo)通道武器系統(tǒng)，應(yīng)滿足:

其中，N為目標(biāo)通道數(shù)，Δti為武器i的射擊周期，ΔtFi為多通道武器發(fā)射兩枚導(dǎo)彈的時間間隔。

1.2.3 其他約束

本文對于其他約束條件，重點考慮上級的指令和同一TBM攔截次數(shù)。

對于上級指定攔截的目標(biāo)，只要滿足空間和時間約束條件，則至少保證有一個武器系統(tǒng)實施攔截，那么:

其中，C為上級或指揮員命令攔截的目標(biāo)集合。

同時，對任一目標(biāo)攔截的次數(shù)均不超過Num，即對任一目標(biāo)攔截Num次，均能以較高的攔截效益值將其擊毀，即

1.2.4 約束條件的處理

對于上述列舉的約束條件，可以利用綜合約束罰函數(shù)進(jìn)行處理。對于式（4），若目標(biāo)j相對武器i不滿足約束，則武器i無法攔截目標(biāo)j，則令pij=0。因此，仿真求解時可以不考慮此約束，認(rèn)為pij=0即不滿足此約束。

對于式（5）和式（6）決定的單目標(biāo)通道武器時間約束，若需要攔截的目標(biāo)數(shù)量是兩個以上時，須判斷是否存在發(fā)射的時間窗口，且先到先打，將武器i需要攔截的目標(biāo)集合按到達(dá)武器i的發(fā)射區(qū)遠(yuǎn)界的先后順序排列，設(shè)目標(biāo)j最先到達(dá)發(fā)射區(qū)遠(yuǎn)界，則令tij=tSij，對第2個目標(biāo)w的發(fā)射時刻，以此類推。綜合約束罰函數(shù)為:

同理，對于式（5）和式（7）決定的多目標(biāo)通道武器時間約束，設(shè)目標(biāo)j最先到達(dá)發(fā)射區(qū)遠(yuǎn)界，則令tij=tSij，對第2個目標(biāo)w的發(fā)射時刻，以此類推。綜合約束罰函數(shù)為:

對于式（8），定義綜合的約束罰函數(shù)，只要有一個子約束不滿足，就可以知道解是不可行的，則綜合約束罰函數(shù)為:

同理，對于式（9），綜合約束罰函數(shù)為:

其中，M為懲罰因子，是一個很大的正數(shù)。至此，將帶有約束的多目標(biāo)決策問題轉(zhuǎn)換成一個不帶約束的單目標(biāo)組合優(yōu)化問題。

2 改進(jìn)人工魚群算法的目標(biāo)分配方法

2.1 基本思路

人工魚群算法是一種自下而上的新型尋優(yōu)策略，但當(dāng)部分人工魚處于漫無目的的隨機(jī)移動或人工魚群在非全局極值點出現(xiàn)較嚴(yán)重聚集情況時，收斂速度大大減慢，同時，人工魚群算法由于視野、步長的隨機(jī)性和隨機(jī)行為的存在，最優(yōu)解的精度往往較低。

為有效應(yīng)對以上不足，本文引入遺傳算法中的交叉變異算子以提高收斂速度，通過設(shè)立公告板來記錄最優(yōu)人工魚個體狀態(tài)，人工魚在行動一次后將當(dāng)前狀態(tài)的函數(shù)值與公告板進(jìn)行比較，若優(yōu)于公告板則用當(dāng)前狀態(tài)取代公告板狀態(tài)，當(dāng)最優(yōu)個體狀態(tài)在連續(xù)多個迭代過程中沒有變化或變化極小時，開始交叉變異操作，保留歷史最優(yōu)人工魚個體狀態(tài)，將其他人工魚按一定的概率對少部分維進(jìn)行交叉變異，從而實現(xiàn)人工魚的跳變，調(diào)整優(yōu)化整個魚群。并且同時引入模擬退火算法以提高收斂精度，對最優(yōu)解狀態(tài)的人工魚個體進(jìn)行局部模擬退火，“精細(xì)搜索”局部優(yōu)化，提高整個算法的局部搜索能力。

具體本文的問題，人工魚狀態(tài)對應(yīng)武器的目標(biāo)分配即決策變量xij，人工魚當(dāng)前位置的食物濃度對應(yīng)目標(biāo)函數(shù)Z'。

2.2 算法流程

假設(shè) n 個武器的編號為 1，2，3，…，n，m 個目標(biāo)的編號為1，2，3，…，m。當(dāng)?shù)趈個目標(biāo)分給了第i個火力單元時，可令yj=i，則相應(yīng)的分配方案（人工魚狀態(tài)）X 為:y1，y2，…，ym。這種編碼方式直觀、簡單，并大大減少了個體總量和非可行的個體量。其反操作為:

用人工魚所在位置的食物濃度表示目標(biāo)函數(shù)Z'，即Y=Z'。人工魚群通過覓食、聚群及追尾行為向食物濃度更大的區(qū)域游動的過程，就是動態(tài)尋優(yōu)的過程，通過這一過程不斷變化，使目標(biāo)分配方案不斷向最優(yōu)解附近的區(qū)域靠近。具體算法流程為:

1）產(chǎn)生初始可行解:①對于第j個目標(biāo)，將武器按射擊的有利程度排隊。若排在第k名的武器具備射擊條件，則用F（j，k）表示該火力單元的代號，否則就置F（j，k）=0；②在可行域內(nèi)構(gòu)造L個個體如下:第 1 個個體 T1:F（1，1），F(xiàn)（2，1），…，F(xiàn)（M，1）；第h 個個體（h＜L）Th的構(gòu)造為:假設(shè) Th為:y1，y2，…，yM，對于 yk，若 F（k，h）≠0，則令 yk=F（k，h）；若 F（k，h）=0，則令 yk=F（k，1），其中 L 為群體規(guī)模；

2）公告板賦初值:計算初始魚群各人工魚個體當(dāng)前狀態(tài)的目標(biāo)函數(shù)值Y，比較大小，取最大值者進(jìn)入公告板，將此魚賦值給公告板，并設(shè)置初始公告板最優(yōu)人工魚狀態(tài)連續(xù)不變化或變化極小時的迭代次數(shù)Beststep為0，初始迭代次數(shù)Sum為0；

3）行為選擇:各人工魚分別模擬覓食、追尾、聚群和隨機(jī)行為，選擇行動后Y值較大的行為實際執(zhí)行；

4）更新公告板:各人工魚每行動一次后，檢驗自身的Y與公告板的Y，如果優(yōu)于公告板，則以自身取代之；

5）變異條件判斷:判斷Beststep是否已達(dá)到預(yù)置的連續(xù)不變化次數(shù)的最大閾值，若是就執(zhí)行第6步，否則轉(zhuǎn)到第7步執(zhí)行；

6）對魚群內(nèi)除公告板中最優(yōu)個體之外其他所有人工魚執(zhí)行:①交叉操作:交換概率為pc，隨機(jī)從人工魚群中選擇兩個個體，執(zhí)行單點交叉操作，然后將形成的兩個新個體的函數(shù)值Y計算，并與公告板中的最優(yōu)值進(jìn)行比較，如果優(yōu)于公告板，則以自身取代之；②變異操作:對各人工魚的所有維分別產(chǎn)生隨機(jī)數(shù) r∈（0，1），如果 r＜pm，對該個體該維進(jìn)行隨機(jī)初始化，否則該維保持不變，對新形成的魚群計算各人工魚的函數(shù)值Y，并與公告板中的最優(yōu)值進(jìn)行比較，如果優(yōu)于公告板，則以自身取代之；③置 Beststep為 0；

7）終止條件判斷:判斷Sum是否已達(dá)到預(yù)置的最大迭代次數(shù)或判斷最優(yōu)解是否達(dá)到了滿意的誤差界內(nèi)，若不滿足，則Sum=Sum+1，Beststep=Beststep+1，轉(zhuǎn)到第3步執(zhí)行，進(jìn)行下一步魚群優(yōu)化過程，否則轉(zhuǎn)到第8步執(zhí)行；

8）對滿意最優(yōu)解域進(jìn)行局部優(yōu)化:調(diào)用模擬退火優(yōu)化算法，對解進(jìn)一步局部優(yōu)化，產(chǎn)生高精度最終解；

9）如果結(jié)果滿足約束則輸出最優(yōu)結(jié)果Y，即為分配問題目標(biāo)值Z'，否則，增大罰函數(shù)值重新跳回第1步進(jìn)行計算。

圖1 算法流程圖

3 算例分析

依據(jù)經(jīng)驗，對模型參數(shù)進(jìn)行取值:最大攔截次數(shù)Num=5，子懲罰函數(shù)權(quán)重l=0.25（l=1，…，4），子目標(biāo)函數(shù)權(quán)重 ωF=0.5、ωY=0.3、ωR=0.2，懲罰因子初值M=1 000；算法參數(shù)取值:人工魚群規(guī)模Nf=300，可視距離Lvs=mn/20（表示人工魚可視距離是解域的1/20），步長Lst=mn/40（表示人工魚最大步長是解域的1/40），擁擠因子δ=0.11（表示90%的解域中只有不到10條人工魚），交叉概率pc=0.5，變異概率pm=1/20 mn（表示一條人工魚狀態(tài)中只有一維改變的概率大概是0.05），模擬退火初始溫度Ts=1，終止溫度Tf=0.001，最大進(jìn)化代數(shù)NSA=1 000。

武器系統(tǒng)數(shù)量n=6，其中單、多目標(biāo)通道武器系統(tǒng)數(shù)量分別為4和2，來襲目標(biāo)數(shù)量m=30，上級命令必須攔截的目標(biāo)數(shù)為3（為一般化起見，隨機(jī)選?。Ｄ繕?biāo)到達(dá)武器系統(tǒng)攔截區(qū)遠(yuǎn)界的時間從［0，40］均勻分布隨機(jī)選取，目標(biāo)在武器系統(tǒng)的攔截區(qū)域停留時間從［25，50］中按均勻分布隨機(jī)選取。目標(biāo)威脅值從［0.2，0.8］中按均勻分布隨機(jī)選取，攔截效益值在［0，1］中隨機(jī)選取。武器系統(tǒng)的射擊周期為20 s。多目標(biāo)通道武器通道數(shù)為4，通道射擊間隔為3.5 s。用設(shè)計算法求解10次后，結(jié)果按照目標(biāo)函數(shù)值降序排列，如表1所示:

表1 目標(biāo)分配結(jié)果

則對應(yīng)最大Z'值的目標(biāo)分配方案為:

將本文所設(shè)計的算法與粒子群算法（PSO）、蟻群算法（ACO）進(jìn)行比較，分別隨機(jī)運行50次，3種算法的性能比較指標(biāo)如第73頁圖2所示。

從圖2中可以看出本文所設(shè)計的算法在第10次迭代時便可以達(dá)到目標(biāo)的最優(yōu)分配，而PSO和ACO算法分別需要24次和36次迭代才能達(dá)到最優(yōu)，且最優(yōu)解及平均解均高于其他兩種算法，說明本算法具有較好的收斂特性，能較快地找到問題的最優(yōu)解，適應(yīng)現(xiàn)代戰(zhàn)爭中反TBM作戰(zhàn)輔助決策的要求。

圖2 算法性能比較圖

4 結(jié)論

本文針對TBM飽和式攻擊以及多彈頭突防的戰(zhàn)場環(huán)境，研究有效攔截時的目標(biāo)分配問題。建立了體現(xiàn)多目標(biāo)多約束決策模型，設(shè)計了帶有交叉變異算子模擬退火人工魚群復(fù)合算法，并進(jìn)行了實驗仿真驗證，證明了算法的實時性和有效性。同時，對于作戰(zhàn)想定、初始位和算法參數(shù)的確定還需要進(jìn)一步探討研究，以便更好地符合作戰(zhàn)實際。