基于蚁群-遗传算法的改进多目标数据关联方法

第３２卷第６期

２０１１年６月

通信学报

Ｊｏｕｍａｌ

ｏｎ

、，０１．３２Ｎｏ．６

ＣｏｍｍｕｎｉｃａｔｉｏｎｓＪｕｎｅ２０１ｌ

基于蚁群一遗传算法的改进多目标数据关联方法

袁东辉１，２刘大有１，２申世群１＇２

（Ｉ．吉林大学知识工程与符号计算教育部重点实验室，吉林长春１３００１２；２．吉林大学计算机科学与技术学院，吉林长春１３００１２）

摘要：将蚁群算法与遗传算法相结合，提出一种快速实现多目标数据关联的ＡＣ．ＧＡＤＡ（ａｎｔ

ｃｏｌｏｎｙ，ｇｅｎｅｔｉｃａｌｇｏ－

ｒｉｔｈｍｄａｔａａｓｓｏｃｉａｔｉｏｎ）算法，该算法利用种群个体携带信息素，并改进了全局信息素扩散模型，同时为了提高算法

的收敛速度并且避免局部极值的出现，引入了交叉变异策略和种群适应度模型，通过大量的实验数据证明，该算法在获得较高关联准确率的同时可以有效地提高关联速度。关键词：数据关联；多目标；蚁群算法；遗传算法中图分类号：ＴＰ３９１

文献标识码：Ａ

文章编号：１０００－４３６Ｘ（２０１１）０６，００１７．０７

ＩｍｐｒｏｖｅｄＡＣ－ＧＡｂａｓｅｄｄａｔａａｓｓｏｃｉａｔｉｏｎ

ｍｅｔｈｏｄｆｏｒｍｕｌｔｉ－ｔａｒｇｅｔｔｒａｃｋｉｎｇ

ＹＵＡＮＤｏｎｇ．ｈｕｉｌＰ，ＬＩＵＤａ－ｙｏｕｌ．＿，ＳＨＥＮＳｈｉ—ｑｕｎｌ’２

（１．ＫｅｙＬａｂｏｒａｔｏｒｙ

ｏｆ

ＳｙｍｂｏｌｉｃＣｏｍｐｕｔａｔｉｏｎａｎｄＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇｏｆＭｉｎｉｓｔｒｙ

ｏｆＥｄｕｃａｔｉｏｎ，Ｊｉｌｉｎ

Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００１２，ａｌｉ【Ｉａ：

２．Ｃｏｌｌｅｇｅｏｆ

ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ

１３００１２，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ａｎ

ＡＣ－ＧＡＤＡ（ａｎｔｃｏｌｏｎｙ－ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｄａｔａａｓｓｏｃｉａｔｉｏｎ）ａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄ

ｔｏｄｅａｌｗｉｔｈｔｈｅ

ｄａｔａａｓ－

ｓｏｃｉａｔｉｏｎｐｒｏｂｌｅｍｆｏｒ

ｍｕｌｔｉ—ｔａｒｇｅｔｔｒａｃｋｉｎｇ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｄｅｓｉｇｎｅｄｄｉｆｆｅｒｅｎｃｅｐｈｅｒｏｍｏｎｅｆｏｒｅａｃｈａｎｔａｎｄｉｍｐｒｏｖｅｄ

ｃｒｏｓｓｏｖｅｒ

ｇｌｏｂａｌｐｈｅｒｏｍｏｎｅｉｎｃｒｅｍｅｎｔｍｏｄｅｌ，ａｎｄｃｏｍｂｉｎｅｄｄｅｒ

ｔｏ

ａｎｄ

ｍｕｔａｔｉｏｎｓｔｒａｔｅｇｙｗｉｔｈｆｉｔｎｅｓｓｏｆｐｏｐｕｌａｔｉｏｎ

ｗｉｔｈ

ｍｏｄｅｌｉｎ

ｏｒ－

ｉｍｐｒｏｖｅ

ｒａｔｅ

ｏｆｃｏｎｖｅｒｇｅｎｃｅ

ａｎｄ

ａｖｏｉｄｔｈｅａｐｐｅａｒａｎｃｅｏｆ

ｌｏｃａｌｅｘｔｒｅｍｕｍ．Ｔｈｅｃｏｍｐａｒｉｓｏｎ

ｉｔｓ

ＡＣＤＡ（ａｎｔ

ｃｏｌｏｎｙ

ｄａｔａａｓｓｏｃｉａｔｉｏｎ）ａｎｄＪＰＡＤ（ｊｏｉｎｔｐｏｂａｂｉｌｉｓｔｉｃｄａｔａａｓｓｏｃｉａｔｉｏｎ）ｐｒｏｖｅｄ

Ｋｅｙ

