一种改进粒子群通讯算法在目标搜索中的应用

何乔

摘 要：针对粒子群算法应用于机器人目标搜索过程中存在的早熟现象，提出一种基于改进粒子群算法和模拟退火算法相结合的目标搜索新方法，以提高算法的全局搜索能力。为解决通讯距离有限、机器人无法与基站进行信息交互和不能实时追踪动态目标等问题，引入通讯功能。算法中机器人与基站有两种通讯方式，一种是基站跟随最优机器人移动的通讯方式，另一种是在前者基础上将机器人按一定比例分为通讯机器人和搜索机器人的通讯方式，由通讯机器人负责搜索机器人与基站之间的通讯。两种通讯方式下机器人都采用动态多目标搜索策略搜索动态多目标。在考虑通讯距离的情况下，经过仿真测试，与传统的通讯粒子群算法相比，提出的改进通讯粒子群算法能更加有效地追踪动态目标。

关键词：粒子群算法；模拟退火算法；通讯机器人；动态多目标搜索

DOI：10. 11907/rjdk. 182395

中图分类号：TP301 文献标识码：A 文章编号：1672-7800（2019）005-0031-06

Abstract： Aiming at the prematurity of swarm optimization （PSO） algorithm when applied to the robot target search process， a new target search method based on improved particle swarm optimization algorithm and simulated annealing algorithm is proposed. For the premature phenomenon of particle swarm optimization algorithm， the simulated annealing algorithm is introduced to improve the algorithm of the global search capability. In order to tackle the problem that the robot can not have information interaction with the base station and real-time dynamic target tracking due to the limited communication distance， this paper introduces the communication function. Algorithm of robot and base station has two kinds of communication methods， one is the base station with the optimal robot of mobile communication， the other is based on the former general robot according to certain proportion into the communication robot communication methods and search robot， the robot communications is responsible for the search robot and communications between the base station. Robots are under two kinds of communication methods using dynamic multi-objective search strategy. Under the condition of considering the communication distance， compared with the traditional communication particle swarm optimization algorithm， the improved communication particle swarm optimization algorithm can track dynamic targets more effectively according to the simulation test.

Key Words：particle swarm optimization；simulated annealing algorithm； communication robots； dynamic multi-objective search

0 引言

粒子群算法思想源于對鸟群简化模型的研究及行为模拟。由Craig Reynolds[1]建立的Boid模型是一个简单的人工生命系统，专门用来模拟鸟类聚集飞行的行为。模型中的每个个体行为只与周围的邻近个体行为有关，每个个体只需要遵循下面3项原则：①避免碰撞原则：避免每个个体与相邻的个体发生碰撞；②速度一致原则：和相邻个体间平均速度保持一致；③向中心聚集原则：向相邻个体的平均位置移动。Kennedy & Eberhart[2-3]从鸟类群居性动物的觅食行为中得到启示，提出了粒子群算法（PSO）。在PSO中，将食物地点看成求解问题的最优解，通过每个个体之间位置信息的交互，逐步指引所有粒子聚集，同时朝着最优解方向移动。PSO实现简单，容易理解，与GA[4-5]等进化算法的很大不同之处在于：①PSO没有交叉和变异过程；②PSO没有淘汰粒子机制；③PSO不但具有局部信息交互能力，还有全局信息交互能力，这些能力通过粒子群的记忆能力体现。

现实生活中有很多恶劣环境，机器人比人更适合工作，如爆炸物和放射源的检测，使用机器人操作会更安全[6]，因此一些学者将粒子群算法应用于机器人目标搜索中。文献[7]提出运用分布式粒子群算法搜索动态目标，利用分布式思想的优势改进算法从而提升算法效率；文献[8]提出运用一种动态粒子群算法搜索动态目标，从而减少算法耗时；文献[9]提出一种多机器人粒子群目标搜索算法对多个目标进行搜索。这些算法改进只是对参数作了修改，当搜索范围很大、机器人之间在相互通信[10-11]时难以完成对移动目标的跟踪，即动态多目标追踪问题没有得到很好解决。

