一种改进的粒子群算法的路径规划研究

王文丰,宋 勇,韩龙哲,包学才,刘天元,徐 灯

1(南昌工程学院 江西省水信息协同感知与智能处理重点实验室,南昌 330099)2(南昌工程学院 信息工程学院,南昌 330099)3(武汉理工大学 自动化学院,武汉 430000)

1 引 言

随着经济全球化,各国之间的贸易往来越来越密切.在进行贸易过程中,交通运输是个重要问题.海洋运输以其成本低等特点在跨国贸易中扮演重要角色,而其发展主要受限于船舶航行路径规划的科学性,因此实现船舶航行路径规划的智能化具有重要的现实意义[1].

目前,国内外众多专家学者对船舶路径规划问题进行了深入的研究.船舶航行路径规划问题主要包括海洋环境建模和路径优化.其中,海洋环境建模主要有可视图法、栅格法、拓扑法、链接图法等.可视图法算法灵活、实现简单,但不能对圆形障碍物进行有效处理,每次搜索都要重新构建可视图,比较耗费时间;栅格法对于栅格大小的选取要求较高;拓扑图法具有建模速度快、存储空间少等优点,但不能解决障碍物特征不明显、分布稀疏的环境下路径规划问题;链接图法具有运用灵活的优点,当路径的起点和终点发生改变时,整个连通图不会发生变化,其缺点在于:当环境中的障碍物较多时,所构造的连通图会较复杂,加大了路径规划的难度.路径优化的典型方法有神经网络、蚁群算法和遗传算法等[2-4].神经网络具有规划速度快、鲁棒性强等优点,但泛化能力差,通常将其和其它算法结合运用进行路径规划;蚁群算法能够完成分布式计算,但算法计算量大、收敛速度慢,而且容易陷入局部最优;遗传算法具有实时性好的优点,但运算速度慢、进化规则多等缺点限制了其应用.

近年来,由于粒子群算法具有参数简单、搜索速度快等优点,因此在船舶路径规划的研究中得到了广泛的应用.文献[5]提出将粒子群算法和滚动优化策略进行结合,利用粒子群算法求解每一个移动窗口内的最优路径,从而获取全局最优路径.粒子群算法为解决船舶路径规划问题提供了有效方法,但依然存在路径规划速度慢、规划路径较长甚至失败等缺点.文献[6]针对传统的粒子群算法存在的问题,提出了一种非线性的动态调整惯性权重的方法,同时在适应度函数中引入平滑度和安全度概念.该方法能够明显降低算法陷入局部最优的概率.也有部分学者从改进算法本身的角度出发,和其它算法相结合以避免陷入局部最优并提高全局求解精度,如文献[7]通过将遗传算法和粒子群算法结合以充分利用两者的优点,大大提高了局部寻优能力.

本文在传统的船舶路径规划研究的基础上,针对粒子群算法存在的容易陷入局部最优、寻优精度低等问题,提出了一种基于混沌理论并引入多种群的粒子群优化算法(Chaos Multi-population Particle Swarm Optimization,CMPSO).在提高算法的解的精度同时,将速度自适应调整策略引入到种群更新中来,加快算法的收敛速度.

2 海洋环境的建模

解决船舶路径规划问题,首先需要对相应的海洋环境进行建模,将非状态空间转换为状态空间.海洋环境的建模在实际的处理过程中主要考虑航线的表达、航线的安全和信息的处理等问题.由于本文所研究的海洋环境相对陆地以及其它环境的障碍物较少,能充分发挥链接图法的优点、避免了其不足之处,因此本文选用链接图法作为环境建模方法.

链接图法是自由空间建模的一种方法,它先把空间内的障碍物抽象成各种平面凸边形,再利用图论知识在该空间中建立一个全局连通图,最后在这个连通图上实现路径规划.在进行环境建模之前,考虑到船舶本身的特性以及海洋环境的复杂性需要进行相应的简化处理,作出以下几点假设:

1)只考虑必要的环境信息,忽略气流等信息;

2)只考虑船舶在二维平面上的运动,不考虑高度信息;

3)用凸多边形描述环境中的边界以及各种障碍物;

