基于改進蟻群算法的多目標跟蹤數據關聯方法

尹玉萍，劉萬軍，魏林

1.遼寧工程技術大學電氣與控制工程學院，遼寧葫蘆島 125105

2.遼寧工程技術大學軟件學院，遼寧葫蘆島 125105

3.遼寧工程技術大學基礎教學部，遼寧葫蘆島 125105

基于改進蟻群算法的多目標跟蹤數據關聯方法

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

1.遼寧工程技術大學電氣與控制工程學院，遼寧葫蘆島 125105

2.遼寧工程技術大學軟件學院，遼寧葫蘆島 125105

3.遼寧工程技術大學基礎教學部，遼寧葫蘆島 125105

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

蟻群算法；混沌；多目標跟蹤；數據關聯

1 引言

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

本文以蟻群算法為基礎，利用蟻群算法的正反饋和并行搜索能力構建初始解并進行優化，引入自適應混沌機制，對信息素進行全局更新和混沌擾動，提出一種快速實現多目標數據關聯的方法CACDA。通過仿真實驗表明，改進后的數據關聯算法在執行時間和關聯準確度上都有較大優勢。

2 數據關聯的組合優化模型

2.1 多目標數據關聯基本模型

數據關聯問題中，最佳關聯的目標函數定義如下：

其中，Kt是Xt和Yt已知情況下的最佳關聯。

數據關聯目標函數定義如下：

約束條件為：

其中，aj，k為二值變量，即觀測yj，t與目標k相關聯時，aj，k為1，否則為0。uj，k為觀測yj，t與目標k相關聯的費用值，定義為：

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

2.2 降維處理

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

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

式（4）為目標解，也稱作原始問題。

約束條件為：

其中，ci1，i2，…，is為滿足S維約束時對應的時間，效益等條件。ρi1，i2，…，is是二進制變量，當S元量測與某一候選目標不進行互聯時，ρi1，i2，…，is=0；當S元量測與某一候選目標產生互聯時，ρi1，i2，…，is=1。

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

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

3 混沌蟻群算法應用于數據關聯問題

3.1 蟻群算法基本原理

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

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

3.2 信息素的混沌擾動

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

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

混沌系統加入算法后，對信息素進行全局更新和混沌擾動，將信息素更新方程修改為：

其中，zij為混沌變量，通過公式（6）迭代得到，λ是調節系數。

3.3 CACDA模型

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

本文沿用文獻[4]的方法對路徑和路徑長度進行定義，做如下假設：

假設1：某時刻，一個目標最多只能產生一個觀測；

假設2：一個觀測最多只能與一個目標進行關聯。

另外，在基本蟻群算法應用于數據關聯的基礎上，對螞蟻群各個螞蟻的特征做出如下規定[13-14]：

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

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

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

規定4：每個航跡和觀測的關系是一一對應的；

規定5：對螞蟻k，一次循環中確定的所有量測對稱為路徑，所有關聯對的標準距離之和稱為路徑長度。

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

根據ACDA模型構建蟻群t+1時刻信息素模型如下：

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

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

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

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

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

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

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

（5）如果未達到最大迭代次數，轉到步驟（2）；否則，輸出最優解，終止算法。

4 仿真實驗及分析

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

圖1 數據關聯前雜波存在情況

圖2 5目標跟蹤數據關聯對比

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

圖3 兩目標交叉時跟蹤情況

為了更直觀地驗證本文算法比傳統ACDA算法在關聯準確率及執行時間上的優越性，本文將ACDA與CACDA算法進行比較，其中每種算法的關聯目標數分別取值50、100、150、200四組進行比較，種群數量分別取值40、80進行比較，執行時間為相同條件下執行60次結果的平均值，比較結果如表1～表4所示。

表1 兩種算法取目標數為50時實驗結果對比

表2 兩種算法取目標數為100時實驗結果對比

表3 兩種算法取目標數為150時實驗結果對比

表4 兩種算法取目標數為200時實驗結果對比

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

5 結論

本文利用蟻群算法解決組合優化問題的優勢，在蟻群算法搜索過程中，對局部最優解加入混沌擾動，通過調整信息量避免陷入局部極值，提出一種快速實現多目標數據關聯的方法CACDA。通過仿真實驗表明，改進后的數據關聯算法在執行時間和關聯準確度上都有較大優勢，能很好地應用于多傳感器多目標系統中的數據關聯問題。

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

[2]張波雷，許蘊山，夏海寶.一種基于自適應蟻群算法的數據關聯方法[J].傳感器與微系統，2012，31（8）：27-29.

[3]袁述，袁東輝，孫基洲，等.蟻群-遺傳算法在多傳感器多目標跟蹤技術中的應用[J].電子學報，2013，41（3）：609-614.

[4]康莉，謝維信，黃敬雄.一種基于蟻群算法的多目標跟蹤數據關聯方法[J].電子學報，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].火力與指揮控制，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].北京：科學出版社，2011：107-127.

[10]原文林，曲曉寧.混沌蟻群優化算法在梯級水庫發電優化調度中的應用研究[J].水力發電學報，2013，32（3）：47-61.

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

[12]王希彬，趙國榮，李海君.基于禁忌搜索的混沌蟻群算法在SLAM數據關聯中的應用[J].北京理工大學學報，2012，32（7）：725-728.

[13]邸憶，龍飛，李卓越.一種基于改進蟻群算法的多目標跟蹤數據關聯方法[J].計算機應用與軟件，2013，30（4）：306-309.

[14]袁東輝，劉大有，申世群.基于蟻群—遺傳算法的改進多目標數據關聯方法[J].通信學報，2011，32（6）：17-23.

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

[16]王月領，王讓定.嵌入卡爾曼預測器的粒子濾波目標跟蹤算法[J].計算機應用研究，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.

國家自然科學基金（No.61172144）。

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

2013-12-16

2014-01-26

1002-8331（2014）16-0016-05

CNKI網絡優先出版：2014-02-26,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1312-0219.htm l