基于改進多目標HQPSOGA求解武器目標分配問題

邱少明 馮江惠 杜秀麗 王建偉

(大連大學通信與網絡重點實驗室 遼寧 大連 116622)

0 引 言

武器-目標分配問題(Weapon Target Assignment, WTA)提供武器資源的分配方案，是一種非確定性多項式(Non-deterministic Polynomial, NP)完全問題，目前重點研究多個判別標準下求解最優分配方案的問題，因此常看作多目標優化問題(Multi-objective Optimization Problem, MOP)。啟發式隨機搜索智能優化算法，如粒子群算法(Particle Swarm Optimization, PSO)[1]、蟻群算法[2]和差分進化算法[3]等極大地提高了WTA求解效率。PSO及其派生算法在WTA的研究主要從求解效率和解的質量兩方面展開，文獻[4]根據超鞅收斂定理證明靜態粒子群優化算法(Static Particle Swarm Optimization, SPSO)的收斂性在概率上達到全局最優，且量子行為粒子群算法(Quantum-behaved Particle Swarm Optimization, QPSO)也是一種全局收斂算法。Clerc等[5]、Kadirkamanathan等[6]和Cleghorn等[7]給出穩定收斂時加速因子的取值范圍，豐富了PSO的理論研究。

目前PSO的應用研究更豐富，算法迭代中種群的多樣性求解質量好壞是重要衡量指標。基于此，文獻[8]提出一種“反向預測器”資源規劃粒子群算法，迭代時將粒子位置進行擾動，增加粒子多樣性；文獻[9]提出的算法中，設置程序挑選引導粒子更新種群，保證算法多樣性和快速收斂性。近年來，量子計算為智能計算的優化提供了新思路，孫俊[10]提出基于δ勢阱的QPSO，給出描述量子空間中粒子行為的量子模型，粒子具有更強的不確定性；針對QPSO的早熟收斂現象，提出多樣性控制的QPSO；文獻[11]根據聚集度判斷早熟停滯，并用慢變函數克服早熟收斂,保持了種群多樣性；文獻[12]針對QPSO粒子間信息共享機制單一等問題，利用社會學習策略和萊維飛行策略提高算法的收斂精度和速度。在多目標QPSO方面，文獻[13]將QPSO與遺傳算法(Genetic Algorithm, GA)相結合，提出混合量子行為粒子群和可調節遺傳算法(Hybrid Quantum-behaved Particle Swarm Optimization and self-adjustable Genetic Algorithm, HQPSOGA)，作用于雷達干擾資源優化多目標分配模型，為干擾機的形成提供了更好的整體干擾能力。但是QPSO在求解多目標優化問題時，收斂速度快也易過早喪失解的多樣性，陷入早熟收斂[14]。

本文首先引入一種多樣性判別方法，提出粒子多樣性貢獻度的概念，基于隨機選擇的聚類算法(CLARANS)和模糊貼近度原則，從目標函數和決策空間兩個角度綜合度量粒子間相似性，從而判別粒子多樣性貢獻度。該方法用于HQPSOGA的QPSO部分，根據粒子多樣性貢獻度和適應度值比較隨機新增粒子與舊有粒子的優劣并更新個體最優解，最終引導粒子找到Pareto最優解。HQPSOGA充分利用了QPSO和可調節遺傳算法(Adjustable Genetic Algorithm, AGA)在尋找全局最優解上的優勢，在解決方案質量、穩定性、收斂速度和可信度方面具有更優越的性能[13]，因此提出基于多樣性貢獻度的HQPSOGA(Diversity Contribution Improved HQPSOGA, DCI-HQPSOGA)，在QPSO部分引入多樣性判別，通過性能測試函數，可更直觀地展現所提方法對QPSO與HQPSOGA求解質量及種群多樣性的影響，便于對比分析。最后，改進算法應用于兩目標模型下的靜態武器-目標分配問題(Static Weapon Target Assignment, SWTA)，提升戰場環境下的求解精度。

1 相關理論

1.1 多目標優化問題

MOP由一組目標函數和約束組成，數學描述如下：

(1)

