基于改进象群算法的多传感器资源调度方法

李 琦,韦道知,谢家豪

(1.空军工程大学防空反导学院,陕西 西安 710043;2. 解放军93605部队,北京 102100)

0 引言

在当前信息化、智能化作战背景下,空天作战能力迅猛发展。面对“隐身化、无人化、多域化、集群化、智能化”等新型空天目标威胁,单个传感器在探测范围、探测信息类别、探测精度等方面能力有限,很难完成对目标信息的整体跟踪探测,更难以适应复杂多变的作战环境和作战需求。在此情况下,需要多传感器协同进行优化以发挥传感器网络最大效能。对于“传感器协同探测” 来讲,其核心就是根据某种度量指标确定传感器之间的最佳“协同方式”,在传感器调度过程中也被称为“传感器调度方案”[1-4]。

在过去的十年中,大量的群智能优化算法被提出,鲸鱼优化算法(WOA)[5]、黏菌优化算法(SMA)[6]、粒子群算法(PSO)[7]、布谷鸟算法(CSA)[8]和象群算法(EHO)[9]等在解决多种优化问题方面有很多成功的应用。除此之外,近几年群智能优化算法在传感器资源分配问题方面的研究也成为热点[10-12]。文献[13]在传统的粒子群算法中引入免疫策略,较大程度提升了算法的全局搜索能力,减少了传感器网络的能耗。文献[14]在多部雷达分配目标时引用萤火虫算法,一定程度提高了目标分配的速度和效果。文献[15]在研究传感器分配中,通过引入粒子群算法并进行优化,提高了传感器资源分配效率。文献[16]提出了基于蚁群算法的多传感器优化分配模型,通过仿真实验证明了其可行性。文献[17]通过精英策略对蛙跳算法进行升级,提高了传感器网络配置算法的收敛速度与时间满意度,文献[18]通过引入种群进化策略对布谷鸟算法进行改进,提高了目标分配的速度和精度。文献[19]通过改进猴群算法对传感器配置进行优化,寻优能力和收敛精度得到加强。文献[20]在解决多约束条件下目标分配问题中通过研究引入多种群遗传算法,提高了算法的搜索能力。文献[21]在多传感器任务调度中,通过添加方向系数和远离因子对粒子群算法进行优化,解决了局部收敛的缺陷。

上述文献中,虽然调度算法在收敛性或稳定性等某一方面得到了改善,但在多目标、复杂和复合多传感器调度优化问题中,调度模型构建考虑因素不全面,缺少说服力;并且在智能搜索算法运用中,由于算法本身的随机特征,存在控制参数设置过多、计算复杂、容易陷入局部最优等缺陷。针对以上问题,由于EHO算法具有全局优化能力、控制参数数量少、实现策略简单等优点,本文选择将EHO算法和反向学习机制(OBL)[22]及正余弦算法(SCA)[23]相结合,提出一种基于IEHO算法的多传感器调度方法,并将其应用到求解传感器调度模型中。

1 传感器调度模型建立

1.1 决策变量

(1)

(2)

(3)

因此,传感器调度方案可以写成式(4)的解矩阵,该矩阵包含目标、传感器和时间三维信息。

(4)

1.2 目标函数

1) 传感器探测效益最大

为提高传感器的探测跟踪效果,在对目标进行探测跟踪时,应选择探测跟踪效益最大的传感器执行任务,在进行多传感器调度建模过程中,由于不同类型的传感器探测影响因素不同,接收到的目标信息不同,本文以传感器和目标之间的距离以及传感器的探测角度来研究传感器探测效益。

传感器对目标的探测效益函数可定义为

(5)

(6)

2) 传感器负载最小

当传感器i对目标j探测全过程中,传感器完成探测跟踪任务的负载为

(7)

在传感器调度时间区间ΔT内,各类传感器的总负载为

(8)

3) 传感器交接次数最少

当目标的运动超过传感器的探测范围或者传感器状态发生改变时,需要考虑在调度区间内传感器之间的交接。对调度区间内的传感器的交接次数进行统计有利于判断传感器是否存在跟丢目标的情况,将相邻两个传感器的探测跟踪矩阵对应元素进行“异或”逻辑运算,可以计算出发生状态改变的传感器数目。

(9)

1.3 约束条件

1) 传感器探测跟踪可行性约束

本文建立的模型的求解是指在调度区间ΔT内随着传感器与目标的可视化情况对应生成的传感器对目标探测跟踪与否的方案,故矩阵t与s内的对应元素存在如下关系：

(10)

2) 传感器观测时间约束

传感器在执行探测跟踪任务时,观测时间应在调度区间内,即

(11)

3) 传感器探测跟踪能力约束

不同传感器因其自身能力与容量设计存在差异,导致每个传感器的探测跟踪目标的数量不能超过其最大的探测跟踪能力,即