4)适当扩大障碍物的边界范围,以保证当船舶在航行过程中沿着障碍物边缘行进时,不会与障碍物发生碰撞;

5)将船舶看作一个质点,忽略其尺寸大小;

6)根据需要适当缩小环境的边界范围以减少一些不必要的工作量;

3 路径规划算法设计

3.1 初始路径规划

1959年,E.W.Dijkstra基于贪心算法研究单源最短路径问题,提出了Dijkstra算法,该算法是目前公认的最好的求解最短路径的方法[8].算法解决的是有向图中单个源点到其它顶点的最短路径问题,其基本思路是每次迭代时始终选择除标记点之外其它顶点中距离源点最近的点作为下一个顶点,从而保证所得路径最短[9].

图1 Dijkstra算法获取船舶初始路径流程图Fig.1 Flowchart of acquiring initial path by Dijkstra

通过Dijkstra计算图G中的最短路径时,需要指定起点s.此外,引进两个集合S和U.集合S用于记录已求出最短路径的顶点以及相应的最短路径长度,而集合U则记录还未求出最短路径的顶点以及该顶点到起点s的距离[10].Dijkstra算法流程图如图1所示.

3.2 路径优化

通过Dijkstra算法规划出的路径是基于链接图法所建立的模型所得,并非全局最优路径.因此,在该初始路径的基础上,采用粒子群算法进行路径优化.在利用PSO算法进行路径规划时,通常将一条条路径对应于种群中的粒子,每一条可行路径包括一系列路径点,粒子各个维度的分量表示路径点在该链接线上的位置,再利用算法的全局寻优能力对路径点的位置进行调整,最终获得全局最优路径.

(1)

其中,hi为比例系数,d为路径划分的节点数.

由式(1)可知,通过Dijkstra算法得到的路径经过自由链接线时,任意一组参数(h1,h2,…,hd)即对应一条从起点到终点的新路径.因此,(h1,h2,…,hd)可表示相应的路径信息,也即粒子群优化算法解的形式.

通过仿真实验发现,粒子群优化算法虽然能获取全局最优路径,但算法本身存在的容易陷入局部最优、寻优精度不高等问题依然突出[11,12].为解决上述问题,本文对粒子群优化算法进行改进,提出了一种基于混沌理论并引入多种群的粒子群优化算法(Chaos Multi-population Particle Swarm Optimization,CMPSO).

1)基于混沌理论的粒子群优化算法改进

一般粒子群优化算法的种群初始化是随机进行的.这种处理方法虽然简单,但可能造成初始粒子分布不够均匀,而且远离最优解,这会造成大量不必要的搜索操作,严重影响了算法的执行效率.因此,本文利用混沌理论产生初始种群以使初始粒子分布均匀,提高算法执行效率.基于混沌理论的模型有很多种,本文采用较常见的Logistic映射模型.Logistic模型是一种最简单的回归方程,而且遍历性较好,可使粒子均匀分布,其回归方程如下:

xi+1=4xi(1-xi),xi∈(0,1)

(2)

根据上述分析,充分利用混沌理论的随机性和遍历性,在种群初始化时,利用混沌序列产生初始化种群以保证粒子的均匀分布.同时,为了提高初始粒子的质量,在利用混沌序列进行种群初始化时产生过量粒子,并从中选出适应度值高的部分粒子作为初始种群.这样既保证了初始粒子在解空间中的均匀分布,也使初始种群中粒子更接近最优解,加快算法收敛速度[13].

2)引入多种群的粒子群优化算法改进

通过前文对粒子群算法原理和数学模型的分析可知,粒子具有全局搜索能力和局部搜索能力,而且这两种能力相互影响.当前学者通过引入惯性权重来平衡粒子的全局搜索能力和局部搜索能力[14].这虽然取得了一定效果,但在处理复杂问题时效果欠佳.

