基于協(xié)同Memetic自適應(yīng)QPSO算法的傳感器-目標分配問題求解

段修生, 徐公國, 單甘霖

(軍械工程學院電子與光學工程系, 河北 石家莊 050003)

?

基于協(xié)同Memetic自適應(yīng)QPSO算法的傳感器-目標分配問題求解

段修生, 徐公國, 單甘霖

(軍械工程學院電子與光學工程系, 河北 石家莊 050003)

對復(fù)雜防空作戰(zhàn)環(huán)境下的傳感器-目標分配(sensor target assignment,STA)問題進行了研究,建立了基于識別、跟蹤、定位多階段綜合作戰(zhàn)效能的分配模型。針對該模型,首先基于粒子群聚集度和進化度判斷,對傳統(tǒng)量子粒子群(quantum particle swarm optimization, QPSO)算法進行了改進,提出了自適應(yīng)QPSO算法。然后,結(jié)合多粒子群協(xié)同和Memetic搜索策略,提出了基于協(xié)同Memetic自適應(yīng)QPSO算法的STA求解方法。同時,為使粒子位置矢量反映分配方案,依據(jù)不同戰(zhàn)場環(huán)境設(shè)計了兩種特殊的粒子編碼方案。最后通過仿真實驗驗證了所提算法的有效性。

傳感器-目標分配; 傳感器管理; 量子粒子群; 自適應(yīng); Memetic算法; 防空系統(tǒng)

0 引 言

現(xiàn)代防空作戰(zhàn)環(huán)境日趨多樣化和復(fù)雜化,呈現(xiàn)出全空域、全天候、多傳感器、多目標的特點,傳感器管理的作用日益突出。尤其是在防空C3I系統(tǒng)中,傳感器-目標分配(sensor target assignment,STA)問題是傳感器管理中的關(guān)鍵問題之一,如何快速地將傳感器資源合理地分配給多個目標以達到最大作戰(zhàn)效能,并滿足戰(zhàn)場的實時性要求,成為現(xiàn)代防空指揮作戰(zhàn)系統(tǒng)中的研究重點。

STA問題屬于軍事運籌學中的經(jīng)典NP-hard完全問題,實質(zhì)是非線性、多約束的整數(shù)規(guī)劃問題,求解復(fù)雜且收斂速度慢。傳統(tǒng)的研究方法有:基于規(guī)劃論、基于協(xié)方差控制、基于信息論、基于博弈論、基于模糊理論等。文獻[1] 將傳感器分配問題描述成一種非線性部分可觀馬爾可夫決策過程模型,并給出充分條件以使最優(yōu)策略具有特殊的閾值結(jié)構(gòu),從而降低了求解計算的復(fù)雜度。文獻[2]則將傳感器資源分配問題描述成二元混合整數(shù)規(guī)劃問題和二元凸規(guī)劃問題,并分別利用線性規(guī)劃法和外部近似法對這兩種規(guī)劃問題進行求解。文獻[3]研究了基于協(xié)方差控制的集中式雷達組網(wǎng)跟蹤融合系統(tǒng)資源管理問題,設(shè)計了一種基于 Riccati 方程的穩(wěn)態(tài)傳感器分配算法。文獻[4]討論了誤差協(xié)方差與傳感器精度指標的關(guān)系,并提出基于容積卡爾曼濾波的雷達與紅外傳感器融合算法。文獻[5]提出了基于Fisher 信息增量最大化的傳感器資源分配算法。文獻[6]引入博弈理論對動態(tài)武器目標分配問題進行了求解。近年來,智能啟發(fā)式搜索算法,如蟻群算法、粒子群算法等,因其魯棒性強、收斂速度快等特點被廣泛應(yīng)用于多傳感器管理問題中。

本文在上述研究的基礎(chǔ)上,立足防空作戰(zhàn)的實際流程,分析了防空作戰(zhàn)各分任務(wù)階段性能對綜合作戰(zhàn)效能的影響,提出了一種新的基于多階段綜合作戰(zhàn)效能的STA分配模型,所提模型更加貼近實際戰(zhàn)場環(huán)境。然后,利用量子粒子群智能優(yōu)化(quantum particle swarm optimization,QPSO)算法[7]進行求解,在粒子群聚集度和進化度實時判斷的基礎(chǔ)上,對傳統(tǒng)QPSO算法進行了改進,提出了自適應(yīng)QPSO(adptive QPSO,AQPSO)算法,并且引入多粒子群協(xié)同搜索和Memetic搜索策略,最終構(gòu)建了協(xié)同Memetic AQPSO (M-AQPSO)尋優(yōu)算法。所提算法有很強的全局搜索能力和穩(wěn)定性,最后將通過仿真實驗驗證了算法的有效性。

1 STA模型的構(gòu)建

1.1 目標函數(shù)

