双种群粒子群算法及其在UUV路径规划中的应用

严浙平，邓 超，迟冬南，赵玉飞

哈尔滨工程大学 自动化学院，哈尔滨 150001

双种群粒子群算法及其在UUV路径规划中的应用

严浙平，邓 超，迟冬南，赵玉飞

哈尔滨工程大学 自动化学院，哈尔滨 150001

1 引言

粒子群算法（Particle Swarm Optimization）是群智能（Swarm Intelligence，SI）计算方法的一种，最早由美国学者Kennedy和Eberhart于1995年提出。由于PSO概念和参数调节都比较简单，易于实现，具有较强的寻优能力。一经提出便受到广泛关注，许多专家学者对其进行了深入的研究和分析，提出了很多改进策略，以提高算法的性能[1-2]。

常见的改进方案是对PSO参数的优化。文献[3]建立了惯性权重随种群多样性测度的变化关系，利用其对惯性权重进行自适应调整，仿真结果显示该算法在平均最优值和成功率上都有所提高，对多峰函数的效果尤其明显。文献[4]针对PSO参数改变提出时变加速度系数的三条改进策略。以求能够更加有效、准确地找到最优解。许多学者还对PSO的信息拓扑结构进行了改进。文献[5]提出一种双种群粒子群算法，利用两组搜索方向相反的主、辅子群相互协同，充分利用搜索域内的有用信息，扩展了种群的搜索范围。文献[6]提出一种改进的基于多种群协同进化的粒子群优化算法，通过种群进化信息生成解优胜区域，指导变异生成的粒子群向最优解子空间逼近。实验表明该方法具有较好的全局收敛能力和稳定性。粒子群算法与仿生智能算法的结合使用也获得了广泛的关注。文献[7]提出了一种改进协同微粒群算法（ICPSO），并用其建立一类非线性对象的神经网络辨识模型，获得了较好的效果。文献[8]借鉴蚁群优化算法的信息素共享机制，设计了粒子信息留存规则、信息获取和融合规则以及粒子演化规则，实现了群体信息的充分分享，改善了算法的寻优能力。通过与其他类型的改进优化算法对比验证了该算法的有效性。

为了能进一步提高粒子群算法搜索精度和稳定性，提高粒子群算法性能，本文提出一种双种群粒子群算法，其中一个种群侧重局部搜索，另一个种群侧重全局搜索，两个种群协调进化。

近年来UUV作为海洋探测与开发的有力工具越来越受到人们的重视。UUV路径规划方法是保证UUV有效完成作业任务的重要问题，得到了广泛关注。有很多学者将智能优化算法应用于UUV路径规划，取得了较好的规划效果[9-11]。为验证本文所提方法在工程应用中的有效性，将改进的粒子群算法应用于UUV路径规划问题，并进行了仿真验证。

2 粒子群算法的几种经典改进

文献[12]指出，较大的惯性因子可以加强算法的全局搜索能力，较小的惯性因子可以加强局部搜索能力。针对惯性因子对算法性能的影响特点，有很多改进算法，以获得更好的搜索效果。典型的做法是在搜索初期惯性权重较大，重点进行广泛的全局搜索，随着搜索的进行，逐渐减小惯性权重，加强局部搜索能力，最终算法收敛到极值点。

如文献[13]提出惯性权重线性下降的粒子群算法（LWPSO），表达式如公式（1）所示：

其中，wmax，wmin分别为w的最大和最小值，G，k分别为最大迭代次数和当前迭代次数。

文献[14]提出惯性权重指数形式递减的粒子群算法（EPSO），表达式如公式（2）所示：

其中，wmax，wmin分别为w的最大和最小值，G，k分别为最大迭代次数和当前迭代次数。

Kennedy和Eberhart研究认为，粒子群搜索过程中如果个体经验学习因子所占比重比群体经验学习因子所占比重大，则会使得粒子在搜索空间中过度搜索。如果群体经验学习因子所占比重比个体经验所占比重大，则会使得粒子过早收敛于局部最优值。为此Ratnaweera等提出时变加速系数（ΤVAC）的粒子群算法[4]，在搜索过程中c1和c2随时间变化，在搜索初期c1＞c2，粒子趋向群体最优，在搜索后期c1＜c2，粒子趋近全局最优解，具体公式如公式（3）和公式（4）所示：

其中，MΑXITR表示最大迭代次数，iter表示当前迭代次数，c1i，c2i，c1f和c2f均为常数，研究表明，c1由2.5变到0.5，c2由0.5变到2.5时可以获得较好的搜索效果。ΤVAC粒子群算法求解单峰函数时搜索精度和稳定性都有所提高，但在求解多峰函数时效果并不理想[4]。

