遗传模糊聚类算法在数据关联中的应用概要.docx
《遗传模糊聚类算法在数据关联中的应用概要.docx》由会员分享，可在线阅读，更多相关《遗传模糊聚类算法在数据关联中的应用概要.docx（13页珍藏版）》请在冰点文库上搜索。
遗传模糊聚类算法在数据关联中的应用概要
第17卷第3期2010年3月
电光与控制
ElectronicsOptics&Control
V01.17No。
3Mar.2010
遗传模糊聚类算法在数据关联中的应用
胡傲,冯新喜,王冬旭,郭威武
（空军工程大学电讯工程学院,西安710077
摘要:
针对传统数据关联算法存在计算量偏大或关联精度不高的问题,提出了一种利用遗传模糊聚类策略来求解数据关联问题的算法。
该算法将多传感器多目标的数据关联问题看作是一类约束条件下的组合优化问题,先通过对同一时刻不同传感器提供的量测按照其相似性用遗传算法进行模糊聚类,再用聚类后的等效量测对各目标的状态进行估计。
聚类方式的改进不仅增加了算法的局部寻优能力,有效地减少了计算的复杂度。
而且还具备一定的野值剔除能力。
仿真结果表明该算法关联精度较高,计算量适中,具有一定的工程应用价值。
关键词:
数据关联;多目标跟踪;模糊聚类;遗传算法
中图分类号:
V271.4;TN953文献标志码:
A文章编号:
1671—637X（201003—0030—05
ApplicationofGeneticFuzzyClusteringAlgorithminDataAssociation
HUAo,FENGXinxi,WANGDongxu,GUOWeiwu
（InstituteofTelecommunicationEngineering,AirForceEnsineeringUniversity,Xi’an710077,China
Abstract:
Traditionaldataassociationalgorithmhasthedrawbacksoflargecomputationcostandlowassociationprecision.Tosolvetheproblem,weproposedageneticfuzzyclusteringbaseddataassociationalgorithm.Takingthemulti—target,multi—sensordataassociationasacombinationoptimizationproblemunderatypeofrestrictions,fuzzyclusteringweremadeforthemeasurementdataofdifferentsensorsatthesynchronizedinstantaccordingtotheirsimilarity,andthentheclusteredequivalentmeasurementWasusedtoestimatethestateofeachtarget.Theimprovementofclusteringcanstrengthenthealgorithm’Slocaloptimizationcapabilityandreducethecomputationcomplexityconsiderablywhileeliminatingsomeoutliers.Thesimulationresultsshowthatthepresentedalgorithmhashighassociationprecisionandacceptablecomputationalcomplexity,thus
ispracticaHyvaluable.
Keywords:
dataassociation;multi—targettracking;fuzzyclustering;geneticalgorithm
0引言
密集杂波环境下的数据关联问题一直是多机动目标跟踪领域一个相当重要但又非常棘手的问题。
国内外众多学者在这方面做了许多工作,有关数据关联问题的理论和技术近年来都取得了很大的进步。
具有代表性的算法主要有:
最近邻法（NN、多假设跟踪法（MHT、联合概率数据关联法（JPDA、广义多维分配算法（S—DAssignment以及Viterbi算法等¨。
1;此外
收稿日期:
2009一ol一08修回日期:
2009—03—18
基金项目:
军队科研基金资助项目（kj06104
作者简介:
胡傲（1984一,男,湖南岳阳人,硕士生。
研究方向为多源信息融合,目标跟踪技术。
也有不少学者通过对关联问题进行建模,利用模糊逻辑、神经网络、遗传算法等智能计算方法和技术来求解模型的最优解H。
1,最终达到正确关联的目的。
文献[4]利用基于梯度算子的模糊聚类算法来解决数据关联问题,但是这种聚类方法对于初始值的选择很敏感,容易陷入局部最优,从而影响关联的效果。
文献[7]在利用遗传算法对量测集进行聚类时加入模拟退火算法,以期减小对初始聚类中心选择的依赖性,但模拟退火算法的加入势必增加计算的复杂度,影响跟踪的实时性。
本文根据数据关联问题的特殊性,在应用遗传模糊聚类算法求解关联问题时,放松了部分已知条件,并对染色体的选择、种群的编码方式等方面进行了改进,相对于文献[4]中的算法而言,在没有明显增加计算量的前提下,提高了算法的关联精度和滤
万方数据
第3期胡傲等:
遗传模糊聚类算法在数据关联中的应用
3l
波效果。
1
多目标数据关联问题的数学描述
假设M部雷达跟踪JI、r个目标,则目标t的状态方
程为
r（k+1=F（kF（尼+G（ku（||}+移（.|}（1雷达_『在k+l时刻对目标t的量测方程为Z（k+1=日（k+1刀（k+1+埘（k+1（2式中:
F（k为状态转移矩阵;日（||}为量测矩阵;r（后为第t个目标在k时刻的状态;G（尼为输入控制矩阵;“（后为已知输入或控制信号;过程噪声∥（五和量测噪声tt,（k+1都为零均值的高斯白噪声序列,且它们与初始值之间互不相关;z,（五表示k时刻第.『个雷达提供的全部量测数据,那么此时融合中心接收到的量测集合为z={互（五},_『=1,2,…,肘。
由于目标跟踪环境的不确定性以及传感器本身观测误差的存在,导致不同传感器关于同一目标的量测在融合中心处并不重合,而是在目标真实值附近成团状分布。
模糊理论在处理这种不确定性问题时具有良好的性能,将数据关联问题看作是一类约束条件下的模糊聚类问题,采用模糊聚类方法来求解数据关联问题,可以有效地简化多传感器多目标数据关联问题的
复杂度。
2
基于增强型遗传模糊聚类的数据关联算法
2.1改进的模糊C均值聚类算法
J.C.Bezdek等人在普通聚类的基础上,利用模糊集合概念提出了模糊分类方法,认为被聚类对象集合中的每一个对象都是以一定的隶属度隶属于某一类。
每一类被看作是对象集合上的一个模糊子集,每一种这样的分类结果对应着一个模糊划分矩阵,通过模糊划分矩阵可以求得各类的中心,在数据关联问题中即为目标某一时刻的等效量测。
设k时刻融合中心接收到的量测集{z,},_『=1,2,…,肘为要聚类的样本集{蔸i}√=1,2,…,n。
k一1时刻已经形成的稳定航迹数c为待聚类的数目。
把样本集中的n个量测按照一定的准则划分为c类,那么对应的模糊分类矩阵u为
U=
/Z11/1,12
1221//'22
“cIUC2
U满足下面3个条件:
1/J,#∈[0,1],即每一个量测对某一个目标的隶属度在0与1之间取值;
2∑如=1,即每一量测对所有目标的隶属度之
和为1;
3∑如≥1,即某一时刻目标被检测到,如果某
时刻没有该目标的量测,可以用前一时刻的预测值加
以代替。
模糊c均值聚类算法是一种基于目标函数的聚类方法,它把聚类归结为一个带约束的非线性规划问题,通过各种优化方法来求解该问题,从而获得数据集的模糊划分和聚类中心。
通过式（3和式（4反复修改聚类中心y和分类矩阵u来实现动态的迭代聚类,使得具有相似属性的对象被归并到同一类中,而不同类之间的相似度最小。
P“乙弘qxiq=上},i=1,2,…,c
（3
Pm2pF
f
!
\m_1’
p。
:
』垫_I,_『:
1,2,…,/7,（4
p日2———————————T’J2
I,z,…,L斗,
砉（竞与佃。
1’
但是这种基于梯度算子迭代求解聚类中心的方法对于初始值的选择很敏感,聚类初始中心选择不当将影响量测的分类,最终有可能出现滤波发散现象。
遗传算法在求解聚类问题时,利用多个个体并行进化机制,可以在很大程度上减少量测聚类结果对初值选择的依赖性,从而有效提高了数据关联精度和目标跟踪效果。
在模糊C均值聚类算法中,由于引入了归一化约束条件2,在样本集不理想的情况下可能会导致分类结果不好。
比如,某个野值样本远离各类的聚类中心,本来它严格属于各类的隶属度都很小,但是由于约束条件2的限制,将会使它对于各类都有较大的隶属度,这种野值的存在将影响聚类的最终结果,为了克服这种缺陷,将隶属度归一化的条件放松n】,让所有样本
对各类的隶属度总和为n,即:
∑∑如=n。
在这个
新的约束条件下,计算类心的式（3仍然不变,而式（4则变成:
!
/
l
、（m—I
nl页而J
肛#2—————————工;
砉（最%m。
1’
i=1,2,…,c;.『=1,2,…,乃
（5
显然,用改进的模糊C均值得到的隶属度值会大于1,并不是真正意义上的隶属度函数,按照式（6对
蛳蛳;蜘
●
●
●
万方数据
32电光与控制第17卷
其进行归一化处理即可消除由于隶属度值大于l而对
最终聚类结果的影响。
弘7d=粤,i=1,2,…,c∥=1,2,…,n（6∑心
‘=l
2.2增强型遗传算法求解聚类问题
遗传算法（GeneticAlgorithm是由Holland创建的一种启发式搜索算法,它将每个可能的解看作是种群中的一个个体,并将每个个体编码成字符串的形式,根据预先设定的目标函数对每个个体进行评价,给出一个适应度值。
开始随机地产生一些个体（候选解,根据这些个体的适应度值利用遗传算子对这些个体进行操作,得到一群新的个体,这群新的个体由于继承了上代的优良性状,因而明显优于上一代,这样逐步引导着种群朝最优解的方向进化。
文献[9]已经证明,在一定的条件下,遗传算法可以以概率1收敛到全局最优解。
2.2.1编码方式的改进和种群初始化
文献[10]根据量测与目标的对应关系,采取对划分矩阵进行c进制编码的方式,这实质上是一种硬划分,并且随着数据集的增加,这种编码方式的计算量成指数形式增长。
若采用对类心进行编码的方式则可以明显地减小算法的搜索空间,从而提高跟踪的实时性。
二进制自然码存在一个缺点,即有时数值上极小的变化却要求很多比特位发生变化,从而影响遗传算法的进化速度。
而Gray码中相差一个单元的码字之间只有一个比特位不同。
因而采用Gray码往往会比自然码获得更好的效果。
同时利用某一时刻各目标跟踪门内的量测集来实时更新编码的范围也在一定程度上减少了计算量,增加了算法的精度。
本文中假设初始种群在搜索范围内服从均匀分布,染色体的编码长度则为|i}一1时刻已经形成的稳态航迹数c与量测维数P的乘积。
2.2.2自适应函数的构造及遗传算子的选取对于基于目标函数的模糊聚类问题,其最优聚类结果对应于目标函数的极小值,故定义GA的适应度函数为
1
∥（u,V=——i——I_——一（7∑∑舻;D2（誓,q+f
式中:
模糊加权指数m∈（1,∞;D（・为相似性测度函数,一般取Mahalanobis距离;f为一给定正常数。
并且需要在上一节已给限定的基础上对隶属度矩阵‰i]…作如下修改:
f11mq’
‘:
fzI部。
:
』堕E生‘（8‘=fzI部d=—二∑L二旦——r（8砉1（矗1J可佃。
1’i=、\_=‘i—ui,’
‘≠12j部#=0,Vi∈t,∑晰=1（9
式中:
‘={i11≤i≤c,O（xj,q=0};,i={1,2,…,c}一‘。
在利用遗传算法求解聚类问题时对所有算子都选用,只不过赋予其不同的使用概率,使其按概率进行操作。
为了防止遗传算法早熟或者陷入局部最优,采用改进的选种算子和自适应的交叉、变异算子,具体参数的选取请参看文献[9],由于篇幅限制本文不再详述。
2.2.3自适应函数的构造及遗传算子的选取
为了使遗传模糊聚类算法能收敛到极值点,首先在算法中引入梯度算子,然后把进化结束的准则改为范数准则。
设只对聚类中心进行编码,则梯度算子的使用过程为:
将个体S进行解码,得到V=Ec（s,按照传统方法求解相应的u,再迭代得到新的y,然后将这个新得到的y编码后加入到群体中去。
对群体中的最优个体s使用梯度算子得到S’,若llU（S一U（S7Il≤占,则算法终止;否则继续进化。
在上述过程中,遗传算法与传统的模糊聚类算法实际上同时运行,这种基于增强型遗传模糊聚类的方法不仅提高了算法的分析性能,同时也加快了算法的收敛速度,但是计算量不会显著增加。
2.3目标的状态估计
由于前一时刻形成的稳态航迹数目已知,故在利用本文中的聚类算法求得各目标的等效量测番后,用压缩后的量测对目标t进行Kalman滤波,即可得到基于融合量测的各目标状态的滤波值和协方差值,从而完成航迹的维持和更新。
3仿真实验及结果分析
本文中的所有仿真都是在二维平面上进行的,并且假设各雷达提供的量测数据时间上已经同步,空间上已经转化为同一个坐标系。
为了增加实验的针对性,在得到各个目标的等效量测后,采用最大加速度值自适应的当前统计模型对目标的状态进行估计。
3.1仿真场景设置
仿真采用3部雷达组成的集中式融合系统跟踪4个目标,它们的监视区域完全重合。
各雷达扫描周期r都为1s。
目标1和目标2平行飞行,初始状态分别为[1000m;150m/s;0m/s2;6000m;100m/s;0m/s2]和[1000m;150m/s;0m/s2;4500m;100m/s;0m/s2]两目标0—20s做匀速直线运动,21—40s做匀加速运动,加速度值都为[6m/s2;8m/s2],4t~60s继
万方数据
第3期胡傲等:
遗传模糊聚类算法在数据关联中的应用33
续做匀速直线运动;目标3和目标4交叉飞行,初始位置分别为[1500m;2000m]和[14000m;13500m],初始速度分别为[200m/s;100rn/s],[一120m/s;一180m/s]这两个目标在整个仿真过程中均做匀速直线运动。
3部雷达的观测噪声标准差分别为100m、120m、150m。
杂波以各目标状态预测值为中心,在其lo倍跟踪门体积内服从均匀分布,而每个跟踪门体积内的杂波个数服从参数为A的泊松分布。
其他参数的取值分别为:
检测门限y=16;检测概率P。
=0.9997;机动频率d=0.05;种群数目为NIND=20;染色体长度Len=32;进化代数N=100;kI=0.9;k2=0.6;k3=0.8;后4=0.04;Al=5.0×10—6,A2=1.0×10。
5。
仿真次数NUM=50次。
3.2仿真结果分析
性能的评价采用下面两个指标:
1均方根误差RMSE=,0为状态
的真值;0;为第i次仿真状态的估计值;
个
2每步耗时TBPS5丽历再南,F为算法总时间;NUM为仿真次数;STEP为跟踪步数。
为了描述方便,定义文献[4]中基于梯度算子的模糊聚类的关联算法为方法1,本文提出的基于增强型遗传模糊聚类的关联算法为方法2,利用这两种方法分别对观测空域内的4个目标进行跟踪,跟踪轨迹和部分目标位置及速度的均方根误差如图1一图7所示。
为了便于比较跟踪效果,选取平行飞行中的目标1和交叉飞行中的目标3,对它们x方向的状态估计数据进行分析,y方向的跟踪结果由于篇幅所限,暂不讨论。
X方向位移/m
图1目标真实轨迹和估计轨迹
Fig.1Therealandestimatedtrajectoriesoftargets从图2一图7中可以看出方法2的位置均方根误差和速度均方根误差总体上讲都要比方法1小;图2一图4反映了两种算法跟踪平行飞行中目标的效果,图5一图7则反映了两种算法跟踪交叉飞行目标的效果。
结合这几幅图可以看出,方法2在跟踪平行和交叉飞行目标时,其性能相差不大,但是方法1在跟踪交叉飞行目标时跟踪误差明显增大,这主要是由于方法2采用了改进的模糊聚类算法,并在一定程度上减小了野值对跟踪性能的影响;再者采用方法2进行跟踪滤波时,其收敛速度要比方法l稍快,这可以从图3、图6以及图7中看出;在机动发生时刻,方法2的误差抖动幅度比方法l的误差抖动幅度小,这点在图3和图4中已经反映出来了;对比图2~图4与图5一图7可以得出结论:
无论是跟踪机动目标还是非机动目标,方法2的滤波精度和鲁棒性都比方法1要好。
Fig.2
瑙
整二、
校墨
k3
g\
鉴至
图2目标1的x方向位置均方根误差
TheRMSEoftarget1’spositioninXcoordinate
扫描次数（T=Is
图3目标1的x方向真实速度和估计速度
Fig.3Therealandestimatedvelocitiesoftarget1
inXcoordinate
耍
H凹
器毯
皿制
图4目标1的x方向速度均方根误差
Fig.4
TheRMSEoftargetl’8velocityinXcoordinate
运
钕罢
k墨
窖凹
n涮
峰q
皿
扫描次数（/'--18
图5目标3的x方向位置均方根误差
Fig.5TheRMSE
oftarget3’spositioninXcoordinate本文采用CPU主频为2.8GHz,内存为1GDDR2的硬件平台,在Matlab软件环境中完成整个仿真过程。
表1是在不同杂波密度环境下分别采用方法1和方法2跟踪4个目标时,对各算法每步平均耗时以及
万方数据
电光与控制第17卷
瑙
测
足
钕
随
g
∞
蜷
皿
图7目标3的x方向速度均方根误差
Fig.7TheRMSEoftarget3’SvelocityinXcoordinate表1不同环境下各算法每步计算时间及正确关联概率TableIThecomputingtimeandcorrectassociationprobabilityofalgorithmsindifferentscenarios
每步耗时/一正确关联概率/%杂波密度/A——方法1方法2方法1方法25.0×10—216.4631.280.188.31.0×10—5357.5873.676.985.44结束语
数据关联算法是多传感器多目标跟踪技术的基础和关键部分。
尽管已有很多文献介绍了各种关联方法,但大多数是建立在假设理论的基础上,需要的先验信息较多,难以满足现代战争的实际需要。
将数据关联问题看作是一类约束条件下的组合优化问题,通过建立关联的数学模型,将问题转化为求这类约束条件下的全局最优解可以有效地降低多目标跟踪问题的复杂性。
本文提出的这种数据关联算法,它先将各传感器提供的量测按照其相似性进行聚类,利用压缩后的等效量测进行目标的状态估计,因而有效地减小了计算量。
但是本算法聚类前需事先确定类的数目,即稳态航迹数目,跟踪维持阶段没有考虑航迹的起始过程,这将是今后需要解决的一个问题。
参考文献
[1]BAR—SHALOMY,LIXiaorong.Multi—targetmulti-sensortracking,principleandtechniques[M].Norwood,MA:
ArtechHouse,1995.
[2]李辉,左现刚,张安,等.复杂环境下数据关联算法的研究现状及发展趋势[J].火力与指挥控制,2007,32（9:
30-35.
[3]吴伟,王东进,陈卫东.基于动态多维分配的多基地雷达多目标跟踪算法[J].中国科学技术大学学报,2006,36（11:
1143-1149.
[4]张晓丽.模糊聚类分析在多目标跟踪中的应用[J].国防技术基础,2008（6:
53-56.
[5]韩红,韩崇昭,朱洪艳,等.基于FCM的多传感器融合多目标跟踪的数据[J].系统仿真学报,2004,16（9:
2096-2099.
[6]朱志宇,皇风辉,姜长生.杂波环境下的粒子滤波器数据关联方法[J].电光与控制2008,15（2:
50-54.[7]刘以安,曹奇英,刘同明,等.基于遗传模拟退火算法的机动多目标数据关联问题研究[J].系统工程理论与实践,2001（9:
67-72.
[8]边肇祺,张学工.模式识别[M].北京:
清华大学出版社,2002.
[9]高新波.模糊聚类分析及其应用[M].西安:
西安电子科技出版社,2004.
[10]朱力立,张焕春,经亚枝.模糊自适应遗传算法在多传感器多目标跟踪中的应用[J].信息与控制,2003,32（7:
711-716.
（上接第29页
[7]POLYCARPOUMM,YANGYanli,PASSINOKM.A咖operativesearchframeworkfordistributedagents[c3z/IntelligentControlProceedingsof2001IEEEInternationalSymposiumonMexico,2001:
1-6.
[8]任博,潘景余.不确定环境下的侦察无人机自主航路规划仿真[J].电光与控制,2008,15（1:
31-34.[9]
[10]
SUJITPB,BEARDR.CooperativepathplanningformultipleUAVsexploringanunknownregion[C]//Amer-icanControlConference,NewYork。
2007:
347.352.SUJITPB,GHOSED.SearchusingmultipleUAVswithflighttimeconstraints[J].AerospaceandElectronicSy8.terns,IEEETransactions2004,40（2:
491.509.
万方数据
遗传模糊聚类算法在数据关联中的应用作者：
作者单位：
刊名：
英文刊名：
年，卷（期：
被引用次数：
胡傲，冯新喜，王冬旭，郭威武，HUAo，FENGXinxi，WANGDongxu，GUOWeiwu空军工程大学电讯工程学院,西安,710077电光与控制ELECTRONICSOPTICS&CONTROL2010,17（31次参考文献（10条1.高新波模糊聚类分析及其应用20042.边肇祺;张学工模式识别20023.刘以安;曹奇英;刘同明基于遗传模拟退火算法的机动多目标数据关联问题研究[期刊论文]-系统工程理论与实践2001（094.朱志宇;皇风辉;姜长生杂波环境下的粒子滤波器数据关联方法[期刊论文]-电光与控制2008（025.朱力立;张焕春;经亚枝模糊自适应遗传算法
升级会员 