基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法

工程科学学报，第41卷，第10期：1342-1350,2019年10月 Chinese Journal of Engineering,Vol.41,No.10:1342-1350,October 2019 D0I:10.13374/j.issn2095-9389.2018.09.02.002;http:/journals.ustb.ed.cn 基于改进鸽群优化和马尔可夫链的多无人机协同搜索 方法 王瑞，肖冰松四 空军工程大学航空工程学院，西安710038 ☒通信作者，E-mail:58818252@qq.com 摘要针对多无人机在协同搜索过程中存在重复搜索、目标静止、搜索效率低的问题，提出基于改进鸽群优化和马尔可夫 链的多无人机协同搜索方法.首先，建立类似传感器探测范围的蜂窝状环境模型，降低对搜索区域的重复搜索：其次，建立满 足高斯分布的马尔可夫链动态目标运动模型：然后，将柯西扰动引入基本鸽群优化算法的地图和指南针算子，高斯扰动引入 地标算子，同时利用模拟退火机制保留次优个体，进而有效缓减基本鸽群优化算法易陷入局部最优的问题.最后，通过仿真实 验将本文算法与其他群体智能算法进行比较，结果表明新型算法的合理性和有效性 关键词多无人机：协同搜索：蜂窝状模型：马尔可夫链：柯西扰动：高斯扰动：鸽群优化 分类号V249.1 Cooperative search for multi-UAVs via an improved pigeon-inspired optimization and Markov chain approach WANG Rui,XIAO Bing-song Aeronautics Engineering College,Air Force Engineering University,Xi'an 710038,China Corresponding author,E-mail:58818252@qq.com ABSTRACT Compared with manned aircraft,unmanned aerial vehicles (UAVs)are affordable and convenient for high-risk mis- sions.Therefore,UAVs are increasingly playing an important role in military and civilian fields.Today,UAVs have been exploited to perform special missions carrying some important equipment.However,influenced by the constraints of single UAV's performance and load,it has become a research hotspot that multi-UAVs perform search cooperatively.The process is to minimize the uncertainty of the unknown area and to find the target as much as possible.In terms of cooperation among UAVs,the more effective method based on search map is used.And search process optimization on the basis of distributed model predictive control(DMPC)or traditional swarm intelligence algorithms are adopted,but these methods have some limitations.Due to the behavior of swarm intelligent individual have the characteristics of the decentralization,distribution,and overall self-organization,which match with the requirements of the localiza- tion,distribution and robustness of the UAV cooperate search.Nevertheless,the traditional swarm intelligence algorithms have low search efficiency and are easy to fall into local optimum.To solve the problem of repeated search,static targets and low efficiency in cooperative search for multi-UAVs,a method based on improved pigeon-inspired optimization (PIO)and Markov chain was proposed. Firstly,a honeycomb environmental model similar to the sensor detect region was established to reduce repeated search for the area. Secondly,Markov chain with the Gaussian distribution was used to represent dynamic movement of targets.Thirdly,Cauchy mutation and Gaussian mutation were introduced into the map and compass operator and the landmark operator of PlO,respectively.Meanwhile, 收稿日期：2018-09-02 基金项目：空军工程大学航空工程学院科研创新基金资助项目(CXJJ201809)