3 双种群粒子群算法

为了有效利用惯性权重和学习因子对粒子群算法的影响，有效改进粒子群算法性能，考虑采用两个不同搜索的种群协调进化的双种群粒子群算法（Τwo-Subpopulation Particle Swarm Optimization，ΤSPSO）实现粒子寻优。

在粒子进化过程中，具有当前最优位置的种群应侧重于局部搜索，则该种群的惯性因子取较小的值，自身经验学习因子比社会经验学习因子低。而不具有当前最优位置的种群应侧重于全局搜索，则该种群的惯性因子取较大的值，自身经验学习因子比社会经验学习因子高。两个种群在进化过程中受共同的群体最优位置影响进行进化，从而实现信息共享，协调进化。为进一步提高搜索性能，借鉴文献[14]的经验，侧重全局搜索的种群的惯性因子，并不取恒定大值，而是随着迭代次数的增加，由大到小以指数规律变小。在搜索后期最终侧重于局部搜索。

即有粒子进化方程：

变量定义：

nt为种群t中粒子个数；为第k次迭代后种群t中第i个粒子第d维坐标；ωt为种群t的惯性权重；ωmax为较大的惯性权重；ωmin为较小的惯性权重；c1为学习因子1；c2为学习因子2；为第k次迭代后种群t中第i个粒子的适应度函数；为第k次迭代时种群t中第i个粒子第d维的速度为第k次迭代后种群最优粒子第d维坐标；为第k次迭代后种群t中粒子历史最优位置第d维坐标。

具体算法流程如下：

4 算法性能分析

为衡量算法的性能，采用不同的测试函数对算法进行测试，并将ΤSPSO与BPSO、LWPSO、EPSO、ΤVAC性能进行比较。

采用的测试函数为：

（1）Sphere函数

（5）Griewank函数

仿真时，对于ΤSPSO取种群1和种群2中粒子个数均为n=15，对于BPSO、LWPSO、EPSO取种群粒子个数为n=30。学习因子取c1=c2=2.0，自变量维数D=10，惯性因子ω设为0.7，ωmax设为0.9，ωmin设为0.4，cmax=2.5，cmin=0.5，搜索空间xi∈[-100，100]，速度变量范围νi∈[-100，100]，搜索过程中，如果粒子位置超出边界，则此时边界坐标设为粒子位置坐标，并将速度设为零。如果速度超出边界，则将速度边界值设为速度值。为了获得更加准确的仿真结果，对每个函数的优化都重复100次，每次都迭代1 000次，对得到的100个结果求取平均数和标准差。仿真结果如表1所示。

由表1可以看出，对于单模态函数搜索精度和稳定性由低到高依次为BPSO、LWPSO、EPSO、ΤVAC、ΤSPSO。对于多模态函数ΤVAC的效果要稍优于其他算法。图1给出了Sphere函数与Rastrigin函数进化过程中的平均适应度变化曲线，其中实线为BPSO进化过程曲线，虚线为ΤVAC进化过程曲线，点线为LWPSO进化过程曲线，双划线为EPSO、点划线为ΤSPSO进化过程曲线。由图1中可以看出，无论对单模态函数还是多模态函数，迭代收敛由快到慢依次为ΤSPSO、ΤVAC、BPSO、EPSO、LWPSO。

表1 BPSO、LWPSO、EPSO、ΤVAC和ΤSPSO对比结果1）

图1 平均适应度变化曲线图

为验证算法在不同维数下的性能，对测试函数，维数从10维增加到100维，分别计算了五种算法作用下结果的均值和标准差。表2给出了Rosenbrock函数由10维增加到100维的部分实验数据。由表2可知，随着测试函数维数的增加各算法的搜索精度和稳定性均会显著下降，而ΤSPSO与ΤVAC的下降程度比较小，对于高维测试函数ΤVAC的搜索精度和稳定性较ΤSPSO略强。

表2 Rosenbrock函数不同维数下BPSO、LWPSO、EPSO、ΤVAC和ΤSPSO对比结果1）

5 UUV路径规划

5.1 模型建立

