中国指挥与控制学会会刊 
目前用于“低慢小”无人机目标探测的手段主要有雷达、光电、声学、无线电等手段,这些探测技术特性各异,虽然在发现距离、灵敏度、能效范围、抗恶劣气候影响、多目标同时探测跟踪能力等方面各有所长,但尚难有效解决复杂环境下“低慢小”无人机目标的探测跟踪问题[1]。通过多体制探测手段进行协同探测以及时获取目标位置、视频图像等目标信息[2]。
针对“低慢小”无人机目标的协同防控过程来说,各探测装备的协同探测任务分配在获取目标信息以及跟踪探测方面起着至关重要的作用,其核心问题是获取各探测装备的最大化探测效能[3]。在来袭的无人机目标获得分配终线之前,探测任务的优化分配是一个动态过程,分配预案将随着目标航迹、目标威胁程度、各探测装备能效范围、各探测装备工作模式等情况变化而适时调整。
多元传感器协同探测任务分配问题,和指挥控制学中的火力分配问题类似,同属于军事运筹学中典型的NP问题,其解空间的大小与问题规模息息相关,且存在指数关系。传统的枚举法、动态规划法和匈牙利法,算法思想较为简单,但编程烦琐、收敛速度慢,仅适用于解决简单的探测分配问题[4]。为求解满足杀伤概率的火力分配问题,蚁群算法和遗传算法得到了广泛的应用,但在复杂环境下,这两类算法难以同时满足求解精度和时间性能两方面的要求[5]。为寻求更快速、更有效的任务分配方案,文献[6]采用收敛速度更快的粒子群优化算法对模型进行求解,但存在容易陷入局部最优解和映射空间大的问题。
在面对实际的“低慢小”无人机区域防控协同探测时,探测装备的探测性能与部署位置、目标距离、航迹和飞行速度等都有紧密的关联,探测装备仅能分配给那些满足探测条件的目标。本文研究一种考虑探测可行域的编码方法,以缩小NP问题的解空间;同时探讨了一种改进的种群控制方法,解决算法早熟现象,以提高协同探测任务分配算法的性能。
1 问题描述
1.1 效能函数
为定量描述探测装备探测任务分配问题,需要综合考虑来袭“低慢小”无人机目标的威胁程度、探测装备的跟踪探测能力,下面讨论综合探测效能求解最佳的协同探测策略。
假设“低慢小”无人机防控区域内有nD个探测装备,探测装备集合表示为
RD=
来袭目标有nT个,且其集合表示为
RT=
设Pij代表第i个探测装备对第j个目标的探测概率,Pij=0时表示探测装备不能对相应的目标实施跟踪探测,Pij=1时表示探测装备能对相应的目标实施稳定的跟踪探测。则探测装备对目标的跟踪探测性能矩阵可表示为
P=
设Mi为第i个探测装备拟跟踪探测的目标序号,探测装备探测任务分配方案描述为
M={M1,M2,…, }
探测装备探测任务分配问题是探测装备与目标配对的0-1规划问题,引入决策变量sij,当且仅当Mi=j(表示第i个探测装备跟踪第j个目标)时,决策变量sij=1,否则sij=0。
防控系统需要根据来袭的“低慢小”目标距防控中心的位置、速度和方向来进行目标威胁排序,从而便于形成目标威胁态势。这里假设wj为第j个目标对防控区域的威胁权重系数,综合来袭目标威胁系数表示为
w=
探测装备探测任务分配的问题可描述为使对探测装备所有目标跟踪探测概率之和为最大,即对威胁系数大的目标具有更高的跟踪探测概率。因此,效能函数可表达为
max f= wj·[1- (1-pij)sij]
1.2 约束条件
“低慢小”无人机区域协同防控时,探测装备的探测任务分配是一个受约束的优化问题,其约束条件考虑如下:
1)对于探测跟踪“低慢小”无人机的光电、雷达等探测装备来说,虽然当其处于搜索模式下可以发现多个目标,但出于跟踪模式下,每个探测装备Di每次仅能跟踪探测一个目标Tj,因此
sij=1
其中,i=1,2,…,nD,j=1,2,…,nT,k=1,2,…,nT。
2)探测任务分配必须考虑实际防控任务环境,分配给某探测装备Di的目标必须可被其探测跟踪,即在其探测能力范围内,有
pij>0,(sij=1)
由此,“低慢小”无人机区域协同探测任务分配模型是一个以式(6)作为目标函数,式(7)与式(8)为约束条件的0-1整数规划问题[7]。
在实际的“低慢小”无人机目标防控环境下,每个探测装备仅可能跟踪其探测范围内的目标,而求解变量的取值为整数,同时变量的取值范围受到探测装备的跟踪探测能力的约束,这就导致了目标函数是非线性的,这必然给数值寻优过程带来诸多困难。通常可以采用罚函数法来将此问题转化为一个无约束问题。本文研究粒子群算法,探讨其在解决多个探测传感器相互协作的可行性。
2 粒子群优化算法
2.1 基本粒子群算法
假设nE维解空间存在n个不同变量x=(x1,x2,…, )的粒子。第m个粒子为xm=(xm1,xm2,…, ),其当前经历过的最优位置为pm=(pm1,pm2,…, ),第m个粒子的速度为vm=(vm1,vm2,…, ),种群全局最优粒子为pg=(pg1, ,…, )。在进化过程中,每一代各粒子在本身惯性速度的基础上,同时向当前的粒子自身历史最优位置和群体最优位置方向加速获得新的速度,并对所在位置进行更新[8]。设l为粒子进化代数,粒子群优化进化更新算法为
式中,下标d=1,2,…,nD代表探测装备变量的维数;r1、r2为[0,1]区间均匀分布的随机数;c1、c2分别代表粒子自我认知和群体协同能力的加速因子,w为粒子的惯性权重(威胁权重系数)。
在更新阶段,当粒子速度或位置超界时,对粒子状态限定公式如下,
设定粒子群算法总进化代数为lmax,第l代的惯性权重系数进行更新采用的线性递减策略如下式,
w=wini+(wend-wini)·l/lmax
式中,wini、wend分别为对进化起始代到终止代惯性权重的控制。
通常采用对连续粒子群算法的直接离散化方式来满足获取整数配对的需要。在每次粒子位置更新之后,通过将式(10)与式(11)中粒子位置的近似取整运算,并以粒子对应的目标函数来评价此解的质量,然后进行迭代,这样就使得算法结构依然能够保持连续粒子位置和速度更新中的运算规则。
2.2 粒子编码方法
用粒子群算法求解探测任务分配问题时,需要将分配问题进行合理的编码。常规的做法是将粒子对应为长度和探测装备数相同的变量,粒子的每维xi表示探测装备跟踪探测的目标编号。这种编码方法概念清晰、编码简单,但求解过程假设每个探测装备都可对任意目标进行跟踪探测,即没有考虑式(8)的约束。
一般情况下,处理优化问题的约束有三种途径:
1)考虑约束的编码;
2)引入与约束相关的罚函数;
3)在进化过程中,检验变量的合法性,迭代生成可行变量。
方法2)更改了目标函数,且没有强制解的合法性;方法3)通过反复迭代增加了算法运行时间,当问题维数增大时通常不可取。这里研究一种新的粒子编码方法,不仅保证编码的合法性,而且缩小了解空间的大小,使得建模上提高了协同探测任务分配的优化效率。
式(8)描述了探测装置的协同探测任务分配需满足一定的约束条件:“低慢小”无人机目标处于探测装备探测范围内。假设经过探测适应性检验后, 为第d个探测装备对应可跟踪探测目标的总数量,第d个探测装备可跟踪探测的目标集合,记为探测可行域 ,探测可行域是来袭目标集合RT的一个子集。
={ ≤nT,1≤i≤ }
式中,1≤ ≤nT, ⊂RT。
设 =( , ,…, )为第l代中,第d个粒子的nE维位置矢量,粒子第d维变量表示第d个探测装置与其探测可行域的第 个目标配对, 取值范围不能超过第d个探测装备探测可行域的目标数量。
采用基于探测装备探测可行域的粒子编码,可有效缩小探测装备协同探测任务优化问题的映射空间,加速了算法寻优速度。进一步地,若xl=( , ,…, )为协同探测任务分配问题的解,则第d个探测装备分配协同探测任务的目标为 ( ),其变量取值范围为xd∈[ , ]=[1, ],该粒子的飞行速度为vd∈[ , ]=[- /2, /2]。
2.3 改进的粒子群算法
通过式(10)与式(11)可以看出:在自身最优解和全局最优解的信息引导下,粒子的样本一直处于收缩过程。当找到问题的一个局部最优解时,粒子群将聚集在较小的区域内,且目标函数也将趋于停滞更新状态。本质上,粒子群算法在进化过程中,可不断降低群体的多样性,也减小了寻优的搜索空间。
为控制算法的搜索过程,以增强群体的多样性,定义 为第l代群体的样本浓度,总的群体数量不变,搜索空间越大,样本浓度越低。引进了群体多样性的度量公式
ρl=
式中,N为种群的大小, 为粒子群第d位变量的平均值 = /N。
当ρl<ρmin时,粒子就开始向中心的反向加速,可采用速度更新策略如下
=w -c1r1·(- )-c2r2·(- )
当ρl>ρmin时,粒子停止发散运动,采用式(10)与式(11)更新策略开始向着中心收缩。
该改进策略从效果上看如同粒子间存在一个斥力,当间距小于允许值时,该斥力便产生作用,将各粒子推至斥力影响范围之外;而当间距大于允许值时,斥力转为吸力,各粒子开始收缩。粒子群在多样性的指导下反复作收缩与发散运动,可以在群体聚集时呈现增大样本空间的趋势,解决了算法早熟现象,跳出局部最优情形。
3 算例与分析
以某次要地防控任务为例,现有7个探测装备,来袭目标共7个。根据各探测装备搜索上报的来袭目标的距离、速度与方向,将目标的威胁系数定义为(w1,w2,w3,w4,w5,w6,w7)=(0.8,0.7,0.5,0.4,0.7,0.3,0.6),经过对各探测装备的探测性能分析,各探测装备对目标的可跟踪探测情况如表1 所示。来袭目标nT=7,编号为RT= ,探测装备nD=7,编号为RD= 。
表1 各探测装备对目标的跟踪探测情况Pij/sij |
| T1 | T2 | T3 | T4 | T5 | T6 | T7 | |
|---|---|---|---|---|---|---|---|
| D1 | 0.65 | 0 | 0.74 | 0.82 | 0 | 0.77 | 0 |
| D2 | 0.81 | 0.78 | 0 | 0 | 0.83 | 0.65 | 0.69 |
| D3 | 0.77 | 0.75 | 0.81 | 0.53 | 0 | 0.61 | 0.82 |
| D4 | 0 | 0.81 | 0 | 0.77 | 0.71 | 0.83 | 0.64 |
| D5 | 0 | 0 | 0.83 | 0.75 | 0 | 0 | 0.81 |
| D6 | 0.82 | 0 | 0.8 | 0.61 | 0.57 | 0.74 | 0.81 |
| D7 | 0.72 | 0.83 | 0.79 | 0 | 0.81 | 0 | 0 |
从表1 可以看出各装备的探测可行域分别为 = 、 = 、 = 、 = 、 = 、 = 。即第1个探测装备能跟踪探测的目标为T2与T3;第2个探测装备能跟踪探测的目标为T1、T3与T5;第3个探测装备能跟踪探测的目标为T1与T5;第4个探测装备能跟踪探测的目标为T2、T3与T5;第5个探测装备能跟踪探测的目标为T2、T3与T4;第5个探测装备能够跟踪探测的目标为T2与T4。
当7个探测装备全部正常工作,上报的7个来袭目标全部进入防控预警范围时,设置装备数nD=7,目标数nT=7,种群规模n=10,粒子维数nE=nD,最大迭代次数lmax=50,学习因子c1=c2=1.2。
经计算得到全局最优粒子pg=(3,3,6,4,1,1,2),协同探测分配方案为M=(4,5,7,6,3,1,2),跟踪探测概率f=84.23%。如图1 、图2 所示,给出了改进后的粒子群算法与基本粒子群算法的效能函数与粒子群寻优过程对比。
由图1 、图2 可以看出,采用改进的粒子编码策略,可有效地缩小分配问题的解空间,使算法获得了全局寻优能力和更快的收敛速度,而通过增加多样性控制手段后,群体将经历收缩和发散两个交替过程,在一定的空间范围内,粒子样本在群体协同下向中心收缩,解决算法早熟现象,提升了粒子在可行域内的搜索能力。
在实际执行防控任务时,会出探测装备已分配任务或者探测装备出现离线或故障的情况。假设当7个探测装备只有5个(D1~D5)正常工作,而上报的来袭目标只有4个(T2~T5)进入防控预警范围时,设置装备数nD=5,目标数nT=4,种群规模保持不变n=10,粒子维数nE=nD,最大迭代次数与学习因子不变。考虑算法模型基于每个探测装备每次只能执行一次跟踪探测任务的条件约束,经计算得到全局最优粒子pg=(2,1,1,2,2),协同探测分配方案为M=(4,1,1,2,3),跟踪探测概率f=88.84%。改进后的粒子群算法与基本粒子群算法的效能函数与粒子群寻优过程对比如图3 、图4 所示。
4 结束语
在一次针对“低慢小”无人机目标的协同探测任务过程中,各探测装备的部署是相对固定的,协同探测任务分配主要是由探测装备的性能决定的,同时受到无人机目标离探测装备的距离、其飞行航迹和速度等条件的限制。
为了尽可能发挥现有探测装备的跟踪探测效能,从而构建行之有效的防控态势图,本文将多元探测装备的协同探测任务规划描述成一个典型的多约束整数规划问题,研究了基于探测装备跟踪探测可行域的粒子编码方案,缩小了规划问题的解空间,并探讨了一种基于多样性控制策略的改进粒子群算法。通过两个算例进行仿真分析,该方法可加快粒子搜索速度,避免了算法早熟现象,跳出了局部最优情形,可为多传感器跟踪探测任务分配提供参考。