基于模糊多目標規劃的防空反導火力分配

徐 浩, 邢清華, 王 偉

(空軍工程大學防空反導學院, 陜西 西安 710051)

0 引 言

信息化條件下,空襲是高度集成的體系化作戰。作為防御方,需要同時執行防空和反導任務,即利用防空反導武器系統擔負起同時反空氣動力學目標和反彈道類目標的作戰任務[1]。火力分配(weapon target assignment,WTA)作為防空反導作戰的關鍵環節,對防空反導作戰效能的發揮具有重要影響。因此研究防空反導WTA具有非常重要的意義。

鑒于WTA的重要性,廣大學者紛紛采用蟻群算法[2]、遺傳算法[3]、克隆選擇算法[4]、Memetic 算法[5]和粒子群算法[6]等對WTA問題進行了深入研究。這些研究大多以對敵毀傷概率最大為目標函數構建單目標優化WTA模型,需要分配全部火力,不符合作戰實際。為此,文獻[5-6]提出以最大作戰效費比為目標函數構建WTA模型,避免分配全部火力。然而,這種方法本質上還是單目標優化,采用事先提供的決策偏好信息,僅能給出一種WTA方案,對戰場態勢變化的適應性較弱和對不同指揮員的決策偏好體現不夠。并且,隨著戰場環境的日益復雜化,防空反導作戰過程中獲取的信息具有很強的不確定性,確定型WTA方法[2,6]已很難適用。

為此,考慮到基于多目標優化的WTA方法[7-8]能提供多種分配方案,具有對戰場態勢變化適應性較強和能較好地融合指揮員決策偏好的優點,并針對防空反導WTA面臨目標威脅信息不確定的情況,采用模糊多目標規劃方法構建WTA模型以提高不確定情況下防空反導WTA方法對戰場態勢變化的適應性。鑒于量子行為粒子群算法的優良性能,提出具有單/雙勢阱的多目標量子行為粒子群算法(multi-objective quantum-behaved particle swarm optimization with double/single-well, MOQPSO-D/S)以求解所建立的WTA模型。

1 基于模糊多目標規劃的防空反導WTA建模

1.1 模型假設

假設m個防空反導武器系統參與作戰,需要攔截n個來襲目標,其中,第1～na個目標為空氣動力學目標,記為A類目標,其余為彈道類目標,記為B類目標。

假設第i個武器系統發射xij枚攔截彈攔截第j個目標,且單發毀傷概率為pij。

1.2 模糊多目標建模

以攔截效益最大化和攔截損耗最小化為目標建立多目標火力分配優化模型

(1)

(2)

約束條件為

(1) 武器系統i最多射擊一種類型的目標

(3)

(2) 武器系統i攔截的目標數量不能多于其目標通道

(4)

(3) 武器系統i發射的攔截彈數量不能多于其導彈通道

(5)

(4) 武器系統i發射的攔截彈數量不能多于其攜帶的導彈數量

(6)

(5) 用于攔截目標j的攔截彈數量不少于攔截其所需的最少火力

(7)

1.3 模型的等價清晰化

該WTA模型的目標函數含有模糊參數,不能直接采用優化算法對其進行求解,需要對含有模糊參數的目標函數進行處理,轉化為相應的清晰等價形式。

利用不確定理論中的必要性測度[9]將含有模糊參數的目標函數式(1)轉化為

minc

(8)

式中,θ為來襲目標剩余威脅度小于或等于c的必要性測度。

因此，可以將式(8)轉化為

minc

(9)

進一步得到其清晰等價形式

(10)

這樣將基于模糊多目標規劃的WTA模型轉化為了清晰的多目標規劃模型,可以利用多目標優化算法對其進行求解。

2 基于MOQPSO-D/S的模型求解

量子行為粒子群算法[10](quantum-behaved particle swarm optimization,QPSO)相對粒子群算法具有收斂速度更快、控制參數更少和全局收斂等優點,已受到廣大學者關注[11-12]。起初,QPSO主要用于求解單目標優化問題。后來,學者們將其引入到多目標優化問題中,提出了多種基于QPSO的多目標優化算法[13-17]。鑒于這類算法的優良性能,將其引入到WTA多目標優化問題的求解中。

2.1 MOQPSO-D/S算法

