一种基于粒子群优化改进策略的智能驾驶车辆路径规划方法

刘晓欢，张德干，张 捷，张 婷，朱浩丽

(1.天津理工大学 计算机科学与工程学院，天津 300384;2.北京交通大学 电子信息工程学院，北京 100044)

自1959年Dantzig等提出车辆路径规划的问题[1]，随着研究人员们的深入探索，这一难题得到不同程度的解决[2]，包括遗传算法，蚁群算法，粒子群优化等[3].在设计智能驾驶车辆路径规划算法时，人们将研究重点放在复杂环境和多移动目标的系统上[4-5]，包括模糊控制，强化学习，智能决策等[6].

粒子群算法[6-7]通过鸟群搜寻食物源和相互传递各自的信息使整个鸟群都能聚集在食物源周围[8].该算法在路径规划中的应用受到很多研究人员的青睐[9].其结构简单、需要调节的参数少而被普遍应用[10-11].但由于其在搜索后期，粒子群种群的多样性下降容易导致粒子陷入局部极值最优解[12-13].针对这一问题，文献[14]提出一种变异操作方法，增加种群多样性，通过路径点冗余筛选算法使所规划路径更平滑更短.文献[15]提出了将细菌觅食算法引入到粒子群搜索过程的具有全局搜索能力和快速收敛的混合算法.

结合神经网络算法的路径规划方法有很好的适应性，因此市场应用前景良好[16].所以近年来与之相关的问题也成为研究人员们的关注热点[17-20].例如：为解决网络流量时间序列的预测问题，文献[21]提出了量子遗传算法与模糊神经网络相结合的网络流量时间序列预测模型.量子遗传算法具有运算效率高、全局寻优能力强、稳定性好等优点[22].因此利用量子遗传算法优化模糊神经网络的权值可以获得较好的预测精度和效果[23].文献[24]提出采用小波网络和前向神经网络相结合的四层神经网络结构.文献[25]将神经网络算法与Dijkstra算法结合，解决神经网络的神经元活动值计算成本和时间成本急剧增加这一问题.

本文作者设计利用新的权重和学习因子更新方式的粒子群优化算法对模糊神经网络进行优化，克服局部极值问题，并将之应用于智能驾驶车辆的路径规划中，求解最优路径问题.

1 HPFA算法

本文设计利用粒子群优化算法对模糊神经网络权值参数进行训练，提出一种基于粒子群优化策略与模糊神经网络算法的混合算法(Hybrid PSO and FNN Algorithm, HPFA).

1.1 问题描述

1.1.1 移动环境建模

对智能驾驶车辆的行驶环境进行移动环境映射，在进行环境地图建立模型时，对于同一个工作环境，划分的网格数量愈高，网格就会愈小，地图的精度就会愈高[26].为了更形象的模拟，采用栅格方式进行环境映射，设计如下步骤：

1)边界学习：智能驾驶车辆由一个特定的地方开始沿着行驶区域的边界或与边界紧挨着的障碍的边界按某一特定方向搜索一周，在此过程中获知整个行驶环境的轮廓及障碍物的分布情况，并对数据进行记录.

2)生成映射环境：在Matlab中将记录的数据进行重现，标记所有障碍的形状，大小，位置等参数.

1.1.2 最优路径选择

在智能驾驶车辆的移动过程中，会自动根据优化指标来选择最优的路径[27].HPFA算法依据综合代价参数确定最优路径，参数定义如下：

定义1将智能驾驶车辆在行驶中的路径成本与躲避障碍物路径成本进行等价换算，并将结果定义为等价代价.其计算方式为

(1)

式中：C为等价代价；N为映射环境中最大维度的边界值；n为步长；α、β∈[0,1]，表示加权系数；L代表规划路径长度；l表示躲避障碍的代价路径长度.

定理1等价代价的增长并不随着网络规模或者路网中节点数目固定比例规律增长，而是随着网络的变大，结点的增多，增长速率越来越大，即网络中后期参与计算节点的等价代价更大.