本文通过建立多种群机制以对粒子群算法进行改进.在改进的粒子群优化算法中,将整个种群分成三个子种群.第一个种群粒子的惯性权重较大.根据对粒子群优化算法数学模型的分析可知,该种群具有较强的全局搜索能力,能够完成在解空间内的大范围搜索,提高算法收敛速度.第二个种群的惯性权重较小,该种群具有较强的局部搜索能力,能够对局部范围进行精细搜索,提高算法解的精度.第三个种群粒子的全局搜索能力和局部搜索能力相当.为了提高第三个种群算法的收敛速度,在该种群中引入自适应速度调整的策略.根据实际情况的分析可知,当粒子朝全局最优粒子方向运动且粒子不断找到更优的点时,此时若不改其飞行方向可使粒子更快地飞向最优粒子,从而加快算法收敛速度.因此,第三个种群的速度更新公式改为如下:

(3)

根据上式可知,若当前粒子本次迭代的适应度值比上次高,则说明该粒子沿着当前方向运动有利于找到全局最优粒子;若当前粒子本次迭代的适应度值比上次低,则说明粒子当前并非向全局最优粒子方向运动,下次粒子的速度按标准粒子群优化算法粒子速度更新方式进行更新.

通过上述改进方法可保证粒子种群的多样性,各个子群分工明确、相互协作,使算法将解空间中的极值点一一找出,避免算法陷入局部最优,而且加快了算法的收敛速度,提高了解的精度.

3.3 路径平滑优化

通过上述算法规划所得的最优路径是由一系列路径点组成的折线.若船舶按该路径航行,船舶的转弯次数较多,且某些航段航行距离较短,某些转向点处转弯角度过大,这不利于船舶的安全航行,增加了经济成本,这并非一个理想的效果.

本文在基本粒子群优化算法的基础上引入路径平滑处理,从而提高算法执行效率,减少船舶转弯次数,增强所得路径的实用性.本文所采取的平滑处理思路是,对于优化后的每个航段进行处理,尽可能地截弯取直,用直线将各个路径点相连,从而减小了船舶的转弯角度,并且使船舶在每个航段的航行距离较长.假设粒子群优化算法所得路径序列为(P1,P2,…,Pi,…,Pn),路径平滑处理流程图如图2所示.按照初始所得路径序列顺序,从第一个路径点开始与最后一个路径点相连,若所连线段没有穿越障碍物,则将该段路径存入路径序列作为全局路径的一个子路径段,否则与其前一个路径点相连.如此循环,直至求解到倒数第二个路径点为止.通过将每个路径点进行平滑处理即可得到更理想的全局最优路径.

图2 路径平滑处理流程图Fig.2 Flowchart of smoothing path

4 实验结果分析

本文以某海岛区域为背景,利用Matlab软件对相关算法进行仿真实验.

首先,在进行必要的假设后,利用链接图法对海洋环境建模.设置起点坐标为P(148.56,37.42),终点坐标为Q(198.84,145.68),利用Dijkstra算法获取一条从起点到终点的初始路径,如图3所示.

图3 Dijkstra算法获取初始路径示意图Fig.3 Obtain the initial path by Dijkstra algorithm

接着,在初始路径的基础上利用线性递减惯性权重粒子群算法(LDW-PSO)搜索出全局最优路径.从图3中可看出,Dijkstra算法规划出的初始路径共有8个路径点.因此,LDW-PSO的每个粒子包括8个维度.设置算法的粒子数为100,迭代次数为300,max=0.95,min=0.2,c1=c2=2.采用线性递减惯性权重粒子群算法(LDW-PSO)进行全局路径规划所得路径如图4所示,图5为路径长度随迭代次数变化情况.从图3可看出,船舶在航行过程中8次改变航向,且部分转向角度过大,这不利于船舶的安全高速航行.从图5可看出,当算法迭代到了第27代时即出现了并非最优的收敛,并陷入局部最优状态,直至到第261代才出现了相对可行的路径,所得最优路径长度为171.114km,总共耗时6.87s.

图4 LDW-PSO进行全局路径规划示意图Fig.4 Global path planning by LDW-PSO

图5 路径总长度随迭代次数变化曲线Fig.5 Changes for total length of the path with the number of iterations

图6 采用加入路径平滑优化处理的路径规划示意图Fig.6 Schematic diagram of path planning with path smoothing optimization

在上述基础上加入路径平滑处理,所规划出的路径如图6所示.本次规划所得路径长度为148.372km,总共耗时1.65s, 路径全长总共有2次改变航向, 且每次所需转向角度都不大.进行路径优化处理前后相关数据如表1所示.通过两者对比可看出,加入路径平滑处理方法可极大地提高算法的执行效率,且所规划出的路径转向点数更少,对于船舶的安全高速航行具有重要意义.

