基于自适应遗传算法的多目标跟踪资源调度

基于自适应遗传算法的多目标跟踪资源调度

袁磊 袁方宇 刘湘德

（中国电子科技集团公司第二十九研究所  四川成都  610036）

摘  要 ：现代信息化作战，随着作战目标多种多样、装备不断增多，传统单传感器单平台难以有效对抗作战目标的体系化发展，需通过多平台协同实现对多目标的有效侦察跟踪。针对传统多目标跟踪资源调度方法优化目标单一、适应能力差、收敛速度慢、求解时间长、无法实现一个资源匹配多个目标等问题，提出了一种基于自适应遗传算法的多目标跟踪资源调度方法，有效提高收敛精度，缩短求解时间，同时提升体系对资源和目标变化的适应能力。

关键词：多目标跟踪;资源调度;自适应遗传算法;多平台协同;信息化作战

A Multi-objective Tracking Resource Assignment Method Based On Adaptive Genetic Algorithm

Yuan Lei Yuan  Fang Yu  Liu Xiang De

(The 29th Research Institute of China Electronics Technology Group Corporation, 610036, Chengdu, Sichuan)

Abstract:Modern Information Warfare, With perse Target And Increasing Resources, The Traditional Single Sensor Platforms Are Difficult To Effectively Counter Combat Targets, It Needs to achieve Scouting and tracking The multiple Targets Through Multi-Platform Cooperative. Aiming At The Problems Of Multi-objective Tracking Resource Assignment Methods, Such As Single Objective Optimization, Poor Adaptability, Slow Convergence Speed, Long Solving Time, And Inability To Achieve Matching of One Resource With Multiple objectives, etc. A Multi-objective Tracking Resource Assignment Method Based On Adaptive Genetic Algorithm Has Been Proposed That Can Effectively Improve Convergence Accuracy, Shorten Solution Time, And Enhance Adaptability To Changes In Resources And Objectives.

Key words: Multi-objective Tracking; Resource Assignment; Adaptive Genetic Algorithm; Multi-Platform Cooperative; Modern Information Warfare.

1 引言

随着作战环境复杂多变、对抗目标多种多样、作战资源不断增多，现代化作战单个装备发挥的作战功能极为有限，传统单传感器单平台独立侦察跟踪难以有效对抗作战目标的体系化发展，需通过多平台协同配合实现对多目标的有效跟踪。在跟踪目标时，特别对于机动目标通常需要两个及以上无源侦察传感器同时侦收才能解算出其位置信息，理论上每个目标分配传感器资源越多其跟踪效果越好，但是整个体系中装备资源数量有限，不同平台的侦察资源能力各异，且不同对抗目标所需资源能力要求各不相同，如何将有限的资源合理分配给多个目标从而满足对每个目标的跟踪性能要求，已成为了多目标跟踪的关键问题之一[1][2]。确切的说，需要制定一种切实有效的多目标跟踪资源调度方法，优化选择合适的传感器资源侦收合适的目标并获取目标位置，从而实现对作战目标的综合跟踪效益最大化。

目前的研究主要集中于静态资源调度方法，多目标跟踪资源调度本质是一种带约束的多目标组合优化问题，这类问题通常使用遗传算法等方法进行求解，面向实际使用目前主要存在以下问题[3][4][5]：

（1）传统多目标跟踪资源调度方法优化目标较为单一，未考虑目标和资源的实时变化，适应能力差，实际上资源和目标都是在实时动态变化的，目标跟踪的效能还与目标特性、资源能力、协同构型等方面密切相关，在设计优化目标函数时应该考略进去；

（2）传统多目标跟踪资源调度方法通常假定一个资源只能对抗一个目标，且一个目标只分配一个资源，实际的传感器资源通常具备多目标跟踪能力，并且对于作战目标通常需要两个及以上的无源侦察资源协同才能实现对目标的定位和有效稳定跟踪，这些都应该作为优化问题求解的约束条件考略进去；

（3）利用传统遗传算法求解多目标跟踪资源调度问题，优化过程的收敛速度较慢，求解时间长，而且算法稳定性较差，易造成早熟现象而陷入局部最优。并且传统编码方式把染色体上每一个位置当做一个资源，该位置的基因代表把该资源分配的目标编号，这种编码方式一个资源只能分配一个目标，不满足系统多目标跟踪能力需求。

