基于混合編碼遺傳算法的最優跟蹤門

趙 菡, 張 琤, 林家駿

(華東理工大學信息科學與工程學院,上海 200237)

基于混合編碼遺傳算法的最優跟蹤門

趙 菡, 張 琤, 林家駿

(華東理工大學信息科學與工程學院,上海 200237)

跟蹤算法優化可以提高跟蹤質量,選擇恰當的跟蹤門是優化跟蹤算法的關鍵措施之一。本文提出了一種基于混合編碼的遺傳算法,用于雜波環境下目標跟蹤過程中跟蹤門參數的離線優化。該算法將二進制編碼與浮點數編碼結合,對跟蹤門的形狀和大小進行混合編碼,選擇跟蹤精度性能指標構造遺傳算法的適應度函數,以此將跟蹤算法的優化問題轉化為遺傳算法尋優,在不同雜波環境下優化跟蹤門參數設置。

目標跟蹤; 跟蹤門; 遺傳算法; 混合編碼

跟蹤門的形成是多機動目標跟蹤過程中首當其沖的問題,選擇恰當的跟蹤門能減少數據錯誤關聯的次數,提高目標跟蹤精度[1]。但目前聚焦跟蹤門的研究并不多見,在為數不多的研究中,有學者提出了跟蹤門的自適應設計方法[2-3];有研究通過計算性能評價函數的最優值以逆向推算跟蹤門的尺寸[4];還有文獻[5]提出采用數論法,根據測量誤差和狀態估計誤差設計跟蹤門。這些研究基本集中在如何設定、調整跟蹤門的大小,忽略了跟蹤門形狀對于跟蹤質量的影響。

選擇恰當的跟蹤門可理解為是對跟蹤門算法的優化,因此可當作目標跟蹤算法管理的一個部分。而算法管理的實質是一種優化過程,從理論上說現有的優化算法均可考慮用于算法管理[6]。算法管理可以分為3個層次:算法的參數設置、單點步驟上的算法選擇、多個步驟上的算法組合。本文借助遺傳算法,通過將跟蹤門形狀和大小進行混合編碼,實現對跟蹤門的形狀和大小整體優化。同時選擇細粒度性能指標構造適應度函數,該指標能較靈敏地體現出參數變化對于跟蹤性能的影響,實現了算法參數層面的優化。

1 航跡跟蹤算法與跟蹤門

1.1 狀態估計與數據關聯

(1)

觀測向量的一步預測為

(2)

卡爾曼濾波增益矩陣為

(3)

對應的新息協方差為

(4)

則第i個候選回波的目標狀態估計為

(5)

假設跟蹤門總共選中了mk個候選回波,計算每個候選回波來源于真實目標的互聯概率βi(k),然后對所有候選回波加權求和得到狀態更新方程:

(6)

1.2 跟蹤門理論

圖1 橢圓門示意圖Fig.1 Elliptic gate schematic diagram

2 基于遺傳算法的波門尋優實現

2.1 混合編碼實現

跟蹤門的形狀和門限常數分屬不同的數據類型,要兼顧遺傳算法運算的精度和速度,考慮對上述兩個參數采用混合編碼。波門形狀采用二進制編碼,門限常數采用浮點數編碼[10]。個體混合編碼后的基因串包含兩類參量,即G=[GS,GL],如圖2所示。其中GS為跟蹤門形狀的二進制編碼,GL為門限常數的浮點數編碼。

圖2 混合編碼基因串Fig.2 Gene string by hybrid coding

2.2 算法描述

遺傳算法的尋優建立在目標跟蹤這一動態系統上,尋優過程如圖3所示。將初始種群中個體對應的跟蹤門參數G作為初始化設定輸入系統,根據輸出的跟蹤航跡與真實航跡的誤差,標定個體適應值。經遺傳操作后產生的新個體,在保持其余參數不變的情況下,作為參數設定輸入系統,進行新一輪的適應值計算和種群更新,系統的停止判據為達到系統迭代條件或者滿足一致性條件。

由此可見,混合編碼遺傳算法與目標跟蹤系統形成了閉環尋優系統。遺傳算法對跟蹤過程中的一個環節進行優化,其優化目標和整個跟蹤系統的優化目標一致。用于指導遺傳操作的適應值并非經數學運算得到的代數值,而是在目標跟蹤動力學系統生成跟蹤誤差的基礎上得到。這種思路有效地將多目標優化問題轉化為單目標優化,為今后進一步優化跟蹤系統中的其他參數和算法模塊提供了參考。