证明：根据式(1)的实际意义，C的增加和网络的大小有关.即网络规模越大，节点越多，关联边越多，规划路径长度和躲避障碍形式路径长度值越大，等价代价越高.因此有

(2)

(3)

随着路网中节点数目的增多，L和l可以看作是两个与指数增长趋势相同的变量，因此C的增长速率也越来越快，但不是固定的比例规律.

定义2根据路径规划过程中的位置坐标得出

(4)

(5)

式中：(xg,yg)代表目标节点坐标；(xs,ys)代表起始节点坐标；(xn,yn)代表当前节点坐标；M代表目标节点最大维度坐标值；m表示当前节点坐标中的最大维度坐标值.

定理2规划路径长度越长，对应躲避障碍行驶代价路径越长，反之，躲避障碍行驶代价路径越短，所规划路径也越短.

证明：规划路径是指从起始节点到终止节点之间的欧氏距离，到达终点时的最后一个节点计算中，当前节点坐标到达终止节点坐标，则

xn=xg,yn=yg

(6)

即

(7)

此时l最小，即最后一次计算的躲避障碍行驶距离最小.而中间每次计算的躲避障碍行驶距离长度都为不小于零的数，因此，初始节点与终止节点坐标距离越大，每次计算的代价路径长度累加值就越大，对应躲避障碍行驶代价路径越长，反之亦成立.

1.2 粒子群算法优化策略

1.2.1 粒子群算法

基本的PSO算法原理简单，假设存在一个能够搜索的n维空间，种群由m个单独粒子组成，并记为X=[x1,x2,…，xm]T，其中，第i个个体粒子的位置信息为xi=[xi1,xi2,…，xin]T；速度信息为vi=[vi1,vi2,…，vin]T；每个粒子的个体极值表示为Pi=[pi1,pi2,…，pin]T；而用pg=[pg1,pg2,…，pgn]T代表整个种群的全局极值[28].粒子的位置与速度以迭代方式进行更新，其更新方式如下

(8)

(9)

式中：k表示迭代次数；d代表粒子维度；p表示最优解；i和g分别代表粒子个体和粒子群；ω代表惯性权重；c1和c2为学习因子；r1,r2为均匀分布的随机数，且r1,r2∈U[0,1].

1.2.2 惯性权重更新

在粒子群算法优化中，首先对惯性权重的更新进行优化，方便在优化算法的训练中使用.惯性权重是平衡全局和局部搜索能力的关键，较大的ω值可以保证较强的全局搜索能力，同时局部搜索能力就会减弱，反之亦然，因此合理的设置ω值可以提高算法整体性能以减少迭代次数，提高搜索效率[29].

定义3在算法迭代过程中，惯性权重更新设计采用阈值非线性递减策略计算，设计将惯性权重的调整与迭代次数关联，并定义

(10)

式中：ωmax,ωmin表示惯性权重的最大值和最小值；kT表示迭代阈值;递减因子λ>0.迭代过程由于递减因子引入，ωk随迭代次数增加而非线性递减，有利于避免陷入局部极值.算法开始惯性权重值较大，有利于粒子以较大的速度遍布整个搜索空间从而确定最优解的范围，然后其值逐渐减小以集中寻找最优解[30].

1.2.3 学习因子更新

设计了新的学习因子更新方式，c1保持较大值有助于粒子大范围地搜索，但是收敛速度相对较慢.c2保持较大的值，有助于粒子学习群体的社会经验从而快速收敛，但是搜索规划空间的能力相对较弱[31].

定义4为增强粒子在算法初期的搜索能力和后期的收敛能力，在算法前期保持较大的c1值和较小的c2值，在算法后期保持较小c1值和较大c2值，定义学习因子的更新公式为

(11)

1.2.4 适应度函数

关于适应度函数的确定，优化问题的可行解能够用每个个体粒子的位置信息表示，而适应度函数的取值很大程度上影响解的最优与否[32].即适应度函数是对每个粒子中包含的网络参数好坏的评价，因为适应度函数选择决定了整个系统的性能.

定义5在粒子群训练中，通常认为适应度值越低的个体性能越好，因此基于代价函数设计如下适应度函数

