基于改進(jìn)蟻群算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法

尹玉萍，劉萬軍，魏林

1.遼寧工程技術(shù)大學(xué)電氣與控制工程學(xué)院，遼寧葫蘆島 125105

2.遼寧工程技術(shù)大學(xué)軟件學(xué)院，遼寧葫蘆島 125105

3.遼寧工程技術(shù)大學(xué)基礎(chǔ)教學(xué)部，遼寧葫蘆島 125105

基于改進(jìn)蟻群算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法

尹玉萍1，劉萬軍2，魏林3

1.遼寧工程技術(shù)大學(xué)電氣與控制工程學(xué)院，遼寧葫蘆島 125105

2.遼寧工程技術(shù)大學(xué)軟件學(xué)院，遼寧葫蘆島 125105

3.遼寧工程技術(shù)大學(xué)基礎(chǔ)教學(xué)部，遼寧葫蘆島 125105

針對多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)問題，提出一種快速實現(xiàn)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)算法CACDA（Chaos Ant Colony Data Association），利用蟻群算法的正反饋和并行搜索能力構(gòu)建初始解并進(jìn)行優(yōu)化，引入自適應(yīng)混沌機(jī)制，對信息素進(jìn)行全局更新和混沌擾動，改善了蟻群算法在搜索后期出現(xiàn)停滯以及收斂于局部最優(yōu)解的缺陷。實驗結(jié)果表明，該算法不僅可以獲得較高的關(guān)聯(lián)準(zhǔn)確率，也可以有效提高關(guān)聯(lián)速度。

蟻群算法；混沌；多目標(biāo)跟蹤；數(shù)據(jù)關(guān)聯(lián)

1 引言

數(shù)據(jù)關(guān)聯(lián)和跟蹤維持是多目標(biāo)跟蹤算法的核心，是跟蹤技術(shù)中最重要并且最困難的方面。數(shù)據(jù)關(guān)聯(lián)過程是將所有的候選量測與已知的目標(biāo)航跡相比較，并最后確定觀測和已知目標(biāo)航跡的配對過程[1]。國內(nèi)外學(xué)者針對多目標(biāo)的數(shù)據(jù)關(guān)聯(lián)方法進(jìn)行了許多深入的研究，目前，解決數(shù)據(jù)關(guān)聯(lián)問題的方法主要分為以下兩類[2]：一是基于統(tǒng)計的方法，如最近鄰域（NN）法、概率數(shù)據(jù)關(guān)聯(lián)（PDA）算法、聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)（JPDA）算法。但NN算法關(guān)聯(lián)正確率較低，PDA算法只針對單目標(biāo)的數(shù)據(jù)關(guān)聯(lián)，JPDA算法是目前比較好的對多目標(biāo)進(jìn)行跟蹤的理想方法，但計算開銷大。二是基于模糊聚類的方法，如模糊數(shù)據(jù)關(guān)聯(lián)（FDA）算法，但該算法容易陷入局部最小值且對初始值比較敏感。近年來，隨著仿生智能算法的發(fā)展，一些研究學(xué)者將遺傳算法、粒子群算法、蟻群算法等智能算法應(yīng)用于目標(biāo)數(shù)據(jù)關(guān)聯(lián)中，比如袁述等提出的蟻群-遺傳算法在多傳感器多目標(biāo)跟蹤技術(shù)中的應(yīng)用[3]，康莉等提出的一種基于蟻群算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法[4]等都取得了較好的結(jié)果。

本文以蟻群算法為基礎(chǔ)，利用蟻群算法的正反饋和并行搜索能力構(gòu)建初始解并進(jìn)行優(yōu)化，引入自適應(yīng)混沌機(jī)制，對信息素進(jìn)行全局更新和混沌擾動，提出一種快速實現(xiàn)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)的方法CACDA。通過仿真實驗表明，改進(jìn)后的數(shù)據(jù)關(guān)聯(lián)算法在執(zhí)行時間和關(guān)聯(lián)準(zhǔn)確度上都有較大優(yōu)勢。

