基于CE-CAPSO 武器目標(biāo)分配優(yōu)化算法

王力超，喬勇軍，李永勝

（1.海軍航空大學(xué)，山東 煙臺 264001；2.解放軍31004 部隊，北京 100089）

0 引言

武器目標(biāo)分配（WTA）是指在一定約束條件下（如武器種類和數(shù)量受限），按照武器毀傷概率、彈藥成本、目標(biāo)威脅程度、作戰(zhàn)任務(wù)要求等條件將武器與目標(biāo)匹配、分配，以達(dá)成作戰(zhàn)目標(biāo)最佳效果的過程，是典型的非線性組合優(yōu)化問題［1］。其中模型求解的關(guān)鍵是計算的精度和速度。

當(dāng)前，求解WTA 問題主要采用啟發(fā)式算法，如遺傳算法、蟻群算法、模擬退火算法等。粒子群（PSO）算法由于其參數(shù)簡單，易于實現(xiàn)且收斂速度快的優(yōu)點，得到了廣泛的應(yīng)用。PSO 源于對鳥群捕食行為的模擬，是一種隨機搜索的迭代進(jìn)化算法。但PSO 算法存在容易陷入局部最優(yōu)，從而導(dǎo)致“早熟”的問題，為此，研究人員通過分析算法的原理，提出了很多改進(jìn)方法。文獻(xiàn)［2］提出了一種云自適應(yīng)粒子群算法（CAPSO），文獻(xiàn)［3］提出了一種基于鯰魚效應(yīng)的粒子群算法（CEPSO），這些優(yōu)化均取得了滿意的結(jié)果，在一定范圍內(nèi)改善了算法的性能。

為了加快粒子尋優(yōu)和避免陷入局部最優(yōu)，在基本粒子群算法的基礎(chǔ)上，受文獻(xiàn)［3-4］的啟發(fā)，提出一種求解WTA 問題的改進(jìn)云粒子群算法——CE-CAPSO 算法，仿真實驗結(jié)果表明，本算法具有更好的全局尋優(yōu)能力，收斂速度也有明顯提高。

1 WTA 問題模型

其中，第1 個不等式表示第i 種武器平臺打擊所有目標(biāo)使用武器彈藥不超過自身擁有的數(shù)量mi；第2個約束條件表示消耗的武器彈藥是非負(fù)的。

由于作戰(zhàn)資源有限或目標(biāo)威脅度不高，實際戰(zhàn)場環(huán)境下，不一定攻擊或攔截所有目標(biāo)，通常指揮員會根據(jù)實際情況權(quán)衡各種因素，確定一部分目標(biāo)必須打擊，而其他目標(biāo)“可打可不打”，因此，在這里假設(shè)前t 個目標(biāo)必須要受到打擊，所以約束條件變?yōu)椋?/p>

2 基于PSO 武器目標(biāo)分配算法

2.1 基本粒子群算法

在PSO 算法中，粒子在d 維空間中的位置（x）和飛行速度（v）都表示為一個矢量，每次迭代都有一個標(biāo)準(zhǔn)評價粒子的位置的好壞，稱之為適應(yīng)值函數(shù)（fitness function），此外粒子們知道自己到目前為止最好的位置（pbest）和整個粒子群中歷史上最好的位置（gbest），前者稱之為個體認(rèn)知經(jīng)驗，后者為社會認(rèn)知經(jīng)驗，粒子通過個體認(rèn)知經(jīng)驗和社會認(rèn)知經(jīng)驗經(jīng)過一定次數(shù)迭代尋找d 維空間中最好的位置［6］，其速度與位置更新公式如下：

2.2 粒子編碼方式

表1 例子編碼方式示意

表格中數(shù)字表示該單元格行武器打擊該單元格列目標(biāo)所消耗彈藥數(shù)量，如M4武器平臺打擊N4消耗3 枚彈；0 為不打擊。矩陣編碼的方式，減少了計算循環(huán)次數(shù)，降低了計算步驟復(fù)雜度。

2.3 約束條件處理

