基于改进蚁群算法的多目标跟踪数据关联方法

尹玉萍，刘万军，魏林

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