基于混合編碼遺傳算法的最優(yōu)跟蹤門

趙 菡, 張 琤, 林家駿

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

基于混合編碼遺傳算法的最優(yōu)跟蹤門

趙 菡, 張 琤, 林家駿

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

跟蹤算法優(yōu)化可以提高跟蹤質(zhì)量,選擇恰當?shù)母欓T是優(yōu)化跟蹤算法的關(guān)鍵措施之一。本文提出了一種基于混合編碼的遺傳算法,用于雜波環(huán)境下目標跟蹤過程中跟蹤門參數(shù)的離線優(yōu)化。該算法將二進制編碼與浮點數(shù)編碼結(jié)合,對跟蹤門的形狀和大小進行混合編碼,選擇跟蹤精度性能指標構(gòu)造遺傳算法的適應(yīng)度函數(shù),以此將跟蹤算法的優(yōu)化問題轉(zhuǎn)化為遺傳算法尋優(yōu),在不同雜波環(huán)境下優(yōu)化跟蹤門參數(shù)設(shè)置。

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

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

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

1 航跡跟蹤算法與跟蹤門

1.1 狀態(tài)估計與數(shù)據(jù)關(guān)聯(lián)

(1)

觀測向量的一步預(yù)測為

(2)

卡爾曼濾波增益矩陣為

(3)

對應(yīng)的新息協(xié)方差為

(4)

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

(5)

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

(6)

1.2 跟蹤門理論

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

2 基于遺傳算法的波門尋優(yōu)實現(xiàn)

2.1 混合編碼實現(xiàn)

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

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

2.2 算法描述

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

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

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

2.3 Hellinger距離與適應(yīng)值計算

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

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

(7)

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

(8)

用BL與BU分別表示預(yù)設(shè)的門限常數(shù)上界和下屆,則跟蹤門優(yōu)化問題可轉(zhuǎn)化為

G=argGmaxffitness(G)

(9)

s.t.G=[GS,GL]

GS∈{0,1}

BL≤GL≤BU

GL,BL,BU∈R

2.4 遺傳操作

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

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

3 仿真研究

3.1 參數(shù)設(shè)置

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

3.2 實驗結(jié)果與分析

稀疏雜波環(huán)境下跟蹤門參數(shù)收斂于014.217,根據(jù)混合編碼規(guī)則可知,01代表跟蹤門形狀的二進制編碼,對應(yīng)的為橢圓門;4.217代表跟蹤門門限常數(shù)的浮點數(shù)編碼,表示尋優(yōu)結(jié)果是門限常數(shù)4.217的橢圓門。在這樣的參數(shù)設(shè)定下,得到的Hellinger距離為0.173 5。

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

限定跟蹤門的形狀,依次用遺傳算法僅對門限常數(shù)尋優(yōu),可得到不同形狀跟蹤門所對應(yīng)的最小跟蹤誤差,實驗結(jié)果如表1所示。由表1可見,在兩種雜波環(huán)境下,采用混合編碼遺傳算法尋優(yōu)結(jié)果的系統(tǒng),其跟蹤誤差最小,系統(tǒng)跟蹤精度最高。

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

表1 跟蹤門參數(shù)及跟蹤誤差統(tǒng)計表

3.3 跟蹤門優(yōu)化結(jié)果適應(yīng)范圍

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

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

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

4 結(jié)束語

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

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

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

[2] 董國,岳三創(chuàng).航跡預(yù)處理中相關(guān)波門研究[J].現(xiàn)代電子技術(shù),2012,35(13):19-21.

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

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

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

[6] 姜麗,林家駿.信息融合系統(tǒng)中的算法管理理論研究[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] 張潔,林家駿,陳小偉.跟蹤門對多目標跟蹤系統(tǒng)性能的影響[J].華東理工大學(xué)學(xué)報(自然科學(xué)版),2006,32(12):1468-1471.

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

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

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

[13] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,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-),女,安徽蚌埠人,副教授,博士生,主要研究方向為信息融合性能評價和目標跟蹤算法優(yōu)化。E-mail:lotus@ecust.edu.cn

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

TP391

A