多目標優化不同于單目標優化收斂于一個全局最優解,它要求解集多樣性要好、分布均勻、與真實Pareto解集盡可能接近。然而,QPSO的快速收斂特性,導致基于QPSO的多目標優化算法具有容易早熟收斂的缺陷;QPSO全局收斂于一個最優解的特性又限制了基于QPSO的多目標優化算法解的多樣性和分布性。為此,提出MOQPSO-D/S算法用于求解防空反導WTA多目標規劃模型。該算法采用單/雙勢阱粒子位置更新方法均衡解的多樣性、求解精度及速度之間的關系;采用混合隨機變異方法避免算法早熟收斂及提高算法整體尋優精度;采用兩階段法選取領導粒子,提高解的分布均勻性和求解速度。

2.1.1 單/雙勢阱粒子位置更新公式

所謂單/雙勢阱位置更新方法就是在尋優早期,為提高種群多樣性和避免算法早熟收斂,采用兩個吸引子來更新粒子的位置;在尋優后期,為提高算法收斂精度和速度,采用單個吸引子來更新粒子的位置。具體的位置更新公式為

xk(t+1)=

(11)

(12)

Lk(t)=

(13)

式中,α是擴張-收縮因子。

2.1.2 粒子混合隨機變異方法

為了避免算法在尋優早期出現早熟收斂以及提高算法在尋優后期的收斂精度,提出混合隨機變異方法。所謂混合隨機變異,就是在尋優早期采用均勻隨機變異,在尋優后期采用高斯變異。均勻隨機變異可以使粒子以等概率在[xmin,xmax]上完全遍歷,從而可以提高解的多樣性,避免算法早熟收斂。其中[xmin,xmax]是決策變量的優化取值范圍。高斯變異可以使粒子在原位置附近變異,從而避免算法后期因變異范圍過大而導致尋優倒退,同時可以提高算法后期的局部尋優精度。具體方法為

(15)

式中,rand是閉區間[0,1]上均勻分布的隨機數;Rand(·)是均勻隨機變異算子;Gaussian(·)是高斯變異算子;σ是高斯變異均方差;pm是變異概率。

2.1.3 兩階段領導粒子選取方法

(16)

式中,x是粒子的位置；Nf是目標函數的個數。

sigma值法選擇領導粒子的原理如圖1所示。

圖1 Sigma值法選擇領導粒子Fig.1 Selection guider particle by sigma method

圖2 第2個領導粒子的選取方法Fig.2 Selection method of the second guider particle

2.2 MOQPSO-D/S算法求解WTA模型

2.2.1 粒子編碼

由于MOQPSO-D/S算法不能直接求解離散問題,因此需要對粒子的位置進行編碼才能求解WTA模型。記粒子位置為x,采用矩陣式編碼方式進行編碼,具體為

式中,xij表示武器系統i攔截目標j所使用的攔截彈數量。

2.2.2 基于MOQPSO-D/S的模型求解過程

基于MOQPSO-D/S算法求解防空反導WTA模糊規劃模型的具體步驟如下:

步驟1設置算法參數,隨機初始化種群。

步驟3初始化外部存儲文件ARCHIVE。根據粒子的適應度計算粒子間的支配關系;將非支配粒子存儲到ARCHIVE中,并計算ARCHIVE中粒子的擁擠距離和sigma值。

步驟4令迭代次數t=1。

步驟5采用兩階段法選擇各粒子的領導粒子gbest1和gbest2(當t>tmax/2時,不選取gbest2),并按式(11)更新粒子位置。

步驟6判斷是否滿足變異條件。若滿足,則對粒子進行混合隨機變異操作;否則轉步驟7。

步驟8計算粒子xk與ARCHIVE中粒子的支配關系,若粒子xk支配ARCHIVE中的粒子xg,則將粒子xk加入ARCHIVE中,并刪除粒子xg;若粒子xk與ARCHIVE中的粒子互不支配,則將粒子xk加入ARCHIVE中,轉步驟9;否則,轉步驟10。

步驟9計算更新后ARCHIVE中粒子的擁擠距離及新加入粒子的sigma值;判斷ARCHIVE中的粒子數是否超過容量,若超出容量,則將擁擠距離最小的粒子刪除;否則轉步驟10。

步驟10令t=t+1;判斷t>tmax是否成立,若成立,則終止迭代,輸出ARCHIVE中的粒子作為多個防空反導WTA方案;否則轉步驟5。

2.3 MOQPSO-D/S算法的計算復雜度分析