表1 路径平滑优化处理前后对比
Table 1 Comparison before and after smoothing path

方法规划路径长度(km)最小航段长度(km)转弯点数量(个)最大转弯角度(度)平均计算时间(s)改前171.11424.42864.86.87改后148.37247.81242.71.65

接着,分别利用线性递减惯性权重粒子群算法(LDW-PSO)和改进的粒子群优化算法(CMPSO)进行船舶路径规划以比较两者实际效果.改进的粒子群优化算法的第一个子群的惯性权重ω=0.9,第二个子群的惯性权重ω=0.4,第三个子群的惯性权重ω=0.75,而且这三个子群占整个种群的比例分别为2∶1∶2,三个子群中c1=c2=2.采用线性递减的粒子群优化算法的ωmax=0.9,ωmin=0.4,c1=c2=2.两种算法的种群粒子数均为100,最大迭代次数为300.设置起点坐标为P(68.25,72.36),终点坐标为Q(131.72,23.64),分别利用两种算法进行路径规划30次,且均不加入路径平滑优化处理,记录所获取的全局最优路径长度,其最优个体适应度值的平均值随迭代次数的变化如图7所示.计算全局最优路径的均值以及方差,结果如表2所示.

图7 路径规划适应度值随迭代次数变化曲线1Fig.7 Fitness of path planning varies with the number of iterations firstly

从图7、表2可看出LDW-PSO和CMPSO均能实现全局路径规划,两者所规划出的全局最优路径长度相差不大,但本文提出的改进算法计算时间更短、效率更高,方差也稍小于前者.结合本次路径规划所定的起点和终点,发现算法的搜索环境较好,没有很多复杂障碍物.因此可得出,在相对简单的环境下进行路径规划,线性递减惯性权重粒子群算法和本文提出的改进算法均能实现全局路径规划,但改进后的算法收敛速度更快,算法的稳定性更高.

表2 利用粒子群优化算法和改进后的算法效果对比1
Table 2 Particle swarm optimization algorithm and the improved algorithm are compared firstly

方法平均规划路径长度(km)方差平均计算时间(s)LDW-PSO118.480.0272.47CMPSO117.2501.28

为检验两种算法在复杂环境下进行路径规划的表现,设置起点坐标为P(47.24,233.75),终点坐标为Q(163.48,32.63),其它参数均与上述实验相同.分别利用两种算法进行路径规划30次,记录所获取的全局最优路径长度, 其最优个体适应度值的平均值随迭代次数的变化如图8所示.计算全局最优路径的均值以及方差,结果如表3所示.

图8 路径规划适应度值随迭代次数变化曲线2Fig.8 Fitness of path planning varies with the number of iterations secondly

结合图8、表3分析可看出,在对复杂环境进行路径规划时,线性递减惯性权重粒子群算法较容易陷入局部最优,偏差较大,不能有效规划出全局最优路径.相对而言,本文提出的改进算法不仅能取得更好的最优值,规划出更优的全局路径,而且算法平均计算时间短,方差较小.这些说明改进的算法不仅能解决复杂环境下的全局最优解的搜索,而且算法收敛速度更快,搜索精度更高,稳定性更强.

表3 利用粒子群优化算法和改进后的算法效果对比2
Table 3 Particle swarm optimization algorithm and the improved algorithm are compared secondly

方法平均规划路径长度(km)方差平均计算时间(s)LDW-PSO277.844.76212.74CMPSO246.470.0672.54

5 结 语

本文利用粒子群优化算法规划出全局最优路径,并加入平滑优化处理,将优化后的路径与前者进行对比可发现删除冗余点的平滑优化处理方法可极大地提高算法运行效率,保证船舶安全高速航行.针对线性递减惯性权重粒子群算法存在的问题,本文提出了改进算法.通过混沌序列对初始种群进行初始化,并进行一定的筛选,保证了初始粒子的质量和分布的均匀性.并且建立多种群机制,平衡种群的全局搜索能力和局部搜索能力,最后通过仿真实验验证了该算法的有效性.