论文:2016,Vol:34,Issue(3):514-519
引用本文:
高颖, 陈旭, 王永庭, 武梦洁. GPU加速的航迹关联改进蚁群求解算法[J]. 西北工业大学学报
Gao Ying, Chen Xu, Wang Yongting, Wu Mangjie. Improved ant Colony Solution Algorithm Accelerated by GPU in Track Correlation[J]. Northwestern polytechnical university

GPU加速的航迹关联改进蚁群求解算法
高颖1,2, 陈旭1, 王永庭2, 武梦洁2
1. 西北工业大学 航海学院, 陕西 西安 710072;
2. 光电控制技术重点实验室, 河南 洛阳 471009
摘要:
分布式信息融合系统中,航迹关联问题可转化为多维分配进行求解,现有的求解方法存在着收敛速度慢、求解代数多的缺点,难以满足实时性要求。鉴于此,提出了一种GPU加速的改进蚁群求解算法。首先,运用灰色理论建立航迹关联多维分配问题模型;其次,蚁群算法求解过程中,通过选择最大灰关联系数邻域内的状态估计对搜索列表进行更新,缩小蚂蚁的搜索区域,并采用狼群分配原则更新信息素,避免了搜索陷入局部最优;最后,采用GPU加速的并行策略进行求解。仿真结果表明,一个关联周期内,10步迭代之内该算法的关联正确率可达90%以上;GPU加速的并行求解策略能够提高求解效率,且随着问题规模的增大,加速效果越明显。
关键词:    航迹关联    灰色关联理论    多维分配求解    蚁群算法    GPU加速   
Improved ant Colony Solution Algorithm Accelerated by GPU in Track Correlation
Gao Ying1,2, Chen Xu1, Wang Yongting2, Wu Mangjie2
1. School of Marine Science and Technology, Northwestern Polytechnical University, Xi'an 710072, China;
2. Science and Technology on Electro-Optic Control Laboratory, Luoyang 471009, China
Abstract:
In the distributed information fusion system, the problem of track correlation can be transformed into the problem of multi-dimension assignment. However, it's a NP-Hard problem. In view of the low convergence-rate and the more iterative times for the existing methods, which is difficult to meet the need of track correlation for real-time, a kind of improved ant colony solution algorithm accelerated by GPU has been put forward. First of all, the multi-dimension assignment model of track correlation should be established based on grey theory. Secondly, narrow down the search area to get higher searching efficiency through updating the search listings based on the neighbourhood of the maximum grey relational coefficient, and update the pheromones using the wolves allocation principles for reference in order to avoid trapping in local optimum. At last, use the parallel strategy of GPU acceleration to realize the improved algorithm. The simulation results show that the improved algorithm can obtain the correct association rate of 90%; In addition, the parallel solving strategy based on GPU acceleration can improve the solving efficiency, and the acceleration result of the algorithm is more obvious with the problem scale magnifying.
Key words:    track correlation    grey relational theory    multi-dimension assignment    improved ant colony algorithm    GPU acceleration    calculation    computational efficiency    estimation    iterative methods    target tracking    tracking    extended kalman filters    information fusion   
收稿日期: 2015-09-29     修回日期:
DOI:
基金项目: 光电控制技术重点实验室与航空科学基金(20145152027)资助
通讯作者:     Email:
作者简介: 高颖(1965—),西北工业大学副教授,主要从事虚拟现实及数据融合研究。
相关功能
PDF(1300KB) Free
打印本文
把本文推荐给朋友
作者相关文章
高颖  在本刊中的所有文章
陈旭  在本刊中的所有文章
王永庭  在本刊中的所有文章
武梦洁  在本刊中的所有文章

参考文献:
[1] Guan Xin, He You, Yi Xiao. Grey Track-to-Track Correlation Algorithm for Distributed Multitarget Tracking System[J]. Signal Processing, 2006, 86(11): 3448-3455
[2] 刘颢,陈世友,汪学东,张必银. 一种自适应航迹关联算法[J]. 电子学报,2013, 41(12): 2416-2421 Liu Hao, Chen Shiyou, Wang Xuedong, Zhang Biyin. An Adaptive Track Correlation Algorithm[J]. Acta Electronica Sinica, 2013, 41(12): 2416-2421 (in Chinese)
[3] 徐丽,马培军,苏小红. 基于K-Medoids聚类的多传感器航迹关联算法[J]. 哈尔滨工业大学学报,2012, 44(1): 107-110 Xu Li, Ma Peijun, Su Xiaohong. A Multisensor Track Association Algorithm Based on Medoids Clustering[J]. Journal of Harbin Institute of Technology, 2012, 44(1): 107-110 (in Chinese)
[4] 郭蕴华,袁成. 一种异步航迹关联的变异蚁群算法[J]. 电子学报,2012,40(11):2200-2205 Guo Yunhua, Yuan Cheng. A Mutation Ant Colony Algorithm for the Asynchronous Track Correlation[J]. Acta Electronica Sinica, 2012, 40(11): 2200-2205 (in Chinese)
[5] 朱洪艳,韩崇昭,韩红,等. 分布式多传感器信息融合系统的异步航迹关联方法[J]. 控制理论与应用,2004,21(3): 453-456 Zhu Hongyan, Han Chongzhao, Han Hong, et al. Asynchronous Track to Track Association Method in Distributed Multi-Sensor Information Fusion System[J]. Control Theory & Applications, 2004, 21(3): 453-456 (in Chinese)
[6] 田宝国,何友,杨日杰. 平均场网络在航迹关联中的应用[J]. 航空学报,2005,26(1): 94-97 Tian Baoguo, He You, Yang Rijie. Application of Mean-Field Network to Track Correlation[J]. Acta Aeronautica et Astronautica Sinica, 2005, 26(1): 94-97 (in Chinese)
[7] Chen Huimin, Bar-Shalom Y, Kirubarajan T. Tracking of Spawning Targets with Multiple Finite Resolution Sensors[J]. IEEE Trans on Aerospace and Electronic Systems, 2008, 44(1): 2-14
[8] 田宝国,何友,杨日杰. 基于遗传算法的分布式多传感器航迹关联算法[J]. 火力与指挥控制,2005, 30(5): 44-47 Tian Baoguo, He You, Yang Rijie. Track Correlation Algorithm based on Genetic Algorithm for Distributed Multi-Sensor System[J]. Fire Control and Command Control, 2005, 30(5): 44-47 (in Chinese)