設群體規模為N,ARCHIVE容量為M,目標函數個數為Nf,則MOQPSO-D/S算法單次迭代的計算復雜度主要由以下幾部分決定:計算各粒子適應度的計算復雜度O(NfN);粒子個體最優位置更新的計算復雜度O(NfN);種群位置更新后,各粒子與ARCHIVE中的粒子進行比較的計算復雜度O(NfMN);更新ARCHIVE,進行擁擠距離排序的計算復雜度O(Nf(M+N)2);計算更新后ARCHIVE中粒子的sigma值的計算復雜度為O(N)。以上都是各部分最差情況下的計算復雜度。因此,MOQPSO-D/S算法每進行一次迭代的計算復雜度為O(Nf(M+N)2)。這與文獻[15]中給出的MOQPSO-CD的計算復雜度是相同的,在可接受范圍內。

3 實例分析

為了驗證基于模糊多目標規劃的火力分配模型的合理性,同時考察MOQPSO-D/S算法求解火力分配問題的尋優性能,給出以下實例。

假設某次防空反導作戰中,我方6個武器系統Wi(i=1,2,…,6)需要攔截5個來襲目標Tj(j=1,2,…,5)。各武器系統所擁有的目標通道、導彈通道、彈藥庫存量以及單發攔截彈的歸一化價值如表1所示。

表1 各武器系統的WTA及攔截彈價值

表2 單發毀傷概率

在Core i5 3.3 GHz、內存4 GB的計算機上的Matlab 2013a環境下進行仿真實驗。以單目標優化算法IDPSO[6],以及MOQPSO-DPS[17]、MOQPSO-CD[14]和MOPSO-CD[20]等多目標優化算法作為對比算法,與本文提出的MOQPSO-D/S在求解WTA問題上進行性能對比。各算法均采用相同的粒子編碼和不可行解調整方式,多目標優化算法的ARCHIVE容量都設置為100, MOQPSO-D/S、MOQPSO-DPS和MOQPSO-CD算法的擴張-收縮因子α隨著迭代次數變化由1呈線性遞減到0.4。

3.1 實時性分析

在不同群體規模和迭代次數下采用MOQPSO-D/S算法求解算例,分別運行30次,算法平均運行時間如表3所示。

表3 算法平均運行時間

由表3可知,MOQPSO-D/S算法可以有效滿足防空反導WTA對算法實時性的需要。

在群體規模和迭代次數都為100的情況下,采用MOQPSO-DPS、MOQPSO-CD和MOPSO-CD求解算例,分別運行30次,將它們的運行時間與本文算法相對比,結果如圖3所示。

圖3 各算法的實時性比較Fig.3 Comparison of real-time performance

由圖3可知,MOQPSO-D/S的實時性要明顯優于其他3種算法。

3.2 收斂性分析

采用MOQPSO-D/S求解算例,在群體規模和迭代次數都為50的情況下,獲得的結果如圖4所示。

圖4 MOQPSO-D/S求解算例的仿真結果Fig.4 Simulation results of MOQPSO-D/S solving the example

由圖4可知,采用MOQPSO-D/S求解防空反導WTA的模糊多目標規劃模型得到的解,分布較為均勻。其中,每個點對應一種WTA方案,可以為指揮員提供多種決策方案。指揮員根據戰場態勢和風險偏好做出最終的WTA決策。相較于僅能給出WTA方案的單目標優化方法,該方法可以更好地適應戰場態勢的變化和融合指揮員戰術思想來進行WTA。

為了驗證采用MOQPSO-D/S求解WTA問題得到的結果的有效性,采用文獻[6]中以最大效費比為目標函數建立的單目標WTA模型和IDPSO算法求解本算例。設置群體規模和迭代次數均為50,進行30次仿真,平均運行時間為0.719 3 s,算法的迭代曲線和最優WTA結果分別如圖5和表4所示。

圖5 基于IDPSO的WTA迭代曲線Fig.5 Iterative curve of WTA based on IDPSO

由圖5可知，單目標優化算法所得到的最優分配結果與圖4中紅色五角星標注點對應結果相同,而算法在相同群體規模和迭代次數條件下的平均運行時間比MOQPSO-D/S算法略小。由此表明,雖然采用MOQPSO-D/S求解WTA問題一定程度上分散了計算資源,但依然能獲得包含單目標最優分配結果的滿意結果。同時證明了基于模糊多目標規劃的WTA模型是合理的,采用MOQPSO-D/S求解模型是可行的。

表4 基于IDPSO的最優WTA