傳統(tǒng)的傳感器目標分配,多以單個目標收益作為客觀分配原則,如探測概率最大、定位精度最優(yōu)[3]、信息增量最大[5]等。而在防空作戰(zhàn)中,單個目標并不能完整刻畫作戰(zhàn)過程,有其局限性。當前,傳感器的任務(wù)趨于多樣化和復(fù)雜化,防空作戰(zhàn)傳感器的任務(wù)就包括搜索、截獲、識別、跟蹤、定位等一系列階段性任務(wù),且不同傳感器在不同階段的性能也具有差異性。本文則以識別、跟蹤、定位3個階段的綜合作戰(zhàn)效能作為分配目標函數(shù)對傳感器目標進行分配。下面給出傳感器目標分配綜合作戰(zhàn)效能的計算方法。

識別性能:傳感器識別目標是從目標回波信號中提取目標的信息特征,確定目標的類型及屬性的過程。目標識別性能的衡量采用傳感器的目標識別正確率來定義,假設(shè)傳感器對某一目標的識別正確率為η,則傳感器對目標的識別性能Reco可定義為

Reco=η

(1)

(2)

式中,ηi為傳感器i對某一目標的識別正確率。

跟蹤性能:目標跟蹤的主要目的是估計目標的狀態(tài)軌跡,故可用濾波誤差協(xié)方差來衡量傳感器的跟蹤性能。設(shè)跟蹤濾波誤差協(xié)方差為P,則定義傳感器對目標的跟蹤性能Trac為

(3)

(4)

式中,Pi為傳感器i的跟蹤濾波誤差協(xié)方差陣。

定位性能:目標定位主要是利用觀測信息和傳感器目標的幾何關(guān)系來推算出目標的空間位置,在精度要求高的情形下,還要考慮時間定位。可用定位精度幾何稀釋因子GDOP來定義傳感器對目標的定位性能:

(5)

式中,σx,σy,σz分別為x,y,z方向的測量精度。同樣,當N個傳感器同時跟蹤同一目標時,采用基于極大似然融合估計算法,融合定位精度幾何稀釋因子GDOP′可由式(6)求得

GDOP′=Fusion(GDOP1,GDOP2,…,GDOPN)=

(6)

式中,σxi,σyi,σzi分別為傳感器i的x,y,z方向的測量精度。在得出各分任務(wù)階段傳感器目標配對性能的基礎(chǔ)上,定義綜合作戰(zhàn)效能Gain為

Gain=c1·Reco+c2·Trac+c3·Loca

(7)

式中,c1+c2+c3=1(c1,c2,c3∈[0,1]),權(quán)重可依據(jù)實時戰(zhàn)場環(huán)境變化進行不同的側(cè)重設(shè)置。

1.2 約束條件

由于STA問題是一個具有約束條件的優(yōu)化問題,本文在建立分配模型時主要考慮以下約束條件。

(1) 單個傳感器可同時處理的目標個數(shù)約束:每個傳感器都有最大跟蹤能力,傳感器所分配的目標個數(shù)不能超過其跟蹤能力。

(2) 單個目標所能分配的傳感器個數(shù)約束:為充分利用傳感器資源,防止過度集中造成冗余浪費,每個目標最多分配2個傳感器。同時又為了防止漏防,在資源充分的條件下,每個目標至少分配1個傳感器。

(3) 多傳感器系統(tǒng)的處理能力負荷約束:系統(tǒng)有其處理能力上限,處理負荷約束即系統(tǒng)可同時處理的最大目標個數(shù)。

(4) 任務(wù)處理時間約束:目標跟蹤對實時性要求比較高,單次分配任務(wù)的處理時間需設(shè)置最大上限,否則等待時間太長會造成目標丟失,故當處理時間太長時,依據(jù)上一次分配結(jié)果處理。

1.3 分配模型的構(gòu)建

假設(shè)某次防空作戰(zhàn)中,探測到來襲目標個數(shù)為n個,為T1,T2,…,Tn;我方有m個傳感器S1,S2,…,Sm,每個傳感器的跟蹤能力分別為C1,C2,…,Cm,系統(tǒng)最大跟蹤能力為C=C1+C2+…+Cm。引入虛擬傳感器的概念,即當2個傳感器同時跟蹤1個目標時,組合傳感器構(gòu)成新的虛擬傳感器,此時理論上的傳感器個數(shù)應(yīng)該是(m2+m)/2個,其作戰(zhàn)效能由第1.1節(jié)中的融合算法求得,配對綜合作戰(zhàn)效能矩陣為Gain[n,(m2+m)/2]:

(8)

式中,Gij為當目標i分配給傳感器j時的總作戰(zhàn)效能。進一步定義分配矩陣R=[rij]n×m來表示分配結(jié)果,當目標i分配給傳感器j時,rij=1;否則,rij=0。依據(jù)約束條件R的每行中1的個數(shù)不大于2,每列中1的個數(shù)不得大于相應(yīng)傳感器的跟蹤能力,總的1的個數(shù)不得大于系統(tǒng)處理能力。

經(jīng)過以上分析,防空作戰(zhàn)中的STA問題可轉(zhuǎn)化為下面的最優(yōu)化模型:

(9)

約束條件為

(10)

式中,Cj傳感器j的跟蹤能力;C為系統(tǒng)總跟蹤能力;Tmax為單次處理時間上限;P(Ti)目標優(yōu)先級函數(shù)。當m≤C時,選取處理的目標為m個;當m>C時,依據(jù)目標優(yōu)先級選取C個目標進行處理。

目標優(yōu)先級反映目標對我防區(qū)的威脅程度,威脅程度越大,目標優(yōu)先級越高;威脅度越小,目標優(yōu)先級越低。目標威脅度的評估依靠所觀測到的目標類型和屬性確定,求解方法有層次分析法、模糊推理、神經(jīng)網(wǎng)絡(luò)等,這里不做具體的闡述。依據(jù)目標優(yōu)先級,可以對威脅度高的目標重點處理,尤其在目標數(shù)目大于系統(tǒng)跟蹤處理能力時,可以依靠目優(yōu)先級進行目標選取。定義目標優(yōu)先級函數(shù)為

P(T)=W

(11)

式中,T為目標;W為目標T的威脅度。目標威脅度越大,目標優(yōu)先級函數(shù)值越大,目標優(yōu)先級則越高。

2 STA問題的求解

在建立了STA分配模型之后,下面討論如何快速求解模型。針對傳統(tǒng)QPSO算法易陷入局部最優(yōu)和收斂速度慢等問題,本文依據(jù)粒子群聚集度和進化度指標,對QPSO算法進行了自適應(yīng)改進。又結(jié)合Memetic和協(xié)同搜索策略,構(gòu)建了一個多粒子群群協(xié)同搜索、全局搜索與局部搜索相結(jié)合的自適應(yīng)QPSO尋優(yōu)算法。

2.1 QPSO算法

針對普通粒子群(particle swarm optimization,PSO)算法全局尋優(yōu)能力不佳的缺陷,Sun Jun等在量子理論的基礎(chǔ)之上,提出了具有量子行為的QPSO算法。該模型賦予粒子量子行為,即粒子的位置由波函數(shù)來描述,粒子的狀態(tài)變化則由薛定諤方程決定。QPSO假設(shè)每個粒子在一個局部吸引子為中心的δ勢阱中移動, 而粒子在各自δ勢阱中的具體位置則由一個概率密度函數(shù)P(x)決定。實驗表明,當P(x)為二次分布時算法具有最佳性能, 可以通過薛定諤方程求得粒子的概率分布函數(shù)。進一步通過蒙特卡羅隨機模擬的方法得到粒子的位置方程為

x(t)=Q±L/2ln(1/μ)

(12)

式中,μ是在[0,1]上服從均勻分布的隨機數(shù);L,Q則由下式計算而來。

L(t+1)=2β(t)|mbest(t)-x(t)|

(13)

Q(t)=φpib(t)+(1-φ)pgb(t)

(14)

式中,β為收縮擴張因子,通常情況下隨著迭代次數(shù)線性地從1遞減到0.5,計算公式為:β=1-0.5(iter/iterm),式中iter是當前迭代次數(shù),iterm是最大迭代次數(shù)。mbest是粒子群pbest的中間位置,即平均值,計算公式為

(15)

式中，φ是在[0,1]上服從均勻分布的隨機數(shù);pib(t)表示第t次迭代時第i個粒子的當前最優(yōu)位置;pgb(t)表示第t次迭代時所有粒子的全局最優(yōu)位置。進而粒子的位置更新方程為

x(t)=φpib(t)+(1-φ)pgb(t)+

rand(t)·2β(t)|mbest(t)-x(t)|ln(1/μ)

(16)

式中,rand(t)的取值如下所示:

(17)

式中,λ是隨機產(chǎn)生的隨機數(shù),且在[0,1]上服從均勻分布。

與普通PSO算法相比,QPSO算法主要有兩個方面的優(yōu)勢。

(1) 因為引入量子特性,粒子以概率的方式出現(xiàn)在某個位置上,沒有了固定的運動軌跡和限制區(qū)域,這就使得粒子可以在整個解空間中進行搜索,極大的提高了粒子的全局尋優(yōu)能力。

(2) QPSO算法不再考慮粒子的運動速度,只考慮粒子的位置,控制參數(shù)只有一個β,大幅減少了算法的復(fù)雜度,使得算法實現(xiàn)更加容易。

2.2 QPSO算法

粒子群算法表現(xiàn)出的強烈趨同性會使種群多樣性很快喪失,容易出現(xiàn)早熟收斂、全局尋優(yōu)能力較差等問題,許多學者因此做了大量的改進算法研究。文獻[8]從收斂速度、跳出局部極值、探索、開發(fā)幾個不同角度融合了4種具有不同優(yōu)勢的變異策略,提出一種基于混合策略自適應(yīng)學習的粒子群優(yōu)化算法。此外,自適應(yīng)學習[9-10]近年來成為不少學者研究的熱點問題。例如文獻[11]提出了一種自適應(yīng)的學習策略,根據(jù)種群中粒子的運行狀況動態(tài)地為每個粒子指派學習樣本,以增強粒子間的信息交流。本文也從自適應(yīng)學習策略出發(fā),設(shè)計提出了參數(shù)可自適應(yīng)調(diào)整的AQPSO尋優(yōu)算法。