圖3 基于混合編碼遺傳算法的跟蹤門尋優流程圖Fig.3 Flow chart of tracking gate optimization based on hybrid coding genetic algorithm

2.3 Hellinger距離與適應值計算

常用的航跡誤差指標有:位置均方根誤差(PRMSE)、馬氏距離、Hellinger距離等。其中,Hellinger距離考慮了協方差的影響,解決了PRMSE在狀態估計相同、不確定度不同的情況下難以區分的問題,具有較高的精確度和敏感度,選擇其作為跟蹤誤差的評估指標[11]。

若兩個概率分布f=N(x,Σx)、g=N(y,Σy)均服從高斯分布,其Hellinger距離有如下的形式:

(7)

在目標跟蹤系統中,可以將(x,Σx)看成真實的狀態向量分布,將(y,Σy)看成估計的狀態向量分布,對于真實的狀態向量,其不確定度可以作為一種基準應該具備最優的特性,選用克拉美羅下界(Cramer-Rao)[12]。若用Hellinger距離dH|k(f,g)表示k時刻真實航跡和估計航跡之間的距離,可構造如下的適應度函數:

(8)

用BL與BU分別表示預設的門限常數上界和下屆,則跟蹤門優化問題可轉化為

G=argGmaxffitness(G)

(9)

s.t.G=[GS,GL]

GS∈{0,1}

BL≤GL≤BU

GL,BL,BU∈R

2.4 遺傳操作

遺傳算法中需要通過選擇、復制等來保證最優個體不被交叉、變異等遺傳運算破壞。本文采用最優保存策略進化模型,先計算種群中每個個體的適應度比例,通過輪盤賭的方式,使擁有更大適應度比例的個體有更大的概率遺傳到下一代的種群[13]。

針對混合編碼方式,交叉操作分為兩種:代表跟蹤門形狀的的二進制編碼采用單點交叉,代表門限常數的浮點數編碼采用非均勻算術交叉,變異操作也相應地分為單點變異和非均勻變異兩種。

3 仿真研究

3.1 參數設置

仿真劇情是不同雜波環境下高機動的單目標跟蹤,目標的初始狀態為[4.92 km,-79.4 m/s,0,0;0.891 km,94.6 m/s,0,0],種群規模為20,交叉概率pcrossover=0.6,變異概率pmutate=0.01。跟蹤系統的采樣為114個點,采樣間隔為1 s,仿真次數為50。設定目標的檢測概率PD=0.98,虛假量測在以正確量測為中心的正方形區域內隨機均勻產生,虛假量測總數nc=λAv,其中λ是雜波密度,Av為區域的面積。本文分別給出了λ=2和λ=20,即稀疏雜波和密集雜波兩種劇情。

3.2 實驗結果與分析

稀疏雜波環境下跟蹤門參數收斂于014.217,根據混合編碼規則可知,01代表跟蹤門形狀的二進制編碼,對應的為橢圓門;4.217代表跟蹤門門限常數的浮點數編碼,表示尋優結果是門限常數4.217的橢圓門。在這樣的參數設定下,得到的Hellinger距離為0.173 5。

密集雜波環境下跟蹤門參數收斂于016.145,同理可知尋優結果是選擇門限常數6.145的橢圓門,相應的Hellinger距離為0.202 4。保持目標檢測概率不變,雜波密度增大要求跟蹤門相應增大,實驗結果與此結論相符。

限定跟蹤門的形狀,依次用遺傳算法僅對門限常數尋優,可得到不同形狀跟蹤門所對應的最小跟蹤誤差,實驗結果如表1所示。由表1可見,在兩種雜波環境下,采用混合編碼遺傳算法尋優結果的系統,其跟蹤誤差最小,系統跟蹤精度最高。

進一步對比橢圓門和矩形門的實驗結果,相同門限常數時兩種跟蹤門得到的誤差雖然相差不大,但矩形門對應的面積遠遠大于橢圓門,在檢測概率和雜波密度已定的前提下,跟蹤門面積的增加必然導致計算量增大。

表1 跟蹤門參數及跟蹤誤差統計表

3.3 跟蹤門優化結果適應范圍