2 數(shù)據(jù)關(guān)聯(lián)的組合優(yōu)化模型

2.1 多目標(biāo)數(shù)據(jù)關(guān)聯(lián)基本模型

數(shù)據(jù)關(guān)聯(lián)問題中，最佳關(guān)聯(lián)的目標(biāo)函數(shù)定義如下：

其中，Kt是Xt和Yt已知情況下的最佳關(guān)聯(lián)。

數(shù)據(jù)關(guān)聯(lián)目標(biāo)函數(shù)定義如下：

約束條件為：

其中，aj，k為二值變量，即觀測yj，t與目標(biāo)k相關(guān)聯(lián)時，aj，k為1，否則為0。uj，k為觀測yj，t與目標(biāo)k相關(guān)聯(lián)的費用值，定義為：

式中，PD為檢測概率，V為觀測空間，雜波在觀測空間內(nèi)服從均勻分布[4]。

2.2 降維處理

當(dāng)觀測區(qū)域有三個或三個以上傳感器同時工作時，數(shù)據(jù)關(guān)聯(lián)問題的組合優(yōu)化模型可描述為廣義S維分配問題[5]。當(dāng)維數(shù)大于等于3時，多維分配問題就是NP—hard問題。即使在檢測概率為1和無虛假量測的前提下也是如此。一旦監(jiān)視區(qū)域內(nèi)目標(biāo)數(shù)目很多，算法的計算時間是不可接受的，利用最優(yōu)算法尋求最優(yōu)解在此種情況下已沒有任何意義。因此，要進(jìn)行降維處理，本文采用拉格朗日松弛的思想對多維分配問題進(jìn)行松弛降維處理來解決此問題。

S維分配問題是將K時刻，對來源于S個序列的ns(s=1，2，…，S)個量測進(jìn)行關(guān)聯(lián)。得到如下的S維分配問題：

式（4）為目標(biāo)解，也稱作原始問題。

約束條件為：

其中，ci1，i2，…，is為滿足S維約束時對應(yīng)的時間，效益等條件。ρi1，i2，…，is是二進(jìn)制變量，當(dāng)S元量測與某一候選目標(biāo)不進(jìn)行互聯(lián)時，ρi1，i2，…，is=0；當(dāng)S元量測與某一候選目標(biāo)產(chǎn)生互聯(lián)時，ρi1，i2，…，is=1。

運用文獻(xiàn)[6]和文獻(xiàn)[7]提出的方法[6-7]，將約束條件中最后(S-r)個約束附加到目標(biāo)函數(shù)中，此時目標(biāo)函數(shù)由更新的拉格朗日乘子ur的形式給出，松弛降維形成了二維松弛子問題：

將S維分配問題轉(zhuǎn)化成二維子問題，具體過程可參考文獻(xiàn)[6-7]，而二維分配問題的解決有O(n3)時間內(nèi)求得最優(yōu)解的技術(shù)，二維分配問題可以在多項式時間內(nèi)求得最優(yōu)解。本文結(jié)合蟻群算法在組合優(yōu)化問題上的優(yōu)勢，在蟻群算法搜索過程中，對局部最優(yōu)解加入混沌擾動，通過調(diào)整信息量避免陷入局部極值，最終找到最優(yōu)解，從而實現(xiàn)了數(shù)據(jù)關(guān)聯(lián)。

3 混沌蟻群算法應(yīng)用于數(shù)據(jù)關(guān)聯(lián)問題

3.1 蟻群算法基本原理

蟻群算法是意大利學(xué)者Dorigo于1991年首次提出的一種新型優(yōu)化算法[8]，自出現(xiàn)以來，在TSP問題、調(diào)度以及二次分配等組合優(yōu)化問題中獲得了很好的應(yīng)用。

蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設(shè)計出的一種群集智能算法。螞蟻在覓食過程中能夠在其經(jīng)過的路徑上留下一種稱之為信息素的物質(zhì)，并在覓食過程中能夠感知這種物質(zhì)的強(qiáng)度，并指導(dǎo)自己行動方向，它們總是朝著該物質(zhì)強(qiáng)度高的方向移動，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對信息素的正反饋現(xiàn)象。某一條路徑越短，路徑上經(jīng)過的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構(gòu)成的正反饋過程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑[9]。蟻群算法的詳細(xì)原理可參考文獻(xiàn)[9]。

3.2 信息素的混沌擾動

混沌優(yōu)化算法（Chaos Optimization A lgorithm，COA）是近年來隨著混沌學(xué)科的發(fā)展而提出的一種新的優(yōu)化算法。其基本思想是把混沌變量映射到優(yōu)化變量的取值空間，構(gòu)造混沌變量序列，充分利用混沌變量在混沌運動中所具有的遍歷性、隨機(jī)性、規(guī)律性來尋找全局最優(yōu)解[10]。將其融入蟻群算法中，提出混沌蟻群算法，利用混沌擾動避免搜索過程陷入局部極值。Logistic映射是一個典型的混沌系統(tǒng)，其迭代公式如下：

其中μ為控制參量，當(dāng)μ=4時，同時z0?{0，0.25，0.5，0.75，1}，此時，Logistic產(chǎn)生的序列完全處于混沌狀態(tài)[11-12]。

混沌系統(tǒng)加入算法后，對信息素進(jìn)行全局更新和混沌擾動，將信息素更新方程修改為：

其中，zij為混沌變量，通過公式（6）迭代得到，λ是調(diào)節(jié)系數(shù)。

3.3 CACDA模型

ACDA模型是一種將蟻群優(yōu)化算法應(yīng)用于多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)中的仿生優(yōu)化方法，但還存在一些如蟻群算法前期收斂速度慢，易陷入局部最優(yōu)等問題有待解決。本文將蟻群算法和信息素混沌擾動思想加入數(shù)據(jù)關(guān)聯(lián)，建立航跡-觀測對和信息素模型，對提高關(guān)聯(lián)的準(zhǔn)確率及尋優(yōu)過程中減少程序的執(zhí)行時間、迭代次數(shù)等方面有積極作用。其基本思想是：每只螞蟻依概率選擇相應(yīng)的航跡-觀測關(guān)聯(lián)對，為每個目標(biāo)分配一個合適的觀測，當(dāng)每只參與路徑搜索的螞蟻均生成一條路徑后，計算出每只螞蟻路徑的長度，從中找出路徑長度最短的路徑，因為關(guān)聯(lián)程度越強(qiáng)，其相應(yīng)的路徑越短。此時，加入混沌擾動并修改信息素模型，使所有螞蟻都找到一條穩(wěn)定的最優(yōu)路徑，并有效防止了早熟收斂。

本文沿用文獻(xiàn)[4]的方法對路徑和路徑長度進(jìn)行定義，做如下假設(shè)：

假設(shè)1：某時刻，一個目標(biāo)最多只能產(chǎn)生一個觀測；

假設(shè)2：一個觀測最多只能與一個目標(biāo)進(jìn)行關(guān)聯(lián)。

另外，在基本蟻群算法應(yīng)用于數(shù)據(jù)關(guān)聯(lián)的基礎(chǔ)上，對螞蟻群各個螞蟻的特征做出如下規(guī)定[13-14]：

規(guī)定1：螞蟻k從每個航跡出發(fā)，并且以一定概率p選取觀測；

規(guī)定2：信息素存在于每個觀測上，且信息素值域為[0，1]；

規(guī)定3：螞蟻搜索路徑時，選擇的航跡關(guān)聯(lián)必須是觀測集中沒有被選擇過的觀測點；

規(guī)定4：每個航跡和觀測的關(guān)系是一一對應(yīng)的；

