基于改进遗传算法的多传感器航迹关联

赵翻东，蔡益朝，李 浩，师维克

(空军预警学院 预警情报系，湖北 武汉 430019)

随着未来战场范围日益扩大，传感器类型和数目不断增加，对信息融合实时性的要求也越来越高[1]。准确、完整、一致的战场目标态势是辅助指挥员执行作战任务，定下作战决心的重要支撑，也是态势生成的首要任务。航迹关联是态势生成中保障态势清晰、完整、一致的关键技术，有着潜在的实用价值和明确的应用前景[2]，其目的是判断多传感器产生的局部航迹是否来自同一目标。在分布式信息融合系统中，每个传感器是一个单元并拥有独立的处理系统，对收集到的航迹信息进行加工处理，滤除虚假目标和各种干扰，形成融合前的真实航迹。收到各传感器的航迹后，信息融合中心需判断多条航迹是否为同一目标。随着测量目标的传感器数目日益增多，目标航迹出现交叉、分岔等复杂情况，航迹关联过程也变得困难[3]。

目前涌现了多种航迹关联算法，针对两个局部节点的情况主要有统计学、模糊数学、灰色理论、小波变换等方法。其中，基于统计学的加权[4]、修正加权[5]、最近邻、K近邻法[6]、独立序贯、相关序贯是基本方法，而这类方法面对群目标密集时，目标间容易相互遮挡，且计算量呈指数增长[7]。近年来模糊数学和灰色理论方面发展迅速，靳冰洋等[8]将灰色关联度计算与航迹关联问题相结合进行修正，提出一种两级航迹关联判决方法；田宝国等[9]则提出了模糊综合函数航迹关联算法。多局部节点多目标的航迹关联问题可以转换为多维分配问题,当传感器数目M≥3时,可以采用两两关联的方法，但该方法会出现随着节点数的增多运算量呈指数增长的问题。因此，Lagrange松弛算法、蚁群算法、遗传算法、自适应遗传算法[10]、人工神经网络求解法等相继被提出并运用，但这些方法均存在求解过程复杂、求解精度不高、收敛速度慢等缺陷，不能满足融合中心对实时性的要求，需要寻找一种可以简化求解过程的算法。基于此，笔者提出了一种改进的遗传算法，对传统的遗传算法采用精英保留策略和最优个体组合策略来进行改进和优化，并对多传感器的航迹关联问题进行求解。该算法在迭代次数较少时，可以得到较高的关联正确率并避免局部收敛。

1 航迹相关模型

航迹相关模型是对运动目标的运动特性进行分析，结合数学建模的相关理论建立的。笔者采用卡尔曼的滤波方式对传感器的航迹进行滤波，假设送至融合中心的数据已经经过时间对齐与空间坐标变换处理。

1.1 空间状态模型

一般状态方程为：

X(k+1)=Φ(k)X(k)+G(k)W(k)

(1)

式中：Φ(k)为k时刻状态转移矩阵；X(k)为运动目标在k时刻的状态向量；G(k)为过程噪声分布矩阵；W(k)为均值为零的白噪声信号，W(k)～N(0,q(k))，q(k)为协方差，由q(k)构成的正定协方差矩阵为Q(k)。

传感器s的量测方程为：

Zs(k)=Hs(k)X(k)+Vs(k)

(2)

式中：Zs(k)为第s个传感器在k时刻对运动目标的观测向量,s=1,2,…,M；Hs(k)为传感器s的测量矩阵；V(k)为均值为零的白噪声信号，即V(k)～N(0，r(k))，r(k)为协方差，由r(k)构成的正定协方差矩阵为R(k)。

1.2 加权航迹关联

(3)

(4)

由于加权法不考虑航迹的历史情况，即假设两传感器的误差是独立的，所以可以构建其检验统计量：

(5)

在H0假设的条件下λij(k)服从χ2分布，则可以选取适当的门限(通常选取α=0.05所对应的值)，当λij(k)小于其门限时，则接受H0假设，即两传感器的航迹为同一航迹；否则接受H1，即收到的航迹不是同一目标的航迹。当在公共区域内有M个传感器时，则构建统计量βis-1is和全局统计量ηi1i2…iM(k)：

(6)

(7)

式中：is为传感器s的第i条航迹，is∈[1,ns]，ns为传感器s上报的n条航迹数。

接下来定义一个二进制变量：

(8)

于是多局部节点情况下的加权航迹关联算法便被转化成多维分配问题，即：

(9)

(10)

为了研究方便，使得n1=n2=…=nM相等，即每个传感器观测到的航迹数都相等。

2 改进遗传算法

遗传算法是一种模拟生物进化过程的仿生全局寻优算法[11]，是借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。一条染色体代表对某一问题的解，对染色体上的基因进行选择、交叉、变异等操作，从而找到最优后代，得到最优解。在这个过程中，最重要的是建立适应度函数，它由目标函数来确定，适应度越大其生存能力越强，越容易保留其基因到下一代。由于遗传算法随机选择初始群体，当用来解决航迹关联问题时，需要对遗传算法的选择算子、交叉算子和变异算子进行改进[12]，以便找到最优后代。