(12)

ci=αli+βld

(13)

(14)

(15)

式中：ld表示当前节点与障碍物之间的距离;ci表示当前节点的等价代价.因为智能驾驶车辆目前并不能完全实现理想的驾驶理念，因此在研究和试应用中，都将对象设置为中高速车辆，在保证安全的前提下，实现其他功能.因此根据实际情况，在进行智能驾驶车辆的路径规划设计时，更关注算法对于突发交通状况的处理速度，联系适应度函数参数的意义，相比而言，行驶距离的代价权重要次于当前节点(即智能驾驶车辆本身)的安全性权重，其与障碍物之间距离越近越危险，因此设置系统随机分配它们值，且满足：α<β.

1.2.5 训练规则

通过训练关系，确定粒子群优化算法对模糊神经网络结构参数的训练规则.

定义6在迭代次数满足k

(16)

(17)

迭代次数到达阈值后，即ωk=ωmax，是一个反向过程，此时在程序中设置不再更新cij、σij以减少冗余计算.由于这两个参数用于确定模糊神经网络隶属函数的位置和形状，需要不断调整以获得更精确的结果，因此设计这样的训练规则，促使模糊神经网络逐渐逼近并确定最优解的最小范围及最优解.

1.3 模糊神经网络结构设计

神经网络与模糊系统相结合得到的模糊神经网络融合了二者的优势[33].本文中为智能驾驶车辆的路径规划设计使用模糊神经网络算法实现，而在模糊规则定义中，使用粒子群优化算法对神经网络的输出进行训练，以得到更精确的最优路径解.路径规划的控制模型设计如图1所示.

模糊神经网络的结构设计使用五层结构的模块化网络，其中：

1)输入层：用于将系统的输入层传输至下一层，节点没有函数变换，共有3个节点，每个节点代表一个方向的数据信息，即Front、Left和Right，用来描述关于障碍的数据信息，该层将输入直接传递到下一层，其作用是模糊界面，此时输入与输出相等.

2)模糊化层：将输入进行模糊化，节点函数为模糊系统中的隶属函数，即为隶属函数的生成层.该层每个节点计算一个隶属度函数.将输入的3个模糊量分别分为3种程度的代价，分别为较小代价S、中等代价M和高昂代价B来进行模糊化.因此本层共有9个节点，对第i个输入分量的第j个隶属函数节点有

(18)

(19)

3)规则层：即规则前件匹配层.其功能在于实现规则前件的匹配.通过与第2层节点之间的连接，进行组合匹配，通过各输入模糊值的逻辑运算，实现规则的前件，并在层内完成归一化耦合.节点数目为27个，该层输入是隶属度，输出为每条规则的归一化适用度，即为每条规则的权重ωk.

(20)

(21)

4)结论层：该层节点计算规则后件，并与输入的规则归一化使用度加权求和.节点数与第3层相同，本文中的输出表示总规划路径成本.

(22)

5)反模糊化层：即模糊判决层，也是输出层.所有第四层的规则节点都与该层输出节点连接，完成清晰输出模糊变量的实现.

具体结构见图2，这样的模糊神经网络结构设计既能够保证模糊算法功能的实现，又具有比传统的模糊神经网络结构简洁的优势，在实际路径规划中，尤其在大型复杂网络中，能够为整体规划算法提供更好的时间和效率优势.

1.4 HPFA算法步骤

本文算法的执行流程规划见图3，具体步骤设计如下：

1)初始化路网环境，完成栅格映射，并获取起始点和终点位置坐标.

2)初始化粒子群算法，设置种群规模，学习因子，障碍权重，当前迭代次数设置为1，设置粒子初始位置和速度，规定个体继承属性，设置原始最优位置为初始位置.

3)计算适应度函数，利用初始粒子群算法参数调整模糊神经网络参数，计算下一时刻网络输出.

根据式(4)和式(12)计算适应度函数的伪代码如下

function F=fit(i)

f=0;

for i =1:N

f=fi+(αli+βLd);

%α，β are random?data in[0,1],α<β

% euclidean