针对这些问题，为使机器人目标搜索仿真实验更加接近真实情况，考虑通讯距离限制问题，本文提出一种改进的粒子群通讯方式，以实现动态多目标搜索。

1 相关工作

1.1 粒子群算法

粒子群算法模拟鸟类觅食过程，采用更新粒子速度-位置的方式搜索目标。算法中潜在的解被称为“粒子”，粒子通过一些简单的规则“飞越”解空间寻找目标。所有的粒子都有一个根据所处位置得到的适应值和一个指引其搜索方向的速度。种群最初被随机分布在空间中，通过不停迭代找到最优解。在每次迭代过程中，粒子通过追随两个极值更新自己的速度和位置，一个是粒子本身在迭代过程中所找到的使适应值最优的位置，另一个是当前粒子群中找到的最优位置。粒子找到上述两个极值后，通过式（1）更新自己的速度，式（2）更新自己的位置[12]。

1.3 移动基站下的通讯方式

在实际目标搜索过程中通常会设置一个基站，基站会保存要搜索目标的最优位置。机器人在目标搜索过程中需要不断把搜索目标位置信息传送给基站。然而在大多数模拟机器人目标搜索仿真实验中，只要其中一个机器人找到目标位置就意味着其它机器人也获得这个位置。这只是理想的情形，而现实中机器人在空间中搜索目标很不确定，因为现实搜索过程中每个机器人都会有一个通讯半径，如果超过这个半径，机器人和基站之间信息就不能相互传递。在这种背景下，提出一种在有限通讯距离下的新型通讯方式。由粒子群算法基本原理可知，搜索过程中机器人的运动趋势是向着群体中的最优机器人移动，如果在搜索中基站向最优机器人移动，则会最大可能地使基站与绝大部分机器人通讯，但同时也会错过与一些机器人的通讯机会。所以在新型通讯方式下，为了在仿真实验中使基站与机器人实现更好的通讯，基站在移动过程中将保存所遇到的机器人位置，并向着最优机器人位置和基站内保存的其它机器人平均位置合成方向运动[20]。

1.4 增加通讯机器人的通讯方式

为了让移动基站模式具有更广的通讯范围，在移动基站通讯方式的基础上将机器人群按一定比例分为通讯机器人和搜索机器人。通讯机器人主要负责与处在基站通讯范围外的机器人进行通讯，搜索机器人主要负责搜索任务。这样的分工可使搜索机器人不用去考虑通讯问题，只需依靠通讯机器人就能使基站与所有搜索机器人进行通讯。在通讯过程中基站保存着每个搜索机器人的个体极值，在移动中广播自己的位置和全局极值的同时，广播每个搜索机器人的个体极值。如果通讯机器人无法与基站进行通讯，则增大移动步长向基站方向运动，并保证每个通讯机器人的通讯范围内至少存在一个通讯机器人，这样可使每个通讯机器人能完成通讯任务。搜索机器人在搜索过程中的位置是实时变化的，当搜索机器人有通讯需求时，如果通讯机器人能接近搜索机器人将要搜索的路径，也就是将通讯机器人往个体极值和全局极值合成的方向逐个运动，以增大与搜索机器人进行通讯的概率。进行通讯时，搜索机器人将所获得的位置信息与基站内保存的位置进行比较，如果优于基站内保存的位置则更新。为了使机器人之间的消息传递更加接近实际，在此参照了路由协议中的信息传递方式，如图1所示。

图1中，SRobot表示搜索机器人，CRobot3表示通讯机器人。假设机器人之间的最大通讯距离为[R]，图中通讯机器人之间的距离R1、R2、R41、R32都小于R。当满足某个通讯机器人与基站的通讯条件时，其它通讯机器人只要在通讯范围内就可经过这个机器人与基站进行信息交互，而经过的机器人数量称为跳数，例如能直接与基站进行通讯跳数为1。在通讯过程中通讯机器人会将自己到基站之间的跳数传递给基站，由基站广播所有通讯机器人当前的跳数。通讯中只可与拥有同样跳数或更低跳数的机器人进行通讯。CRobot3可经过两条路径与基站通讯，一条跳数为2，一条跳数为3。为了提高消息传递效率，降低丢包率，本文将使用迪杰斯特拉算法计算出经过节点数最少的一条传递路径。