為了進一步驗證MOQPSO-D/S算法求解WTA問題時的收斂性,在群體規模和迭代次數都為100的條件下,采用MOQPSO-D/S、MOQPSO-DPS、MOQPSO-CD和MOPSO-CD求解算例,將得到的Pareto最優解集進行對比。以支配覆蓋率C(X1,X2)[21]衡量各算法的收斂性優劣。其中,X1和X2分別表示兩種算法得到的Pareto最優解集,C(X1,X2)越大、C(X2,X1)越小,表明X1對應算法的收斂性能越優于X2對應算法。各算法的對比結果如表5所示,表中A1,A2,A3和A4分別代表MOQPSO-D/S、MOQPSO-DPS、MOQPSO-CD和MOPSO-CD算法所求得的Pareto最優解集。

表5 各算法的Pareto最優解集之間的支配覆蓋率

由表5可知,MOQPSO-D/S求解WTA問題的收斂性與其他3種多目標優化算法相比是最好的。

3.3 多樣性分析

為了驗證MOQPSO-D/S算法求解WTA問題得到的Pareto解的分布均勻性,采用分布廣度指標SP[22]進行評價,SP值越小,表明Pareto解分布越均勻。在群體規模和迭代次數都為100的條件下,算法均獨立運行30次,SP值的統計結果如圖6所示。

圖6 各算法的Pareto最優解集的分布性Fig.6 Diversification of four algorithms’ Pareto optimal sets

由圖6可知,MOQPSO-D/S算法求解WTA問題得到的Pareto最優解集的分布是最均勻的,并且MOQPSO-D/S求得的 Pareto最優解集的分布性是最穩定的。

為了進一步驗證MOQPSO-D/S算法求解防空反導WTA問題的有效性,在此對不同作戰規模(m×n)算例進行仿真求解。各算法求解作戰規模分別為6×6、20×30和50×80的算例,必要性測度均為0.8,進行30次仿真得到的仿真結果如表6所示。

表6 各算法求解不同作戰規模算例的性能比較

由于篇幅所限,在此不一一列出各武器系統的火力配置及攔截彈價值、目標威脅度和單發毀傷概率。由表6可知,求解不同作戰規模的算例時,MOQPSO-D/S算法在實時性及解的分布均勻性方面依然比其他3種算法優越。另外,通過采用支配覆蓋率對比各算法所求得的Pareto最優解集可知, MOQPSO-D/S求解不同作戰規模的WTA問題的收斂性依然是最好的。在此不再列出各算法所求Pareto最優解集之間的支配覆蓋率。

4 結 論

基于模糊多目標規劃方法建立的防空反導WTA模型,考慮了來襲目標威脅值不確定的問題,可以為不確定情況下的防空反導WTA提供參考。

基于MOQPSO-D/S的WTA方法可以得到多種WTA方案,相比單目標優化方法,在輔助WTA決策時,能更好地適應戰場態勢的變化及融合指揮員的戰術思想。

由于采用了單/雙勢阱粒子位置更新、混合隨機變異和兩階段領導粒子選取等方法,所提出的MOQPSO-D/S算法相比MOQPSO-DPS、MOQPSO-CD及MOPSO-CD算法,在求解WTA問題時,具有更好的實時性、收斂性以及可以獲得分布更為均勻的Pareto最優解集,可以為WTA多目標優化模型的求解提供優良算法。

[1] TEAGUE J M, DORNER K R, HARTMAN W B. Back to the future: integrated air and missile defense in the pacific, AD-A622600[R].Maxwell AFB,AL:Air Force Research Institute,2015.

[2] 常天慶,陳軍偉,郝娜,等.裝甲分隊動態武器目標分配中蟻群算法終止控制[J].系統工程與電子技術,2015,37(2):343-347.

CHANG T Q, CHEN J W, HAO N, et al. Terminating control of ant colony algorithm for armored unit[J].Systems Engineering and Electronics, 2015, 37(2): 336-342.

[3] 董朝陽,路遙,王青.改進的遺傳算法求解火力分配優化問題[J].兵工學報,2016,37(1):97-102.

DONG C Y, LU Y, WANG Q. Improved genetic algorithm for solving firepower distribution[J]. Acta Armamentraii,2016,37(1):97-102.

[4] LIANG H, KANG F. Adaptive chaos parallel clonal selection algorithm for objective optimization in WTA application[J]. Optik-International Journal for Light and Electron Optics, 2016, 127(6): 3459-3465.

[5] 顏冀,李相民,劉立佳,等.基于Memetic算法的超視距協同空戰火力分配[J].北京航空航天大學學報,2014,40(10):1424-1429.