工程科学学报,第 41 卷,第 10 期:1342鄄鄄1350,2019 年 10 月 Chinese Journal of Engineering, Vol. 41, No. 10: 1342鄄鄄1350, October 2019 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 09. 02. 002; http: / / journals. ustb. edu. cn 基于改进鸽群优化和马尔可夫链的多无人机协同搜索 方法 王 瑞, 肖冰松苣 空军工程大学航空工程学院, 西安 710038 苣通信作者, E鄄mail: 58818252@ qq. com 摘 要 针对多无人机在协同搜索过程中存在重复搜索、目标静止、搜索效率低的问题,提出基于改进鸽群优化和马尔可夫 链的多无人机协同搜索方法. 首先,建立类似传感器探测范围的蜂窝状环境模型,降低对搜索区域的重复搜索;其次,建立满 足高斯分布的马尔可夫链动态目标运动模型;然后,将柯西扰动引入基本鸽群优化算法的地图和指南针算子,高斯扰动引入 地标算子,同时利用模拟退火机制保留次优个体,进而有效缓减基本鸽群优化算法易陷入局部最优的问题. 最后,通过仿真实 验将本文算法与其他群体智能算法进行比较,结果表明新型算法的合理性和有效性. 关键词 多无人机; 协同搜索; 蜂窝状模型; 马尔可夫链; 柯西扰动; 高斯扰动; 鸽群优化 分类号 V249郾 1 收稿日期: 2018鄄鄄09鄄鄄02 基金项目: 空军工程大学航空工程学院科研创新基金资助项目(CXJJ201809) Cooperative search for multi鄄UAVs via an improved pigeon鄄inspired optimization and Markov chain approach WANG Rui, XIAO Bing鄄song 苣 Aeronautics Engineering College, Air Force Engineering University, Xi爷an 710038, China 苣Corresponding author, E鄄mail: 58818252@ qq. com ABSTRACT Compared with manned aircraft, unmanned aerial vehicles (UAVs) are affordable and convenient for high鄄risk mis鄄 sions. Therefore, UAVs are increasingly playing an important role in military and civilian fields. Today, UAVs have been exploited to perform special missions carrying some important equipment. However, influenced by the constraints of single UAV爷s performance and load, it has become a research hotspot that multi鄄UAVs perform search cooperatively. The process is to minimize the uncertainty of the unknown area and to find the target as much as possible. In terms of cooperation among UAVs, the more effective method based on search map is used. And search process optimization on the basis of distributed model predictive control (DMPC) or traditional swarm intelligence algorithms are adopted, but these methods have some limitations. Due to the behavior of swarm intelligent individual have the characteristics of the decentralization, distribution, and overall self鄄organization, which match with the requirements of the localiza鄄 tion, distribution and robustness of the UAV cooperate search. Nevertheless, the traditional swarm intelligence algorithms have low search efficiency and are easy to fall into local optimum. To solve the problem of repeated search, static targets and low efficiency in cooperative search for multi鄄UAVs, a method based on improved pigeon鄄inspired optimization (PIO) and Markov chain was proposed. Firstly, a honeycomb environmental model similar to the sensor detect region was established to reduce repeated search for the area. Secondly, Markov chain with the Gaussian distribution was used to represent dynamic movement of targets. Thirdly, Cauchy mutation and Gaussian mutation were introduced into the map and compass operator and the landmark operator of PIO, respectively. Meanwhile