ｅｆｆｉｃｉｅｎｃｙａｎｄｓｕｐｅｒｉｏｒｉｔｙ．

ｗｏｒｄｓ：ｄａｔａａｓｓｏｃｉａｔｉｏｎ；ｍｕｌｔｉ—ｔａｒｇｅｔ；ＡＣ；ＧＡ

１引言

新世纪以来科学技术与武器装备的飞速发展以及战场环境的日益复杂，使得多传感器数据融合技术备受关注，国内外学者针对多目标的数据关联方法进行了许多深入的研究，如最近邻数据关联（ＮＮ）、概率数据关联（ＰＤＡ）、联合概率数据关联（ＪＰＤＡ）、模

糊数据关联（ＦＤＡ）和神经网络概率数据关联（ＮＰＤＡ）等，在这些方法中多假设跟踪法【ｌ】和联合概率数据关联【２】都存在随着目标数增加，计算量级数增长的问题，最近邻数据关联法则只适用于稀疏目标环境的目标跟踪。也有学者将多目标数据关联的组合优化形式转换为广义娶维分配问题【３】并推广到了异类传感器应用领域１４】，Ｂａｒ－Ｓｈａｌｏｍ等人将广义孓维分配

收稿日期：２０１０．０７．３０；修回日期：２０１０．１１．１８

基金项目：国家自然科学基金资助项目（６０７７３０９９，６０８７３１４９，６０９７３０８８）；国家高技术研究发展计划（“８６３”计划）基金资助项目（２００６ＡＡｌ０２２４５，２００６ＡＡｌ０Ａ３０９）；中央高校基本科研业务费专项基金资助项目（２００９０３１８９，２００９０３１８２）

ＦｏｕｎｄａｔｉｏｎＲｅｓｅａｒｃｈＣｅｎｔｒａｌ

Ｉｔｅｍｓ：Ｔｈｅ

ＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅ

Ｆｏｕｎｄａｔｉｏｎ

ｏｆ

Ｃｈｉｎａ（６０７７３０９９．６０８７３１４９．６０９７３０８８）；ＴｈｅＮａｔｉｏｎａｌＨｉｇｈ．Ｔｅｃｈ

ａｎｄ

Ｄｅｖｅｌｏｐｍｅｎｔ

Ｐｌａｎ

ｏｆ

Ｃｈｉｎａ（２００６ＡＡｌ０２２４５，２００６ＡＡｌ０Ａ３０９）：ＴｈｅＳｐｅｃｉａｌＦｕｎｄｆｏｒＢａｓｉｃＳｃｉｅｎｔｉｆｉｃＲｅｓｅａｒｃｈｏｆ

Ｃｏｌｌｅｇｅｓ（２００９０３１８９，２００９０３ｌ８２）

万方数据

通信学报第３２卷

算法与传统的跟踪理论相结合，提出了大量具有实际应用价值的多传感器多目标跟踪算法【５ｑＪ。近年来随着仿生算法的日益成熟，一些研究者将此类算法应用于多目标数据关联中，做出了初步探索１８】。本文以孓维分配算法为基础，结合蚁群算法和遗传算法在解决组合优化问题中的优势，以遗传算法的染色体模型构造蚁群个体的信息素编码，充分体现了种群多样性原则，同时对信息素局域扩散模型进行了完善。仿真实验表明，改进后的数据关联算法在执行时间和关联准确度上都有明显优势。

２基于组合优化的多目标数据关联方法

２．１

多目标数据关联基本形式

当观测区域有』ｖ个传感器对空间中的不同区域

进行观测时，数据关联问题即是将系统当前所有观测分配给对应航迹的过程，Ｄｅｂ等人将数据关联问题的组合优化形式描述为广义ｐ维分配问题【３Ｊ，当维空间大于等于３时，数据量的膨胀会使其演化为ＮＰ－难问题，如果考虑检测概率和虚警情况则更无法在多项式时间内获得最优解，粒子群算法、遗传算法等智能算法在处理组合优化问题上的优势则

可以提供有效地解决途型９’１０１。本文采用拉格朗日

松弛算法，将Ｓ一维分配问题松弛为一系列低维分配问题（２一Ｄ较适宜），在低维分配问题中同时结合蚁群算法与遗传算法在寻求最优解问题上的优势，根据源于相同目标的量测约束指导蚁群的初始化，信息素构成以及交叉变异策略，在有限的迭代次数内找到最优解，即实现了数据关联。

２．２

广义Ｓ一维分配算法与多目标数据关联

拉格朗日松弛算法可以将Ｓ一维分配问题转化