在通訊过程中，为了模拟机器人的通讯需求，提高目标搜索效率，本文引入通讯间隔概念，只有当前时间和上一次与移动基站通讯的时间差大于通讯间隔才能让机器人与基站进行通信。把上一次和基站信息交互的时间定义为[tc]，[t]定义为当前时间，[c]表示通讯间隔，如果时间[t]和通讯时间[tc]之间的时间间隔大于[c]，通讯机器人就会和基站通讯，通讯成功后[tc]将更新为[t]。时间间隔[c]是可以调整的变量，当希望通讯机器人与基站频繁交流时就设置较小的[c]，反之则通讯机器人能够搜索到更广阔的区域。

2 改进的通讯粒子群算法

粒子群算法是一种启发式算法，具有记忆功能，可以进行信息共享，但是却容易陷入局部最优解。模拟退火算法具有全局寻优的优点，可以接受较差的点，扩大寻优范围，能够很好地跳出局部最优解。融合两种算法，弥补各自的缺点，能够提高算法性能。本次实验求解最小值，具体流程如图4所示。

机器人在搜索目标过程中的每一次迭代都会与基站通讯。如果通讯没有成功，则根据新粒子的速度和位置计算粒子的适应度函数。如果适应度函数差值小于0，则接受粒子的位置作为个体的最优值保存下来，如果适应度差值大于0，则按照概率接受粒子的当前位置开始退火，如果没有满足终止条件则继续迭代。如果[t-tc>c+θi]时机器人和基站开始通讯，能否更新全局最优值由机器人是否能和基站直接连接或间接通过其它机器人连通决定。如果连通则通讯成功，记录最优值并把最优值传给其它机器人，否则通讯失败。没有满足终止条件就继续迭代，寻找最优值，只有找到新的最优值才会和基站通讯。

3 仿真实验

3.1 实验内容与实验设置

（1）改进的通讯粒子群算法在不同通讯机器人数量上的实验对比。本实验将通讯机器人比例取10%、20%、30%、50%，分别测试这4种比例下的算法性能，以测试改进后的通讯模式是否可行，最终的算法评价指标为每一次迭代的全局最优值与目标真实位置之间的欧氏距离。

从图4-图7可以看出，当通讯机器人比例为20%时，算法性能最好，當比例为50%时，算法误差过大且波动也较大。因为提高通讯机器人比例就会减少搜索机器人数量，使机器人搜索范围缩小，也就降低了找到最优值的概率。

（2）改进的通讯粒子群算法与C-dPSO仿真对比。以上实验得到一个算法性能较优的通讯机器人比例，为更好地验证本文提出的改进的通讯粒子群算法性能，将两种通讯方式与传统通讯粒子群算法C-dPSO进行对比。传统的C-dPSO中基站为固定不动，机器人与基站在通讯范围内才进行信息交流。

图8、图9、图10分别为移动基站—无通讯机器人模式和移动基站下通讯机器人比例为20%和C-dPSO下的误差仿真。将图8无通讯机器人模式与图9存在通讯机器人模式相比，发现在相同条件下，当通讯过程中存在通讯机器人时的误差要比没有通讯机器人时小，但是带通讯机器人的移动基站模式算法性能很大程度受机器人数量的限制，所以在机器人数量较少的情况下，无通讯机器人模式可能更佳。图10为C-dPSO的误差仿真，可以看出在C-dPSO模式下能很平稳地追踪目标，但是各个目标误差值差距较大。经过与图8移动基站—无通讯机器人模式和移动基站下通讯机器人比例为20%的误差仿真图进行对比，可以看出本文提出改进的通讯粒子群算法在误差上要小于C-dPSO，这是因为融合带通讯粒子群算法下两种通讯模式都能使机器人与基站进行信息交流。从以上分析可以得出，本文提出的改进通讯粒子群算法通讯能力较传统的C-dPSO更优，且具有实时追踪动态多目标的能力。