王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1343· simulated annealing(SA)mechanism was exploited to reserve the worse individual,which effectively reduced the problem that PIO was easy to fall into local optimum.Finally,the algorithm was compared with other swarm intelligence algorithms through simulation experi- ments.The results show that the new method is effective and available. KEY WORDS multi-UAVs;cooperative search;honeycomb model;Markov chain;Cauchy mutation;Gaussian mutation;pigeon- inspired optimization 军事领域的智能无人化发展，是“加快军事智 响其性能的主要因素有搜索环境、无人机自身特性、 能化发展”的重要内容，也是军事智能“由人向物” 目标运动等 迁移的关键领域.无人机具有持续工作能力强、全 1.1环境信息图 寿命周期成本低等特点，在尺寸、速度和机动性等方 环境信息图，是无人机在搜索过程中对环境不 面具有独特的优势口，成为影响未来信息化战争的 确定性的反应.文献[4]和[9]均采用矩形栅格离 时代力量.由于单架无人机所能携带的任务载荷相 散化搜索区域，但是传感器对周围环境的探测更接 对单一，执行任务能力有限，而通过多无人机的能力 近于圆形域，所以本文采用六边形构建蜂窝状的搜 互补和行动协调，可实现整个系统效能的提升.因 索环境，这样可以减少重复区域的搜索，进而提高搜 此，无人机的应用样式逐步从单平台向群体智能的 索效率.将搜索区域L离散化为L×L,的栅格，每 多平台发展 架无人机看作栅格中的一个质点，这样多无人机协 多无人机协同搜索，即多架无人机按照一定的 同搜索问题就可以转化成无人机之间栅格位置的协 搜索规则，在未知区域中最大限度地降低环境的不 同.构建环境信息模型如图1所示. 确定性，且尽可能地发现目标的过程.Peng等对 几种典型协同目标搜索策略进行仿真分析.如，随 机搜索、贪婪搜索、滚动时域控制(receding horizon control,RHC)搜索等.由于群体智能个体行为的去 中心化、交互合作分布式、整体自组织等特点与无人 机协同搜索的局部性、分布式和鲁棒性等要求存在 契合之处[).因此，研究群体智能的多无人机协同 图1环境信息模型 Fig.I Environmental information model 搜索成为热点话题.文献[4]基于搜索图建立环境 模型，采用局部粒子群实时构建无人机子群，实现分 图1中，灰色阴影部分为搜索区域.假设该区 布式搜索多个静态目标.Yang等]提出基于不确 域用二维坐标(x,y)表示，传感器的探测半径为「， 定环境的改进蚁群多无人机协同搜索方法，该方法 横坐标x的增幅△x为V5r,纵坐标y的增幅△y为 使用改进蚁群算法的行为规则决定航路点的转移， 3r/2. 并基于信息素图进行更新.但是基于群体智能的蚁 假设p(x,y,t)是t时刻目标在栅格(x,y)内存 群优化算法、粒子群优化算法、人工蜂群优化算法存 在的概率，p(x,y,t)∈[0,1].ud(x,y,t)是环境信 在搜索效率低、收敛速度慢等问题，段海滨等6)提 息的不确定度，可用目标存在概率p(x,y,t)的嫡描 出的鸽群优化(pigeon-inspired optimization,PIO)算 述，定义为： 法能够有效克服以上问题，并已在很多方面取得研 (0 p(x,y,t)=0或者1 究成果).Li等[8】提出边缘势函数和改进鸽群优化 ud(x,y,t)= (H[p(x,y,)]其他 的图像目标检测方法.但以上算法在两方面存在局 (1) 限性：(1)针对静态目标完成协同搜索：(2)群体智 H[p(x,y,t)]=-p(x,y,t)logzp(x,y,t)- 能算法容易陷入局部最优.因此，本文提出运动目 (1-p(x,y,t))log2(1-p(x,y,t))(2) 标模型和扰动模拟退火鸽群优化(mutations simula- 1.2无人机运动模型 ted annealing pigeon-inspired optimization,MSAPIO) 假设所有无人机处于相同飞行高度.UAV,在t 算法完成多无人机协同搜索 时刻的状态信息x:(t)为： 系统建模 x:(t)=[pos:(t)且0：(t)] (3) 式中，pos(t)=(x:(t),y:(t))∈{1,2，，L}× 多无人机协同搜索是一个复杂的动态过程，影 {1,2,…,L,}为UAV的空间位置；方向O,(t)∈{0

王 瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 simulated annealing (SA) mechanism was exploited to reserve the worse individual, which effectively reduced the problem that PIO was easy to fall into local optimum. Finally, the algorithm was compared with other swarm intelligence algorithms through simulation experi鄄 ments. The results show that the new method is effective and available. KEY WORDS multi鄄UAVs; cooperative search; honeycomb model; Markov chain; Cauchy mutation; Gaussian mutation; pigeon鄄 inspired optimization 军事领域的智能无人化发展,是“加快军事智 能化发展冶的重要内容,也是军事智能“由人向物冶 迁移的关键领域. 无人机具有持续工作能力强、全 寿命周期成本低等特点,在尺寸、速度和机动性等方 面具有独特的优势[1] ,成为影响未来信息化战争的 时代力量. 由于单架无人机所能携带的任务载荷相 对单一,执行任务能力有限,而通过多无人机的能力 互补和行动协调,可实现整个系统效能的提升. 因 此,无人机的应用样式逐步从单平台向群体智能的 多平台发展. 多无人机协同搜索,即多架无人机按照一定的 搜索规则,在未知区域中最大限度地降低环境的不 确定性,且尽可能地发现目标的过程. Peng 等[2] 对 几种典型协同目标搜索策略进行仿真分析. 如,随 机搜索、贪婪搜索、滚动时域控制( receding horizon control,RHC)搜索等. 由于群体智能个体行为的去 中心化、交互合作分布式、整体自组织等特点与无人 机协同搜索的局部性、分布式和鲁棒性等要求存在 契合之处[3] . 因此,研究群体智能的多无人机协同 搜索成为热点话题. 文献[4]基于搜索图建立环境 模型,采用局部粒子群实时构建无人机子群,实现分 布式搜索多个静态目标. Yang 等[5] 提出基于不确 定环境的改进蚁群多无人机协同搜索方法,该方法 使用改进蚁群算法的行为规则决定航路点的转移, 并基于信息素图进行更新. 但是基于群体智能的蚁 群优化算法、粒子群优化算法、人工蜂群优化算法存 在搜索效率低、收敛速度慢等问题,段海滨等[6] 提 出的鸽群优化( pigeon鄄inspired optimization,PIO) 算 法能够有效克服以上问题,并已在很多方面取得研 究成果[7] . Li 等[8]提出边缘势函数和改进鸽群优化 的图像目标检测方法. 但以上算法在两方面存在局 限性:(1)针对静态目标完成协同搜索;(2)群体智 能算法容易陷入局部最优. 因此,本文提出运动目 标模型和扰动模拟退火鸽群优化(mutations simula鄄 ted annealing pigeon鄄inspired optimization, MSAPIO) 算法完成多无人机协同搜索. 1 系统建模 多无人机协同搜索是一个复杂的动态过程,影 响其性能的主要因素有搜索环境、无人机自身特性、 目标运动等. 1郾 1 环境信息图 环境信息图,是无人机在搜索过程中对环境不 确定性的反应. 文献[4]和[9]均采用矩形栅格离 散化搜索区域,但是传感器对周围环境的探测更接 近于圆形域,所以本文采用六边形构建蜂窝状的搜 索环境,这样可以减少重复区域的搜索,进而提高搜 索效率. 将搜索区域 L 离散化为 Lx 伊 Ly的栅格,每 架无人机看作栅格中的一个质点,这样多无人机协 同搜索问题就可以转化成无人机之间栅格位置的协 同. 构建环境信息模型如图 1 所示. 图 1 环境信息模型 Fig. 1 Environmental information model 图 1 中,灰色阴影部分为搜索区域. 假设该区 域用二维坐标(x, y)表示,传感器的探测半径为 r, 横坐标 x 的增幅 驻x 为 3 r,纵坐标 y 的增幅 驻y 为 3r/ 2. 假设 p(x,y,t)是 t 时刻目标在栅格( x,y)内存 在的概率,p(x,y,t)沂[0,1]. ud(x,y,t)是环境信 息的不确定度,可用目标存在概率 p( x,y,t)的熵描 述,定义为: ud(x,y,t) = 0 p(x,y,t) = 0 或者 1 H[p(x,y,t)] { 其他 (1) H[p(x,y,t)] = - p(x,y,t)log2 p(x,y,t) - (1 - p(x,y,t))log2 (1 - p(x,y,t)) (2) 1郾 2 无人机运动模型 假设所有无人机处于相同飞行高度. UAVi在 t 时刻的状态信息 xi(t)为: xi(t) = [posi(t)且 Oi(t)] (3) 式中,posi( t) = ( xi ( t),yi ( t)) 沂{1,2, …,Lx } 伊 {1,2, …,Ly}为 UAVi的空间位置;方向 Oi(t)沂{0, ·1343·

.1344· 工程科学学报.第41卷，第10期 1,2,3,4,5,6,7},如图2所示，8个数字代表8个方 信息素的数量： 向.UAV在飞行过程中由于受到最小转弯变径的限 (3)E,和E.表示引力信息素和斥力信息素的 制，只能到达相邻的三个位置，即直行、左拐和右拐 蒸发系数： 即： (4)P,和P.表示引力信息素和斥力信息素的 0(t+1)∈{0：(t)-1,0:(t),0(t)+1}mod8 传播系数 (4) 假设数字信息素按照先传播后蒸发的原则进行 计算.那么，t时刻栅格(x,y)的引力信息素sa定 义为： sa(x,y,t)=(1-Ea)[(1-Pa)(sa(x,y,t-1)+ d,(x,y,t)+ga(x,y,t) (6) 式中，∈(0,1)是调节因子；f(x,y)是最后一次访 问栅格(x,y)到当前的时间周期数，定义为： fx.y)=4(z.r) 图2UAVs可选航向图 T。 Fig.2 UAVs optional heading diagram 8a(x,y,t)= 1.3目标信息图 P -1)+d()) 目标信息图，反应特定栅格目标存在的概率，其 (7) 先验信息由情报和监视平台提供.随着搜索的进 式中，(x,y)是最后一次访问栅格(x,y)到当前的时 行，目标信息图在不断更新.假设在t时刻，栅格 间：T是信息素更新周期，通常设置为无人机运动周 (x,y)的目标存在概率为p(x,y,t),其更新方法为： 期的10倍；Nei(x,y)是(x,y)的相邻栅格；N(x',y') p(x,y,t+1)= 是相邻栅格总数.g4(x,y,)定义表明，传播到栅格 Pap(x,y,t) 8(t)=1 (x,y)的引力信息素量是所有相邻栅格对外传播总 Pr+(Pa-pr)p(x,y,t)' 量的加权和 (1-Pa)p(x,y,t) 与引力信息素类似，t时刻栅格(x,y)的斥力信 1+pap(x.y.t)-P:(1-p(x.y.t)). 6(t)=0 息素s定义为： (5) sR(x,y,t)=(1-ER)[(1-P)(s(x,y,1-1)+ 式中，6(t)=1表示栅格(x,y)中的目标被发现； dg(x.y,t)+ga(x,y,t)) (8) δ(t)=0表示未被发现.p和p,分别表示检测率和误 gr(x,y,t)的更新方法为： 报率 gn(x,y,t)= 1.4数字信息素图 通过人工势函数实现无人机之间位置的协同， P (5n(y-1)+d()) 可以有效形成多机空间结构，但是存在任务协调性 (9) 不好，资源浪费的问题.而基于数字信息素的多无 因此，t时刻栅格(x,y)的信息素浓度定义为引 人机协同机制能够解决该问题).数字信息素图 力信息素与斥力信息素的差 (digital pheromone map)),本质上是一种具有隐性 s(x,y,t)=sA(x,y,t)-sR(x,y,t) (10) 协调机制的扩展势场方法.本文定义引力信息素和 2目标运动模型和适应度函数 斥力信息素两种基本信息素，实现无人机的动态协 作行为 2.1目标运动模型 首先，定义表示相应栅格信息素浓度的参数： 马尔可夫链是时间和状态均离散的特殊马尔可 (1)d(x,y,t)和d(x,y,t)是常量，表示t时 夫过程，它不具有后验特征，相关定义如下： 刻栅格(x,y)释放的引力信息素和斥力信息素的 定义1：马尔可夫链.假定状态空间的离散随机 数量： 序列{S(i),i=0,1,2,…,n}为1，m个非负整数n1, (2)ga(x,y,t)和g(x,y,t)表示(t-1,t]时间 n2,…,nn(0≤m1<n2<…<nn)以及所有t>0,i1, 内从相邻栅格传入栅格(x,y)的引力信息素和斥力 i2,…,im,imtn∈l有：

工程科学学报,第 41 卷,第 10 期 1,2,3,4,5,6,7},如图 2 所示,8 个数字代表 8 个方 向. UAV 在飞行过程中由于受到最小转弯变径的限 制,只能到达相邻的三个位置,即直行、左拐和右拐. 即: Oi(t + 1)沂{Oi(t) - 1,Oi(t),Oi(t) + 1}mod 8 (4) 图 2 UAVs 可选航向图 Fig. 2 UAVs optional heading diagram 1郾 3 目标信息图 目标信息图,反应特定栅格目标存在的概率,其 先验信息由情报和监视平台提供. 随着搜索的进 行,目标信息图在不断更新. 假设在 t 时刻,栅格 (x,y)的目标存在概率为 p(x,y,t),其更新方法为: p(x,y,t + 1) = pd p(x,y,t) pf + (pd - pf)p(x,y,t) , 啄(t) = 1 (1 - pd )p(x,y,t) 1 + pd p(x,y,t) - pf(1 - p(x,y,t)) , 啄(t) ì î í ï ï ï ï = 0 (5) 式中,啄( t) = 1 表示栅格( x,y) 中的目标被发现; 啄(t) = 0表示未被发现. pd和 pf分别表示检测率和误 报率. 1郾 4 数字信息素图 通过人工势函数实现无人机之间位置的协同, 可以有效形成多机空间结构,但是存在任务协调性 不好,资源浪费的问题. 而基于数字信息素的多无 人机协同机制能够解决该问题[10] . 数字信息素图 (digital pheromone map) [11] ,本质上是一种具有隐性 协调机制的扩展势场方法. 本文定义引力信息素和 斥力信息素两种基本信息素,实现无人机的动态协 作行为. 首先,定义表示相应栅格信息素浓度的参数: (1) dA (x,y,t)和 dR (x,y,t)是常量,表示 t 时 刻栅格( x,y) 释放的引力信息素和斥力信息素的 数量; (2) gA(x,y,t)和 gR(x,y,t)表示(t - 1,t]时间 内从相邻栅格传入栅格( x,y)的引力信息素和斥力 信息素的数量; (3) EA和 ER表示引力信息素和斥力信息素的 蒸发系数; (4) PA和 PR表示引力信息素和斥力信息素的 传播系数. 假设数字信息素按照先传播后蒸发的原则进行 计算. 那么,t 时刻栅格( x,y) 的引力信息素 sA 定 义为: sA(x,y,t) = (1 - EA)[(1 - PA)(sA(x,y,t - 1) + 姿 1 f(x,y) dA(x,y,t) + gA(x,y,t))] (6) 式中,姿沂(0,1)是调节因子;f( x,y)是最后一次访 问栅格(x,y)到当前的时间周期数,定义为: f(x,y) = t(x,y) Tc gA(x,y,t) = (x忆,y忆) 移沂Nei(x,y) PA N(x忆,y忆) (sA(x忆,y忆,t -1) + dA(x忆,y忆,t)) (7) 式中,t(x,y)是最后一次访问栅格(x,y)到当前的时 间;Tc是信息素更新周期,通常设置为无人机运动周 期的 10 倍;Nei(x,y)是(x,y)的相邻栅格;N(x忆,y忆) 是相邻栅格总数. gA(x,y,t)定义表明,传播到栅格 (x,y)的引力信息素量是所有相邻栅格对外传播总 量的加权和. 与引力信息素类似,t 时刻栅格( x,y)的斥力信 息素 sR定义为: sR(x,y,t) = (1 - ER)[(1 - PR)(sR(x,y,t - 1) + 姿 f(x,y) dR(x,y,t) + gR(x,y,t))] (8) gR(x,y,t)的更新方法为: gR(x,y,t) = (x忆,y忆) 移沂Nei(x,y) PR N(x忆,y忆) (sR(x忆,y忆,t -1) + dR(x忆,y忆,t)) (9) 因此,t 时刻栅格(x,y)的信息素浓度定义为引 力信息素与斥力信息素的差. s(x,y,t) = sA(x,y,t) - sR(x,y,t) (10) 2 目标运动模型和适应度函数 2郾 1 目标运动模型 马尔可夫链是时间和状态均离散的特殊马尔可 夫过程,它不具有后验特征,相关定义如下: 定义 1:马尔可夫链. 假定状态空间的离散随机 序列{S(i),i = 0,1,2,…,n}为 I,m 个非负整数 n1 , n2 ,…,nm (0臆n1 < n2 < … < nm )以及所有 t > 0,i 1 , i 2 ,…,im ,im + t沂I. 有: ·1344·

王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·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·

·1346· 工程科学学报.第41卷，第10期 1 最小值 由于地标算子是对目标的精细搜索，在初始扰 fitness(X;(t-1))+s (18) 动时的步长可以稍大一些，但随着迭代的进行扰动 fitness(X (t-1)), 最大值 步长应逐渐减小.而logsig(·)函数恰好具有从1到 假设地标算子的最大迭代次数是NC2,当t> 0的非线性下降特性.所以，本文引入logsig(·)函 NC,时，停止地标算子.记录每次迭代的最优位置， 数表示扰动步长，其位置更新如式(22)所示.扰动 并用X表示： 时机为中心位置X在最近的K,次迭代内，如果每一 X。=max(X.(1),X.(2),…,X(t)) 维变化大小的绝对值小于阈值2，那么，对中心位置 3.2鸽群优化算法的改进模型 X执行高斯扰动操作 基本鸽群优化算法的每一次迭代均在寻找全局 最优，虽然具有收敛速度快、搜索效率高的优势，但 该思想在求解多最值问题时极易陷入局部最优 X:(t)=X:(t-1)+and(X(t-1)-X,(t-1) 为了最大限度地避免算法模型陷入局部最优， (22) 本文将柯西因子、高斯因子和模拟退火[1)(simula- 另外，基本鸽群优化算法在搜索过程中，始终 ted annealing,SA)机制引入基本鸽群优化算法模型 寻找全局最优解，极易陷入局部最优.因此，应以 中，从而提高算法性能.在进化计算理论中，高斯 一定概率保留次优个体.20世纪80年代提出的 扰动和柯西扰动是两种流行的扰动技术.柯西扰 模拟退火算法可以解决这一问题.假定，次优个体 动在跳出局部最优方面具有优势，而高斯扰动在 以概率P保留，添加高斯扰动后的个体X.与扰动 局部收敛方面表现较好4).因此，可将柯西扰动 前的个体X之间适应度值的差为△f,概率P,定 引入基本鸽群优化算法的地图和指南针算子，高 义为： 斯扰动引入地标算子，这样既可以避免过早收敛 P.exp (Af/T) (23) 陷入局部最优问题，又可以确保地标算子找到全 式中，T是退火温度，随着迭代的进行该值逐渐下 局最优解 降.而且，如果初始退火温度较高，退火率较低，改 便于扰动机制的描述，在搜索目标函数最大 进模型将更有助于跳出局部最优 值时，将每一维位置x:看成1，即x:=x:,则扰动后 将上述思想融入基本鸽群优化算法，得到扰动 的位置x=x:=x:+△r·X;△r是扰动步长，X是随 模拟退火鸽群优化(MSAPIO)算法模型.算法实现 机变量.若采用高斯扰动，则X是满足高斯分布的 过程描述如下. 一个随机变量X=N(u,σ2)，其概率密度函数如式 第一步：建立搜索图.根据式(5)和式(14)构 (19)所示： 建目标信息图，根据式(1)构建环境信息图： 第二步：初始化参数.初始化扰动模拟退火鸽 人(x)=】e器x(-0,+）(19) V2To 群优化算法参数.如，鸽子总数N:两个算子的最大 若采用柯西扰动，则X是满足柯西分布的随机 迭代次数NC,、NC,(具体如表1所示)，以及鸽群中 变量X=C,其概率密度函数如式(20)所示： 每只鸽子的初始位置和初始速度等； 第三步：估计鸽子的适应度值.利用式(15)的 适应度函数评价每只鸽子的位置： 因此，在地图和指南针算子中引入柯西扰动的 第四步：地图和指南针算子更新.利用式(16) 新一代鸽子的位置、速度更新如式(21)所示).扰 基本鸽群优化算法的地图和指南针算子更新位置和 动时机为全局最优的适应度函数值在最近K,次迭 速度，每次迭代，若有鸽子的适应度值优于X,则 代内，如果变化大小的绝对值小于阈值e,:那么，对 利用该鸽子的位置替换X;若满足柯西扰动条 全局最优位置执行柯西扰动操作 件，利用式(21)跳出局部最优，继续执行本步操作， 直至迭代次数达到NC,; V,(t)=(t-l)eRx+{X+ 第五步：地标算子更新.利用式(17)基本鸽群 axtn [=(rand-)]-x(t-1)) 优化算法的地标算子更新中心位置和每只鸽子位 置，每次迭代，若新一代X(t)优于上一代X(t- X:(t)=X:(t-1)+V(t) 1),则利用新一代X.()替换上一代X(t-1):若满 21) 足高斯扰动条件，利用式(22)局部调整，若高斯扰

工程科学学报,第 41 卷,第 10 期 1 fitness(Xi(t - 1)) + 着 , 最小值 fitness(Xi(t - 1)), ì î í ïï ïï 最大值 (18) 假设地标算子的最大迭代次数是 NC2 ,当 t > NC2时,停止地标算子. 记录每次迭代的最优位置, 并用 Xp表示: Xp = max (Xg (1),Xg (2),…,Xg (t)) 3郾 2 鸽群优化算法的改进模型 基本鸽群优化算法的每一次迭代均在寻找全局 最优,虽然具有收敛速度快、搜索效率高的优势,但 该思想在求解多最值问题时极易陷入局部最优. 为了最大限度地避免算法模型陷入局部最优, 本文将柯西因子、高斯因子和模拟退火[13] ( simula鄄 ted annealing,SA)机制引入基本鸽群优化算法模型 中,从而提高算法性能. 在进化计算理论中,高斯 扰动和柯西扰动是两种流行的扰动技术. 柯西扰 动在跳出局部最优方面具有优势,而高斯扰动在 局部收敛方面表现较好[14] . 因此,可将柯西扰动 引入基本鸽群优化算法的地图和指南针算子,高 斯扰动引入地标算子,这样既可以避免过早收敛 陷入局部最优问题,又可以确保地标算子找到全 局最优解. 便于扰动机制的描述,在搜索目标函数最大 值时,将每一维位置 xi 看成 1,即 xi = xi,则扰动后 的位置 x忆i = x忆i = xi + 驻r·X;驻r 是扰动步长,X 是随 机变量. 若采用高斯扰动,则 X 是满足高斯分布的 一个随机变量 X = N(滋,滓 2 ) ,其概率密度函数如式 (19)所示: fN(x) = 1 2仔滓 e - (x - 滋)2 2滓2 ,x沂( - 肄 , + 肄 ) (19) 若采用柯西扰动,则 X 是满足柯西分布的随机 变量 X = C,其概率密度函数如式(20)所示: f c(x) = 1 ( 仔 a a 2 + x 2 ) ,x沂( - 肄 , + 肄 ) (20) 因此,在地图和指南针算子中引入柯西扰动的 新一代鸽子的位置、速度更新如式(21)所示[15] . 扰 动时机为全局最优的适应度函数值在最近 K1次迭 代内,如果变化大小的绝对值小于阈值 e1 ;那么,对 全局最优位置执行柯西扰动操作. Vi(t) = Vi(t - 1)e - R 伊 t + { Xgbest + a 伊 tan [ 仔 (rand - ) ] 1 2 - Xi(t - 1)) } Xi(t) = Xi(t - 1) + Vi(t ì î í ï ïï ï ïï ) (21) 由于地标算子是对目标的精细搜索,在初始扰 动时的步长可以稍大一些,但随着迭代的进行扰动 步长应逐渐减小. 而 logsig(·)函数恰好具有从 1 到 0 的非线性下降特性. 所以,本文引入 logsig(·) 函 数表示扰动步长,其位置更新如式(22)所示. 扰动 时机为中心位置 Xc在最近的 K2次迭代内,如果每一 维变化大小的绝对值小于阈值 e2 ,那么,对中心位置 Xc执行高斯扰动操作. X忆c(t -1) = Xc(t -1) + log sig ( NC2 / 2 - t ) k N(滋,滓) Xi(t) = Xi(t -1) + rand·(X忆c(t -1) - Xi(t -1 { )) (22) 另外,基本鸽群优化算法在搜索过程中,始终 寻找全局最优解,极易陷入局部最优. 因此,应以 一定概率保留次优个体. 20 世纪 80 年代提出的 模拟退火算法可以解决这一问题. 假定,次优个体 以概率 Pr保留,添加高斯扰动后的个体 Xig与扰动 前的个体 X 之间适应度值的差为 驻f,概率 Pr 定 义为: Pr = exp (驻f / T) (23) 式中,T 是退火温度,随着迭代的进行该值逐渐下 降. 而且,如果初始退火温度较高,退火率较低,改 进模型将更有助于跳出局部最优. 将上述思想融入基本鸽群优化算法,得到扰动 模拟退火鸽群优化(MSAPIO)算法模型. 算法实现 过程描述如下. 第一步:建立搜索图. 根据式(5) 和式(14) 构 建目标信息图,根据式(1)构建环境信息图; 第二步: 初始化参数. 初始化扰动模拟退火鸽 群优化算法参数. 如,鸽子总数 N;两个算子的最大 迭代次数 NC1 、NC2 (具体如表 1 所示),以及鸽群中 每只鸽子的初始位置和初始速度等; 第三步:估计鸽子的适应度值. 利用式(15)的 适应度函数评价每只鸽子的位置; 第四步:地图和指南针算子更新. 利用式(16) 基本鸽群优化算法的地图和指南针算子更新位置和 速度,每次迭代,若有鸽子的适应度值优于 Xgbest,则 利用该鸽子的位置替换 Xgbest;若满足柯西扰动条 件,利用式(21)跳出局部最优,继续执行本步操作, 直至迭代次数达到 NC1 ; 第五步:地标算子更新. 利用式(17)基本鸽群 优化算法的地标算子更新中心位置和每只鸽子位 置,每次迭代,若新一代 Xc ( t) 优于上一代 Xc ( t - 1),则利用新一代 Xc(t)替换上一代 Xc(t - 1);若满 足高斯扰动条件,利用式(22) 局部调整,若高斯扰 ·1346·