(12)

4) 传感器探测跟踪目标最大数量约束

为防止出现多个传感器同时探测跟踪一个目标,根据不同传感器的性能要求,要在实现对目标的连续探测和稳定跟踪的同时避免传感器资源的浪费,应约束传感器资源的最大数量。即

(13)

1.4 调度模型

在前面建立的目标函数和约束条件的基础上,建立如下多传感器调度多目标的调度模型：

(14)

式(14)中,a、b、c分别为探测效益函数、负载函数以及切换函数的权重比,a+b+c=1。

2 多传感器调度算法

2.1 基本象群(EHO)算法原理

1) 部落更新操作

象群算法(elephant herding optimization,EHO)是通过模拟自然界大象部落放牧过程中的社会行为来求解问题的近似解或者最优解[24-25]。算法主要分为两个过程,即部落更新操作和部落分离操作。

来自不同部落的大象在其女族长的领导下一起生活,其他大象的位置都根据女族长和自身的位置进行更新,位置更新公式如式(15)所示。女族长的位置根据部落中心的位置进行更新,由式(16)表示。

xnew,c=xc+α×(xbest,c-xc)×γ,

(15)

式(15)中,xnew,c和xc分别是大象在部落c中的新位置和旧位置;α代表部落中女族长对大象个体的影响因子,α∈[0,1];γ用来增加每一代的种群多样性,γ∈[0,1];xbest,c定义了部落中最适合的大象个体。每个象群部落中最合适的大象位置更新可以如下实现

xbest,c=β×(xcenter,c),

(16)

式(16)中,β设置为 0 和 1 之间的随机数, 它控制着部落中心对女族长位置的影响,其中部落c中心被定义为

(17)

式(17)中,nc是部落c中的大象数量,xc,d是大象个体xc的第d个维度,1≤d≤D,D是搜索空间的总维数。

2) 部落分离操作

每个部落c中适应度最差的个体在当它成熟时将远离部落,在空间中进行随机搜索以增加全局搜索性能,它们的位置更新表达式为

xworst,c=xmin+(xmax-xmin+1)×rand,

(18)

式(18)中,xmax和xmin分别表示种群中大象搜索位置的上、下限,rand∈[0,1]。

2.2 改进象群(IEHO)算法原理

虽然基本象群算法能够较好地解决寻优问题,算法简单,易于实现,但是由于象群优化算法的初始解都是随机生成的,且在空间进行随机搜索,存在收敛速度较慢和易陷入次优区域的问题,同时在部落分离操作位置更新中,采用的是随机更换的方式,适应度最差的个体可能被移动到更差的位置,不能保证搜索获取更优解。针对此问题,通过引入交替使用正余弦算法(SCA)和反向学习机制 (OBL)对算法性能进行改进。

2.2.1正余弦算法(SCA)

正余弦算法是Seyedali于2016年提出的利用正余弦函数的数学模型使解震荡性地趋于最优解的一种方法[20]。针对算法分离操作步骤中适应度最差个体的位置随机替换,采用正余弦算法使适应度最差个体的每个位置都采用了信息正余弦函数共享策略进行替换,使其总是在当前局部最优解周围更新位置,这样能够保证搜索不断趋向于空间的最佳区域,获取更优解。

其位置更新方程为

(19)

式(19)中,γ2∈(0,2π),γ3∈(0,2),γ4∈(0,1)为均匀分布的随机数;xbest,c为当前最优解个体的位置;γ1为控制参数,表示为

(20)

式(20)中,a为一个常数,t为当前迭代次数,Tmax为最大化迭代次数。

2.2.2反向学习策略(OBL)

反向学习策略是由Tizhoosh等人提出的用于改进元启发式算法的收敛性,找到优化问题全局最优解的一种重要方法[21]。它是通过反向学习产生候选解的反向位置,随后采取贪婪策略从当前候选解和反向候选解中寻找最优解决方案,求解思路如下：

1) 更新当前的搜索区域区间;

2) 设定一个反向学习跳变率P(P0∈[0,1],且为一个常数),产生一个随机数rand(rand∈[0,1],且为一个常数),如果rand

3) 根据一般反向学习公式,产生与N个候选解对应的N个反向候选解,其由式(21)表示：

X′i=Xmax+Xmin-Xi,Xi∈[Xmax,Xmin],

(21)

式(21)中,Xi是d维空间中的一个候选解,X′i是Xi的反向候选解;

4) 从候选解∪反向候选解2N个总体中选择最好的N个个体组成新的群体。

本文的OBL算法具体实现：首先,在象群总体初始化中使用OBL,通过在整个搜索域中搜索解,提高收敛速率,避免陷入局部最优;其次,在总体解更新阶段,使用OBL来检查相反方向的更新是否优于当前更新。