为一系列松弛的２维分配问题来求解，其方法是通过拉格朗日乘子将约束条件代入到代价函数中，并使松弛２维分配算法问题的代价最小化，由此可以得到一个真实解的下界，而可行解则是真实解的一个上界。两者之差被称作近似对偶间隙，在每次迭代中不断修正拉格朗日乘子，使得对偶解和可行解趋于一致。

孓维分配问题是将ｋ时刻，来自于Ｓ个序列的‰个量测ｓ＝ｌ，２，…，Ｓ进行关联。设Ｒ，ｂ，…，‘为Ｓ维空间中，满足ｉｌ，ｉ２，…，‘所有Ｓ维条件的操作，并且肛一…；：｛ｏ，翌、銎仃，则孓维分配问题的数学模＆，¨‘２１１，则３一维分配Ｉ口Ｊ赳削裂子俣Ｌ１＇

士ｈ符

驴～Ｉ

ｏ

型可以描述为

万方数据

，ｌＩ

啦

＾．

．，＝驷ｎ∑∑…∑％．‘以驴‘

＾也‘‘＝０ｂ＝０

ｉｊ＝０

其约束条件为

主羔…羔Ｒ如…。：１，‘：１，２，…，％

＾＝Ｏ／２－－ｏ

‘一ｌ＝０

一∑忡

羔唧；

％∑：ｌ：＝

～∑坤

Ｒ

．ｏ

＝

２

％

∑ｎ２…∑ｎｓ－２艺Ｂ驴‘：ｌ，‘：１，２，…，啊

其中，气曩．‘可表示为满足Ｓ维约束时对应的时间、效益等条件。其对偶问题的代价为

吒≯，“＝蝉ｎ（气≯．‘一％），Ｖ‘＝１＇２，…，，ｌｌ，

Ｖｆ２＝１，２，…，ｔ１２，…，ｖ／，一ｌ＝１，２，…，％一ｌ

则其一系列对偶子可表达为

∞‰）＝恶蒜，‘喜％＾．．－

若缈：…＝１，令ｒ／（ｆ１，ｆ：…ｆ川）＝ｆ川，

‘

。

ｑＱ０—１

‘

一’‘

Ｖｌｌ＝ｌ，２，…，ｌｌ，Ｖｆ２＝１，２，…ｎ２

ｏＶｔ一２＝１，２，…以一２，

ｖ／，一ｌ＝ｌ，２，…／＇ｌｓ—ｌ；

∑‰…“＝１，Ｖｉ２＝ｌ，２，…，，１２，…，Ｖｉ，一ｌ＝１，２，…州ｎｓ∑‰≮。＝１，ｖ／，＝ｌ，２，…川ｎａ一，ｖ／，一２＝１，２，…，ｎｓ一２

则问题被分解为娶１维的分配问题，以此类推最终

可转化为２维分配问题，进而可利用优化算法求得最优解，此时的解属于原问题的目标解下界，通过不断修正拉格朗日乘子使对偶间隙趋近设定的阈值，从而得到问题的理想解。

３蚁群一遗传算法应用于数据关联

多维分配算法的目的是求解全局最小化代价函数，每个蚂蚁个体所建立的关联对记为一个划分，整个种群所获得的就是一个划分集合，经过多次迭代后，整个种群会趋向于代价函数最小的关联即最优值。ＡＣＤＡＩｓ］对蚁群算法应用于多目标跟踪进行了初步的探讨，但对算法的参数设置、收敛能力都未

进行深入探讨。将蚁群一遗传算法相结合［１１，１２］能够

第６期袁东辉等：基于蚁群—遗传算法的改进多目标数据关联方法

１９

充分利用２种算法寻优性能上的优势，而目前的研究多属于过程融合，即将问题的求解过程拆分后使用２种或多种智能算法分别求解，对解空间存在２次优化的过程，在每个单独求解阶段算法仍受到自身缺点的限制，如遗传算法参数设置复杂且对性能影响较大，蚁群算法则存在前期收敛速度慢的缺陷。本文通过对蚂蚁个体及信息素模型的构建，充分融合了２种算法的寻优特性，为解决多目标数据关联问题提供了一种新的可行方

法。将蚁群一遗传算法应用于数据关联主要包含着２个方面：一是航迹一观测对的建立，二是信

息素模型的设计。第一点决定了关联的准确率，而第二点则会对算法在寻优过程中的执行时间和迭代次数产生影响。３．１航迹选择模型

在一次观测的回波中会存在大量的观测值，而将这些观测与目标进行关联的过程中，需要对过滤杂波和噪声后的观测数据进行遍历，针对数据关联

问题本文中采用的蚁群一遗传算法确定的路径定义为：所有航迹一观测对距离的和１８】。同时在基本

蚁群算法的基础上，做以下补充假设。

假设１信息素存在于每个观测上，其值会随着

航迹一观测对的建立而增加，随迭代次数、时间而