4 结语

使用MATLAB对本文提出的改进通讯粒子群算法搜索动态多目标进行对比仿真。实验表明，在通讯距离限制的情况下，本文算法能使机器人与基站良好通讯，更好地追踪多个动态目标。经过仿真对比发现，新型通讯方式下的误差比现有通讯粒子群算法小，这说明本文提出的算法是切实有效的。本文算法使机器人搜索目标仿真实验更加贴近实际，为粒子群算法应用于实际目标搜索提供了思路。但是对于如何选择合适的通讯机器人比例需根据不同情况确定，这有待进一步研究。

参考文献：

[1] REYNOLDS C W. Flocks， herds and schools： a distributed behavioral model[J]. Computer Graphics， 1987， 21（4）：25-34.

[2] KENNEDY J， EBERHART R C. Particle swarm optimization.proceedings[J]. IEEE International Conference on Neural Networks，1995（4）：1942-1948.

[3] EBERHART R，KENNEDY J. A new optimizer using particle swarm theory[C].Proceeding of the sixth international symposium on Micro Machine and Human Science，1995：39-43.

[4] COLORNI A，DORIGO M.Distributed optimization by ant colonies[C].Proceeding of the First European Conference on Artificial Life，1991：134-142.

[5] DORIGO M. Optimization，learning and natural algorithms[C]. Dissertation.Dipartimentodi Elettronica，Politecnico di Milano，Italy，1992.

[6] PERREAULT L，WITTIE M P，SHEPPARD J. Communication-aware distributed PSO for dynamic robotic search[C]. Swarm Intelligence. IEEE， 2014：1-8.

[7] LEE J，CHO K，LEE S，et al. Distributed and energy-efficient target localization and tracking in wireless sensor networks[J]. Computer Communications， 2006， 29（13）： 2494-2505.

[8] HEREFORD J M，SIEBOLD M，NICHOLS S. Using the particle swarm optimization algorithm for robotic search applications[C].2007 IEEE Swarm Intelligence Symposium. IEEE，2007： 53-59.

[9] PUGH J，MARTINOLI A. Distributed adaptation in multi-robot search using particle swarm optimization[C].International Conference on Simulation of Adaptive Behavior，2008：393-402.

[10] CAI Y，YANG S X. A potential field-based pso approach for cooperative target searching of multi-robots[C]. Intelligent Control and Automation. IEEE， 2015：1029-1034.

[11] KENNEDY J. Why does it need velocity[C]. Swarm Intelligence Symposium，2005：38-44.

[12] SHI Y H，EBERHART R C. A modified particle swarm optimizer[C].Proceeding of the IEEE International Conference on Evolutionary Computation，1997：303-308.

[13] 康立山. 非数值并行算法——模拟退火算法[M]. 北京：科学出版社，1997：22-55.

[14] DANTZING G，RAMSER J. The truck is patching problem[J]. Management science，1959（6）：80-91.

[15] TIKANM，KI A，KEL，et al. Multi-robot system for exploration in an outdoor environment[C]. International Conference on Robotics and Applications，2007：470-476.

[16] 赵志刚，黄树运，王伟倩. 基于随机惯性权重的简化粒子群优化算法[J]. 计算机应用研究，2014，31（2）：361-363.

[17] JOHNSON D S，ARAGON C R，MCGEOCH L A，et al. Optimization by simulated annealing： an experimental evaluation； part III[J]. Science， 1990， 39（2548）：671-680.

[18] BOULEIMEN K，LECOCQ H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research， 2003， 149（2）：268-281.

[19] YANG H，YANG Y，YANG Z， et al. A particle swarm optimization algorithm based on simulated annealing[J]. Advanced Materials Research，2014（989-994）：2301-2305.

[20] PELUSI L，PASSARELLA A，CONTI M. Opportunistic networking： data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine， 2006， 44（11）：134-141.

（責任编辑：杜能钢）