已知,當擴張收縮因子β較小時,粒子群處于收縮狀態(tài),粒子群向δ勢阱中心聚集,多樣性減少,極易陷入局部最優(yōu)陷阱中;當β較大時,粒子群處于擴張狀態(tài),粒子群向δ勢阱外運動,粒子群的多樣性增加,但收斂速度會放慢。在標準QPSO算法中β參數(shù)隨迭代次數(shù)增加逐漸減小,粒子極易陷入局部最優(yōu)陷阱。基于擴張收縮因子β的良好特性,在AQPSO算法中,當粒子群的多樣性下降或者長時間停止進化時,算法進行自適應(yīng)調(diào)整,重置β為擴張狀態(tài),增加種群的多樣性,從而改善QPSO算法的全局搜索性能,加速搜索全局最優(yōu)值。

為準確衡量粒子群的多樣性和進化狀態(tài),提出兩個量化指標:粒子群聚集度、粒子群進化度。粒子聚集度描述粒子狀態(tài)的多樣性。粒子進化度描述粒子代際之間的進化程度。當粒子群多樣性很小,且在連續(xù)多次迭代時間內(nèi)粒子群的適應(yīng)值沒有進化,基本可以確定粒子群已經(jīng)陷入局部最優(yōu)陷阱。

(1) 粒子群聚集度:統(tǒng)計方差是衡量一組數(shù)據(jù)離散程度較為準確的度量,但在優(yōu)化搜索時,粒子群的規(guī)模和維數(shù)都比較大,計算方差勢必會大大延長搜索時間。為簡化運算,選取當前全局平均適應(yīng)值MFit(x(t))與當前全局最優(yōu)值BestFit(x(t))和當前全局最差值BadFit(x(t))的距離和來反映粒子群聚集度,聚集度的具體計算方法見式(18),其中距離取歐氏距離。

J(t)=1/[(MFit(x(t))-BestFit(x(t)))2+

(MFit(x(t))-BadFit(x(t)))2]1/2

(18)

易得J∈[0,1],設(shè)置一個闕值λj,當J≥λj,粒子群視為太過聚集,其中λj的選取與粒子群的維數(shù)和取值范圍有關(guān)。

(2) 粒子群進化度:當前全局最優(yōu)值BestFit(x(t))反映了當前代際整體粒子群的適應(yīng)性,故代際之間的進化度可以用當前全局最優(yōu)值的變化率表示。但一次迭代變化并不能準確反映粒子群進化程度,多次迭代的變化情況能比較準確反映粒子群的整體進化程度。因此選取一段時間上,當前全局最優(yōu)值的變化情況的累加值來定義粒子群進化度,具體計算方法見式(19)。

(19)

式中,Δt為觀測時間段(離散值),一般選取8～12代的變化情況較為合適。同樣設(shè)置一個闕值Tk,當k≤λk,粒子群視為進化緩慢或停止進化,其中λk的選取與觀測時間段有關(guān)。

在對粒子群聚集度和進化度狀態(tài)做出準確判斷之后,就可以對擴張收縮因子β做出自適應(yīng)的調(diào)整。當粒子群陷入局部最優(yōu)或者停止進化時,及時調(diào)整β處于較大值,增加粒子多樣性,并使粒子盡快擺脫局部最優(yōu)陷阱;當粒子群脫離局部最優(yōu)后,調(diào)整β處于較小值,并逐步減小,保證算法收斂。擴張收縮因子β具體擴張狀態(tài)值的選取,將在仿真實驗中進行說明。

2.3 Memetic算法

Memetic算法是文獻[12]提出的一種基于種群的全局搜索和基于個體的局部搜索相結(jié)合的智能尋優(yōu)算法,通過引入個體的局部搜索來增加種群的多樣性,提高全局搜索能力。本文通過引入Memetic算法理念,進一步增強算法的全局搜索能力,提出了M-AQPSO尋優(yōu)算法。M-AQPSO算法采用“QPSO算法全局搜索+鄰域局部搜索”的策略,局部搜索在每次全局搜索之后,對全局最優(yōu)粒子再進行鄰域局部搜索。此外,當解維數(shù)較大時,可控制鄰域點的選擇。由于搜索空間不大,對運算耗時影響很小,算法性能卻有較大提高。

圖1 鄰域搜索示例Fig.1 Example of neighborhood searching

通過上述改進,算法的全局搜索性能有了很大的提高。M-AQPSO算法的具體流程如圖2所示。

圖2 M-AQPSO算法流程圖Fig.2 Flow chart of the M-AQPSO algorithm

2.4 多粒子群協(xié)同搜索