規(guī)定5：對螞蟻k，一次循環(huán)中確定的所有量測對稱為路徑，所有關(guān)聯(lián)對的標(biāo)準(zhǔn)距離之和稱為路徑長度。

比如觀測空間有三條航跡A、B、C，三個觀測a、b、c，如果螞蟻k形成的一條搜索路徑為(A，c)-(B，a)-(C，b)。則路徑長度為dk=dAc+dBa+dCb，其中dij為航跡i和觀測j之間的距離。

根據(jù)ACDA模型構(gòu)建蟻群t+1時刻信息素模型如下：

式中，ρ表示信息素?fù)]發(fā)系數(shù)，為防止信息的無限積累，ρ的取值范圍為[0，1]，τij(t)為t時刻邊(i，j)上的信息素，為本次循環(huán)中邊(i，j)上的信息素增量。

螞蟻k(k=1，2，…，m)根據(jù)觀測上留下的信息素隨機(jī)選擇關(guān)聯(lián)，第k只螞蟻將第i個量測分配給第j條航跡的概率為：式中，tk表示本次關(guān)聯(lián)中螞蟻k的禁忌表，參數(shù)α為信息素因子，用來控制信息素對螞蟻個體的重要程度；β為啟發(fā)式因子，用來控制路徑長度相對重要程度。

假設(shè)m只螞蟻分別被放置在隨機(jī)選擇的n條航跡上，CACDA算法的具體步驟如下：

（1）把相同數(shù)量的信息量分配給每一個航跡-量測對。

（2）螞蟻選擇策略，螞蟻k(k=1，2，…，m)依公式（9）將量測i分配給目標(biāo)j，然后查找沒有被分配的量測，從中找出一個與之關(guān)聯(lián)程度大的量測分配給第二個目標(biāo)，如此繼續(xù)，一直到航跡集合為空時停止。如果分配給某個目標(biāo)的量測概率很小，則舍棄該量測，繼續(xù)為下一個目標(biāo)分配量測，沒有被分配的量測認(rèn)為是虛假回波放在禁忌表的末尾。

（3）當(dāng)螞蟻k選擇完一條路徑，即程序運行一次循環(huán)后，禁忌表清空。如果量測i已經(jīng)與目標(biāo)j成功關(guān)聯(lián)，則每只螞蟻一定在對應(yīng)的量測關(guān)聯(lián)對上留下了信息素，記為=Mdk，其中dk是螞蟻k的路徑長度，M是信息素的調(diào)整系數(shù)。

（4）程序迭代一次后，此時所有螞蟻都選擇了路徑，在所有選擇的路徑中，找出路徑長度最短的即為此次迭代的最優(yōu)解，此時，加入混沌擾動，修改信息素模型為：

（5）如果未達(dá)到最大迭代次數(shù)，轉(zhuǎn)到步驟（2）；否則，輸出最優(yōu)解，終止算法。

4 仿真實驗及分析

為了驗證算法的有效性，本文對5批目標(biāo)的關(guān)聯(lián)情況進(jìn)行仿真。在跟蹤過程中設(shè)傳感器的檢測概率PD=0.92，雜波密度服從泊松分布，結(jié)果如圖1、圖2所示，圖中“o”表示目標(biāo)位置，“*”表示傳感器獲得的航跡觀測，圖1中包括較多雜波，用關(guān)聯(lián)門排除大部分雜波并用原始ACDA算法進(jìn)行數(shù)據(jù)關(guān)聯(lián)后的結(jié)果如圖2（a）所示。用關(guān)聯(lián)門排除大部分雜波并用CACDA算法進(jìn)行數(shù)據(jù)關(guān)聯(lián)后的結(jié)果如圖2（b）所示，顯然，CACDA算法關(guān)聯(lián)后數(shù)據(jù)要優(yōu)于ACDA算法關(guān)聯(lián)后數(shù)據(jù)。

