浅谈关于PSO算法路径规划的研究-德赢Vwin官网网

0 引言

路径规划是车载导航系统的基本功能，由于其有较强的应用价值，国内外学者对此进行了深入的研究[1-3]。现今较流行的算法有Dijstra算法（简称D算法）和A*算法，但D算法搜索速度较慢，A*算法搜索速度快但成功率不高，且这些算法只能在静态地图上进行路径规划，没有考虑实时变化的交通状况。

近年来，智能算法因其强大的搜索能力而被广泛应用于路径规划中。杨易[4]把遗传算法与A*算法相结合，提高路径规划算法的效率；王健[5]把蚁群算法应用到导航的路径规划中，但其没有考虑随时间的动态变化因素；于海璁等人[6]提出了一种适用于多模式路径规划的遗传算法，可用于个性化的路径导航。本文将PSO算法应用到车载导航的路径规划中，引入变异算子解决PSO算法的局部最优问题，不仅拥有较快的收敛速度，还能增强全局搜索能力。

1 粒子群算法的描述

粒子群算法由Eberhart博士和Kennedy博士在1995年提出[7]，它通过粒子间的协作和信息共享来寻找最优解。算法在搜索时，根据粒子自身历史的最佳位置pbest和种群内所有粒子历史的最佳位置gbest的基础上进行位置变化，其速度和位置公式如下：

其中，t表示迭代次数，r1、r2是（0，1）之间的随机数，c1、c2为学习因子，w为惯性权重，其表达式为：

其中wmax、wmin为权重的最大和最小值，tmax为最大迭代次数。

2 粒子群算法在路径规划中的应用

本章节的主要内容是解决粒子的编码和适应度函数的构造，编码方式涉及粒子位置和速度的更新操作，适应度函数用来评价粒子的适应值。最后还解决了PSO算法自身陷入局部最优的问题。

2.1 粒子编码

编码即粒子位置的表达方式，是设计粒子群优化和应用操作的关键问题，根据路径规划的实际情况，本文采用直观、方便的实数编码[8]。粒子状态表达方式如式（4）所示，编码方式如式（5）所示。

其中，f（x）表示适应值，m表示粒子个数。

2.2 适应度函数

2.2.1 适应度函数的设计

将粒子群算法用于路径规划时，适应度函数的设计使得该算法不仅能够在静态网络下获得最优路径，通过增加惩罚项M[9]也能适用于实时变化的交通状况，其适应度函数定义为：

（1）当0

（2）当0.5≤n<0.75时，微拥挤状态；

（3）当0.75≤n≤1时，严重拥堵状态。

针对不同的拥堵状态采用不同的适应度函数。

适应度函数主要取决于是否有交通拥堵等状况，车载导航仪[10]将接收到的交通信息转换成路段的相关特性数据，同时给出交通拥堵系数n，并根据n的大小选择相应的适应度函数。采用该适应度函数的优点是占用的存储空间少，并根据实时的交通状况找出最佳路径。

2.2.2 适应度函数对路径规划的影响

如图1所示，粒子群的起点为S，终点为D。粒子群从S点开始搜索，若不定义适应度函数，则粒子随机选择移动方向，而根据适应度函数（式（6）），大部分粒子选择更靠近终点的右方，小部分粒子选择左方，如图1（a）所示。当粒子到达下一路口时，重新计算自身适应值，并共享当前全局最优解，各个粒子根据式（1）、（2）更新自身的速度与方向。因此，在单位时间段内，沿着上方行走的粒子数量高于其他方向的粒子数，同时这些粒子记录自身的局部最优解，也能得到全局最优解。后续粒子选择路径时会受这些最优解的影响，沿着粒子较多的方向前进，也有小部分粒子会选择其他方向来寻求更短的路径，如图1（b）所示。当某个粒子到达终点时，其他粒子将会收到该粒子共享的信息，所有粒子将会朝该方向前进，如图1（c）所示。

2.3 解决陷入“局部最优”的问题

为了避免PSO陷入“局部最优”，本文在PSO算法中引入变异算子，其思想是：当算法达到特定的迭代次数h之后，除去之前拥有全局最优解的粒子外，计算其他粒子与当前全局最优值gbest的距离，若距离小于阈值，则取这些粒子的百分比重新初始化，使这部分粒子重新寻找最优值，使种群获得更高的粒子多样性，扩大搜索范围，避免粒子群算法陷入局部最优，同时能够增强全局搜索能力。带变异算子的粒子群算法如下：

If（th）

取满足dp-gbest

Else

按式（1）、（2）更新粒子速度和位置；

End

其中，t为当前迭代次数，tmax为最大迭代次数，h为特定的迭代次数，dp-gbest表示粒子的当前点到全局最优解gbest的距离，DistValue为设定的距离值。

3 算法验证与分析

为了验证上述算法的可行性，本文根据上海市松江区部分实际地图抽象得到的路网数据结构进行实验，如图2所示。