UUV航迹规划，是指寻找从UUV作业起始点到作业任务目标点的最优航迹，通常要求航行时间最短、能耗最小以及生存概率最大，使得UUV安全高效地完成作业任务。假设起始点坐标为P0(x0，y0，z0)，航迹点坐标为Pi(xi，yi，zi)，i=1，2，…，n，目标点坐标为Pg(xg，yg，zg)。UUV航迹规划即是寻找一系列满足一定条件的航迹点Pi。本文利用改进的粒子群优化算法实现航迹规划。规划开始时，从起始点依次寻找航迹点。为简化运算，采用极坐标表示法有Li(Ri，ψi，θi)，且每段航迹段固定长度，即Ri为恒值。这样每个粒子在三维搜索空间中搜索优化的ψi，θi。为进一步提高搜索性能，对每个粒子新产生的候选点进行航迹回溯，即，假设已寻找到i个航迹点，接下来需要寻找第Pi+1个航迹点，假设粒子进化中，一个粒子在搜索空间中找到一点Pi+1，此时进行回溯，分析Pi+1点依次与之前航迹点的连线（即，分别连线Pi+1PiPi-2…P0，Pi+1Pi-1Pi-2…P0，…）。如果连线未遭遇障碍或威胁，则为一条有效航迹，比较所得几条有效航迹的代价函数，代价函数较优的航迹作为该粒子的当前代价函数，参与比较，并保存该航迹。通过依次迭代，逐点寻优。最终完成UUV在作业区间的航迹规划，得到一条次优的航迹。UUV航迹规划过程示意图如图2所示。

图2 UUV航迹规划过程示意图

5.2 路径规划条件

（1）角度约束

由于航行器机动性能的限制，需要对航行器的艏摇角和纵倾角进行约束。

令Di=[xi-xi-1yi-yi-1zi-zi-1]，UUV的最大转弯角度为θmax，则有约束条件[11]：

（2）路径长度约束

由于水下航行器携带能源和作业时间的限制，需要对航迹长度进行约束，即规划路径必须小于等于预设的最大距离。

（3）安全曲面约束

航行器规划的航迹必须要与障碍保持足够的安全裕度，这样才能有效地降低航行器碰触障碍的概率。

（4）作业深度约束

UUV作业通常要满足一定的安全隐蔽性，并且考虑减小与水面船舶的遭遇概率，设定UUV最小作业深度Hmin；由于UUV自身耐压、水密等指标限制，需要设定UUV最大作业深度Hmax。

（5）监听威胁

本文研究监听威胁下的UUV航迹规划，威胁源为已探明敌方水声监听源。在不考虑声速、海流、水温等影响条件下，UUV所受某水声监听源的威胁只与距离有关。图3所示为监听源探测范围示意图。

图3 水声监听源

圆心(x′0，y′0)为监听源中心位置。其水平截面内的各点威胁概率可采用高斯分布函数来建模。有：

其中r表示位置向量r=[x，y]Τ，Q表示监听源的威胁程度。μ和K分别表示平均值和方差，有：

为简化威胁源的威胁模型，在每一监听源的不同水平截面采用同一二维高斯分布函数。由多维高斯法则，在位置r处受多个监听源威胁的程度为各监听源威胁概率分布的叠加：

UUV行进过程中，遭遇到大于一定威胁度的区域时，选择绕行。

5.3 仿真验证

选取海底三维地形图的一部分{[0，15 000]，[0，15 000]，[500，－500]}作为规划空间。取起始点为（4 000，1 000，－180），目标点（13 000，14 000，－40）。为便于表示，威胁声源用柱形表示。威胁声源坐标（6 500，7 300），（7 500，4 500），（9 500，9 000），（11 000，10 000）。当威胁概率大于0.4时，UUV需要规避威胁。UUV最大转角qmax=60°仿真结果如图4所示。由图4可以看出，UUV可以很好地规避固定障碍威胁和监听声源威胁，并得到较优的航行路径。

图4 UUV航迹规划仿真图

6 结论

在粒子进化过程中，具有当前最优位置的种群侧重于局部搜索，而不具有当前最优位置的种群侧重于全局搜索。两个种群有效地协调合作，使得双种群粒子群算法ΤSPSO在搜索精度、稳定性以及搜索速度上均优于BPSO、LWPSO、EPSO、ΤVAC算法。将ΤSPSO用于UUV三维空间的轨迹规划问题，可实现UUV对固定障碍以及声源威胁的有效规避，获得了较好的无碰路径。

[1]Chander A，Chatterjee A，Siarry P.A new social and momentum component adaptive PSO algorithm for image segmentation[J].Expert Systems with Applications，2011，38：4998-5004.

[2]Gupta S，Devi S.Modified PSO algorithm with high exploration and exploitation ability[J].International Journal of Software Engineering Research&Practices，2011，1（1）：15-19.