减弱。

假设２每个航迹会根据一定的概率选择观测，

此概率是信息素强度和航迹一观测对之间能见度

参数的函数。

假设３每个航迹和观测具有一一对应关系。假设４阈值设定，航迹不会选择距离大于阈值的观测相关联（阈值初始为无限大，其后随迭代不断修正）。

３．２蚁群信息素模型

ｔ（ｔ）表示ｔ时刻观测ｉ上所保持的信息素大小，由２部分组成，一是经过ｆ的蚂蚁所滞留的信息素，二是当有蚂蚁经过ｆ邻域内的其他观测时产生的叠加，可以用下式表达：

Ｉｏ）＝４０）＋∑△ｔＯ）

（１）

其中，Ｍ代表ｉ邻域内的所有观测，蚂蚁ｋ（１≤七≤，，ｚ）在为航迹选择观测的过程中，将根据观测上滞留的信息素随机地选择关联。每只蚂蚁确定由航迹ｆ指向观测＿『的关联可以根据下式确定。

万方数据

ｌａｒｇｍａｘ｛【气（ｆ）【％ｒ］），ｑ＜ｑｏ

【．，，其他

其中，Ｕ。表示蚂蚁ｋ在本次关联中在当前航迹点允许选择的观测列表，巩为关联ａ血的能见度（启发信息），一般取１１，。＝１１九；ｑｏ是初始设定的参数，ｑ是一个随机采样的数，且卯，口∈［０，１】；Ｊ是一个随机变量，作为蚂蚁ｋ将航迹ｉ分配给观测Ｊ的概率可按下式计算得到。

承归』嚣器小玑∽露∽＝｛≤㈨ｒ时刊～‘

（３）

１０，其他

其中，口、∥分别表示观测上的残留信息和启发信息对蚂蚁选择转移方向时的影响权重，简单来讲口代表了信息素对蚂蚁个体的影响程度，而∥则代表了蚂蚁个体对信息素的采纳程度。

结合遗传算法的某些特征本文对信息素模型重新构造，根据自然界中的现象，同一蚁群中的蚂蚁个体也存在着优劣之分，因此本文在构造蚁群时随机为每只蚂蚁分配一系列二进制的０一ｌ编码作为每个个体的初始信息素强度。当种群的数目小于６０时，６ｂｉｔ的２进制编码就可以满足为每个蚂蚁个体都分配一个不同编码的需求（如１００１１０代表初始信息素值为７６，０１１０１０代表信息素值为５２），并对信息素模型做如下补充假设。

假设５每只蚂蚁携带的信息素值区间为【０，１１。假设６蚂蚁所经过路径上的信息素，会影响其邻域空间内的其他节点信息素。在此，规定某一节点的信息素会影响半径为ｒ范围内的其他节点，其浓度与距离成反比，并且只有不同个体之间的信息素才能产生叠加。

假设７当经过常量ａ代后，对蚁群个体进行交叉、变异操作，更新种群中的个体信息素。

设有ｍ只蚂蚁，ｎ条航迹，Ｒ。和匙分别代表未选航迹集合和已选航迹集合，初始状态下尺。为

所有航迹的集合，尺。为空，其算法流程如图１所示。

种群中的蚂蚁在遍历所有航迹时首先从未选航迹集合中选择一个航迹点，按照转移规则，即启发函数来选择对应的观测，随后将此航迹加入到已选航迹集合中，同时更新邻域内的其他观测点的信息素浓度值，当所有蚂蚁完成一次路径选择后，

通信学报

第３２卷

ｍ只蚂蚁置于ｎ条航迹上

从凰中选择航迹Ｒ

按费用最小原则分配航迹Ｒ给观测ｋ

二［

Ｒ－＞见

Ｒｓ．＞Ｒｗ，风置空

———１——一

更新ｋ邻域内其他Ｉ否观测的信息素值

《翁≮登纱

Ｉ是否

若Ｒ。为空

．．．．．．．．．．．．．：Ｉ对蚁群进行交叉

！．．．．．．．一了‘

变异操作

丫

是否达到最优解

军繇到预淤至

是

结束

图ｌ

ＡＣ－ＧＡＤＡ算法流程

按照力珑。更新阈值设定，五为常量，算法在执行

过程中对于每次只有很小概率与航迹关联的观测点或在其阈值区域内没有对应航迹的观测点将作为杂波或噪声进行舍弃。种群中蚂蚁个体所携带的染色体及交叉变异算子产生子代的示意如图２、图３和图４所示，如果达到预设的种群更新代数时，则按照交叉变异原则产生新的个体，采用轮盘赌的选择策略替换当前种群内的个体。利用遗传算法控制种群交叉变异的过程如下。

步骤１