s.t.gi(X)≤0i=1,2,…,p

式中：X=(x1,x2,…,xn)T是Rn空間的n維向量。X所在空間Ω是問題的決策空間，當且僅當所有目標上的決策向量X1不比另一個決策向量X2差時，叫作X1支配X2；fi(X),i=1,2,…,m為問題的子目標函數，各子目標間相互沖突，即不存在X∈Ω使f1(X),f2(X),…,fm(X)在X處同時取最小值，這樣的折中解的集合叫作Pareto最優解集、非劣解集或非支配解集；m維向量(f1(X),f2(X),…,fm(X))所在空間為問題的目標空間，gi(X)≤0,i=1,2,…,p為約束函數；所有Pareto最優解組成的曲面為Pareto前沿。

1.2 基于隨機選擇的聚類算法

CLARANS算法是大型應用聚類算法(Clustering LARge Applications, CLARA)和k-中心點聚類算法(Partitioning Around Medoid, PAM)的結合，該算法選擇數據的小部分作為樣本，可拓展數據處理量的伸縮范圍，提高聚類效率，在一定程度上克服了K-means聚類算法對“噪聲”數據敏感以及模糊聚類算法求解效率低的問題，也避免了密度聚類算法DBSCAN需調整參數帶來的高計算復雜度。

CLARANS的基本流程：隨機選k個對象作為聚類中心，剩余對象就近分配給對應聚類中心，得到k個簇，聚類中心隨著迭代進行更改：在每個簇中，隨機選一個非聚類中心點，計算該點與其他點的距離之和，如果該和比當前聚類中心與其他點的距離之和小，則該點作為新聚類中心，繼續迭代直到隨機選擇的次數滿足要求為止。

1.3 模糊貼近度原則

模糊貼近度在模糊模式識別中描述兩個模糊集的接近程度，貼近度越大接近程度越大。文獻[15]采用貼近度識別發信號的雷達，采用特征參數集的標準差反映特征參數的影響程度。本文模式識別的聚類過程采用CLARANS，用模糊距離貼近度計算簇中粒子到聚類中心的接近程度[16]，聚類中心即已知模型，其他粒子與聚類中心的距離貼近度即兩個模型的相似度。歐氏距離和余弦距離等相似度計算公式不適用于粒子決策空間維數較多的情況，且不能表示粒子在決策空間中各維度的相似性。

2 基于多樣性貢獻度的混合量子行為粒子群和可調節遺傳算法

2.1 量子行為粒子群算法

QPSO以更多樣化的方式重新定義PSO中粒子的位置和速度[17]，算法假設在局部吸引點的每個維度上存在一維δ勢阱，且種群中每個粒子都具有量子行為，粒子的量子態由波函數描述。粒子的位置由蒙特卡羅模擬方法更新如下：

(2)

2.2 DCI-HQPSOGA及求解步驟

DCI-HQPSOGA在HQPSOGA的基礎上改進，在粒子群位置更新后加入本文的多樣性判別方法，程序流程如圖1所示。本文所指算法均為多目標算法，改進的QPSO部分記為DCI-QPSO。

圖1 DCI-HQPSOGA流程

2.3 DCI-HQPSOGA具體實現

多樣性貢獻度的計算分兩步：第一步，先用CLARANS將粒子分為k類，計算粒子與聚類中心的距離，作為粒子的第一部分多樣性貢獻度。距離越小，相似性越大，多樣性貢獻度越小。CLARANS聚類過程中，k為當前非劣解個數，每個非劣解代表一個多樣性的方向，為找到多個多樣性的方向，用非劣解初始化各聚類中心，使得每個多樣性方向上相似性大的粒子歸為一簇。

從簇中隨機選擇非當前點，更新聚類中心，為平衡解的質量和求解效率，用參數δ計算每個簇中選擇聚類中心的次數tRand，計算式表示為：

tRand=δ×cl

(3)

式中：cl表示當前簇中粒子的數量；tRand∈[1,cl]。

粒子到聚類中心的距離D計算式表示為：

(4)

