基于改進(jìn)多目標(biāo)HQPSOGA求解武器目標(biāo)分配問題

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

(大連大學(xué)通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室 遼寧 大連 116622)

0 引 言

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

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

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

1 相關(guān)理論

1.1 多目標(biāo)優(yōu)化問題

MOP由一組目標(biāo)函數(shù)和約束組成，數(shù)學(xué)描述如下：

(1)

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

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

1.2 基于隨機(jī)選擇的聚類算法

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

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

1.3 模糊貼近度原則

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

2 基于多樣性貢獻(xiàn)度的混合量子行為粒子群和可調(diào)節(jié)遺傳算法

2.1 量子行為粒子群算法

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

(2)

2.2 DCI-HQPSOGA及求解步驟

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

圖1 DCI-HQPSOGA流程

2.3 DCI-HQPSOGA具體實(shí)現(xiàn)

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

從簇中隨機(jī)選擇非當(dāng)前點(diǎn)，更新聚類中心，為平衡解的質(zhì)量和求解效率，用參數(shù)δ計(jì)算每個簇中選擇聚類中心的次數(shù)tRand，計(jì)算式表示為：

tRand=δ×cl

(3)

式中：cl表示當(dāng)前簇中粒子的數(shù)量；tRand∈[1,cl]。

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

(4)

式中：第一項(xiàng)和第二項(xiàng)表示粒子到聚類中心的余弦距離和歐氏距離；D即目標(biāo)函數(shù)上粒子的多樣性貢獻(xiàn)度。

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

(5)

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

綜上，粒子多樣性貢獻(xiàn)度表示為：

(6)

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

通過綜合比較多樣性貢獻(xiàn)度小的粒子與引入的隨機(jī)新增粒子來改善個體最優(yōu)解，先計(jì)算多樣性貢獻(xiàn)度的界限值b，計(jì)算式為：

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

(MAX_Iter-iter+1)/MAX_Iter

(7)

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

3 用DCI-HQPSOGA求解SWTA問題

3.1 SWTA問題模型

在經(jīng)典SWTA場景[19]下構(gòu)建SWTA多目標(biāo)優(yōu)化數(shù)學(xué)模型：

式中：xij表示分配給目標(biāo)j的第i種武器的數(shù)量。

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

(8)

式中：目標(biāo)價值Vj是對戰(zhàn)術(shù)、目標(biāo)威脅度等指標(biāo)的綜合考量[20]。

設(shè)武器消耗量取決于武器使用個數(shù)與其對于目標(biāo)的價值，則f2計(jì)算式表示為：

(9)

(10)

綜上，SWTA模型表示為：

(11)

3.2 用DCI-HQPSOGA實(shí)現(xiàn)WTA

實(shí)現(xiàn)步驟參考圖1，初始化參數(shù)包括武器數(shù)weaponNum、目標(biāo)數(shù)Dim、毀傷概率矩陣p、DCI-HQPSOGA初始參數(shù)的設(shè)置。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 DCI-HQPSOGA性能測試

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

(a) ZDT1

(b) ZDT2

(c) ZDT3

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

表1 五種算法在GD指標(biāo)上的比較

表2 五種算法在IGD指標(biāo)上的比較

表3 五種算法在HV指標(biāo)上的比較

表4 五種算法在Spacing指標(biāo)上的比較

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

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

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

4.2 DCI-HQPSOGA在WTA中的應(yīng)用

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

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

iter/MAX_Iter

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

表6 目標(biāo)價值表

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

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

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

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

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

續(xù)表8

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

圖4 δ=0.1情況下5種算法的目標(biāo)函數(shù)收斂情況

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

5 結(jié) 語

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