目前提出的很多改進PSO算法,大都著眼于對PSO算法的參數(shù)選擇或者某個參數(shù)的動態(tài)調(diào)整策略上,全局搜索能力性能的改進有限。上文中的自適應(yīng)改進和Memetic搜索策略的引進就是如此,仍有其局限性,需進一步改進。文獻[14]則提出了一種多粒子群協(xié)同優(yōu)化算法,能夠有效避免早熟收斂。核心思想是利用n(n≥2)個粒子群協(xié)同進化,前(n-1)個粒子群相互獨立搜索以擴大搜索范圍,而第n個粒子群追逐當前所有粒子群的全局最優(yōu)解以加快搜索速度。該算法從一個全新的角度對PSO算法進行改進,算法簡單明了且效果明顯。本文將此協(xié)同策略引入分配算法中,最終形成了多粒子種群協(xié)同M-AQPSO尋優(yōu)算法。

協(xié)同M-AQPSO為2層結(jié)構(gòu),底層粒子群數(shù)目為3個,搜索算法分別為擴張M-QPSO、M-AQPSO和M-AQPSO,其中,擴張M-QPSO的β值長期處于擴張狀態(tài),目的是增加粒子的多樣性;上層為1個粒子群,搜索算法采用M-AQPSO算法。底層各種群之間相互獨立搜索,上層種群則追逐所有種群的全局最優(yōu)解,以保證全局收斂,整體搜索策略原理如圖3所示。

圖3 協(xié)同搜索策略示意圖Fig.3 The illustration of cooperation searching strategy

3 算法實現(xiàn)

利用粒子群算法求解STA問題時,首先要對解的位置矢量進行編碼,然后在解空間里尋找最優(yōu)解。

3.1 粒子編碼

粒子編碼的策略要使每個粒子唯一對應(yīng)一種分配方案,同時還要盡可能的滿足分配模型中的約束條件。此外,編碼構(gòu)成的解空間要盡可能小,以減少搜索時間?；谝陨峡紤],本文設(shè)計了兩種編碼方案。

方案 1 以傳感器為中心建立粒子位置矢量X,粒子與傳感器的位置對應(yīng)關(guān)系如圖4所示。S1,S2,…,Sm為m個傳感器,C1,C2,…,Cm分別為傳感器的跟蹤能力,則粒子位置矢量X的長度為C=C1+C2+…+Cm。若目標個數(shù)為n,則X的每一維的取值限定在[0,n]之間的整數(shù)。Xi=0表示傳感器未分配給任何目標,Xi=j表示相應(yīng)傳感器分配給了目標j。同時可計算得出,此時的搜索空間為C×(n+1)。

圖4 編碼方案1Fig.4 First particle coding method

方案 2 以目標為中心建立粒子位置矢量X,粒子與目標的位置對應(yīng)關(guān)系如圖5所示。T1,T2,…,Tn為個目標,目標最多分配的傳感器個數(shù)為2,則粒子位置矢量X的長度為2n。若傳感器個數(shù)為m,則X的每一維的取值限定在[0m]之間的整數(shù)。Xi=0表示未給目標分配傳感器,Xi=j表示給相應(yīng)目標分配了傳感器j。同樣可計算得出,此時的搜索空間為2n×(m+1)。

圖5 編碼方案2Fig.5 Second particle coding method

兩種編碼方式各有優(yōu)點,方案1可以保證每個傳感器分配的目標數(shù)不大于其最大跟蹤能力,方案2則可以保證每個目標分配的傳感器不大于2個。由于方案1的搜索空間為C×(n+1),方案2的搜索空間為2n×(m+1),為了減少搜索空間,加快收斂速度,當C×(n+1)<2n×(m+1)時可選擇方案1;當C×(n+1)>2n×(m+1)選擇方案2。

由于位置更新公式是矢量運算,整數(shù)值粒子通過迭代會產(chǎn)生連續(xù)值,因此需要對連續(xù)值粒子進行離散化,離散化采用分段賦值的辦法,具體見文獻[14],這里不再贅述。

3.2 算法的具體流程

多種群協(xié)同M-AQPSO算法流程步驟如下:

步驟 1 參數(shù)初始化設(shè)置傳感器個數(shù)m、目標個數(shù)n、跟蹤能力C、運行時間上限Tmax、聚集度闕值λj、進化度闕值λk、最大迭代次數(shù)iterm、粒子數(shù)目Psize、粒子維度Pdim,分別設(shè)置各粒子種群的擴張收縮因子β,并求得感器-目標分配效能矩陣為Gain;

步驟 2 初始化粒子群,所有粒子的位置矢量隨機產(chǎn)生,粒子種群為4個;

步驟 3 對所有粒子進行離散化操作,并進行合理性檢測,即是否滿足相應(yīng)約束條件;

步驟 4 計算所有粒子的適應(yīng)值,并更新各種群的全局最優(yōu)值,其中種群1～3的全局最優(yōu)為各種群內(nèi)的當前最優(yōu)位置,種群4的全局最優(yōu)為種群1～4內(nèi)的所有粒子的最優(yōu)位置;