式中：第一項和第二項表示粒子到聚類中心的余弦距離和歐氏距離；D即目標函數上粒子的多樣性貢獻度。

第二步，利用式(5)的距離貼近度計算粒子的第二部分多樣性貢獻度。

(5)

用第一步的聚類中心作為模型，同一個簇中的其他粒子作為待識別對象，計算結果表示粒子與聚類中心的相似程度。

綜上，粒子多樣性貢獻度表示為：

(6)

式中：β表示兩種距離所占比例，通常β=0.5。

通過綜合比較多樣性貢獻度小的粒子與引入的隨機新增粒子來改善個體最優解，先計算多樣性貢獻度的界限值b，計算式為：

b=(max(divContri)-min(divContri))×

(MAX_Iter-iter+1)/MAX_Iter

(7)

式中：iter是當前迭代次數;divContri是粒子多樣性貢獻度矩陣。b保證在增加多樣性的同時，不破壞粒子向最優方向移動。記錄貢獻度小于b的粒子，將這些粒子組成的種群稱為pop，引入隨機新增粒子popR，令popR與pop的規模相等，計算兩者對應位置粒子的適應度值，保留較優粒子。

3 用DCI-HQPSOGA求解SWTA問題

3.1 SWTA問題模型

在經典SWTA場景[19]下構建SWTA多目標優化數學模型：

式中：xij表示分配給目標j的第i種武器的數量。

構建兩個目標函數：目標生存概率最小函數f1和武器彈藥消耗最少函數f2，第i種武器對目標j的毀傷概率為pij，第i種武器打擊目標j時目標j的生存概率為qij=1-pij、價值為Vj。f1計算式表示為：

(8)

式中：目標價值Vj是對戰術、目標威脅度等指標的綜合考量[20]。

設武器消耗量取決于武器使用個數與其對于目標的價值，則f2計算式表示為：

(9)

(10)

綜上，SWTA模型表示為：

(11)

3.2 用DCI-HQPSOGA實現WTA

實現步驟參考圖1，初始化參數包括武器數weaponNum、目標數Dim、毀傷概率矩陣p、DCI-HQPSOGA初始參數的設置。

4 實驗與結果分析

4.1 DCI-HQPSOGA性能測試

首先，采用兩目標測試函數ZDT1-ZDT4對比分析QPSO[10]、DCI-QPSO、NSGA-II、HQPSOGA和本文算法的性能，四個測試函數是兩目標最小化問題，其中ZDT4具有局部最優值，干擾全局Pareto前沿的搜索，可檢測算法克服陷入局部最優的能力[23]；再用GD(世代距離)、IGD(反世代距離)、HV(超體積指標)和Spacing(均勻性度量指標)檢測算法收斂性和多樣性，GD度量解的收斂性，Spacing度量解分布的均勻性，IGD和HV綜合度量解的收斂性和多樣性。多樣性包括體現粒子分布均勻程度的均勻性和整個解集在目標空間中分布廣泛程度的廣泛性，GD、Spacing和IGD值越小越好，HV值越大越好。實驗種群數和迭代次數均為100，取20次運行的最好結果，所求Pareto前沿如圖2所示，四種性能指標結果如表1-表4所示。

(a) ZDT1

(b) ZDT2

(c) ZDT3

(d) ZDT4圖2 五種算法在ZDT1-ZDT4上的Pareto前沿

表1 五種算法在GD指標上的比較

表2 五種算法在IGD指標上的比較

表3 五種算法在HV指標上的比較

表4 五種算法在Spacing指標上的比較

對比圖2可知：五種算法在ZDT1-ZDT4都能找到Pareto前沿，在ZDT4上，QPSO只找到少量最優解，DCI-QPSO、NSGA-II和HQPSOGA的解分布不均勻，DCI-HQPSOGA的解在Pareto前沿均勻分布。