實際目標跟蹤過程中,受到的干擾不會是一成不變的。為測試本文提出的優化算法對于干擾變化具備一定的容忍度,將優化結果運用到不同雜波環境中。對比跟蹤航跡與真實航跡,在一定的干擾變化范圍內,跟蹤系統仍能得到較理想的跟蹤效果。如圖4所示,將雜波密度為20環境下的尋優結果,運用在雜波密度為30的環境中,跟蹤航跡與真實航跡吻合度較高。但由圖5可見,當雜波密度繼續增加為50時,跟蹤航跡較真實航跡出現了較大偏差,尤其在目標拐彎等較大機動處。

圖4 雜波密度30時跟蹤效果圖Fig.4 Tracking with clutter density of 30

圖5 雜波密度50時跟蹤效果圖Fig.5 Tracking with clutter density of 50

4 結束語

針對雜波環境下的高機動目標跟蹤,本文采用二進制和浮點數混合編碼,將不同類型的跟蹤門參數作為遺傳算法優化對象,通過離線仿真得到其最優解。驗證了雜波噪聲與該環境下最優跟蹤門之間存在一定關系,對于雜波環境下目標跟蹤系統精確性的提高有著積極意義。

本文僅對跟蹤門的兩個參數進行尋優,影響跟蹤性能的因素還有很多,細粒度來說有機動頻率、量測噪聲、過程噪聲等,粗粒度來說有數據關聯算法、機動模型、濾波算法等,更多參量的尋優需要進一步的探討。另外,本文中的尋優結果是離線得到的,實驗對象為單機動目標跟蹤,多目標跟蹤當中的跟蹤門選取問題往往更加復雜,如何做到實時在線優化跟蹤門也是需要研究的問題。

[1] 周宏仁,敬忠良,王培德.機動目標跟蹤[M].北京:國防工業出版社,1991:200-217.

[2] 董國,岳三創.航跡預處理中相關波門研究[J].現代電子技術,2012,35(13):19-21.

[3] 靳標,糾博,蘇濤.一種用于雜波中機動目標跟蹤的自適應關聯波門設計方法[J].西安交通大學學報,2014,48(10):40-46.

[4] 王明輝,游志勝,趙榮椿,等.性能優化的跟蹤門算法[J].電子學報,2000,28(6):8-12.

[5] 張志芬.基于數論法的跟蹤門計算方法研究[J].宇航學報,2009,30(2):725-729.

[6] 姜麗,林家駿.信息融合系統中的算法管理理論研究[J].火力與指揮控制,2009,34(5):105-108.

[7] KISHORE M,PRAVAS R.A jerk model for tracking highly maneuvering targets[J].IEEE Transactions on Aerospace and Electronic Systems,1997,33(4):1094-1105.

[8] WANG Xuezhi,CHALLA S,EVANS R.Gating techniques for maneuvering target tracking in clutter[J].IEEE Transactions on Aerospace and Electronic Systems,2002,38(3):1087-1097.

[9] 張潔,林家駿,陳小偉.跟蹤門對多目標跟蹤系統性能的影響[J].華東理工大學學報(自然科學版),2006,32(12):1468-1471.

[10] 范虹,孟慶豐,張優云.用混合編碼遺傳算法實現匹配追蹤算法[J].西安交通大學學報,2005,39(3):295-299.

[11] 王曉璇.目標融合航跡質量評估方法[J].指揮信息系統與技術,2012,3(2):17-22.

[12] 鄭永隆.位置級信息融合算法細粒度性能研究[D].上海:華東理工大學,2013.

[13] 周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社,1999:32-41.

OptimalTrackingGateBasedonHybridEncodingGeneticAlgorithm

ZHAOHan,ZHANGCheng,LINJia-jun

(SchoolofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

The track qualities can be depended on tracking algorithm optimization.One of the essential optimization problems in tracking is gate selection.In this paper,a hybrid encoding genetic algorithm is proposed to off-line optimization of tracking gate parameters for maneuvering target tracking in clutter.Binary string and floating-point string represent shapes and size of tracking gate respectively.Hellinger distance is chosen for performance evaluation of tracking and can be core part of the fitness function of genetic algorithm.Generally speaking,the tracking system optimization can be converted into genetic algorithm optimization,then the tracking gate parameters can be efficiently tuned in different scenarios.

target tracking; association gate; genetic algorithm; hybrid coding

1006-3080(2017)06-0844-05

10.14135/j.cnki.1006-3080.2017.06.014

2017-06-13

趙 菡(1980-),女,安徽蚌埠人,副教授,博士生,主要研究方向為信息融合性能評價和目標跟蹤算法優化。E-mail:lotus@ecust.edu.cn

林家駿,E-mail:jjlin@ecust.edu.cn.

TP391

A