趙 菡, 張 琤, 林家駿

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

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

趙 菡, 張 琤, 林家駿

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

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

目標(biāo)跟蹤; 跟蹤門; 遺傳算法; 混合編碼

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

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

1 航跡跟蹤算法與跟蹤門

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

(1)

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

(2)

卡爾曼濾波增益矩陣為

(3)

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

(4)

則第i個(gè)候選回波的目標(biāo)狀態(tài)估計(jì)為

(5)

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

(6)

1.2 跟蹤門理論

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

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

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

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

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

2.2 算法描述

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

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

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

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

(7)

在目標(biāo)跟蹤系統(tǒng)中,可以將(x,Σx)看成真實(shí)的狀態(tài)向量分布,將(y,Σy)看成估計(jì)的狀態(tài)向量分布,對于真實(shí)的狀態(tài)向量,其不確定度可以作為一種基準(zhǔn)應(yīng)該具備最優(yōu)的特性,選用克拉美羅下界(Cramer-Rao)[12]。若用Hellinger距離dH|k(f,g)表示k時(shí)刻真實(shí)航跡和估計(jì)航跡之間的距離,可構(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)個(gè)體不被交叉、變異等遺傳運(yùn)算破壞。本文采用最優(yōu)保存策略進(jìn)化模型,先計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度比例,通過輪盤賭的方式,使擁有更大適應(yīng)度比例的個(gè)體有更大的概率遺傳到下一代的種群[13]。

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

3 仿真研究

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

仿真劇情是不同雜波環(huán)境下高機(jī)動(dòng)的單目標(biāo)跟蹤,目標(biāo)的初始狀態(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個(gè)點(diǎn),采樣間隔為1 s,仿真次數(shù)為50。設(shè)定目標(biāo)的檢測概率PD=0.98,虛假量測在以正確量測為中心的正方形區(qū)域內(nèi)隨機(jī)均勻產(chǎn)生,虛假量測總數(shù)nc=λAv,其中λ是雜波密度,Av為區(qū)域的面積。本文分別給出了λ=2和λ=20,即稀疏雜波和密集雜波兩種劇情。

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

稀疏雜波環(huán)境下跟蹤門參數(shù)收斂于014.217,根據(jù)混合編碼規(guī)則可知,01代表跟蹤門形狀的二進(jìn)制編碼,對應(yīng)的為橢圓門;4.217代表跟蹤門門限常數(shù)的浮點(diǎn)數(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。保持目標(biāo)檢測概率不變,雜波密度增大要求跟蹤門相應(yīng)增大,實(shí)驗(yàn)結(jié)果與此結(jié)論相符。

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

[5] 張志芬.基于數(shù)論法的跟蹤門計(jì)算方法研究[J].宇航學(xué)報(bào),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] 張潔,林家駿,陳小偉.跟蹤門對多目標(biāo)跟蹤系統(tǒng)性能的影響[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,32(12):1468-1471.

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

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

[12] 鄭永隆.位置級(jí)信息融合算法細(xì)粒度性能研究[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àn)樾畔⑷诤闲阅茉u價(jià)和目標(biāo)跟蹤算法優(yōu)化。E-mail:lotus@ecust.edu.cn

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

TP391

A