dli=sqrt((xi-xs)*(xi-xs)′)+sqrt((xg-xi)*(xg-xi)′)

-sqrt((xg-xs)*(xg-xs)′)

dld=sqrt((xd-xi)*(xd-xi)′)

F=1/f;

end

4)确定当前代的个体最优位置和种群最优粒子位置.

5)更新粒子群位置和速度，重复步骤2)～4).

更新位置，速度的伪代码如下：

for t =1:M

for i=1:N

% update location&speed

v(i,:)=?w*v(i,:)+c1*r1*(p(i,:)-x(i,:))

+c2*r2*(pg-x(i,:));

x(i,:)=?x(i,:)+v(i,:);

if fitness(x(i,:))

y(i)=fitness(x(i,:));

p(i,:)=x(i,:);

end

if y(i)

pg=p(i,:);

end

end

% output best solution

Pbest(t)=fitness(pg);

end

6)判断是否到达最大进化代数，若没有，则根据式(10)更新权重参数，依据式(11)更新学习因子；若达到最大进化代数，则确定算法结束条件.

7)根据式(16)、式(17)的规则，利用权重参数ω和迭代参数k对模糊网络的模糊子集参数cij和σij进行调整，并利用最优粒子提供的网络参数计算模糊神经网络输出.

function Train

if k

% update c&sigma

ck=ck*(xi-xs)/(xg-xi)*wk;

sigmak=(1-1/k)sigmak;

% update?w&c1,c2

wk=wmax-(wmax-wmin)*((k-1)/(kt-1))∧λ

% λ=2

c1k=c1s-(c1s-c1f)*k/m

c2k=c2s-(c2s-c2f)*k/m

% c1s>c1f,c2s

end

else

% stop update

ck=ck;

sigmak=sigmak;

end

end

8)采用滤波法进行平滑处理，对模糊神经网络算出的路径进行处理，显示计算结果与最优路径.

1.5 算法复杂度分析

在算法的设计和分析中，将求解问题的关键操作指定为基本操作，通常把算法执行基本操作的次数定义为算法的时间复杂度.算法的空间复杂度定义为所耗费的存储空间，即关于问题规模的函数[34].

定理3HPFA算法的时间复杂度为O(n2).

证明 本文所设计的算法的时间复杂度由网络中所有节点的基本运算和粒子群优化算法对模糊神经网络参数的训练两方面决定.对节点的基本操作可以认为是扫描时对所有节点进行搜索，由于在实际交通网络中一个节点的相关联节点数一般不会达到n-1，即不能达到所有节点均两两相连.因此，复杂度中的关联点数可视为一个常量，则在某些情况下算法的时间复杂度为O(n2).而粒子群算法对神经网络参数的训练根据训练关系，可以理解为每次操作均为基本运算，即时间复杂度也为O(n2).因此HPFA算法的整体时间复杂度为O(n2).

定理4HPFA算法的空间复杂度为Ω(n2).

证明 由于路网结构以邻接矩阵的形式映射及存储在程序中，所采用的n×n矩阵来存储节点和边等数据的关系.因此HPFA算法的空间复杂度应为Ω(n2).

2 实验结果与分析

2.1 参数设置

针对模糊神经网络算法以及粒子群算法与本文所设计HPFA算法在算法功能和性能两个方面进行仿真对比，基本参数设置如下：

环境设置大小为30×30,障碍比例为15%.PSO算法参数中,粒子群规模为50.学习因子c1为1.5,学习因子c2为1.5,最大惯性权重wmax为0.9,最小惯性权重wmin为0.3,允许最大迭代次数m为300.FNN算法中,输入分量i为3,输入分量j为3,初始μij为1.5,初始σij为1.HPFA算法中,迭代阈值KT为20,递减指数λ为2.

在Matlab平台进行仿真实验，首先对本文算法在路径规划功能方面的效果进行仿真；然后对影响算法的参数进行调整，在不同环境下测试算法的性能.仿真测试主要分析参数包括：1)算法收敛速度；2)等价代价；3)求得最优解概率P；4)算法运行时间.

