改進(jìn)MOPSO 的聯(lián)合火力打擊目標(biāo)分配*

陳 曼，周鳳星，張成堯

（1.武漢科技大學(xué)信息科學(xué)與工程學(xué)院，武漢 430081；2.武漢義信恒通科技有限公司，武漢 430073）

0 引言

武器-目標(biāo)分配問題，是指如何采用高效的算法，在打擊多個來襲目標(biāo)時，按照設(shè)置的最優(yōu)分配原則合理地分配現(xiàn)有的武器，根據(jù)其分配原則的不同通?？煞譃閱文繕?biāo)優(yōu)化和多目標(biāo)優(yōu)化［1-3］。隨著海洋領(lǐng)域已成為各國發(fā)展戰(zhàn)略的重心，國內(nèi)外許多學(xué)者都非常關(guān)注艦載武器-目標(biāo)分配問題，對其求解算法進(jìn)行了大量深入的研究。用于解決單目標(biāo)優(yōu)化的常用算法有遺傳算法、蟻群算法、粒子群算法，以及采用混合優(yōu)化算法等，單目標(biāo)優(yōu)化模型通常是以毀傷效能最大作為目標(biāo)函數(shù)，雖然可以達(dá)到理想的打擊效果，但當(dāng)武器數(shù)量較多時容易造成武器浪費(fèi)，因此，構(gòu)建了多目標(biāo)優(yōu)化模型來求解武器-目標(biāo)分配問題［4-6］。文獻(xiàn)［7］構(gòu)造了結(jié)合最大作戰(zhàn)效能和防御效能的雙目標(biāo)優(yōu)化模型，并將NSGA-II用于計算，但所使用的遺傳操作算子耗時太長；文獻(xiàn)［8］建立效能最大和用彈量最少的多目標(biāo)優(yōu)化模型，采用基于Pareto 非劣集分層思想對遺傳算法改進(jìn)進(jìn)行求解；文獻(xiàn)［9］考慮最大作戰(zhàn)效能和武器單元數(shù)量的影響，在求解時簡化了限制條件、更改速度及位置的更新方法。本文建立了結(jié)合失敗概率最小和使用武器量最少的多目標(biāo)優(yōu)化模型，將傳統(tǒng)的武器-目標(biāo)單目標(biāo)優(yōu)化轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，對算法研究有著更長遠(yuǎn)的現(xiàn)實意義。提出了采用改進(jìn)的多目標(biāo)粒子群算法進(jìn)行求解，具有良好的精確性和快速性，實例仿真結(jié)果驗證了所提算法的有效性。

1 多目標(biāo)粒子群優(yōu)化算法

包括m 個目標(biāo)函數(shù)時，一個多目標(biāo)優(yōu)化問題通常可以描述成：

與單目標(biāo)優(yōu)化問題相比，它需要同時優(yōu)化好幾個不可比較、存在沖突的目標(biāo)，意味著沒有解能使目標(biāo)函數(shù)一起取得最優(yōu)，這就需要通過權(quán)衡這些待優(yōu)化的目標(biāo)，來使每個目標(biāo)函數(shù)都達(dá)到較優(yōu)，最終得到的是一個最優(yōu)解集合，也稱Pareto 最優(yōu)解集或非支配解集［10］。Pareto 最優(yōu)解指一個處于決策空間中的解X'，對于任意解X，使得

則稱X'支配X。當(dāng)且僅當(dāng)不存在某個解支配X 時，稱X 為Pareto 最優(yōu)解。Pareto 最優(yōu)解形成的集合叫做Pareto 最優(yōu)解集。

粒子群優(yōu)化算法是一種通過迭代過程進(jìn)行優(yōu)化的智能進(jìn)化算法，具有原理簡單、較易實現(xiàn)、運(yùn)行效率高等特征，在優(yōu)化問題中取得了良好的應(yīng)用效果，基于此將其應(yīng)用到多目標(biāo)優(yōu)化問題中。多目標(biāo)粒子群優(yōu)化算法首先初始化一群粒子（隨機(jī)解），根據(jù)其適應(yīng)函數(shù)值篩選出非支配解集，構(gòu)造外部檔案集，在每次迭代過程中，粒子在解空間里不斷地跟隨個體最優(yōu)粒子和全局最優(yōu)粒子根據(jù)式（3）來更新自己［11-14］。

2 艦載聯(lián)合火力打擊的數(shù)學(xué)模型

艦載武器聯(lián)合打擊目標(biāo)的多目標(biāo)函數(shù)模型表示如下：

綜合以上表述，數(shù)學(xué)模型表示如下：

3 改進(jìn)MOPSO 的主要算子

3.1 外部檔案集的選取

外部檔案集是指保存算法找到的所有非支配解的集合，設(shè)定外部檔案集后，算法每次迭代中選定非支配解時就只用與外部集中的解根據(jù)支配關(guān)系作比較，這樣一來算法運(yùn)行速度加快，且每一次的全局最優(yōu)解都是在外部集中選擇出來的，所以說如何選取、維護(hù)外部檔案集在很大程度上影響了算法的性能［16-18］。