ｔ＜－－ｌ，随机生成Ⅳ个蚂蚁个体形成第

～代种群Ｐｌ，评价种群Ｐｌ的个体差异度值。

步骤２交叉：生成如下子代种群９。１）基于差异度值从只中选择２个个体ｘ和Ｙ；２）应用交叉算子生成子代，并添加到Ｑｆ中。步骤３变异：对每个个体ｘ∈Ｑｆ按照预设的变异率应用变异算子。

步骤４选择：从Ｑｆ中选择Ⅳ个个体并拷贝进

入种群ＲＩ。

特征序号信息素编码

图２

蚂蚁个体携带信息素编码

万方数据

切点

切点

特征序号ｌ２３４５６

父代１

信息素编码ｌｌＯｌＯｌ

特征序号

ｊ

２

３

４

５

６

予ｌ弋

Ｆ

１ｒ

１ｒ

ｒ

信息紊

编码ｌｌＯ１

●１

●０

特征序号

ｌ

２

ｌ３

４

５６

父代２

信息素编码

ｌＯｌ

０ｌ１

图３交叉算子产生子代示意

随机选择２处特征编码

Ｉ

上

特征

序号ｌ

２

３

４

５

６

父代

信息素编码

ｌ｛ＯｌＯ｛

“ｌ。

＼＼、／

插入对应位置其他位顺廷特征序号

１

２

３４５６

子代

１ｒ

信息素编码

１

Ｏ

ｌＯ１ｌ

图４变异算子产生子代示意

步骤５种群差异度判断：基于个体差异函数，对种群户■ｌ计算其个体差异度值。

步骤６如果满足终止标准，则返回当前种群；否则，ｆ÷－ｒ＋ｌ，并转向步骤２继续执行。

为保证初始及关联过程中种群的多样性，本文参考了ＫｏｎａｋＡ【１３］控制种群适应度的方法，通过减小种群中密集区域的个体从而避免局部最优解的出现，达到获得全局最优解的目的。本文中蚂蚁个体的信息素值通过二进制到十进制的转化及取模运算值域为［０，１】，因此保持种群多样性的算法如下。

步骤１在【Ｏ，１】范围内规范化目标空间上计算任意２个个体Ｘ和Ｙ之间的欧式距离，如下：

ｄｚ（ｘ，Ｊ，）＝

第６期

袁东辉等：基于蚁群一遗传箅法的改进多目标数据关联方法

其中，Ｚ。（ ）为个体求模转化后的信息素值，ｚ严和ｚ产

分别是当前种群中个体信息素的最大值和最小值。

步骤２基于步骤１中得到的距离，对种群中每个个体计算小生境数（ｎｉｃｈｅ似圳＝”ｙＥＰ，

ｒ（‰，ｆ）＝ｒ（ｘ，，）

ｙ，，一｛Ｌ掣ｃｏｕｎｔ）如下：

Ｖｓｈａｍ，。｝

Ｊ

其中，吸。。为小生境大小。

步骤３调整每个个体的信息素值：

ｚ，（ｘ，ｔ）：塑盟

ｎｃ（ｘ，ｆ）

此过程中，ｇ慨定义了一个蚂蚁个体信息素浓度的邻域。位于相同邻域的个体能够互相对其小生境数做出贡献，因此，在比较拥挤的邻域内蚂蚁个体就具有一个较大的小生境数，从而减小其被选中作为父代的概率，小生境方法据此对种群中特定邻域内个体的繁殖进行限制。

为验证算法的性能，本文进行了仿真及对比试验，首先对５目标跟踪进行了仿真实验，在５目标跟踪实验中设传感器的检测概率为Ｐｏ＝０．９，杂波密度满足泊松分布，启发函数为

ｔ（ｆ）＝毒（ｆ）＋∑Ａｋ（ｆ）

（４）

其结果如图５所示。

对于目标在三维空问中的六自由度运动，当仅目标交叉情况下的关联结果如图６所示，ｘ轴与ｙ万方数据

（ａ）原始数据

Ｊ方向／ｍ

（ｂ）关联后的数据图５

５目标数据关联结果

ｘ方向／ｍ

图６两目标交叉运动

表１

算法性能比较

针对ＡＣＤＡ和ＡＣ—ＧＡＤＡ２种优化算法，本文３组不同目标数进行了关联，４实验对比及分析

考虑横向与纵向运动时，航器的升降、偏航运动、横滚运动和俯仰运动被忽略即运动由侧向位移和纵向位移组成。实验中观测的采样时间间隔设为１，系统噪声和观测噪声服从均值为零的高斯分布，两轴则分别代表航器沿侧向与纵向的运动位移，两目标均匀速运动且转弯角度小于２。。结合图５和图６可以看出ＡＣ—ＧＡＤＡ算法能够正确地完成运动目标的关联。同时本文对ＡＣ—ＧＡＤＡ、ＡＣＤＡ和ＪＰＤＡ３种算法在关联准确率、执行时间上进行了比较，结果见表１，３种算法的关联目标数为５０，其中，ＡＣＤＡ和ＡＣ—ＧＡＤＡ算法中的种群数量取值为４０，算法的执行时间为同等条件下执行５０次结果的平均值。