2.1 染色体编码

遗传算法解决航迹问题时，普通的随机编码不再适用，这时需要对染色体编码进行一定的调整，传感器送来的航迹信息采用整数编码方式对求解问题进行直观描述[13]，每个时刻收到航迹信息来自不同的目标，一个传感器对应一条染色体编码，染色体上同一位置的基因表示同一个目标。例如，当监视区域内有10批目标、3个传感器进行观测时，染色体编码如表1所示。

表1 染色体编码

这种编码表示传感器A的第5条航迹与传感器B第6条航迹及传感器C第3条航迹来自同一目标，后面的基因也以此类推。传感器内不能出现相同的基因，也不能缺失某一个基因，也就是关联过中航迹不能重复关联，同时避免航迹缺失的情况。

2.2 适应度函数

求y(k)的最优解，也就是求关联正确率的最大值。关联正确率pc(k)为来自多局部节点的目标为同一目标的概率；关联错误率pe(k)为把来自不同目标的两条航迹判断为同一目标的概率；漏关联率pt(k)为来自不同传感器的航迹本来是同一个目标，但却判断为不相关的概率。显然，pc(k)+pe(k)+pt(k)=1。但在实际过程中要想获得pc(k)、pe(k)、pt(k)的值是很困难的，因此用频数来代替概率。

2.3 选择规则

传统遗传算法的选择规则，适应度值越大被选择的概率越大。它的选择方式既没有充分利用群体的信息，同时也会导致进化代数过大，无法满足实时性要求。因此综合整个种群组合出一个最优的种群和最优个体保留策略，将优质基因保留到下一代。

2.3.1 组合优质个体策略

利用种群优势找到每一个种群关联正确的航迹，对最优种群进行调整。建立一个关联矩阵，关联正确记为1，关联错误记为-1，漏关联记为0。则可根据关联矩阵知道种群中哪几个基因代表的是同一目标，可以方便快速地找到关联正确的基因，然后调整最优种群。未组合前初始染色体编码如表2所示。

在展出方式上，我选择了最简单的装框，上墙。这也的确是最适合这一幅作品的展出方式。我选择了一个淡色木纹的画框，将作品的单纯、安静无限放大。

表2 未组合前初始染色体编码

由表2可知，种群1有一个关联正确的航迹点，即第4个基因上两个传感器送来的航迹来自同一目标，种群2有一个关联正确的航迹点，即第6个基因上两个传感器送来的航迹来自同一目标。这里是根据判决门限来判断的，过了门限以后确实是同一条航迹，也就是航迹数编号一样，此时关联矩阵为1，否则为-1。接着根据种群2来调整种群1，最后得到最优种群1。在种群1中，找到编号为5的航迹，并调整到第6个基因的位置，使得传感器A的第1个基因跟第6个基因互换；传感器B的第8个基因跟第6个基因互换。调整后的种群如表3所示。

表3 组合操作后染色体编码

2.3.2 精英保留策略

精英保留策略在整个群体选择时，对种群的适应度值进行排序，把适应度函数值小的部分淘汰，将适应度函数值大的部分直接保留到下一代。保证了当代的最优种群不会因为后面的交叉、变异等操作使得优质基因被破坏，可以有效解决群体收敛的优化问题。

然后对适应度函数值大的部分进行复制，对复制出的种群进行交叉、变异等操作，与另一部分构成下一代种群，既保持了种群数的总量不变，同时也能使优良的基因遗传到下一代。当多个传感器多种群时，以此类推，充分利用整个种群的优势，快速得到最优个体。利用这种选择方式可以明显提高航迹关联的正确率和收敛速度，假设其中一个种群的基因关联错误，但是可以利用其它种群对这一对关联错误的基因进行调整。

2.4 交叉变异

交叉过程中，如果采用基本的交叉方式，会出现基因重复的情况，因此采用传感器内部交换。对适应度值较大的一半种群进行复制，再对复制的这一半进行交叉变异。每个传感器都随机产生两个交叉点，交叉时交叉点两头进行交换，中间保持不变，如表4所示。

表4 交叉前后的染色体编码

传感器内部交叉虽然简单，但不会出现重复的数据，能满足预先编码的要求。在交叉时涉及交叉概率，但并不是对所有的种群都进行交叉，即随机产生一个0～1之间的数，当该随机数小于交叉概率时才进行交叉操作。交叉概率的大小会影响新种群的产生速率，不能过大或过小，过大会对最优个体造成破坏，过小会使结果搜索陷于局部最优，收敛速度减慢。所以选取合适的交叉概率对种群的更新有很大的影响。