按照NSGA-II 中的排序方法對種群進(jìn)行非支配排序，構(gòu)造非支配解集，第一次迭代時，把找到的非支配解集直接放入外部檔案集，在后面的迭代中，將此次產(chǎn)生的非支配解同原有的外部檔案集進(jìn)行Pareto 支配關(guān)系比較，去除被支配的解，新加進(jìn)非支配解，得到新的外部檔案集。

為外部檔案集設(shè)定一個最多存量參數(shù)，伴隨迭代的進(jìn)行，當(dāng)外部集的粒子數(shù)量等于最多存量后，為使繼續(xù)存留較優(yōu)解，通過NSGA-II 中的擁擠距離排序原理實行降序排列，去除超額的擁擠距離較小的解。擁擠距離是一種利用相鄰個體來評判個體與相鄰個體間遠(yuǎn)近即分布是否均勻（多樣性）的指標(biāo)，當(dāng)擁擠距離越大，解集內(nèi)就越松散，解的多樣性就越好。擁擠距離的計算公式如下［15］：

式中，Xk-1和Xk+1是指同Xk分別相鄰的前后兩個個體，n 是指目標(biāo)函數(shù)個數(shù)。

為了使解集的多樣性得到增強(qiáng)，以免算法收斂到局部最優(yōu)，引用遺傳算法中的變異方法來維護(hù)外部集。將外部檔案集依照擁擠距離大小按順序分成兩部分，擁擠距離較大的子集A 和擁擠距離較小的子集B，當(dāng)隨機(jī)數(shù)小于變異概率時，從A 和B 中分別隨機(jī)取得一個個體作為父代，生成兩個新子代，再通過比較新解，換掉外部集內(nèi)的支配解，由于當(dāng)變異概率大時，粒子的全局搜尋能力較好，變異概率小時，利于算法收斂，因此，使用自適應(yīng)變異法，在算法運(yùn)行初始階段使用較大的變異概率，末期使用較小的變異概率，變異概率的表達(dá)式為：

式中，t 和Iter 分別指當(dāng)前迭代次數(shù)和最大迭代次數(shù)，pmin和pmax分別指的是變異概率最小值和最大值。

3.2 個體和全局最優(yōu)解的判定

在每次迭代過程中，粒子都是依據(jù)當(dāng)前得到的兩個極值，即個體最優(yōu)解與全局最優(yōu)解來判斷接下來的去向，所以這兩個最優(yōu)解怎樣獲取成為了算法性能的重要影響因素。算法開始運(yùn)行時，個體最優(yōu)解就是粒子的初始位置，此后，隨著迭代過程的繼續(xù)，個體最優(yōu)解由原個體最優(yōu)與更新后的解依據(jù)Pareto 支配關(guān)系比較得到的非支配解產(chǎn)生，如果兩者之間沒有支配關(guān)系，再比較擁擠距離，擁擠距離更大的就是個體最優(yōu)解。若粒子的個體最優(yōu)位置連續(xù)5 代沒有得到提升，可能是陷入了局部最優(yōu)，此時將此粒子重新賦予新的隨機(jī)值［19］。

全局最優(yōu)解是于非支配解集內(nèi)取值，鑒于外部檔案集里的解互相之間沒有支配關(guān)系，所以依據(jù)擁擠距離來進(jìn)行比較和判定，隨機(jī)選擇依照擁擠距離大小降序排在前面5%的解作為全局最優(yōu)解，能使粒子接下來的走向更寬廣，保證最優(yōu)解具有更好的分布性［20-21］。

3.3 粒子更新時的改進(jìn)

在基本粒子群算法中，對粒子速度和位置進(jìn)行更新的方法見式（3），本文對此進(jìn)行了部分改善，使算法收斂精度達(dá)到更高。

3.3.1 線性遞減的最大速度值

式中，curMax_V 是指第t 次迭代進(jìn)程中的速度最大值，Max_V 是指速度最大值變動的上限。

3.3.2 異步改變的學(xué)習(xí)因子

由粒子的速度、位置更新式（3）可知，學(xué)習(xí)因子能夠使粒子在尋優(yōu)進(jìn)程中掌握自學(xué)和向別的較好的粒子學(xué)習(xí)的能力，逐步接近最優(yōu)解。異步改變的意思是兩者有著不一致的變化，通過使學(xué)習(xí)因子c1和c2異步改變，改變方式如式（8），使得在優(yōu)化開始時粒子的自學(xué)能力好、社會學(xué)習(xí)能力相對差，在優(yōu)化末期正好相反，這種做法能幫助算法收斂到全局最優(yōu)解，防止進(jìn)入局部最優(yōu)。

式中，c1，ini、c2，ini分別指c1、c2的初始值，c1，fin和c2，fin分別指c1、c2的終值。

3.3.3 調(diào)整慣性權(quán)重

