王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1345· PS(nm+)=imS(n)=i,S(n2)=i2,,S(nm)= f(x,y,t+1)=p(x,y,t+1) in=PiS(n)=i.IS(n)=i (11) (3)协同收益 式中，{S(i),i=0,1,2,…,n是马尔可夫链，它的一 f(x,y,t+1)=s(x,y,t+1) 步转移概率为P{S(n+1)=jIS(n)=i,可缩写为 线性整合以上三个收益，生成协作搜索的适应 P 度函数： 在多无人机协同搜索过程中，由于目标未来的 fitness(t)=wf (x,y,t)+of (x,y,t)+osf(x,y,t) 运动状态仅仅与当前状态有关，而与过去的运动状 (15) 态无关，因此，无人机的运动状态可构成典型的马尔 式中，w,ω2和ω分别反应环境不确定收益、目标发 可夫链.当时间离散时，目标下一时刻是运动到它 现收益和协同收益的重要程度，且ω1+w2+ω3=1. 的相邻栅格或静止在当前栅格，由其运动状态转移 矩阵决定 3鸽群优化算法及改进模型 目标运动的状态转移概率依赖于目标运动的特 3.1鸽群优化算法思想 征.根据经验，目标通常运动到无人机对环境不确 鸽群优化算法是受鸽子归巢行为启发设计的一 定性高的栅格，且一步状态转移概率定义为： 种新型群体智能算法.针对鸽子在寻找目标的不同 ud(xi,y;) Pa=ud()+ud(y) (12--1) 阶段使用不同导航工具这一机制，使用2种不同算 子模型：地图和指南针算子、地标算子 ud(x,y） =ud()+ud(jL 在多维搜索空间中初始化鸽子的位置X:和速 (12-2) 0. j使L 度V: 式中，L是目标运动区域：ud(x:,x:)和ud(x,x)分 X:=[xi,x2,…,D] 别是栅格(x,)和(x,x)的不确定性；P:是保持静 V=[a,2,…,vo] 止的概率；P,是运动到相邻栅格的概率 其中：i是第i只鸽子，ie{1,2,…,N},N是鸽子总 另外，目标运动预测的准确与否，很大程度上依 数：D是问题求解维度.每只鸽子根据式(16)更新 赖于目标初始位置的估计.从统计学角度考虑，目 位置和速度： 标运动通常假定遵循一定分布，如：正态分布或Beta (V(t)=V.(t-1)e-xx'+rand.(Xa-X.(t-1)) 分布2].由于Beta分布存在预测步的开销，本文采 (X:(t)=X(t-1)+V,(t) 用两维正态分布表示目标的初始位置，如果目标的 (16) 初始中心位置是(x,少)，(x,y)是相邻位置，方差是 其中：R是地图和指南针因子，随着迭代的进行能降 σ，目标位置的联合概率密度为： 低鸽子的速度；随机数rand∈[0,1]：t是当前迭代 f八x,y）=、1e--0含 e 2m6 (13) 次数；X是t-1次迭代得到的全局最优位置.假 设地图和指南针算子的最大迭代次数是NC,当t> 所以，初始时刻目标位置分布可定义为： NC,时，停止地图和指南针算子，进入地标算子 -0+-0+ 地标算子中，每次迭代鸽子的数量减半，剩余鸽 Po(x,y,0)= f(x,y)dxdy (14) J-0-J-0- 子的中心位置X。,被当作地标，即飞行的参考方向. 2.2适应度函数设计 X和剩余鸽子的位置更新，如式(17)所示： 多无人机协同搜索主要考虑三个因素：尽可能 降低环境的不确定度；尽可能多的发现目标：尽可能 2Xa-1)·fitness(xa-1) 提高搜索效率.因此，适应度函数中应包含环境不 X(t-1)= i= N,∑fitness(X,(t-I) 确定收益、目标发现收益和协同收益三项 (1)环境不确定收益 X,(t)=X:(t-1)+and·(X(t-1)-X:(t-1)) f.(x,y,t+1)=ud(x,y,t+1)-ud(x,y,t) (17) (2)目标发现收益. 式中，V,是t-1次迭代减半的鸽子数；fitness(·)是 根据式(5)和式(14)得到目标在时刻t的位置 每只鸽子的适应度函数.针对求解的最值不同，定 分布，这里定义目标发现收益为目标位置的分布 义也不同.如式(18)所示： 概率： fitness(X;(t-1))=王 瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 P{S(nm + t) = im + t |S(n1 ) = i 1 ,S(n2 ) = i 2 ,…,S(nm) = im} = P{S(nm + t) = im + t |S(nm) = im} (11) 式中,{S(i),i = 0,1,2,…,n}是马尔可夫链,它的一 步转移概率为 P{S(n + 1) = j | S( n) = i},可缩写为 pij . 在多无人机协同搜索过程中,由于目标未来的 运动状态仅仅与当前状态有关,而与过去的运动状 态无关,因此,无人机的运动状态可构成典型的马尔 可夫链. 当时间离散时,目标下一时刻是运动到它 的相邻栅格或静止在当前栅格,由其运动状态转移 矩阵决定. 目标运动的状态转移概率依赖于目标运动的特 征. 根据经验,目标通常运动到无人机对环境不确 定性高的栅格,且一步状态转移概率定义为: pii = ud(xi,yi) 移 j沂L ud(xj,yj) + ud(xi,yi) (12鄄鄄 - 1) pij = ud(xj,yj) ud(xj,yj) + ud(xi,yi) , j沂L 0, j埸 ì î í ïï ïï L (12鄄鄄2) 式中,L 是目标运动区域;ud( xi,xi )和 ud( xj,xj )分 别是栅格(xi,xi)和(xj,xj)的不确定性;pii是保持静 止的概率;pij是运动到相邻栅格的概率. 另外,目标运动预测的准确与否,很大程度上依 赖于目标初始位置的估计. 从统计学角度考虑,目 标运动通常假定遵循一定分布,如:正态分布或 Beta 分布[12] . 由于 Beta 分布存在预测步的开销,本文采 用两维正态分布表示目标的初始位置,如果目标的 初始中心位置是(x0 ,y0 ),(x,y)是相邻位置,方差是 滓 2 0 ,目标位置的联合概率密度为: f(x,y) = 1 2仔滓 2 0 e - (x - x0 )2 + (y - y0 )2 2滓2 0 (13) 所以,初始时刻目标位置分布可定义为: p0 (x,y,0) = 乙 x-x0 + 1 2 x-x0 - 1 2 乙 y-y0 + 1 2 y-y0 - 1 2 f(x,y)dxdy (14) 2郾 2 适应度函数设计 多无人机协同搜索主要考虑三个因素:尽可能 降低环境的不确定度;尽可能多的发现目标;尽可能 提高搜索效率. 因此,适应度函数中应包含环境不 确定收益、目标发现收益和协同收益三项. (1) 环境不确定收益. f e(x,y,t + 1) = ud(x,y,t + 1) - ud(x,y,t) (2) 目标发现收益. 根据式(5)和式(14)得到目标在时刻 t 的位置 分布,这里定义目标发现收益为目标位置的分布 概率: f t(x,y,t + 1) = p(x,y,t + 1) (3) 协同收益. f c(x,y,t + 1) = s(x,y,t + 1) 线性整合以上三个收益,生成协作搜索的适应 度函数: fitness(t) = 棕1 f e(x,y,t) + 棕2 f t(x,y,t) + 棕3 f c(x,y,t) (15) 式中,棕1 、棕2和 棕3分别反应环境不确定收益、目标发 现收益和协同收益的重要程度,且 棕1 + 棕2 + 棕3 = 1. 3 鸽群优化算法及改进模型 3郾 1 鸽群优化算法思想 鸽群优化算法是受鸽子归巢行为启发设计的一 种新型群体智能算法. 针对鸽子在寻找目标的不同 阶段使用不同导航工具这一机制,使用 2 种不同算 子模型:地图和指南针算子、地标算子. 在多维搜索空间中初始化鸽子的位置 Xi 和速 度 Vi: Xi = [xi1 ,xi2 ,…,xiD] Vi = [vi1 ,vi2 ,…,viD] 其中:i 是第 i 只鸽子,i沂{1,2, …,N},N 是鸽子总 数;D 是问题求解维度. 每只鸽子根据式(16)更新 位置和速度: Vi(t) = Vi(t - 1)e - R 伊 t + rand·(Xgbest - Xi(t - 1)) Xi(t) = Xi(t - 1) + Vi(t { ) (16) 其中:R 是地图和指南针因子,随着迭代的进行能降 低鸽子的速度;随机数 rand沂[0,1];t 是当前迭代 次数;Xgbest是 t - 1 次迭代得到的全局最优位置. 假 设地图和指南针算子的最大迭代次数是 NC1当 t > NC1时,停止地图和指南针算子,进入地标算子. 地标算子中,每次迭代鸽子的数量减半,剩余鸽 子的中心位置 Xc,被当作地标,即飞行的参考方向. Xc和剩余鸽子的位置更新,如式(17)所示: Xc(t - 1) = 移 Np i =1 Xi(t - 1)·fitness(Xi(t - 1)) Np移fitness(Xi(t - 1)) Xi(t) = Xi(t - 1) + rand·(Xc(t - 1) - Xi(t - 1 ì î í ï ï ï ï )) (17) 式中,Np是 t - 1 次迭代减半的鸽子数;fitness(·)是 每只鸽子的适应度函数. 针对求解的最值不同,定 义也不同. 如式(18)所示: fitness(Xi(t - 1)) = ·1345·