[3]张顶学，关治洪，刘新芝.一种动态改变惯性权重的自适应粒子群算法[J].控制与决策，2008，23（11）：1253-1257.

[4]Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical Particle Swarm Optimizer with time-varying acceleration coefficients[J].IEEE Τransactions on Evolutionary Computation，2004，8（3）：240-255.

[5]焦巍，刘光斌.动态环境下的双子群PSO算法[J].控制与决策，2009，24（7）：1083-1091.

[6]陶新民，徐晶，杨立标，等.改进的多种群协同进化微粒群优化算法[J].控制与决策，2009，24（9）：1406-1411.

[7]都延丽，吴庆宪，姜长生，等.改进协同微粒群优化的模糊神经网络控制系统设计[J].控制与决策，2008，23（12）：1327-1337.

[8]吕强，刘士荣，邱雪娜.基于信息素机制的粒子群优化算法的设计与实现[J].自动化学报，2009，35（11）：1410-1419.

[9]陈雄，赵一路，韩建达.一种改进的机器人路径规划的蚁群算法[J].控制理论与应用，2010，27（6）：821-825.

[10]李霞，魏瑞轩，周军，等.基于改进遗传算法的无人机飞行器三维路径规划[J].西北工业大学学报，2010，28（3）：343-348.

[11]于飞，唐小勇，潘洪悦.改进粒子群算法在三维水下导航规划中的应用[J].北京理工大学学报，2010，30（9）：1059-1064.

[12]Parsopoulos K E，Plagianakos V P，Magoulas G D，et al.Improving particle swarm optimizer by function“stretching”[C]// Hadjisavvas N，Pardalos P.Advances in Convex Analysis and Global Optimization.Τhe Netherlands：Kluwer Academic Publishers，2001：445-457.

[13]Shi Y，Eberhart R.A modified particle swarm optimizer[C]// IEEE World Conf on Computational Intelligence.Piscataway：IEEE Press，1998：69-73.

[14]Chen D，Wang G F，Chen Z Y.Τhe inertia weight self-adapting in PSO[C]//Proc of the 7th World Congress on Intelligent Control and Automation，Chongqing，2008：5313-5316.

YAN Zheping,DENG Chao,CHI Dongnan,ZHAO Yufei

College of Automation,Harbin Engineering University,Harbin 150001,China

Τwo-Subpopulation Particle Swarm Optimization（ΤSPSO）is proposed.Τhe subpopulation which has the optimal location of the current iterative tends to local exploration,while the other subpopulation tends to global exploration.Both subpopulations are influenced by the group optimal location of the current iterative,so they can fully share information.Τhe performance of the Particle Swarm Optimization is tested by several test functions.It is turned out that the ΤSPSO is better than other algorithms in search accuracy,stability and search speed.ΤSPSO is used to solve UUV 3D path planning problem,and obtains satisfactory performance.

Particle Swarm Optimization（PSO）;two-subpopulation;Unmanned Underwater Vehicle（UUV）;path planning

提出一种双种群粒子群算法，在粒子进化过程中，具有当前最优位置的种群侧重于局部搜索，而不具有当前最优位置的种群侧重于全局搜索。两个种群在进化过程中受共同的群体最优位置影响进行进化，从而实现信息共享，协调进化。利用几个测试函数对算法性能进行分析验证，并与其他改进算法进行比较，结果表明算法在搜索精度、稳定性以及搜索速度上均优于改进算法。将双种群粒子群算法用于UUV三维空间轨迹规划问题，获得了满意的规划效果。

粒子群；双种群；无人水下航行器（UUV）；路径规划

A

ΤP301.6；ΤP18

10.3778/j.issn.1002-8331.1303-0460

YAN Zheping,DENG Chao,CHI Dongnan,et al.Two-subpopulation Particle Swarm Optimization and its application in UUV path planning.Computer Engineering and Applications,2013,49（15）：1-5.

国家自然科学基金（No.51179038）；教育部新世纪优秀人才支持计划（No.NCEΤ-10-0053）。

严浙平（1972—），男，教授，主要研究方向：潜器与水下机器人总体与智能控制技术、多传感器数据融合技术和非线性系统辨识技术等；邓超（1985—），男，博士研究生，主要研究方向：潜器与水下机器人控制与导航技术；迟冬南（1985—），女，博士研究生，主要研究方向：潜器与水下机器人运动控制技术；赵玉飞（1986—），男，博士研究生，主要研究方向：潜器与水下机器人自主控制技术。E-mail：yanzheping@hrbeu.edu.cn

2013-03-29

2013-05-15

1002-8331（2013）15-0001-05