圖1 數(shù)據(jù)關(guān)聯(lián)前雜波存在情況

圖2 5目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)對比

另外，對2批目標(biāo)在平面上運動的情況進(jìn)行仿真，此處跟蹤模型引用文獻(xiàn)[4]中的模型，在此不再贅述。利用卡爾曼濾波[15-16]實現(xiàn)目標(biāo)狀態(tài)和觀測值更新，實驗結(jié)果如圖3所示。從圖中可以看出：在兩目標(biāo)交叉運動的情況下，原始CACDA算法也可以較好的實現(xiàn)相應(yīng)目標(biāo)的關(guān)聯(lián)。

圖3 兩目標(biāo)交叉時跟蹤情況

為了更直觀地驗證本文算法比傳統(tǒng)ACDA算法在關(guān)聯(lián)準(zhǔn)確率及執(zhí)行時間上的優(yōu)越性，本文將ACDA與CACDA算法進(jìn)行比較，其中每種算法的關(guān)聯(lián)目標(biāo)數(shù)分別取值50、100、150、200四組進(jìn)行比較，種群數(shù)量分別取值40、80進(jìn)行比較，執(zhí)行時間為相同條件下執(zhí)行60次結(jié)果的平均值，比較結(jié)果如表1～表4所示。

表1 兩種算法取目標(biāo)數(shù)為50時實驗結(jié)果對比

表2 兩種算法取目標(biāo)數(shù)為100時實驗結(jié)果對比

表3 兩種算法取目標(biāo)數(shù)為150時實驗結(jié)果對比

表4 兩種算法取目標(biāo)數(shù)為200時實驗結(jié)果對比

由表1～表4可以看出，傳統(tǒng)ACDA算法關(guān)聯(lián)準(zhǔn)確率隨著種群數(shù)量上升有所降低，而且始終維持在90%以下，而本文提出的CACDA算法關(guān)聯(lián)準(zhǔn)確率除目標(biāo)數(shù)高于150時略有下降，其他情況一直保持在90%以上。改進(jìn)后的CACDA算法，利用蟻群算法的正反饋和并行搜索能力構(gòu)建初始解并進(jìn)行優(yōu)化，引入自適應(yīng)混沌機(jī)制，對信息素進(jìn)行全局更新和混沌擾動，克服了蟻群算法容易陷入局部極值的缺點，迭代次數(shù)及執(zhí)行時間都明顯優(yōu)于ACDA算法。通過實驗對比分析，已經(jīng)可以很明顯地體現(xiàn)出新算法在多目標(biāo)數(shù)據(jù)關(guān)聯(lián)中的良好性能。

5 結(jié)論

本文利用蟻群算法解決組合優(yōu)化問題的優(yōu)勢，在蟻群算法搜索過程中，對局部最優(yōu)解加入混沌擾動，通過調(diào)整信息量避免陷入局部極值，提出一種快速實現(xiàn)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)的方法CACDA。通過仿真實驗表明，改進(jìn)后的數(shù)據(jù)關(guān)聯(lián)算法在執(zhí)行時間和關(guān)聯(lián)準(zhǔn)確度上都有較大優(yōu)勢，能很好地應(yīng)用于多傳感器多目標(biāo)系統(tǒng)中的數(shù)據(jù)關(guān)聯(lián)問題。

[1]潘泉.多源信息融合理論及應(yīng)用[M].北京：清華大學(xué)出版社，2013：325-326.

[2]張波雷，許蘊(yùn)山，夏海寶.一種基于自適應(yīng)蟻群算法的數(shù)據(jù)關(guān)聯(lián)方法[J].傳感器與微系統(tǒng)，2012，31（8）：27-29.

[3]袁述，袁東輝，孫基洲，等.蟻群-遺傳算法在多傳感器多目標(biāo)跟蹤技術(shù)中的應(yīng)用[J].電子學(xué)報，2013，41（3）：609-614.

