《工程科学学报》：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法.pdf_大学文库

工程科学学报，第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≤m10,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 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·

王瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法动后的中心位置次于扰动前的位置,计算二者的差, 利用式(23)确定 Pr . 然后,用随机数 rand沂(0,1) 与 Pr比较,若 rand < Pr,保留次优位置,否则,退回扰动前状态,继续执行本步操作,直至迭代次数达到 NC2 ,算法收敛. 基本鸽群优化算法的时间复杂度为 O(N + NC1* N*D + NC2*N^2 + N*D),模拟退火算法的时间复杂度是 O(( T0 - Tmin ) / c). 其中,T0 是初始退火温度;Tmin是最低温度;c 是降温速率. 由于模拟退火算法只在地标算子寻优中加入,所以扰动模拟退火鸽群优化算法的时间复杂度为 O(N + NC1*N*D + NC2*N^2 + N*(D + (T0 - Tmin ) / c)). 基本鸽群优化(PIO)算法和扰动模拟退火鸽群优化(MSAPIO)算法的参数选择如表 1 所示: 表 1 PIO 和 MSAPIO 参数表 Table 1 Parameters of PIO and MSAPIO 参数参数定义数值应用 NC1 地图和指南针算子迭代次数 15 NC2 地标算子迭代次数 5 N 鸽子总数 50 R 地图和指南针因子 0郾 3 鸽群优化扰动模拟退火鸽群优化 a 柯西分布概率密度参数 1 滋高斯分布率密度函数参数(均值) 0 滓高斯分布概率密度函数参数(方差) 1 K1 地图和指南针算子的柯西扰动条件 3 K2 地标算子的高斯扰动条件 2 e1 地图和指南针算子扰动阈值 0郾 1 e2 地标算子扰动阈值 0郾 01 T0 初始退火温度 100 扰动模拟鸽群优化 4 实验结果和分析首先,使用经典适应度函数验证本文算法相对基本鸽群优化算法的优越性. 然后从搜索覆盖范围和发现目标数目两个方面衡量多无人机协同搜索的性能. 4郾 1 算法性能比较本文算法采用扰动和模拟退火机制,相对基本鸽群优化算法易跳出局部最优. 使用多峰适应度评价函数进行测试,图 3(a)使用 Rastrigrin 函数,其在 x = (0,0,…,0)处取得极小值 0,为了便于观察对函数取反,即这里取极大值 0;图 3(b)使用 Schaffer 函数,其在 x = (0,0,…,0)处取得极大值 1. 每个函数的前两幅图是基本鸽群优化算法随机一次运行和 10 次迭代取最大值、最小值和均值的收敛情况;后两幅图是扰动模拟退火鸽群优化算法随机一次运行和 10 次迭代取最大值、最小值和均值的收敛情况. 从图中不难发现,本文算法能够有效避免陷入局部最优. 4郾 2 搜索范围覆盖率假设搜索区域 L 为10 伊 10 的栅格. 图4(a)中, 红色“ 伊冶是随机产生的目标初始位置,数字“1,2, 3,4,5,6冶是中间被包围目标下一时刻可能的运动位置. 图 4(b)是随机产生的初始环境不确定度,且绿色阴影部分正比于不确定度. 为了验证本文算法的优越性,图 5 是 4 架无人机在不同仿真步数下的运动轨迹和搜索范围覆盖率,便于观察运动情况. 图5(a)和图5(b)仅给出无人机和目标 1 在 30 步和 60 步的运动轨迹,图 5(c) 是不同算法的搜索范围随着搜索步数的变化情况. 将 20 km 伊 20 km 的搜索区域划分为20 伊 20 的栅格, 4 架无人机的初始位置用“荥冶表示;“ 伊冶是随机产生的动态目标,“si冶是第 i 个目标的起始位置,“ ei冶是经马尔可夫链运动后的终止位置. 由图分析可知,无人机能够用最小步数,实现尽可能多的目标搜索,而且随着搜索步数的增加搜索覆盖范围不断扩大. 4郾 3 搜索目标有效性图 6 从搜索目标的有效性对基本鸽群优化算法、蚁群算法以及扰动模拟退火鸽群优化算法这 3 种算法做仿真分析比较,且图 6( a)和图 6( b)分别表示搜索目标平均数和搜索策略有效性. 使用 4 ·1347·