在粒子群優(yōu)化算法中，慣性權(quán)重w 是一個對算法性能有著關(guān)鍵作用的參數(shù)，它決定了粒子下一步的速度與當(dāng)前速度的繼承關(guān)系，取值得當(dāng)能使粒子具備均衡的搜索能力。偏大的w 可以使粒子的全局搜尋能力更強(qiáng)，使算法保持多樣性，偏小的w 使粒子的局部尋優(yōu)能力更好，利于算法收斂。因此，利用正切函數(shù)的單調(diào)性和非線性等特性，用于文中對慣性權(quán)重作調(diào)整，構(gòu)造基于正切函數(shù)的權(quán)重法，方法如下：

在迭代過程中，w 呈現(xiàn)非線性遞減，式中的系數(shù)0.875 能使w 的大小處在wstart和wend之中，且當(dāng)k 的大小在區(qū)間［0.4，0.6］內(nèi)時，目標(biāo)函數(shù)的平均最優(yōu)值和方差比較穩(wěn)定［23-24］。

4 采用改進(jìn)MOPSO 求解聯(lián)合火力打擊目標(biāo)分配

4.1 粒子的編碼

采取十進(jìn)制整數(shù)編碼方式反映火力打擊的分配方案，種群所有粒子數(shù)用N 表示，所有方案的集合為X，其中一個解即一個粒子表示為Xn。根據(jù)文中艦載聯(lián)合火力打擊目標(biāo)分配的優(yōu)化模型，將Xn設(shè)置成一個m×n 的矩陣。如下所示：

4.2 不等式約束條件的計算處理

艦載聯(lián)合火力打擊目標(biāo)分配中的限制因素較多，為了簡化計算的復(fù)雜性，將約束不等式當(dāng)成罰函數(shù)加進(jìn)目標(biāo)函數(shù)。在粒子不能滿足約束時，將其視為不可行解，加以相應(yīng)的“懲罰”。引入較大的正整數(shù)K1和K2當(dāng)成懲罰因子，將約束條件變?yōu)槟Ｐ图舆M(jìn)目標(biāo)函數(shù)：

4.3 改進(jìn)算法的流程

用于求解艦載聯(lián)合火力打擊目標(biāo)分配問題的改進(jìn)MOPSO 的流程如圖1 所示。

圖1 改進(jìn)MOPSO 的流程

5 仿真實驗和結(jié)果分析

為了檢測改進(jìn)MOPSO 解決艦載聯(lián)合火力打擊目標(biāo)分配問題的性能，將算法與NSGA-II 作比較，在配置為Intel Core i3-3110M 處理器，4 GB 運(yùn)行內(nèi)存的計算機(jī)上進(jìn)行實驗，仿真軟件為Matlab2008。

假定一次艦載聯(lián)合火力打擊行動，5 個性能相同的敵方目標(biāo)來襲，艦艇上共有3 個武器平臺用來攔截這些目標(biāo)，3 個平臺配置的武器數(shù)目分別為5、6、7，打擊過程中最多給每個目標(biāo)分配的武器數(shù)分別為3、4、3、3、2。

同一個武器平臺上配置的是同一類型的武器，對抗目標(biāo)的命中概率是一致的，如下頁表1 所示。

表1 命中概率

表2 改進(jìn)MOPSO 的運(yùn)行時間/s

表3 NSGA-II 的運(yùn)行時間/s

從運(yùn)行時間對比可知，同等情況下，改進(jìn)MOPSO 在一定程度上比NSGA-II 的運(yùn)行時間更短，具有更快的速度，更適合求解武器-目標(biāo)分配的多目標(biāo)優(yōu)化問題。

將算法迭代總次數(shù)設(shè)定為100，粒子總個數(shù)為50，在這種情況下兩種算法實驗得到的Pareto 解集分別如圖2 和圖3 所示。

圖2 改進(jìn)MOPSO 的Pareto 解集

比較兩個結(jié)果圖能得出，改進(jìn)MOPSO 最后求解得到的Pareto 結(jié)果的分布更均勻，精度更高，綜合性能更優(yōu)秀。而NSGA-II 獲得的解分布性稍差，結(jié)果不夠穩(wěn)定。在武器使用量為10 和11 時沒能得到最優(yōu)解，在同等武器消耗時，采用改進(jìn)MOPSO求出的打擊失敗概率更小，此次行動勝利的可能性更高。

圖3 NSGA-II 的Pareto 解集

通過進(jìn)行仿真實驗，比較兩種算法得到的實驗結(jié)果，可知NSGA-II 和本文中的改進(jìn)MOPSO 在解決艦載聯(lián)合火力打擊目標(biāo)分配問題時，都能獲得適宜的分配方案，但使用改進(jìn)MOPSO 的運(yùn)行速度更快，求出的方案可以達(dá)到更大的擊中概率，更能適應(yīng)戰(zhàn)役需求。

6 結(jié)論

本文在打擊失敗概率最小的基礎(chǔ)上兼顧消耗武器數(shù)量最少，構(gòu)建艦載聯(lián)合火力打擊多目標(biāo)分配模型，采用改進(jìn)的多目標(biāo)粒子群算法進(jìn)行求解。通過與NSGA-II 實例仿真對比，改進(jìn)MOPSO 得到的Pareto 解精度更高、多樣性更好，且平均速度更快，更能適用于求解艦載聯(lián)合火力打擊目標(biāo)分配問題。