选取了５０、８０和１００对关联准确率、迭代次数与执行时间进行了单独的

通信学报第３２卷

比较，结果见表２～表４（其中括号内的数字代表种群大小分别为２０、４０、６０、８０、１００），对于２种算法本文将所有航迹与观测都建立完成关联视为一次迭代过程，从表中可以看出基于传统蚁群优化的ＡＣＤＡ算法在进行数据关联时，由于所关联的目标数固定，因此增加种群数目可以减少迭代次数加速算法的收敛，同时也会增加计算量即算法的执行时间。而改进后的ＡＣ—ＧＡＤＡ算法，结合了遗传算法的特性同时对信息素扩散模型进行了完善，具有更快的收敛速度，迭代次数远低于ＡＣＤＡ算法。在算法关联准确率方面，当种群数大于４０后，ＡＣ．ＧＡＤＡ算法的关联准确率能够达到９０％以上，远高于ＡＣＤＡ算法，当进一步增加种群数量时，虽然关联准确率会有相应的提升，但执行时间也会有小幅增加，结果见表３和表４。ＡＣ—ＧＡＤＡ算法结合了蚁群算法和遗传算法的优点，在性能上取得了较好的效果，

表２

ＡＣＤＡ与ＡＣ．ＧＡＤＡ迭代次数与执行时间比较（目标数５０）

表３ＡＣＤＡ与ＡＣ．ＧＡＤＡ迭代次数与执行时间比较（目标数８０）

万方数据

表４ＡＣＤＡ与ＡＣ．ＧＡＤＡ迭代次数与

执行时间比较（目标数１００）

但初始参数的设置较为复杂，例如需要根据所需种群的大小调整蚂蚁个体信息素编码长度，在工程应用中需要较多的实验和调整才能给出合适的初始参数设置。

表５中给出了ＪＰＤＡ算法与ＡＣ．ＧＡＤＡ算法在关联准确率与算法执行时间上的对比数据，其中括号内的数字分别代表了２种方法关联的目标数目及ＡＣ．ＧＡＤＡ算法的种群大小，对于每组目标分别进行了１００次实验，取关联准确率与执行时间的平均值作为最终的实验结果。从表５中数据可以看出，随着关联目标数量的增加，ＡＣ．ＧＡＤＡ算法始终保持着９０％以上的关联准确率，同时算法的执行时间也远远优于ＪＰＤＡ算法。

表５

ＪＰＤＡ与ＡＣ．ＧＡＤＡ关联准确率与执行时间比较

第６期《§＃＃：＃ｆ觳群—遗＊＃涪∞改鞋多日镕敦＊＊ｇ自法

由表１至表５的实验数据可以看出，与传统的ＪＰＤＡ算法相比ＡＣ—ＧＡＤＡ算法在保证了较高关联准确率的同时，算法的执行时间远远优于ＪＰＤＡ算祛，而与同样基于蚁群算法的ＡＣＤＡ算法相比ＡＣ—ＧＡＤＡ算法在关联准确率与算法执行时间上也都存在明显的优势。

５结束语

本文探讨的方法集中于高目标密度条件下的多目标跟踪问题，利用蚂蚁个体携带信息素编码并通过交叉变异机制对全局信息素模型进行更新，有效地提高了数据关联的效率和准确率，结合遗传算法加速收敛的特性提高了数据关联的执行速度，同时通过改进信息素模型以及调整种群适应度避免了局部极值的出现，从而在多目标数据关联中达到了较高的准确率和执行速度。在实际应用中多目标数据关联具有报高的实时性要求，因此在保证关联成功率和准确率的吲时如何进一步提高算法的收敛速度，是下一步研究的关键内容。参考文献

…ＲＥＩＤ

ｏｎ

＾…ａｔⅡｃｏｎ口１９７９．２４＜６）：ｓ４－９０

Ｄ

Ａｎ

ａＩｇ∞ｈｆｏｒ№ｋｉｎｇｍｕｌｆｉｐ［ｃｂ口ⅢＩＥＥＥｍ

【２１

ＢＬＡＣＫＭＡＮＳ．ＰＯＰＯＬ］Ｒ

Ｄｅｓｉｇｎ划ＡｎａｌｙｓｉｓｏｆＭｏｄ咖Ｔｒａｃｋｉｎｇ