传统变异方式会出现基因重复和缺失的情况，必须进行改进。因此，采用传感器内部变异对换，即在一个传感器内随机产生两个变异点，这两个变异的基因交换位置，得到一个新基因组。变异概率过小不易产生新个体，过大的话变异节点过多，则跟随机产生的个体一样，不利于保留最优个体。变异前后的染色体编码示例如表5所示，其中传感器A变异节点为第2个基因位置与第8个基因位置，传感器B变异节点为第4个基因位置与第9个基因位置。

表5 变异前后的染色体编码

经过交叉变异后，可以得到第2个位置的基因代表同一个目标，再利用这一个基因对最优个体进行调整，最终可得到下一代个体，如表6所示。

表6 下一代染色体编码

2.5 求解步骤和流程

①设置算法参数，包括交叉概率、变异概率、种群大小N、遗传代数g等；②初始化种群，随机产生初始种群，并计算每一种群的适应度值；③按照适应度值的大小对种群进行排序；④ 按照精英保留策略，将适应度值最大的一半种群直接保留至下一代；⑤对适应度值小的一半种群进行遗传算法进化操作，产生新的后代；⑥将精英策略保留下来的一半和进行遗传操作的一半合成新的下一代种群；⑦ 计算新种群个体适应度；⑧若进化代数没有达到设定值，则按照交叉变异原则产生新的个体返回步骤③继续进行进化，直到到达设定值。

3 仿真实验

仿真时，每个节点放一部同类传感器，80批目标起始位置在公共区域-10～10 km按正态分布产生；每批目标初始速度在0～100 m/s内均匀分布；初始航向在0～2π内均匀分布。

3.1 两局部节点的仿真

在进行两局部节点仿真时，目标在一个二维平面上做匀速直线运动和变速运动。传感器的位置坐标分别为(0,5 km)、(5 km,0)，其距离分辨力分别为55 m、75 m。目标的运动状态为X=(x,vx,y,vy)，其状态转移矩阵、过程噪声分布矩阵、噪声方差矩阵分别为Φ(k)=[1,T,0,0;0,1,0,0;0,0,1,T;0,0,0,1]，G(k)=[0.5T2,0;T,0;0,0.5T2;0,T]，Q(k)=[12,0;0,12]；T为采样时间，取1 s；观测向量为Z=(x,y)T，其观测矩阵H(k)=[1,0,0,0;0,0,1,0]，量测协方差矩阵R(k)=[12,0;0,12]。设种群数大小N=100，交叉概率为0.9，变异概率为0.05，最大遗传代数g=100。在匀速运动和变速运动两种模型下，当融合中心获得局部传感器送来的局部航迹后，需要对局部航迹进行航迹分类[14]，送到融合中心的航迹经过时间对准与坐标变换后，匀速运动产生的目标航迹如图1所示，其做匀速直线运动时的关联结果如图2所示；变速运动模式下目标的运动轨迹如图3所示，其做变速直线运动时的关联结果如图4所示。

图1 80批目标匀速运动轨迹

图2 两局部节点匀速直线运动

图3 目标变速运动轨迹

图4 两局部节点变速运动

从图2(a)和图4(a)的仿真结果可以看出，匀速运动遗传到第12代左右时，变速运动遗传到第26代左右时，关联正确率达到最大值，且比较稳定。可见所提算法极大地提高了关联正确率，且遗传代数较小，节约了大量时间。对比图2(b)和图4(b)可知，无论是匀速运动还是变速运动，所提出的改进遗传算法相比于模糊法、加权法、修正K近邻法等在关联正确率和收敛速度均有明显的优势。

3.2 多局部节点的仿真

传感器数取M=3,5,7，其他仿真参数与两局部节点数相同。目标匀速运动和变速运动的仿真结果分别如图5和图6所示。由仿真实验结果可得，当传感器数增加时，其在任何一个时刻的遗传代数都明显增加，而且关联正确率有所降低，匀速运动时其遗传代数在100代左右趋于稳定，变速运动时其遗传代数在140代左右趋于稳定，但在190代左右又稍有提高，但比文献[10]的自适应遗传航迹关联算法在目标数为60和120时平均收敛到200代和500代左右有明显的优势。由图5(b)和6(b)可知，随着传感器数目的增加，其关联正确率下降明显，在变速运动模式下其关联正确率存在一定波动，但总体趋于稳定。实验结果表明，改进遗传算法应用于航迹关联分析具有巨大优势，满足复杂战场环境对航迹关联实时性、准确性的要求。

图5 多局部节点匀速运动

图6 多局部节点变速运动

4 结论

针对当前多传感器的航迹关联算法存在求解精度不高、收敛速度慢的问题，笔者提出一种改进的遗传算法解决航迹关联问题。针对航迹关联问题的特点，在遗传算法的编码、选择规则和交叉变异等环节，均提出了不同的改进策略。仿真结果表明，在两局部节点和多局部节点时，即使在目标数目很大的情况下，相较于当前航迹关联算法，所提算法具有较快的收敛速度和较高的关联正确率，充分体现了改进策略的有效性。但随着传感器数目的增加，其关联正确率和收敛速度都有所下降，未来需要针对此问题继续深入研究。