步驟 5 判斷算法是否達到規(guī)定的最大迭代次數(shù),如果滿足轉(zhuǎn)入步驟10,否則轉(zhuǎn)入步驟6;

步驟 6 依據(jù)式(18)和式(19)判斷種群2～4的粒子是否陷入局部最優(yōu),若是則調(diào)整收縮擴張因子β的值,否則轉(zhuǎn)入步驟7;

步驟 7 依據(jù)位置更新式(16)對所有粒子的位置進行更新,進行離散化操作和合理性檢測;

步驟 8 同步驟4對全局最優(yōu)位置進行更新;

步驟 9 對所有種群的全局最優(yōu)位置進行鄰域搜索,轉(zhuǎn)入步驟5;

步驟 10 輸出種群4的全局最優(yōu)位置Gbest,算法結(jié)束。

此外還有一個并行運算的時間監(jiān)督程序,當單次求解時間達到時間上限Timemax,輸出上次分配方案。

4 場景仿真及算法驗證

4.1 擴張收縮因子β的選取

擴張收縮因子β是QPSO算法中的唯一的控制參數(shù),其值直接影響著粒子群的尋優(yōu)效果。為探討β參數(shù)對粒子群尋優(yōu)效果的影響,選取4個典型的尋優(yōu)測試函數(shù)進行實驗。 4個函數(shù)均為多峰函數(shù),其中F1和F2的全局最優(yōu)值周圍有無數(shù)個局部最優(yōu)值,收斂速度比較慢,F3和F4的全局最優(yōu)值位于搜索空間的中心,搜索空間對角方向上分別有4個局部最優(yōu)值,且與全局最優(yōu)值比較接近,極易陷入局部最優(yōu)陷阱中。實驗中各函數(shù)參數(shù)的選擇如表1所示。

表1 實驗參數(shù)設(shè)置

實驗結(jié)果均表現(xiàn)出如圖6所示的變化特性。即當針對同一函數(shù),且在一定的精度要求時,隨著β的增加, QPSO的尋優(yōu)成功率會先上升,直至由于β太大,粒子群無法收斂,尋優(yōu)成功率又呈現(xiàn)下降的趨勢。只是在優(yōu)化對象不同時,變化曲線略有差異。

圖6 Girewank中β特性曲線Fig.6 Characteristic curves of β in the Girewank

同樣,針對本文中的STA尋優(yōu)問題,重復(fù)上述實驗,實驗結(jié)果如圖7所示。由圖可得在[0,1.2]區(qū)間內(nèi),隨著β的增加,STA尋優(yōu)成功率也呈現(xiàn)上升的趨勢。而在[1.2,2]區(qū)間內(nèi)基本保持不變。因此,針對STA尋優(yōu)問題,β擴張狀態(tài)值可設(shè)置為1.2,該狀態(tài)值既能保證算法收斂,還能保證算法有較強的全局尋優(yōu)能力。

綜上實驗,定義尋優(yōu)成功率上升區(qū)間段為精度富余區(qū)間,在此區(qū)間內(nèi),增加β的值非但不會降低尋優(yōu)精度,反而尋優(yōu)的成功率會增加。因此在精度富余區(qū)間內(nèi),可以通過提高β值來提高算法的全局尋優(yōu)能力。

圖7 本文STA問題中β特性曲線Fig.7 Characteristic curves of β in the STA problem

4.2 場景仿真

假設(shè)某次防空作戰(zhàn)中,探測到來襲目標的個數(shù)為6個,記為T1,T2,T3,T4,T5,T6(n=6),同時由防空系統(tǒng)融合中心求得目標的優(yōu)先級為P=[1/2,1,1/3,1/4,1/6,1/5]。我防空系統(tǒng)中有6部傳感器,記為S1,S2,S3,S4,S5,S6(m=6),其中,S5,S6的跟蹤能力為3,而S1,S2,S3,S4的跟蹤能力僅為1。傳感器與目標的配對綜合作戰(zhàn)效能Gain的轉(zhuǎn)置如表2所示。并計算得傳感器總跟蹤能力C=10,每個目標最多分配2個傳感器,由于C×n=60<2n×m=72,故選擇編碼方案一進行粒子編碼,粒子維度為10。

采用本文構(gòu)建的協(xié)同M-AQPSO算法對仿真場景進行求解,同時還采用了協(xié)同Memetic PSO(M-PSO)算法和協(xié)同Memetic QPSO(M-QPSO)算法一并進行求解,并做算法對比。根據(jù)粒子群協(xié)同策略,選取4個粒子種群,種群1～4分別采用擴張M-QPSO、M-AQPSO、M-AQPSO和M-AQPSO。其中擴張MQPSO的擴張收縮因子β始終處于較大值1.5,作用是保證粒子的多樣性,增強算法的全局尋優(yōu)能力。