2 多目标跟踪资源调度方法

针对传统多目标跟踪资源调度方法优化目标单一、适应能力差、求解时间长、无法实现一个资源匹配多个目标等问题，提出一种基于自适应遗传算法的多目标跟踪资源调度方法，在本次作战任务中，根据我方无源侦察资源和对抗目标实际能力情况，设计优化目标函数，并将无源侦察资源具备多目标跟踪能力、作战目标通常需要两个及以上的无源侦察资源协同完成定位跟踪等作为约束条件，建立多目标跟踪资源调度优化模型；然后，根据建立的优化模型，使用自适应遗传算法进行优化求解，通过编码生成、初始种群生成、适应度评估、选择操作、变异操作、交叉操作、逆转操作不断进行优化迭代，生成并输出最佳资源调度结果，并根据环境的变化进行反馈调整。

2.1 多目标跟踪资源调度优化模型建立

多目标跟踪资源调度本质是一个带约束的整数组合优化问题，其数学模型描述如下：对多个无源侦察资源和多个对抗目标分别进行编号，假设我方有m个具备目标跟踪能力的无源侦察资源，敌方有n个辐射源目标，通过我方m个无源侦察资源实现对n个目标的协同跟踪定位。对每个目标的协同跟踪效益主要考虑资源可用性、功能匹配性和实时构型等因素，对第个目标的协同跟踪效益模型为：

               （1）

其中，表示第个资源对第个目标进行跟踪；

表示我方资源对应的功能匹配性参数，通过对我方资源跟踪能力进行打分并进行归一化处理获得，满分1分，数值越大代表性能越好；资源可用性方面，当资源跟踪目标数量小于最多对抗目标数量时取值为1，表示可用，否则取值为0，表示不可用；功能匹配性参数方面，从空域覆盖、频率覆盖、侦察距离、测向精度等维度对我方无源侦察资源跟踪能力进行打分并进行归一化处理获得，满分1分，数值越大代表性能越好。

表示针对第个目标分配的资源实时构型参数，主要与我方资源间的距离有关；对于两个我方无源侦察资源的实时构型，假设我方资源之间的最大通信距离为200km，且距离在80-100km时，跟踪性能最好，设对于第个对抗目标的两个跟踪资源间的距离为Disj，则的计算公式如下：

                  （2）

为功能匹配性和实时构型的加权系数，取值越大代表该参数比重越大也就越重要；

以体系的整体综合跟踪效益最高为优化目标：

            （3）

其中，表示第个目标的权重系数（目标威胁程度越高，权重越大），权重越大的目标优先分配有利的资源，其约束条件主要包括：

约束条件1：第个资源最多可以跟踪个雷达目标，从而满足传感器资源具备多目标跟踪能力的要求：

                           （4）

约束条件2：敌方目标需要个资源完成协同跟踪，从而满足对于作战目标通常需要两个及以上的无源侦察资源协同才能实现对目标的定位跟踪要求：

                           （5）

约束条件3：实际分配的资源总个数不能超过所有资源的总数：

                            （6）

约束条件4：同一个资源分配目标取值为1，不分配目标取值为0：

                   （7）

针对多目标跟踪资源调度问题的优化原则包括：

（1）应尽可能多的跟踪目标，使未跟踪的目标数最少；

（2）使我方无源侦察资源对作战目标的整体综合跟踪效益最高；

（3）对于威胁程度大的作战目标，应优先分配跟踪能力更为有利的资源，确保对高威胁目标的跟踪定位；

（4）在满足跟踪要求的条件下，要使消耗的无源侦察资源数量最小，从而保证对新出现目标的跟踪能力。

2.2 利用自适应遗传算法完成优化问题求解

根据建立的多目标跟踪资源调度优化模型，使用自适应遗传算法进行优化求解，得到最佳资源调度结果，其求解流程如图 1所示，主要步骤如下：

图 1 自适应遗传算法的实现流程图

（1）编码生成：为了简化遗传算法求解带约束组合优化问题的复杂度，提高效率，提出一种满足约束条件的多串染色体十进制编码方案，编码结构如图 2所示。

图 2 满足约束条件的多串染色体编码结构