Ｓｙｓｔｅｍ［Ｍ１

８０…Ａ帜ｈ№ｕｗ

ｌ辨≯

【３１

ＤＥＢ

ｓ，ＹＥＤＤＡＮＡＰＵＤＩｍｕｌ…ｍｕＩｔｈ‘蚪ｓｎｋ

Ｍ，ｐＡＴＴＩｐＡＴＩ

Ｋ

Ｒ

Ａ

ｇ∞ｃＴａＩ“Ｓ－Ｄ

∞ｓｌ＂ｍｃｎｔ

ａｌｇｏｆｉｔｈｒａ

ｆｏｒ

ｅａｔｉｍｔｌｏｎ［Ｊ］

，ＥＥＥｌｍｏＲＡＥＳ，１９９７，３３（２）：５２３－５３８

【４ｌ

ＤＥＢ

Ｓ，ｐＡＴ［Ｔ［ＰＡＴＩＫ＆ＢＡＲ－ｓ｝【ＡＬＯＭ

ＶＡ

ＩＥＥＥＴ—ｃｔｌｏｍｓｏｒ－ｍｕｌｆｉｔａｒｇｅｔｄａ—ｉａｔｉｏｎ

ｏⅡＡｃｍ…ｄＥｌ—ｎｉｃ

ａｌｇｏｒｉｔｈｍｆｏｒ

ｈＨｍ目∞…∞｛月ｍｕｌｔｉ”ｎ－

Ｓｙｓｍｓ，１９９３．２９（２ｋ

５６０－５６８【ｓ１

ＢＬＡＩＲ

日血ｆｄｌ…Ⅻｄｔｒａｃｋｉｎｇ“ＥＣＭ［ｆｌ

ＷＲＷＡＳＴＯＮＧ＾Ｋ１ＲＵＢＡＲＡＪＡＮｔ

Ｂ％ｃｈｍ

ｆｏｒ

ＩＥＥＥ

Ｔ—ｉｏｎｓｏＭ“一

，ｐａ∞∞ｄＥｌｅｃｔｒｏｎｉｃＳｙｓｔ２｜｜ＩＳ，１９９８，３４（４）：１０９７－１１１４ｍｌ

ＫＩＲＵＢＡＲＡＪＡＮＬＢＡＲ－ＳＨＡＬＯＭＹＢＬＡＩＲ

ＷｋＩＭＭｐＳＡＦｆｏｒ

ｒ８ｄⅢｍ∞雄帅哪Ｉ盐ｄ

ｔ一∞ＡｅｆｏｓＩｍｅ

ａｎｄＥｌｍｏｎｉｃＳｙ‰１９９ｓ３Ｗ４ｌ＝ＩｌＩ

ｕ＇ａｃｋｉ，，ｇｈＭｈｎｍｗｉｔｈＥＣＭ啪［ＥＥＥＴｎ—

【７】ＤＡＥＢ。ＯＵＲＥ，ＢＡＲ－ＳＨＡＬＯＭ

Ｙ

ＩＥＥｌⅫｔｍｂｎｇ

１ｗｄｏ…ｏｆ…Ⅷｎｇ

‘％№ｉｎｔｈｅ

Ａ㈣５－１１３３

ＩＭＭ

ｐａｃｅ

ｄ

Ｅｌ—ｎ［ｅ

ｐ…ｏｆ

９１ｎＵ】Ｓｙｓｔｅｍｓ．１９９８，３４（３１．９９０１００３

【８１＆自，ｍ镕镕，＊ｍ￥一＃￥十“群算法∞＃日＃目ｇ戤＊＊Ｂ

女＆｛月自十｝报．２００８，３６（３）：５８６－５８９

ＫＡＮＧ

Ｌ

ＸｌＥ

ＷＸ

ＨＵＡＮＧＪｘＡＣＡ

ｂａｓｅｄ

ｄａｌａ—ｉａｔｉｏｎ

ｍｅｔｈｏｄ自ｒｍｕｉｔｉ－ｔａｒｇｄ

ｏｍｃｋｉｎｇ［Ｊ］Ｃｈｉｎ口Ｊｏｕｒｎａｌ

ｏｆ

Ｅ１…“

万方数据

２００８．３ｑ３１＝５８６－５８９

【９】朱＾ｉ，※焕＃，＆Ⅱ桂一＃基十模＊自ａ＆ＧＡ∞ｒＲＳ镕ｎ目

算＆四《＾＊ⅢＳ＾Ｉ目＊．２００４．１７（Ｉ）：８２－８６

ｚＨＵ

Ｌ

Ｌ，ＺＨＡＮＧＨＣ，ＪＩＮＧＹＺＡ＃ｌｋｍＩｊｚｃｄ

Ｓ－Ｄ％｜Ｆ“…ａｌ