WTA 是多約束問題，直接計算效率不高，因此，在這里利用罰函數(shù)方法，把約束條件合并到適應(yīng)值函數(shù)中，引入懲罰因子W，懲罰因子通常為一個較大的數(shù)；另外，為了計算方便，改寫目標(biāo)函數(shù)為倒數(shù)形式，求最小值，改寫后的適應(yīng)值函數(shù)如下：

式中，第2 項大括號中3 項分別表示對武器彈藥消耗的約束、對打擊到前t 個目標(biāo)上武器彈藥的約束和對武器彈藥非負(fù)的約束，（xij≥0）表示邏輯運算，xij大于等于0 為真，取值1，否則為假，取值0。

3 改進(jìn)的粒子群算法

雖然粒子群算法簡單易于實現(xiàn)，但有早熟收斂、易于陷入局部最優(yōu)和后期粒子多樣性差的問題，解的精度和迭代速度達(dá)不到要求的標(biāo)準(zhǔn)，因此，在基本粒子群算法的基礎(chǔ)上，引進(jìn)云自適應(yīng)模型與鯰魚效應(yīng)模型，來改進(jìn)粒子群算法的不足。

3.1 云自適應(yīng)粒子群算法

粒子群算法中慣性權(quán)重決定粒子飛行速度，傳統(tǒng)對于w 參數(shù)改進(jìn)有線性遞減、自適應(yīng)權(quán)重法，在迭代初期w 值較大，利于粒子全局尋優(yōu)，后期w 較小，利于粒子較快收斂，這在一定程度上提升了算法性能，但卻造成了后期粒子易于陷入局部最優(yōu)而找不到全局最優(yōu)解的尷尬。李德毅院士提出了云理論，使用隨機正態(tài)分布的云模型既具有穩(wěn)定傾向性又有一定隨機性、模糊性，而且對于很多不確定模糊問題，用正態(tài)隸屬描述最合適，可以達(dá)到很好的效果，云模型用期望Ex、熵En、超熵He 和正態(tài)隨機數(shù)En'描述［8］，給定期望、熵、超熵以及云滴數(shù)，就可以通過“云發(fā)生器”計算得到云滴定量值和相對該模糊問題的確定度。云自適應(yīng)粒子群算法（Cloud Adaptive Particle Swarm Optimization Algorithm，CAPSO）［4］根據(jù)粒子適應(yīng)度將粒子分為3 個種群，并把不同慣性權(quán)重用于不同種群粒子迭代中?；緝?nèi)容是：根據(jù)適應(yīng)值函數(shù)求出粒子群平均適應(yīng)值favg，將適應(yīng)值優(yōu)于favg的粒子求平均得到favgnice，將適應(yīng)值次于favg的粒子求平均得到favgbad，慣性權(quán)重w 的取值規(guī)則如下：

1）優(yōu)于favgnice，此時粒子的位置已非常接近全局最優(yōu)解，因此，w 取0.4 加快粒子收斂速度；

2）次于favgnice但優(yōu)于favgbad，這是質(zhì)量一般的粒子，采用云自適應(yīng)模型非線性調(diào)整慣性權(quán)重：

3）次于favgbad，此時粒子較差，w 取0.9 加快粒子飛行速度以尋找全局最優(yōu)解。

加入云模型提高了粒子尋優(yōu)能力和收斂速度，但是算法運行后期粒子還會有陷入局部最優(yōu)的風(fēng)險，因此，引入鯰魚效用模型，加入擾動，使得在算法運行后期陷入局優(yōu)的粒子重新獲得活力。

3.2 鯰魚效應(yīng)——云自適應(yīng)粒子群算法

鯰魚效應(yīng)（Catfish Effect）是指在沙丁魚群中放入幾條鯰魚，生性安逸的沙丁魚看到好動的鯰魚緊張起來而四處游動，從而保持沙丁魚活躍。在粒子群迭代過程中，粒子后期易于陷入局部最優(yōu)解而導(dǎo)致算法準(zhǔn)確度不高，因此，借鑒鯰魚效應(yīng)，標(biāo)記不同粒子為鯰魚粒子和沙丁魚粒子，使得適應(yīng)值較差的粒子加速運動尋優(yōu)，增加粒子群的多樣性［3］。方法如下：