对于有m个具备定位能力的资源，第个资源最多可以跟踪个雷达目标，本方法用一个长度为的整数串来表示一个个体或者可行解。其中代表第1个资源的分配方案，代表第2个资源的分配方案，以此类推，

代表第m个资源的分配方案。的取值为0到n的整数，，如果，则代表所对应的资源没有分配目标，如果，则代表对应的资源分配了第个目标。

（2）初始种群生成：确定种群规模为N，按照上述编码方式，随机给出N种染色体编码（相当于是优化问题的可行解）作为初始种群。根据多目标跟踪资源调度优化模型可以看出，并不是所有生成的个体都是有效的，因此，需要对每个随机生成的个体进行判断，满足约束条件才是有效个体。

（3）适应度评估：本方法中首先用约束条件对染色体进行初步筛选，然后通过目标函数计算种群中每个个体的适应度函数值，本方法中选取体系的整体综合跟踪效益作为适应度函数。

（4）选择操作：使用轮盘赌选择方法和精英保留策略，根据个体适应度值大小进行选择，同时将种群中适应度值最高的几个个体保留，加快收敛速度。使用轮盘赌选择方法，通过适应度比例选择方式来进行下一代个体的选择，个体被选中的概率与适应度成正比，适应度越高，个体被选中的概率越大，同时通过精英保留策略将种群中适应度值最高的2个体保留，不进行遗传运算直接选入下一代，加快收敛速度。

（5）遗传运算：针对本方法的染色体编码结构特点，遗传运算采用交叉、变异和逆转三种操作。其中，交叉操作指随机对两个个体中的两个随机选取的位置点进行基因交换；变异操作指对一个个体中随机选取的两个基因进行交换；为了加速进化本方法特意设计了逆转操作，即对对一个个体上随机选取的两个位置点之间的基因进行反向排序。

需要特别注意的是，进行交叉操作后形成的新个体基因与其他位置上的基因可能会有重复，这样的个体不满足要求，如图 3中两个个体进行交叉操作后产生新个体1的元素8、10、0，新个体2的元素6、7、9都是重复的，还需要进一步把新个体1重复的基因与新个体2重复的基因做交换，以消除冲突，获得有效的新个体。

图 3 交叉操作的示例图

此外，为了进一步解决遗传算法易陷入局部最优、收敛速度慢的问题，提出一种自适应遗传算法，使交叉算子和变异算子能够在求解过程中随着适应度函数值自动调整。使交叉算子和变异算子能够在求解过程中随着适应度函数值自动调整，当种群各个体适应度函数值变化很小或者趋于局部最优时，增大和；当群体适应度函数值比较分散时，减少和使该解得以保护进入下一代；而低于平均适应度的个体，则取较高的和，使该个体被淘汰掉。在保持群体多样性的同时，又保证了遗传算法的快速收敛性。和的计算公式如下：

                （8）

其中，表示种群的最大适应度值，表示种群的平均适应度值，为进行变异操作的个体的适应度值，表示在要交叉的两个个体中较大的适应度值，取值范围为[0,1]，分别表示交叉算法的上限和下限，分别表示遗传算子的上限和下限，本实例中，，。

（6）终止条件判断：设定最大迭代次数为T，当迭代次数达到最大值时，停止进化，选择最优的染色体个体作为优化解输出。

3 仿真分析

实例一：我方有8个无源侦察资源，对抗6个作战目标，其中，每个无源侦察资源最多可以对抗2个目标，每个目标需要2个无源侦察资源协同才能完成目标定位耿总。设定我方无源侦察资源能力匹配度参数分别为{0.2,0.9,0.7,0.6,0.5,0.8,0.75,0.85}，目标的威胁等级分别为{0.7,0.95,0.6,0.5,0.9,0.8}，每个资源二维位置坐标分别表1所示。

表1 资源位置信息

首先根据本次作战任务中，我方资源和对抗目标实际能力情况，对资源和对抗目标分别进行编号，用表示资源，资源总数，用表示对抗目标，目标总数为，其中，每个资源最多可以对抗目标数量为，每个目标需要协同资源数量为。

根据上述建立的调度优化模型，使用自适应遗传算法进行优化求解，选取体系的整体综合跟踪效益作为适应度函数，由公式（3）可得，适应度函数为：

               （9）

