工程科学学报，第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·
王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1347. 动后的中心位置次于扰动前的位置，计算二者的差， 杂度是O((T。-T)/c).其中，T。是初始退火温 利用式(23)确定P.然后，用随机数rand∈(0,1) 度；T是最低温度：c是降温速率.由于模拟退火算 与P比较，若rand”表示：“×”是随机产 数取反，即这里取极大值0：图3(b)使用Schaffer函 生的动态目标，“s:”是第i个目标的起始位置，“e:” 数，其在x=(0,0,…,0)处取得极大值1.每个函数 是经马尔可夫链运动后的终止位置.由图分析可 的前两幅图是基本鸽群优化算法随机一次运行和 知，无人机能够用最小步数，实现尽可能多的目标搜 10次迭代取最大值、最小值和均值的收敛情况：后 索，而且随着搜索步数的增加搜索覆盖范围不断 两幅图是扰动模拟退火鸽群优化算法随机一次运行 扩大 和10次迭代取最大值、最小值和均值的收敛情况. 4.3搜索目标有效性 从图中不难发现，本文算法能够有效避免陷入局部 图6从搜索目标的有效性对基本鸽群优化算 最优 法、蚁群算法以及扰动模拟退火鸽群优化算法这3 4.2搜索范围覆盖率 种算法做仿真分析比较，且图6(a)和图6(b)分别 假设搜索区域L为10×10的栅格.图4(a)中， 表示搜索目标平均数和搜索策略有效性.使用4
王 瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 动后的中心位置次于扰动前的位置,计算二者的差, 利用式(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.搜索策略有效性，即在相同搜索时间 基于改进鸽群优化和动态目标运动模型提出一 内，发现目标数越多，搜索策略越好，算法性能也 种多无人机协同搜索方法.首先，构建环境信息图、 越好.因此，搜索策略有效性=发现目标平均数/ 目标信息图、信息素图等，并建立符合马尔可夫链的 目标总数.仿真结果表明，由于本文算法使用数字 目标运动模型，实现多无人机协同搜索建模.然后， 信息素完成无人机之间的协同，因此，相对另外两 采用改进鸽群优化算法完成优化求解。鸽群优化算 种算法能够发现更多的目标且大大提高了搜索的 法虽然具有收敛速度快、搜索效率高等优势，但容易 有效性 陷入局部最优.因此，本文将柯西、高斯扰动分别加
工程科学学报,第 41 卷,第 10 期 图 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 图 4 目标和环境的初始状态. (a)目标初始位置;(b)初始环境不确定图 Fig. 4 Initial state of target and environment:(a) initial position of the target;(b) initial environment uncertainty 架无人机对不同仿真步数分别做 10 次搜索并计 算发现目标平均数,搜索步数分别是 30、60、90、 120 和 150. 搜索策略有效性,即在相同搜索时间 内,发现目标数越多,搜索策略越好,算法性能也 越好. 因此,搜索策略有效性 = 发现目标平均数 / 目标总数. 仿真结果表明,由于本文算法使用数字 信息素完成无人机之间的协同,因此,相对另外两 种算法能够发现更多的目标且大大提高了搜索的 有效性. 5 结论 基于改进鸽群优化和动态目标运动模型提出一 种多无人机协同搜索方法. 首先,构建环境信息图、 目标信息图、信息素图等,并建立符合马尔可夫链的 目标运动模型,实现多无人机协同搜索建模. 然后, 采用改进鸽群优化算法完成优化求解. 鸽群优化算 法虽然具有收敛速度快、搜索效率高等优势,但容易 陷入局部最优. 因此,本文将柯西、高斯扰动分别加 ·1348·
王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·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·
.1350· 工程科学学报.第41卷，第10期 rithms.J Beijing Unig Technol,2017,43(1):1 ware /Proceedings of the 50th AlAA/ASME/ASCE/AHS/ASC (段海滨，叶飞.鸽群优化算法研究进展.北京工业大学学 Structures,Structural Dynamics,and Materials Conference.Palm 报，2017,43(1)：1) Springs California,2009:1017 [8]Li C,Duan H B.Target detection approach for UAVs tia im- [12]Bertuccelli L F,How J P.Search for dynamic targets with uncer- proved pigeon-inspired optimization and edge potential function. tain probability maps /2006 American Control Conference.Min- Aerosp Sci Technol,2014,39:352 neapolis,MN,USA,2006:737 [9]Zhong Y,Yao P Y,Sun Y,et al.Method of multi-UAVs coopera- [13]Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by simula- tive search for Markov moving targets//201729th Chinese Control ted annealing.Science,1983,220(4598):671 And Decision Conference (CCDC).Chongqing,China,2017: [14]Lan K T,Lan C H.Notes on the distinction of Gaussian and 6783 Cauchy mutations//2008 Eighth International Conference on In- [10]Shen D.Wei R X,Ru C J.Digital-pheromone-based control telligent Systems Design and Applications.Kaohsiung,Taiwan, method for UAV swarm search.Syst Eng Electron,2013,35 2008:272 (3):591 [15]Duan H B,Yang Z Y.Large civil aircraft receding horizon con- (沈东，魏瑞轩，茹常剑.基于数字信息素的无人机集群搜 trol based on Cauchy mutation pigeon inspired optimization.Sci 索控制方法.系统工程与电子技术，2013,35(3)：591) Sin Technol,2018,48(3):277 [11]Kalivarapu V,Winer E.Digital pheromone implementation of (段海滨，杨之元.基于柯西变异鸽群优化的大型民用飞机 PSO with velocity vector accelerated by commodity graphics hard- 滚动时域控制.中国科学：技术科学，2018,48(3)：277)
工程科学学报,第 41 卷,第 10 期 rithms. J Beijing Univ Technol, 2017, 43(1): 1 (段海滨, 叶飞. 鸽群优化算法研究进展. 北京工业大学学 报, 2017, 43(1): 1) [8] Li C, Duan H B. Target detection approach for UAVs via im鄄 proved pigeon鄄inspired optimization and edge potential function. Aerosp Sci Technol, 2014, 39: 352 [9] Zhong Y, Yao P Y, Sun Y, et al. Method of multi鄄UAVs coopera鄄 tive search for Markov moving targets / / 2017 29th Chinese Control And Decision Conference ( CCDC). Chongqing, China, 2017: 6783 [10] Shen D, Wei R X, Ru C J. Digital鄄pheromone鄄based control method for UAV swarm search. Syst Eng Electron, 2013, 35 (3): 591 (沈东, 魏瑞轩, 茹常剑. 基于数字信息素的无人机集群搜 索控制方法. 系统工程与电子技术, 2013, 35(3): 591) [11] Kalivarapu V, Winer E. Digital pheromone implementation of PSO with velocity vector accelerated by commodity graphics hard鄄 ware / / Proceedings of the 50th AIAA / ASME/ ASCE/ AHS / ASC Structures, Structural Dynamics, and Materials Conference. Palm Springs California, 2009: 1017 [12] Bertuccelli L F, How J P. Search for dynamic targets with uncer鄄 tain probability maps / / 2006 American Control Conference. Min鄄 neapolis, MN, USA, 2006: 737 [13] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simula鄄 ted annealing. Science, 1983, 220(4598): 671 [14] Lan K T, Lan C H. Notes on the distinction of Gaussian and Cauchy mutations / / 2008 Eighth International Conference on In鄄 telligent Systems Design and Applications. Kaohsiung, Taiwan, 2008: 272 [15] Duan H B, Yang Z Y. Large civil aircraft receding horizon con鄄 trol based on Cauchy mutation pigeon inspired optimization. Sci Sin Technol, 2018, 48(3): 277 (段海滨, 杨之元. 基于柯西变异鸽群优化的大型民用飞机 滚动时域控制. 中国科学: 技术科学, 2018, 48(3): 277) ·1350·