2.2 仿真实验分析

图4为环境模型和初始环境设置，其中横纵坐标表示方向，设置的起始点和终止点坐标分别为(1.5, 0.5)和(29.5, 27.5)，黑色标记栅格为障碍，其他为安全栅格，可作为路径规划的下一备选节点.

图5为初始参数设置下的路径规划对比.由图5可以看出，3种算法都可以成功规划出从起始点到终止点的路径，但相对而言本文算法所规划路径较其他两种方法更平滑一些，路径较短.

根据实验结果，3种算法在多次实验中规划路径与求得最优解概率如表1所示.

表1 基本参数实验结果

从表1可以看出，3种算法所规划最长路径和最短路径之间都有很大差距，这是因为在3种算法最开始都是未经训练和学习的结果，随着算法的运行，3种算法的结果都趋于最优解.FNN算法虽然规划的最长路径较其他两种算法差，但从平均规划路径长度可以看出，其多次训练之后的结果仍然较PSO算法更靠近最优解，这也是由于两种算法本身性质导致的：FNN算法系统较为复杂，初始运行时其计算结果范围大，但不能更好的向最优解逼近；而PSO算法在后期由于粒子多样性下降导致运行结果质量变差.本文算法在二者基础上进行的改进使得其在该实验中表现出了很好的优势，既能快速逼近最优解，又能保证很好的求解成功概率.

各算法收敛情况仿真结果分别如图6所示，可以看出，PSO算法在初始时收敛较快，之后略有减慢，在约100次迭代时达到收敛效果，此时适应度函数收敛在一个相对较高的值上；FNN算法则不然，其收敛速度由慢加快，在约120次左右迭代后实现收敛，但是适应度函数收敛在一个较PSO算法略优的值上；而本文算法HPFA则以较快速收敛性能，在80次左右迭代后达到收敛在三者中最低适应度函数的效果，且收敛曲线相对平滑，而PSO算法与FNN算法的收敛曲线在到达收敛值之前，均有不同程度抖动，这可能是由于粒子可选性与模糊神经网络的模糊子集参数变化导致的.

更改网络中障碍的比例，并以此来模拟针对突发交通状况所造成的路径规划障碍对路径规划算法的影响，当环境参数中障碍比例变为20%时，仿真实验结果分别如图7和表2所示，其中，路径规划仿真结果可以看出，随着障碍的增加，为了躲避突然发障碍，3种算法规划路径都稍有变化，平滑性受到了影响，但由于仿真环境限制，这种效果并不明显.

表2中的数据也表明，在网络规模不变时增加障碍后，3种算法所规划路径的最长路径都增加很多，尤其是FNN算法，这是由于虽然网络大小不变，但是由于临时障碍的增加，使得系统需要处理的关系变多，因此相对复杂的系统无效搜索也就变多，而PSO的简单系统则表现出较好的优势，因此采用PSO算法对模糊网络的模糊子集进行训练所得到的算法更能适应突然增加的交通障碍和更加复杂的网络，这也从另一个方面证明了设计本算法的意义.

图8为3种算法的运行时间仿真结果记录.可以看出，3种算法运行时间随网络规格增大的趋势大概一致，这是因为在网络较小时，因为节点数量较少，运算量小，而随着网络增大，可供路径选择的节点数变多，且需要处理的边和节点权值以及关系变得复杂，所以算法运行时间都呈现出快速增长的趋势；随着节点持续增多，PSO算法因其生物特性优势，使得其增长趋势相对变缓，而FNN算法则因为结构复杂导致其运行时间明显大于其他两种算法.本文算法HPFA则由于采用了PSO算法对FNN中模糊子集参数的调整，使得其在网络中节点少时运行时间最少，而随着网络节点增多，其表现出了较好的适应性，算法运行时间的增长没有PSO算法与FNN算法增长趋势明显，本算法在实际应用中对缓存和系统硬件的要求,证明在同样网络计算容量的需求下低于其他两种算法.