1）每次迭代判斷粒子當(dāng)前位置與歷史最好位置，如果相同，則標(biāo)記此粒子為鯰魚粒子，否則為沙丁魚粒子cei=0，鯰魚粒子表示粒子陷入了局部最優(yōu)，標(biāo)記為沙丁魚的粒子要遠(yuǎn)離鯰魚粒子；

2）定義沙丁魚粒子逃逸速度［9］為：

3.3 改進(jìn)CE-CAPSO 粒子群算法

粒子速度更新由慣性項、個體經(jīng)驗項和社會經(jīng)驗項構(gòu)成，CAPSO 將粒子群按適應(yīng)值不同分為3 個種群：較好種群、一般種群和較差種群，分別采用不同慣性權(quán)重來計算。借鑒文獻(xiàn)［12］思想，改進(jìn)粒子速度更新公式：對于較好種群，其適應(yīng)值已經(jīng)接近全局最優(yōu)解，因此，速度更新采用社會經(jīng)驗?zāi)Ｐ?，加快全局收斂；對于較差種群，采用個體經(jīng)驗?zāi)Ｐ?；而對于一般種群不作改動，因此，修改后粒子速度更新公式如下：

4 仿真實例

4.1 參數(shù)設(shè)置

表2 武器毀傷概率

分別通過基本粒子群算法（PSO）、云自適應(yīng)粒子群算法（CAPSO）、鯰魚效應(yīng)-云自適應(yīng)粒子群算法（CE-CAPSO）、改進(jìn)CE-CAPSO 算法，與基于輪盤賭選擇的自適應(yīng)交叉變異遺傳算法（GA）的仿真分析對比。PSO 慣性權(quán)重w 設(shè)為0.5，三者學(xué)習(xí)因子都為2，在CE-CAPSO 中，根據(jù)正態(tài)函數(shù)規(guī)則，En 越大，云滴覆蓋寬度越大，結(jié)合算法速度和精度，將α=2.9，He 決定云滴的隨機性，取β=10［4］，n 決定沙丁魚粒子逃逸速度，根據(jù)經(jīng)驗，取n=2。GA 算法設(shè)置兩種，GA1 最小交叉概率0.3，最大交叉概率0.6，最小變異概率0.02，最大變異概率0.05；GA2 最小交叉概率0.3，最大交叉概率0.8，最小變異概率0.03，最大變異概率0.06，輪盤賭最大選擇概率0.2，第j個個體的選擇概率是：

GA 個體與PSO 粒子編碼方式略有不同，即把后者的矩陣改寫為一維數(shù)組形式，方便個體遺傳時交叉和變異操作，其形式如圖1 所示。

圖1 遺傳個體編碼示意

遺傳操作的自適應(yīng)交叉概率Pc和變異概率Pm計算公式如下：

4.2 結(jié)果分析

利用Matlab R2017b 編寫程序，設(shè)置粒子種群數(shù)量popsize=50，迭代次數(shù)gen=80，運行計算結(jié)果如下頁圖2～圖7 所示。

圖2 PSO 計算結(jié)果

圖3 CAPSO 計算結(jié)果

圖4 CE-CAPSO 計算結(jié)果

圖5 改進(jìn)CE-CAPSO 計算結(jié)果

圖6 GA1 計算結(jié)果

圖7 GA2 計算結(jié)果

從圖中對比可以發(fā)現(xiàn)，相比于PSO、CAPSO、GA算法，文中提出的CE-CAPSO 算法與改進(jìn)的CE-CAPSO 迭代速度最快，GA2 次之，然后是GA1 和CAPSO，PSO 最差。在上述參數(shù)設(shè)置下，CE-CAPSO與改進(jìn)的CE-CAPSO 基本上在10 代左右就收斂到最優(yōu)解，而CAPSO、PSO 和GA 算法迭代次數(shù)均大于10 代；另外4 種算法的適應(yīng)值依圖片排序分別為13.729 3、13.893 8、14.830 4、14.816 1、12.121 3、17.101 6， 呈GA2>CE-CAPSO> 改 進(jìn)CE-CAPSO>CAPSO>PSO>GA1 狀態(tài)，但是適應(yīng)值的大小并不能完全說明GA2、CE-CAPSO 的尋優(yōu)能力差，而PSO、GA1 的尋優(yōu)能力最好，因為WTA 問題屬于離散問題，適應(yīng)值最佳并不代表算法求得武器目標(biāo)分配方案最好，還可能不符合約束條件或者現(xiàn)實情況，而且給定的參數(shù)也可能造成解不唯一；此外PSO、GA 本質(zhì)上都是隨機搜索算法，且文中處理約束條件的方法是罰函數(shù)法，沙丁魚粒子逃逸速度也是固定值，沒有考慮其與鯰魚粒子的相對距離，而GA 算法受參數(shù)影響較大，參數(shù)的不同會造成解相差也較大，計算結(jié)果有一定隨機性且仍不可避免有較小的概率陷入局部最優(yōu)。