結合表1-表4中數據分析，GD指標中，QPSO在ZDT1-ZDT3值最小，說明QPSO的收斂性最好，但在ZDT4中效果較差，說明多目標條件下的QPSO易陷入局部最優，DCI-HQPSOGA在ZDT4表現最優，說明DCI-HQPSOGA在易陷入局部最優的環境下收斂性最好；IGD和HV指標中，NSGA-II在ZDT4優于QPSO，但不如HQPSOGA和DCI-HQPSOGA，DCI-HQPSOGA在ZDT4表現最優，且DCI-QPSO在ZDT4優于QPSO，說明本文多樣性判別方法有效提高了算法多樣性，不易陷入局部最優；Spacing指標中，NSGA-II優于HQPSOGA，說明NSGA-II中擁擠距離排序方法使種群在目標空間上分布更加均勻，DCI-QPSO表現最優，說明DCI-QPSO分布性較好，且DCI-HQPSOGA的分布性優于HQPSOGA，說明在本文多樣性判別方法的影響下，DCI-HQPSOGA的分布性有所提高。

綜上，DCI-HQPSOGA在種群多樣性保持方面的各項指標上有明顯優勢，可較好克服粒子陷入局部最優的缺點，但在收斂過程中打亂了部分粒子飛行方向，影響了粒子的收斂速度。

4.2 DCI-HQPSOGA在WTA中的應用

各類型武器對目標的毀傷概率表和目標價值表如表5和表6所示[24]，其中Wi表示第i種武器。迭代次數MAX_Iter=3 000，武器種類數m=10，每種武器數對應為C=[3, 1, 1, 5, 1, 1, 1, 8, 1, 10]，目標數n=8。第iter次迭代的膨脹-收縮系數φ(iter)采用線性減小策略，phe∈[0.5,1]，phemax=1，phemin=0.5，φ(iter)計算如下：

φ(iter)=phemax-(phemax-phemin)×

iter/MAX_Iter

(12) 表5 武器對目標毀傷概率值表

表6 目標價值表

由于CLARANS嵌套在QPSO迭代過程中，為降低算法整體復雜度，δ分別取0.1、0.25、0.5、0.75和1，計算平均求解時間和算法收斂情況，所花時間如表7所示，收斂情況如圖3所示。

表7 δ取不同值時所花時間表

圖3 非線性遞減參數控制策略、不同CLARANS隨機 次數下DCI-HQPSOGA的收斂效果

圖3中，δ=0.5時結果最好，其次是δ=0.25、δ=0.75、δ=1，雖然δ=0.1效果較差，但與δ=0.5的差值小于0.002。考慮對求解效率的要求，δ=0.1是最好的選擇策略，因此取δ=0.1，用DCI-HQPSOGA求解WTA問題。表8展示了非劣解對應的4種方案。

表8 DCI-HQPSOGA求解WTA問題的分配方案

續表8

對比DCI-HQPSOGA與QPSO、DCI-QPSO、NSGA-II、HQPSOGA的Pareto分布曲線，觀察各算法的收斂情況，結果如圖4所示。

圖4 δ=0.1情況下5種算法的目標函數收斂情況

可以看出，NSGA-II最差，可能的原因是分配矩陣較為稀疏，減弱了交叉和變異過程，使迭代尋優過程減慢；DCI-QPSO的解優于QPSO；DCI-HQPSOGA和HQPSOGA都可以取得較好的解，優于其他三種算法，且DCI-HQPSOGA的解最優，說明文中多樣性判別方法的有效性。并且在DCI-HQPSOGA中引入文中多樣性判別方法后，在WTA問題中具有較好的尋優能力，有效提高了求解精度。

5 結 語

本文先提出多樣性貢獻度的概念，利用CLARANS和模糊貼近度原則對HQPSOGA中QPSO的粒子進行多樣性判別，形成了一套多樣性維護機制。通過在ZDT1-ZDT4測試函數中對比分析，表明本文方法對算法多樣性保持有一定改進。將改進算法DCI-HQPSOGA應用到SWTA問題，仿真結果表明該算法相比QPSO、DCI-QPSO、NSGA-II和HQPSOGA，能夠提供更有效的WTA方案，為更精確的火力打擊提供了更多可能。本文算法的不足是犧牲了一定的求解效率換取求解精度，所以如何在保證求解精度的同時，提高求解效率將是今后研究的方向。