记录网络规格为30×30时不同障碍比例下的等价代价，对比如图9所示.由图9所示结果可以看出，随着网络中障碍比例由15%分别增加到20%和25%后，3种算法的等价代价都会有所增长，这是由于新增障碍导致安全栅格变少所致；而相比之下，PSO算法的等价代价增长较为明显，FNN算法次之，HPFA算法的等价代价增长最为缓慢，这是由于FNN算法的自适应性使之表现出较好性能，而本文算法则在此基础上又兼顾了系统的简洁使算法更高效，因此能够以最小的等价代价获取最优路径.

Apollo是很好的智能驾驶研究案例,其基本的路径规则算法为A*算法,因此在算法性能分析中,将HPFA算法与A*的改进算法(A* Algorithm Optimization, AAO)，以及智能驾驶车辆路径规划中比较常用的其他算法进行对比，其中包括：蚁群算法(Ant Colony Optimization, ACO)，遗传算法(Genetic Algorithm, GA)，K则最短路径算法(Kth Shortest Path Algorithm, KSPA)[35].在30×30栅格网络环境，障碍比例为15%时，几种算法规划路径结果对比如图10所示.

由图10所示仿真实验结果可以看出，在整体规划路径方面，HPFA算法所规划路径在长度和平滑性方面明显优于其他四种算法，根据定理2可以判断出算法在规划路径的长度方面具有优势，其躲避障碍行驶距离的等价代价也最小.

当障碍比例增加至20%以模仿交通网络中的突发事故等临时因素导致的障碍时，几种算法所规划路径如图11所示.从图11所示的仿真实验结果中可以看出,当障碍增加时，HPFA算法所规划路径在相对平滑，转弯较少的情况下避开所有障碍规划出了一条长度较短的路径，即HPFA算法能够在等价代价较小的条件下，规划出一条最优路径.而其他几种算法也能够成功规划出从起点到终点的路径，但相对比而言，转弯数量和长度不占优势.

为了更好地说明问题，不同障碍比例环境下几种算法规划路径中的等价代价统计如图12所示.可以看出，HPFA算法在等价代价方面都表现出了比较好的优势，而随着障碍比例的增加，HPFA算法的等价代价增加也是最少的，这也为本算法在实际应用中的可行性提供了保证.

图13为经过多次仿真实验的几种算法的运行时间对比结果.从图中所示结果可以看出,HPFA算法在多次仿真实验中运行时间方面显示出明显优势，尤其是在网络节点越来越多的情况下，这种优势体现得更加明显，这也为本文算法在实际应用中的可行性提供了保证.

2.3 实验测试分析

随机截取的在3000 m×3000 m的天津市实际地图上进行了ACO算法、GA算法、AAO算法、KSPA算法与HPFA算法的规划路径测试对比，其详情如图14～图16所示.

由图16所示结果可以看出，几种算法都能成功规划出由起始点人民医院至终点营口道的路径；其中ACO算法、AAO算法与KSPA算法分别用3个转弯规划出相对较短路径，GA算法所规划路径相对略长，包含两个转弯，而本文HPFA算法所规划路径则规划出了一条含有一个转弯的最优路径实现路径规划.

图17和图18为该实验中5种算法的等价代价和平均运行时间对比结果.从图17和图18所示结果可以看出，不论是在路径规划中的等价代价，还是算法平均运行时间方面，HPFA算法都比几种常用的路径规划算法优秀，该实验也在一定程度上为本文算法的实际应用提供了证明.

3 结论

1)针对粒子群算法在路径规划应用中容易陷入局部极值的缺点，设计了优化惯性权重和学习因子更新方式的改进粒子群算法，并通过该算法对模糊神经网络的模糊子集参数按照定义规则进行训练的方法来解决这一问题.

2)设计了合理的适应度函数来证明该算法的收敛速度更快，通过仿真分析和实验测试证明了本算法在规划路径长度和算法本身效率方面的优势.

3)由于本文算法注重算法效率和收敛状况，即寻找最优解的效率，其算法复杂度相比而言不占优势，寻找一种能够克服算法复杂度的影响，又能快速响应的结构和算法完成智能驾驶车辆的路径规划，是我们下一步的研究方向.