按照所述编码方案，随机给出若干染色体编码作为初始种群的个体；确定种群规模为100，按照上述染色体编码方案，随机给出满足约束要求的100种染色体编码作为初始种群；利用约束条件对初始种群或新种群中的个体进行筛选：不满足约束条件的个体的适应度函数值为0，满足约束条件的个体通过适应度函数计算其适应度函数值。

采用精英保留策略，将适应度函数值最大的2个个体不进行遗传运算直接添加至新种群；其余个体根据其适应度函数值，使用轮盘赌选择方法进行选择。并对轮盘赌选择方法选择出的个体进行交叉、变异、逆转等遗传算法操作后添加至新种群。

根据当前迭代次数进行判定，设定最大迭代次数为1000，当迭代次数达到最大值时，停止进化，选择最优的染色体个体作为优化解输出，否则持续进行迭代。最终通过优化求解得到最佳的资源调度结果为0052340043526116，平均耗时0.827s，通过解码转化为实际调度结果，如表2所示。从调度结果可以看出，每个目标均分配了两个不同的资源，且每个资源最多只对抗两个目标，满足约束条件，此外，对于威胁程度大的目标2和5，优先使用跟踪能力更为有利的资源2和6，并且在满足性能要求条件下为使资源数量最小，资源1和4并未分配目标以保证对新出现目标的跟踪能力。

表2  实例一8个资源6个目标优化调度结果

实例二：为了进一步验证本方法的有效性，将目标个数增加到8个，目标的威胁等级分别为{0.7,0.95,0.6,0.5,0.9,0.8,0.75,0.4}，其他条件保持不变。

同样根据上述流程，最终通过优化求解得到最佳的资源调度结果为8452314831526776，平均耗时0.858s，通过解码转化为实际调度结果，如表3所示。从调度结果可以看出，当目标个数增加为8个后，本方法能自适应调整调度策略，以满足对新出现目标的跟踪需求。

表3  实例二8个资源8个目标优化调度结果

通过上述实例分析表明，本方法实现了符合装备多目标对抗能力和目标跟踪资源个数要求的多目标跟踪资源优化调度，基于本方法提出的自适应遗传算法能有效提高收敛精度，缩短求解时间到1s以内，并提升体系对资源和目标变化的适应能力。

4 结束语

针对多平台无源侦察传感器实现对多目标的协同定位跟踪问题，本文提出了一种基于自适应遗传算法的多目标跟踪资源调度方法，基于作战目标特性和我方资源能力，将目标威胁等级、资源能力匹配度、实时构型等因素加入跟踪效能计算，以体系综合跟踪效益最大为优化目标构建优化模型，基于自适应遗传算法在线求解带约束的协同跟踪目标分配问题，通过设计满足约束条件的多串染色体编码方案并自适应调整算法参数，有效提高收敛精度，缩短求解时间，并提升体系对资源和目标变化的适应能力。

综上所述，由于采用了上述技术方案，其有益效果如下：

（1）结合实际作战使用，构建了符合无源侦察装备多目标对抗能力和目标跟踪无源侦察资源个数要求的多目标跟踪资源优化调度模型，并提出一种满足约束条件的多串十进制染色体编码方案，简化遗传算法求解带约束组合优化问题的复杂度。

（2）自适应遗传算法中交叉算子和变异算子随着适应度函数值自动调整，进一步解决遗传算法易陷入局部最优、收敛速度慢的问题，有效提高收敛速度，将求解时间缩短到1s以内，从而快速根据作战目标的变化进行自适应调整，提升适应能力。

参考文献

[1] 柳向,李东生,胡瑞. 改进遗传算法在协同干扰资源分配中的应用[J]. 探测与控制学报，2018(5):69-75.

[2] 姚昌华. 多无人机协同侦察时间资源分配优化[J]. 电子测量技术,2022,37(4):69-75.

[3] 邓敏, 伍志高, 姚志强, 陈永其. 带精英集并行遗传算法的无人机干扰资源调度[J]. 电 子 与 信 息 学 报,2022,6(44):2158-2165.

[4] 赵亮,史小斌. 多功能相控阵雷达自适应资源调度仿真[J]. 火控雷达技术, 2022(1):102-108.

[5] 张昀普,单甘霖,付强. 多传感器协同地面目标跟踪的调度方法[J]. 西安电子科技大学学报, 2022,5(49):100-108.