[4]康莉，謝維信，黃敬雄.一種基于蟻群算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法[J].電子學(xué)報，2008，36（3）：586-589.

[5]Deb S，Yeddanapudi M，Pattipati K R，et al.A generalized S-D assignment algorithm for multisensor-multitarget state estimation[J].IEEE Trans on AES，1997，33（2）：523-538.

[6]童長寧，林岳松，郭云飛，等.改進(jìn)的拉格朗日松弛數(shù)據(jù)關(guān)聯(lián)算法[J].火力與指揮控制，2011，36（10）：20-27.

[7]Pattipati K R，Somnath D，Bar-Shalom Y，et al.A new relaxation algorithm and passive sensor data association[J]. IEEE Trans on Autom Control，1992，37（2）：198-213.

[8]Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

[9]段海濱，張祥銀，徐春芳.仿生智能計算[M].北京：科學(xué)出版社，2011：107-127.

[10]原文林，曲曉寧.混沌蟻群優(yōu)化算法在梯級水庫發(fā)電優(yōu)化調(diào)度中的應(yīng)用研究[J].水力發(fā)電學(xué)報，2013，32（3）：47-61.

[11]肖樂，吳相林，甄彤.自適應(yīng)混沌蟻群算法的糧食應(yīng)急路徑優(yōu)化研究[J].計算機(jī)工程與應(yīng)用，2012，48（24）：28-31.

[12]王希彬，趙國榮，李海君.基于禁忌搜索的混沌蟻群算法在SLAM數(shù)據(jù)關(guān)聯(lián)中的應(yīng)用[J].北京理工大學(xué)學(xué)報，2012，32（7）：725-728.

[13]邸憶，龍飛，李卓越.一種基于改進(jìn)蟻群算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法[J].計算機(jī)應(yīng)用與軟件，2013，30（4）：306-309.

[14]袁東輝，劉大有，申世群.基于蟻群—遺傳算法的改進(jìn)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)方法[J].通信學(xué)報，2011，32（6）：17-23.

[15]常發(fā)亮，劉雪，王華杰.基于均值漂移與卡爾曼濾波的目標(biāo)跟蹤算法[J].計算機(jī)工程與應(yīng)用，2007，43（12）：50-52.

[16]王月領(lǐng)，王讓定.嵌入卡爾曼預(yù)測器的粒子濾波目標(biāo)跟蹤算法[J].計算機(jī)應(yīng)用研究，2010，27（2）：468-471.

YIN Yuping1,LIU Wanjun2,WEI Lin3

1.School of Electrical and Control Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
2.School of Software,Liaoning Technical University,Huludao,Liaoning 125105,China
3.The Department of Basic Education,Liaoning Technical University,Huludao,Liaoning 125105,China

For the application of multi-sensor multi-target tracking,a method of data association based on improved ant colony algorithm is proposed in this study,in order to improve the ant colony algorithm in which the application effect of global optimization problems,the initial solution is built and optimized by use of the characters of positive feedback and parallel search of ant colony algorithm,introducing an adaptive Chaos mechanism,globally pheromone update and chaotic disturbance.Experimental results show that the presented algorithm is effective.

ant colony algorithm;chaos;multi-target tracking;data association

A

TP391

10.3778/j.issn.1002-8331.1312-0219

YIN Yuping,LIU W an jun,WEI Lin.Improved ant colony algorithm based data association method for multi-target tracking.Computer Engineering and Applications,2014,50（16）：16-20.

國家自然科學(xué)基金（No.61172144）。

尹玉萍（1981—），女，講師，博士研究生，主研方向：計算智能，圖形圖像處理；劉萬軍（1959—），男，教授，博士生導(dǎo)師，主研方向：模式識別與人工智能、圖像處理；魏林（1979—），男，講師，博士研究生，主研方向：智能計算，安全管理工程。E-mail：315227336@qq.com

2013-12-16

2014-01-26

1002-8331（2014）16-0016-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-02-26,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1312-0219.htm l