表2 傳感器目標配對綜合作戰(zhàn)效能值

每個粒子種群里,粒子數(shù)目均為100個,最大迭代次數(shù)為200。 協(xié)同M-AQPSO算法中,粒子群聚集闕值λj=0.8,粒子多樣性觀測代數(shù)為10代,粒子進化度闕值λk=0.9×10=9,當判斷粒子群陷入局部最優(yōu)時,β調(diào)整為1.2,最大單次求解時間為0.5 s。對于仿真場景,程序最終的尋得的最優(yōu)分配方案如圖8所示,最優(yōu)配對綜合作戰(zhàn)效能為14.846 7,單次分配消耗時間為0.23 s,最終分配方案滿足每個目標分配傳感器不超過2個、傳感器分配的目標不超過本身跟蹤能力和系統(tǒng)最大跟蹤能力的約束條件,驗證了分配方案的可行性。需要補充說明的是,在實際作戰(zhàn)環(huán)境中,由于諸多條件的限制,如布站位置等,傳感器組合數(shù)目應(yīng)該小于(m2+m)/2,求解時間則會更快。

圖8 最優(yōu)分配方案Fig.8 Optimal allocation scheme

4.3 算法性能對比

為證明改進算法的有效性,在尋優(yōu)實驗的過程中與其他算法做了對比。選取某次尋優(yōu)過程中前100迭代步數(shù)內(nèi)全局最優(yōu)值變化情況進行對比,如圖9所示。

圖9 算法收斂曲線對比圖Fig.9 Comparison of convergence curves of the three algorithms

可見協(xié)同M-QPSO算法的全局尋優(yōu)能力要明顯優(yōu)于協(xié)同M-PSO算法,而改進的協(xié)同M-AQPSO算法的性能則優(yōu)于協(xié)同M-QPSO算法。此外,協(xié)同M-AQPSO算法曲線圖梯度上升的特性顯示其能及時跳出局部最優(yōu)陷阱,有更好的全局尋優(yōu)能力。

為進一步分析改進算法的穩(wěn)定性能,在上述實驗參數(shù)的基礎(chǔ)上,重復(fù)運行200次,所得實驗結(jié)果如表3所示,協(xié)同M-AQPSO算法的尋優(yōu)平均值和尋得最優(yōu)值成功率要好于協(xié)同M-PSO和協(xié)同M-QPSO算法,但是尋得最優(yōu)值所消耗的平均步數(shù)要少于協(xié)同M-PSO和協(xié)同M-QPSO算法,可見協(xié)同M-AQPSO算法的穩(wěn)定性強。3種算法200次運行結(jié)果的變化情況分別如圖10～圖12所示,顯而易見如圖12,協(xié)同M-AQPSO算法的尋優(yōu)結(jié)果波動性小,更具穩(wěn)定性,且尋優(yōu)效果好。

表3 算法性能比較

圖10 協(xié)同 M-PSO算法尋優(yōu)結(jié)果變化圖Fig.10 Optimization results of the cooperation M-PSO algorithm

圖11 協(xié)同 M-QPSO算法尋優(yōu)結(jié)果變化圖Fig.11 Optimization results of the cooperation M-QPSO algorithm

圖12 協(xié)同 M-AQPSO算法尋優(yōu)結(jié)果變化圖Fig.12 Optimization results of the cooperation M-AQPSO algorithm

4 結(jié) 論

本文對防空作戰(zhàn)中的傳感器-目標分配問題進行了系統(tǒng)的研究分析,區(qū)別于傳統(tǒng)的單一目標參數(shù)的模型構(gòu)建方法,提出了基于多階段綜合作戰(zhàn)效能的傳感器目標分配模型,新模型更加符合戰(zhàn)場環(huán)境,有很強的實用性。此外,本文對基于QPSO的STA問題求解算法進行了重點研究,提出了基于聚集度與進化度判斷的AQPSO算法,AQPSO算法能夠有效避免陷入局部最優(yōu)陷阱,有很強的全局尋優(yōu)能力,其在相關(guān)優(yōu)化求解領(lǐng)域也會有很大應(yīng)用價值。未來的研究的重點應(yīng)是在分配模型參數(shù)的選取和約束條件的設(shè)置上,使其更加貼近實際戰(zhàn)場環(huán)境,滿足實際作戰(zhàn)需求。

[1] Krishnamurthy V, Djonin D V. Structured threshold policies for dynamic sensor scheduling-a partially observed Markov decision process approach[J].IEEETrans.onSignalProcessing, 2007, 55(10): 4938-4957.

[2] Chhetri A S, Morrell D, Papandreou-Suppappola A. Sensor resource allocation for tracking using outer approximation[J].IEEESignalProcessingLetters, 2007, 14(3): 213-216.

[3] Zhou W H, Hu W D, Yu W X. An adaptive sensor allocation algorithm with covariance control[J].SignalProcessing, 2005, 21 (1):57-62.(周文輝, 胡衛(wèi)東, 郁文賢. 自適應(yīng)協(xié)方差控制的傳感器分配算法[J]. 信號處理, 2005, 21 (1):57-62.)