ｇ叩血ｍｈ枷仰ａｆｕｚｚｙａｄａｐｔｉｖｅＧＡ［Ｊ］ＰⅢ咖Ｒｅｃ０印ｎ｜佣ａｎｄ“Ｐ

ｔｉｆｉｃｉｌｄＩｎｔｅｌｌｉｇｏｎｃｅ，２００４

７１１１８２－８６

［１０ｌⅫ蚌薇澎坤．杨莘元基ｆ＃十＃算法∞ｒ卫ｓ镕＊Ｅ＊法ｍｇ弹

；Ⅻ｝≠ｍ．２００５，２５（４）：７９１－７９５

ＦＩＵＷＷＺＨＡＯＬＹⅣ岫ＳＹＡｇｅｎｅｒａｌｉｚｅｄＳ

ｄ…Ｉ咖■∞ｓｉｇｎ—

ｌｍｍａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｏＢ

ＰⅢｃｌ…８ｍ

ｏｐＩｉｍｉⅫｍ【口Ｊｏｕｒｎａｌ

ｏｆ

Ⅲ＃ｄＩ∞，Ｒｏｃｋｅｔｓ。Ｍ ∞¨％ａｎｄＧｕｌ＾‘％２００５－２５（４）：７９１－７９５

¨ＩＩ自☆峰，＊％政基ｆａ＊算＃的％古蚊＃算‰【口＊算机Ｉ程与＆

月００％ｍ¨６）：４２４５

ⅪＡＯＨＥＴＡＮＧｚ脚ｈⅪ删∞岫出硎帅ｈＢＨ帆蚪妇ａ培｝

Ｔｉ山ｍ［ｆｌ

ｃｏｍｐ听ｈ培ｍ自吨口“＾刚船妇Ｅ２。∞＾“ｌ６）．４２＿‘ｔ５

【Ｉ２】刘被，橱镕目，目Ⅲ越融ｅ＃ｆ＃Ｓ蚁＃＃法∞ｎｘＭＬ群件智能

搜索【Ｊ】．计算机目Ｅ５＆＆，２００Ｓ，４５（ｓ）：ｔ３７１—１３７８ＬＩＤ

Ｂ

ｙＡＮＧＬ￣ＬＬＥＩＧＹ

Ａｎ

ｉａｔｅｌｌｉｇｃｎｔｉｚｅｄｍｃｍｏｄ

ｏｆ）ｍ

ｑｕｅｒｙｆｏｒｍⅢ６。Ｍ％ｔ…叫ｍｉ训∞ｃｏｍｂｉｎｅｄ

ＰＳＯａｎｄ

ＡＣＯ［－ｑ

Ｊｏｕｒｎａｌ

ｏｆ

Ｃｏｍｐｕｔ目№ｅａｒｃｈⅫｄ

Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５｛８）＝

２３７１－１３７８

【Ｉ３】ＫＯＮＡＫ＾ＣＯＩＴ

Ｄ砒ＳＭＩＴＨ

Ａ

Ｅ

Ｍｕｌｂ．０％∞“＂ｏｍ删口６册

ｍｍｇＲ∞ｅｔｉｃａｌｇｏｒｉｔｈｍｓ：ａ

ｔｕｔｏｒｉａｌ［Ｊ］ＲｅｌｉａｂｉｌｉｔｙＥｎｇｉｎｅｅｒｉｎｇ４一

ＳｙｓｔｍＳａｆａｙｌ２００６，９Ｉｆ９１：９９２

１０）７

作者简介

袁东辉（１９８０．），男，吉林长春人，

吉林大学博士生，丰要研究方向为智能算；击、语义检索、集成电路测试集优化等。

刘大有（１９４２一），男，吉林长春人．

吉林大学教授、博十生导师，主要研究方向为知识丁程和Ｅｓ、人工智能、时空推理、数据挖掘与统计关系学习、智能软件等。

申世群（１９７７．），男．黑龙江七台河

慧早Ｃ＿¨

人，吉林大学博士生，主要研究方向为时空推理、地理信息系统厘其应用。

基于蚁群-遗传算法的改进多目标数据关联方法

作者：作者单位：刊名：英文刊名：年，卷(期)：

袁东辉， 刘大有， 申世群， YUAN Dong-hui， LIU Da-you， SHEN Shi-qun

吉林大学知识工程与符号计算教育部重点实验室,吉林长春130012;吉林大学计算机科学与技术学院,吉林长春130012通信学报

JOURNAL ON COMMUNICATIONS2011,32(6)

本文链接：http://www.77cn.com.cn/Periodical_txxb201106003.aspx

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新互联网资料基于蚁群-遗传算法的改进多目标数据关联方法全文阅读和word下载服务。