運行多次分析這幾個算法得到的結(jié)果，發(fā)現(xiàn)它們的計算結(jié)果并不每次符合所有約束條件；而對于GA 算法，不同的參數(shù)設(shè)置計算結(jié)果也有較大不同，5 種算法之間尋優(yōu)能力各不相同?，F(xiàn)將程序分別運行100 次，統(tǒng)計符合約束計算結(jié)果如下頁表3 所示。

從表中可以看出，改進(jìn)遺傳算法準(zhǔn)確性最佳，其次是改進(jìn)CE-CAPSO、CE-CAPSO、CAPSO 算法，PSO 算法準(zhǔn)確性最差；粒子群一類算法平均迭代次數(shù)與準(zhǔn)確性呈相同趨勢，其中引入云模型后，算法迭代次數(shù)顯著減少，而遺傳算法由于其本身容易早熟特性，收斂迭代次數(shù)較?。? 種算法中，粒子群一類算法迭代標(biāo)準(zhǔn)差相差不大，CAPSO 最穩(wěn)定，而GA 算法的收斂迭代次數(shù)受參數(shù)設(shè)置較大；相比標(biāo)準(zhǔn)粒子群算法，改進(jìn)的粒子群適應(yīng)值較為穩(wěn)定，最穩(wěn)定的是CE-CAPSO 算法；但是適應(yīng)值最佳的是CAPSO 算法，其次是PSO、CE-CAPSO 算法，而改進(jìn)CE-CAPSO 算法適應(yīng)值略差，而遺傳算法過早收斂，容易陷入局部最優(yōu)，解的質(zhì)量不高；對比這幾種算法的平均運行時間，都在同一個數(shù)量級且相差不大。

表3 4 種算法統(tǒng)計對比

5 結(jié)論

通過對基本粒子群算法改進(jìn)，引入了云模型與鯰魚效應(yīng)，建立相應(yīng)算法模型，計算并分析得到如下結(jié)論：基本粒子群算法迭代速度慢且求解正確性不高，基于CAPSO 算法加快了粒子全局尋優(yōu)、收斂速度和正確性；在此基礎(chǔ)上又引入鯰魚效應(yīng)，避免粒子迭代陷入局部最優(yōu)，增加粒子群多樣性。針對武器目標(biāo)分配問題求解使用基于CE-CAPSO 算法大大提升了計算效率，同時提高了計算準(zhǔn)確性。相比于GA 算法，粒子群實現(xiàn)簡單，對計算機性能要求不高，可以有效求解WTA 問題模型，滿足實際運用。綜上，改進(jìn)的CE-CAPSO 算法，在解的正確率、收斂速度和全局尋優(yōu)方面都有一定提高，有較好的適用價值。

但是WTA 模型求解很大程度上依賴參數(shù)設(shè)置，而作戰(zhàn)實際情況多樣，符合要求的往往有多個合法解，難以保證每次計算結(jié)果一致，只能在計算的效率和準(zhǔn)確性上提升算法性能，此外，本文沒有對學(xué)習(xí)因子、改進(jìn)進(jìn)行考慮，而二者決定粒子學(xué)習(xí)自身經(jīng)驗與種群經(jīng)驗的程度，因此，可以進(jìn)一步地研究，對學(xué)習(xí)因子的改進(jìn)進(jìn)行有益的探索。