[4] Hu Z T, Cao Z W, Li S, et al. Heterogeneous multi-sensor fusion algorithm based on cubature Kalman filter[J].JournalofOptoelectronics.Laser,2014,25(4):697-703.(胡振濤,曹志偉, 李松, 等. 基于容積卡爾曼濾波的異質(zhì)多傳感器融合算法[J]. 光電子·激光,2014,25(4):697-703. )

[5] Fowler M L, Chen M, Binghamton S. Fisher information based data compression for estimation using two sensors[J].IEEETrans.onAerospaceandElectronicSystems, 2005, 41(3):1131-1137.

[6] Ma F, Cao Z Y, Liu H. Construction and search of strategy space of target assignment based on game theory[J].SystemsEngineeringandElectronics,2010,32(9):1941-1945.(馬飛, 曹澤陽, 劉暉. 基于博弈論的目標分配策略空間構(gòu)建與搜索[J]. 系統(tǒng)工程與電子技術(shù), 2010,32(9):1941-1945.)

[7] Sun J. A global search strategy of quantum-behaved particle swarm optimization[C]∥Proc.oftheIEEEConferenceonCyberneticsandIntelligentSystems, 2004: 111-116.

[8] Wu D Q, Zheng J G. Improved parallel particle swarm optimization algorithm with hybrid strategy and self-adaptive learning[J].ControlandDecision, 2013,28(7): 1087-1093.(伍大清, 鄭建國. 基于混合策略自適應(yīng)學習的并行粒子群優(yōu)化算法[J]. 控制與決策, 2013,28(7):1087-1093.)

[9] Li C H, Yang S X. An adaptive learning particle swarm optimizer for function optimization[C]∥Proc.oftheIEEECongressonEvolutionaryComputation, 2009: 381-388.

[10] Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEETrans.onEvolutionaryComputation, 2009, 13(2): 398-417.

[11] Xu G. An adaptive parameter tuning of particle swarm optimization algorithm[J].AppliedMathematicsandComputation, 2013, 219(9): 4560-4569.

[12] Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: memetic algorithms[R]. Technical Report Caltech Concurrent Computation Program, 1989:79-158.

[13] Li A G. Particle swarms cooperative optimizer[J].JournalofFudanUniversity(NaturalScience), 2004,43(5): 923-925.(李愛國. 多粒子群協(xié)同優(yōu)化算法[J]. 復(fù)旦學報(自然科學版), 2004,43(5):923-925.)

[14] Wang Y C, Shan G L, Tong J. Solving sensor-target assignment problem based on cooperative memetic PSO algorithm[J].SystemsEngineeringandElectronics, 2013,35(5):1000-1007. (王一川, 單甘霖, 童俊. 基于協(xié)同memetic PSO算法的傳感器-目標分配問題求解[J]. 系統(tǒng)工程與電子技術(shù), 2013,35(5):1000-1007.)

Solution to sensor-target assignment problem based on cooperative memetic adaptive QPSO algorithm

DUAN Xiu-sheng, XU Gong-guo, SHAN Gan-lin

(DepartmentofElectronicandOpticalEngineering,OrdnanceEngineeringCollege,Shijiazhuang050003,China)

Aiming at the sensor-target assignment (STA) problem under the complex aerial defense combat environment, a new STA model is proposed with the total combat effectiveness of the identification, tracking and positioning stages. And then, the quantum particle swarm optimization (QPSO) algorithm is improved based on the judgment of particles aggregation and evolution, which is called the self-adaptive QPSO algorithm. Next, combined with the cooperation of multi-particles and memetic searching strategy, the cooperative memetic self-adaptive QPSO algorithm is proposed. At the same time, in order to reflect the sensor combination in particle position vector, two special particle coding methods are designed for different combat environments. Finally, the experiments show that the improved algorithm is effective.

sensor-target assignment; sensor management; quantum particle swarm optimization; adaptive; Memetic algorithm; aerial defense system

2016-01-25;

2016-07-05;網(wǎng)絡(luò)優(yōu)先出版日期:2106-09-30。

軍內(nèi)科研基金重點資助項目(ZS2015070132A12009)資助課題

V 243

A

10.3969/j.issn.1001-506X.2016.12.14

段修生(1970-),男,教授,博士,主要研究方向為電子裝備故障診斷、傳感器管理、信息融合。

E-mail: sjzdxsh@163.com

徐公國(1990-),男,碩士研究生,主要研究方向為傳感器管理、信息融合、防空武器系統(tǒng)仿真與應(yīng)用。

E-mail: xugguo@yeah.net

單甘霖(1962-),男,教授,博士,主要研究方向為信息融合理論與應(yīng)用、防空武器系統(tǒng)仿真與應(yīng)用、電子系統(tǒng)故障診斷。

E-mail: shangganlin@163.com

網(wǎng)絡(luò)優(yōu)先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20160930.1141.004.html