YAN J, LI X M, LIU L J, et al. Weapon-target assignment based on memetic optimization algorithm in beyond-visual-rang cooperative air combat[J]. Journal of Beijing University of Aeronautics and Astronautics, 2014, 40(10): 1424-1429.

[6] 范成禮, 邢清華, 鄭明發, 等. 基于IDPSO的武器目標分配優化算法[J]. 系統工程與電子技術, 2015, 37(2): 336-342.

FAN C L, XING Q H, ZHENG M F, et al. Weapon-target allocation optimization algorithm based on IDPSO[J]. Systems Engineering and Electronics, 2015, 37(2): 336-342.

[7] 顧佼佼,趙建軍,顏驥,等.基于MODPSO-GSA的協同空戰武器目標分配[J].北京航空航天大學學報,2015,41(2):252-258.

GU J J, ZHAO J J, YAN J, et al. Cooperative weapon-target assignment based on multi-objective discrete particle swarm optimization-gravitational search algorithm in air combat[J]. Journal of Beijing University of Aeronautics and Astronautics,2015,41(2):252-258.

[8] 張瀅,楊任農,左家亮,等.基于分解進化多目標優化算法的火力分配問題[J].系統工程與電子技術,2014,36(12):2435-2441.

ZHANG Y, YANG R N, ZUO J L, et al. Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms[J]. Systems Engineering and Electronics, 2014, 36(12): 2435-2441.

[9] 劉寶碇, 趙瑞清, 王綱. 不確定規劃及應用[M]. 北京: 清華大學出版社, 2003.

LIU B D, ZHAO R Q, WANG G. Uncertain programming with application[M]. Beijing: Tsinghua University Press, 2003.

[10] SUN J, FENG B, XU W B. Particle swarm optimization with particles having quantum behavior[C]∥Proc.of the IEEE Congress on Evolutionary Computation, 2004: 325-331.

[11] SINGH M R, MAHAPATRA S S. A quantum behaved particle swarm optimization for flexible job shop scheduling[J]. Computers & Industrial Engineering, 2016, 93(1): 36-44.

[12] WANG G G, GANDOMI A H, ALAVI A H, et al. A hybrid method based on krill herd and quantum-behaved particle swarm optimization[J]. Neural Computing and Applications, 2016, 27(4): 989-1006.

[13] 沈佳寧. 基于QPSO算法求解多目標優化問題及其應用[D]. 無錫: 江南大學, 2008.

SHEN J N. Solving multi-objective problem based on QPSO algorithm and application[D]. Wuxi: Southern Yangtze University, 2008.

[14] 施展, 陳慶偉. 基于QPSO和擁擠距離排序的多目標量子粒子群優化算法[J]. 控制與決策, 2011, 26(4): 540-547.

SHI Z, CHEN Q W. Multi-objective quantum-behaved particle swarm optimization algorithm based on QPSO and crowding distance sorting[J].Control and Decision,2011,26(4):540-547.

[15] 施展. 多目標量子行為粒子群優化算法研究[D]. 南京: 南京理工大學, 2011.

SHI Z. Research on multi-objective quantum-behaved particle swarm optimization algorithms[D]. Nanjing: Nanjing University of Science and Technology, 2011.

[16] HEYAM A B. A quantum behaved particle swarm approach to multi-objective optimization[D]. Birmingham, UK: the University of Birmingham, 2015.

[17] XU S H, MU X D, CHAI D, et al. Multi-objective quantum-behaved particle swarm optimization algorithm with double-potential well and share-learning[J]. Optik-International Journal for Light and Electron Optics, 2016, 127(12): 4921-4927.

[18] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Trans.on Evolutionary Computation, 2002, 6(2): 182-197.

[19] MOSTAGHIM S, TEICH J. Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO)[C]∥Proc.of the IEEE Swarm Intelligence Symposium, 2003: 26-33.

[20] RAQUEL C R, JR NAVAL P C. An effective use of crowding distance in multiobjective particle swarm optimization[C]∥Proc.of the Genetic and Evolutionary Computation Conference, 2005: 257-264.

[21] ZITZLER E. Evolutionary algorithms for multi-objective optimization methods and applications[D]. Switzerland: Swiss Federal Institute of Technology Zurich, 1999.

[22] SCHOTT J R. Fault tolerant design using single and multicriteria genetic algorithm optimization[D]. Cambridge: Massachusetts Institute Technology, 1995.