.1348· 工程科学学报.第41卷，第10期 0al)P0算法随机一次收敛情况 (a2) PIO-Rastrigrin函数 a3) MSAPIO算法迭代收敛情况 -2 -20 0 -6 80 最大值一最小值 6 -10 -1 平均值 -8 12 -120 -10 10 2030 40 50 -140% 10 20 30 40 50 16 10 2030 40 50 迭代次数迭代次数迭代次数 0.9628 1.0 -20 (a4 MSAPIO- b1) b2) PO算法随机一次收敛情况 PIO-Schafferp函数 Rastrigrin函数 0.9627 0.8 -40 -60 赵0.9626 0.6 一最大值 -80 一最大值 0.9625 0.4 一最小值 ·平均值 -100 一最小值 -120 ·平均值 0.9624 0.2 -140 20 30 40 50 0.96236 10 2030 50 公 2030 50 迭代次数送代次数迭代次数 1.000 1.0 b3) MSAPIO b4) MSAPIO- 0.998 算法迭代收敛情况 0.8 Schaffer函数 0.996 0.6 0.994 0.4 0.992 一最大值 0.2 一最小值 0.990 ·平均值 0.9880 10 2030 40 50 10 2030 40 50 迭代次数迭代次数图3不同函数随机一次和10次迭代最优值收敛情况.(a)Rastrigrin:(b)Schaffer Fig.3 Optimal value convergence of different functions at random times and 10 times of iteration:(a)Rastrigrin:(b)Schaffer (a 3 30 2 24 2 220 0 15 20 25 30 35 18 40 15 20 25 30 35 40 x/km x/km 图4目标和环境的初始状态.()目标初始位置：(b)初始环境不确定图 Fig.4 Initial state of target and environment:(a)initial position of the target:(b)initial environment uncertainty 架无人机对不同仿真步数分别做10次搜索并计 5 结论算发现目标平均数，搜索步数分别是30、60、90、 120和150.搜索策略有效性，即在相同搜索时间基于改进鸽群优化和动态目标运动模型提出一内，发现目标数越多，搜索策略越好，算法性能也种多无人机协同搜索方法.首先，构建环境信息图、越好.因此，搜索策略有效性=发现目标平均数/ 目标信息图、信息素图等，并建立符合马尔可夫链的目标总数.仿真结果表明，由于本文算法使用数字目标运动模型，实现多无人机协同搜索建模.然后，信息素完成无人机之间的协同，因此，相对另外两采用改进鸽群优化算法完成优化求解。鸽群优化算种算法能够发现更多的目标且大大提高了搜索的法虽然具有收敛速度快、搜索效率高等优势，但容易有效性陷入局部最优.因此，本文将柯西、高斯扰动分别加

王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1349. 20 (a) -UAVI b UAVI UAV2 UAV3 「A3 UAV4 目标1 目标 10 20 10 15 20 x/km x/km 100 80 40 女PIO 20 -ACO --MSAPIO 30 0 120 150 UAVs运动步数/步图5无人机的运动轨迹和覆盖率.(a)30步的运动轨迹：(b)60步的运动轨迹：(c)搜索范围覆盖率 Fig.5 The movement trajectories of unmanned aerial vehicle:(a)the movement trajectory of 30 steps:(b)the movement trajectory of 60 steps;(c) search coverage 10 100 (a) b 9 ▣PIO 80 ▣AC0 □MSAPIO 60 6 40 6-PI0 4 30 --ACO ◆-MSAPIO 20 3 10 20 40 6080100120140 160 30 60 90 120 150 无人机运动步数步搜索时间s 图6协同搜索目标数和有效性评估.(a)搜索目标平均数：(b)有效性评估 Fig.6 Effectiveness evaluation of collaborative search:(a)the average target number;(b)effectiveness assessment 入鸽群优化算法的两个算子中，并使用模拟退火机 (邱华鑫，段海滨。从鸟群群集飞行到无人机自主集群编队制保留次优个体，避免陷入局部最优工程科学学报，2017,39(3)：317) [4] Saadaoui H,El Bouanani F.Information sharing based on local 参考文献 PSO for UAVs cooperative search of unmoved targets//2018 In- ternational Conference on Adranced Communication Technologies [1] Qiu H X,Wei C,Dou R,et al.Fully autonomous flying:from and Netcorking (CommNet).Marrakech,Morocco,2018:1 collective motion in bird flocks to unmanned aerial vehicle autono- [5]Yang F,Ji X L,Yang C W,et al.Cooperative search of UAV mous swarms.Sci China Inf Sci,2015,58(12):128201 swarm based on improved ant colony algorithm in uncertain envi- [2] Peng H,Huo M L,Liu ZZ,et al.Simulation analysis of coopera- ronment /2017 IEEE International Conference on Unmanned Sys- tive target search strategies for multiple UAVs /The 27th Chinese tems.Beijing,2017:231 Control and Decision Conference.Qingdao,2015:4855 [6]Duan H B,Qiao PX.Pigeon-inspired optimization:a new swarm [3] Qiu H X,Duan H B.From collective flight in bird flocks to un- intelligence optimizer for air robot path planning.Int J Intell Com- manned aerial vehicle autonomous swarm formation.Chin /Eng, put Cybern,2014,7(1):24 2017,39(3):317 [7]Duan H B.Ye F.Progresses in pigeon-inspired optimization algo-

王瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法图 5 无人机的运动轨迹和覆盖率. (a)30 步的运动轨迹;(b)60 步的运动轨迹;(c)搜索范围覆盖率 Fig. 5 The movement trajectories of unmanned aerial vehicle: (a) the movement trajectory of 30 steps;(b) the movement trajectory of 60 steps;(c) search coverage 图 6 协同搜索目标数和有效性评估. (a)搜索目标平均数;(b)有效性评估 Fig. 6 Effectiveness evaluation of collaborative search:(a) the average target number; (b) effectiveness assessment 入鸽群优化算法的两个算子中,并使用模拟退火机制保留次优个体,避免陷入局部最优. 参考文献 [1] Qiu H X, Wei C, Dou R, et al. Fully autonomous flying: from collective motion in bird flocks to unmanned aerial vehicle autono鄄 mous swarms. Sci China Inf Sci, 2015, 58(12): 128201 [2] Peng H, Huo M L, Liu Z Z, et al. Simulation analysis of coopera鄄 tive target search strategies for multiple UAVs / / The 27th Chinese Control and Decision Conference. Qingdao, 2015: 4855 [3] Qiu H X, Duan H B. From collective flight in bird flocks to un鄄 manned aerial vehicle autonomous swarm formation. Chin J Eng, 2017, 39(3): 317 (邱华鑫, 段海滨. 从鸟群群集飞行到无人机自主集群编队. 工程科学学报, 2017, 39(3): 317) [4] Saadaoui H, El Bouanani F. Information sharing based on local PSO for UAVs cooperative search of unmoved targets / / 2018 In鄄 ternational Conference on Advanced Communication Technologies and Networking (CommNet). Marrakech, Morocco, 2018: 1 [5] Yang F, Ji X L, Yang C W, et al. Cooperative search of UAV swarm based on improved ant colony algorithm in uncertain envi鄄 ronment / / 2017 IEEE International Conference on Unmanned Sys鄄 tems. Beijing, 2017: 231 [6] Duan H B, Qiao P X. Pigeon鄄inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int J Intell Com鄄 put Cybern, 2014, 7(1): 24 [7] Duan H B, Ye F. Progresses in pigeon鄄inspired optimization algo鄄 ·1349·