2.2.3算法流程

改进象群算法(IEHO)流程图如图1所示。

图1 改进象群算法(IEHO)流程图Fig.1 Improved elephant algorithm (IEHO) flow chart

3 仿真实验结果与分析

3.1 仿真条件

为验证本文算法的有效性,仿真参数如下：侦察卫星8颗,部署高度为300 km,采用2×2×2的Walker星座模型,轨道倾角为55°。X波段地基雷达1个,L波段球载雷达1个,探测距离3 000～5 000 km,空基预警机1个,探测距离700～1 000 km,探测容量均为10。假设在某时刻有8个空袭目标,则传感器对目标探测精度及能耗归一化后如表1所示。

表1 传感器对目标的探测能力及能耗Tab.1 Sensor target detection capability and energy consumption

3.2 算法改进前后传感器调度方案求解对比分析

分别采用基本象群算法(EHO)和改进象群算法(IEHO)对调度方案进行求解。种群容量N=100,最大迭代次数Tmax=100,仿真结果对比如图2所示,传感器调度最优方案对比如表2所示。

表2 最优传感器调度方案对比Tab.2 Comparison of optimal sensor scheduling schemes

图2 改进前后算法适应度值对比Fig.2 Comparison of algorithm fitness values before and after algorithm improvement

从图2可以看出,虽然两个算法最终都收敛到定值,但是收敛速度和最终收敛的值存在差异性, IEHO算法收敛速度较快,在第10次达到稳定,能更快地得到更好的解,最终收敛到0.981,EHO算法收敛速度较慢,在第25次达到稳定最终收敛到0.786,这说明了IEHO算法的优越性。

从表2中可以看出,采用IEHO算法生成的方案中对于每个目标的探测跟踪过程中传感器利用率比较高,减少了传感器资源浪费问题,并且适应度和能耗方面均优于EHO算法。

3.3 改进前后算法时间复杂度分析

上述两种优化算法的计算复杂度主要取决于种群容量N、最大迭代次数T和搜索空间的总维数D。EHO算法的时间复杂度为O(N×D×T),基于EHO种群初始化方法的时间复杂度为O(N×D),利用正余弦算法更新搜索阶段位置的时间复杂度为O(N×D×t),假设引用OBL反向学习实现时间为t,则此时算法的时间复杂度为O(N×D×T+t)=O(N×D×T)。由此可以看出IEHO算法增加了复杂度,但两者处于同一数量级,计算成本没什么差别,因此可以认为,在没有额外成本的情况下,IEHO算法比EHO算法性能更好。

3.4 使用不同优化算法求解对比分析

为进一步说明IEHO算法的优势,将本文算法与鲸鱼优化算法(WOA)、黏菌优化算法(SMA)、基本象群算法(EHO)、粒子群优化算法(PSO)和布谷鸟算法(CSA),关于求解目标函数适应度值、算法运行时间以及探测精度进行对比。各算法参数设置如表3所示。

表3 算法参数设置Tab.3 Algorithm parameter setting

图3中给出了上述不同算法求解目标函数的适应度值曲线。图4给出了不同算法的迭代次数、运行时间和求解精度对比曲线。

图3 不同算法适应度值对比Fig.3 Comparison of fitness values of different algorithms

图4 不同算法迭代次数、运行时间和求解精度对比Fig.4 Comparison of fitness values of different algorithms

从图3中可以看出,尽管所有的算法最终都收敛到定值,但是收敛速度和最终收敛的值存在差异。结合图4可以看出IEHO算法比其他算法都能更快地得到更好的解,收敛速度最快,最终收敛到0.956,这说明了IEHO算法的优越性。EHO算法收敛速度最慢,最终收敛到0.698。主要是因为本文设计算法时将算法在每个阶段存在的劣势进行改进,优化了解的质量。

从图4中不同算法的迭代次数、运行时间和求解精度对比结果可以注意到IEHO算法的优势,IEHO算法的迭代次数、运行时间和求解精度均优于其他算法,与EHO算法相比,迭代次数减少39次,求解精度提高62%,运行时间提高90%。主要原因是IEHO算法通过利用正弦算法在搜索阶段对算法中种群的位置进行更新,在开发阶段通过反向学习更新算法位置方程来不断寻找新的有前景的区域。这种方法有助于防止算法陷入局部最优,改进了EHO算法的局部搜索。

4 结论

本文提出基于改进象群算法的多传感器调度方法。首先建立多传感器调度多目标优化模型,其次通过交替使用正余弦机制和反向学习策略对象群算法的种群多样性、搜索开发之间的平衡和容易陷入局部最优的问题进行了改进。通过仿真实验,进一步验证了改进后的算法具有较强的全局寻优能力和较快的收敛速度,在多传感器调度应用中具有较高的可行性和实效性。