用于车载导航路径规划的改进果蝇算法

李 哲，王嘉玮，吕 萌，梁德禹

(1.唐山市交通运输局，河北省唐山市路北区大里路125号 063000；(2.北京科技大学 自动化学院，北京市海淀区学院路30号 100083)

在现代智能交通系统中，根据起点、终点为驾驶员规划可行、有效的行车路线是极为重要的工作。高质量的行车路线一方面能够协助驾驶员快速驶达目的地，另一方面对缓堵保畅、节约能源、环境保护具有重要意义。

城市道路网络是极为复杂的拓扑结构。对行车路线进行规划时，不易建立精准的数学表达式。在复杂道路网络中，随着节点的增加，运算规模呈指数增长，大幅度提高了路径规划问题的求解难度。

近年来，对智能优化算法的研究取得了长足的进步。以遗传算法[1]、蚁群算法[2]、粒子群算法[3]为代表的经典生物启发式算法被广泛应用于复杂问题的优化求解。研究人员尝试采用这类算法求解路径规划问题，并取得一定成果。梅伟等将喷涂机器人路径规划问题抽象为广义旅行商问题，并提出一种改进的离散灰狼算法实现路线设计，提高喷涂机器人效率[4]。赵杰等对物流车辆配送路线规划问题进行建模，并设计了一种改进的果蝇优化算法，引入多种遗传算子，提高算法性能[5]。徐飞等设计了基于鱼群算法的车载导航系统模型，实现城市交通路线的智能规划[6]。

文中对近年来较为新颖的果蝇优化算法[7][8]进行分析，设计了一种改进算法，并将其集成于车载导航路径规划系统中。在对唐山市人大附近街区进行建模的基础上，设置不同的起点、终点，利用该算法为智能车规划行车路线，开展仿真实验并对比分析。实验结果表明，文中所提算法能够高效构建复杂路网环境中的合理行车路线，规划质量较高。

1 道路建模及分析

选取唐山市唐山市第四幼儿园—市人大/政协—市教育局地块进行建模，共选取38个节点，用经纬度标记这些节点的位置。节点信息如表1所示。

表1 唐山市人大/政协附件区域的行车节点(部分)Tab.1 Nodes in the area of Municipal People's Congress of Tangshan City(part)

图1 该区域的节点分布Fig.1 Node distribution in the area

设定起点、终点后，在该区域规划行车路线可被视为寻求最优“节点序列”的过程。该序列最长不超过节点总数，起点、终点确定，并规定每个节点仅可通过一次。寻优过程中，一条待选序列的构建以达到终点为止。如构建过程中出现当前点周围无可走节点的情况，则该路线构建不成功。节点间的代价简单规定为距离，即优先选择距离较短的下一节点，后续可根据路况等因素进行改进。为规划区域设定环线，即车辆不会驶离城市，仅能够在环线上或环线区域内进行搜寻。

根据该环境设计邻接矩阵A，如节点[i，j]间存在直接连接，则对应位置Aij为节点间距离值；如节点间不存在直接连接，则Aij=∞。由于该区域面积不大，文中近似将地表视作平面，通过2维欧式距离计算节点间距离。

2 基于果蝇算法的车载导航路径规划

生物启发式智能算法在非线性优化问题、NP完全问题(Non-deterministic Polynomial Complete)的求解中具有一定优势。这些智能算法启发自自然界中不同物种种群的特点和行为，如生物体的遗传进化[1]与免疫[9]，鸟群[3]、蚁群[2]、鱼群[6]等种群的觅食行为等。一般而言，这类方法通过种群的多次迭代进化，逐渐向适应度更高的解靠拢，同时适当引入随机性以避免算法陷入局部最优。与自然界中生物的多样性相一致，不同生物启发式算法的流程中也参考了不同的生物行为。

文中主要采用了近年来较为新颖的果蝇优化算法求解车载导航路径规划问题。

2.1 果蝇算法

果蝇优化算法由台湾学者潘文超于2011年提出。该算法启发自果蝇的觅食行为，因其较低的计算复杂度与较好的性能，被广泛应用于最优化问题的求解。在果蝇算法中，“味道浓度”信息判定值S和“味道浓度”值Smell被用作启发式信息，近似不同变量在寻优过程中对适应度函数的影响。

果蝇算法的基本步骤可总结如下：

Step 1超参数确定，即种群大小N、最大迭代代数Max等；

Step 2以随机形式初始化果蝇种群；果蝇利用其嗅觉，进行搜索并飞行至相应位置；假定果蝇在二维空间(X，Y)中搜寻最优解，果蝇种群的位置确定公式如(1)所示；

(1)

式中，n∈[1,2,…，N];Xaxis、Yaxis为以随机方式初始化的果蝇群体位置；R为随机数；

Step 3为每只果蝇计算味道浓度判定值Si，如式(2)，式(3),

(2)

(3)

式中，Dn即为该果蝇距原点的距离；

Step 4将Step 3中求得的味道浓度判定值Sn带入适应度函数，计算味道浓度值Smell(n)，据此判断每只果蝇(第n只果蝇)位置的优劣；如对2维函数f=-5+x2进行最小化优化，则有：

(4)

Step 5依据优化目标确定位置最佳的果蝇，记录浓度值，如式(5)所示；

[bestSmell， bestIndex]=min(Smell(n))

(5)

对应地，对于最大化问题，式(5)中的min替换为max；

Step 6根据Step 5中求得的bestIndex选取位置最佳果蝇，即其位置[X(bestIndex),Y(bestIndex)]；

利用果蝇的“视觉”感知，蝇群整体飞向该最优位置，如式(6)、(7)、(8)所示；

Smellbest=bestSmell

(6)

Xaxis=X(bestIndex)

(7)

Yaxis=Y(bestIndex)

(8)

Step 7在迭代代数N内重复执行Step 2至Step 5；判断该代蝇群中有无位置更佳的果蝇；如有，则执行Step 6；算法在最大迭代代数N时跳出，此时的[X(bestIndex),Y(bestIndex)]即为所求得的解。

在上述优化中，果蝇算法将待优化的参数x转化为具有两个参量的“味道浓度判定值”，从而分散了优化过程中陷入局部最优的风险。这一特性使果蝇算法在对某些模型的超参数进行优化时具有优势，如GRNN中的spread[10]。

2.2 用于车载导航路径规划的果蝇算法

上述经典果蝇优化算法可被用于函数优化、模型超参数优化等连续优化问题。而在现实生活中，需处理的实际问题往往更为多样化。根据问题建模形式的不同，果蝇算法也被赋予了不同的意义。国内外学者结合不同场景，对果蝇算法做出了不同的改进。

对于实数优化问题，果蝇算法中的蝇群可被看作一组位置，位置的变化影响数值的变化[7]。在离散、组合优化问题，如TSP、车辆调度等问题中，果蝇种群常被处理为一组序列[11]。此外，对于机器人路径规划问题，在采用栅格法[12]、基于图的方法[13]等方式构建的地图环境中，果蝇可被视作位置，也可被视作序列。这些算法遵循了果蝇算法的基本思想，即通过果蝇的“嗅觉搜索”和“味道浓度判定值”带入随机变化，发现味道浓度更佳的个体；通过“视觉”信息，在每次迭代中实现在最佳位置的聚集。

文中所求解的车载导航路径规划问题是典型的离散、组合优化问题。遗传算法[1]是求解该问题的常用方法。为便于对路径整体而非单一位置进行评价，同时尽可能减小局部最优风险，本文将果蝇建模为一组序列，也就是道路环境中一组路口节点的组合。

结合车载导航路径规划实际环境，本文算法基于果蝇算法思想，主要进行了以下3点改进。

(1)面向离散优化问题，在果蝇序列的构建过程中，为地图中的每一个节点设计味道浓度判定值，如式(9)、(10)所示。

(9)

(10)

式中，n∈[1,2,…，N]，为种群大小；t为可供选择的节点编码，d为目标节点编码；Dnt为当前点[xnt,ynt]到目标点[xnd,ynd]的距离。

这一设计使得节点离目标点越近，味道浓度判定值越大。在果蝇构建路线的过程中，依据Snt的大小，按照赌轮法选取下一个节点。利用“嗅觉搜索”和味道浓度判定机制引入启发式信息(距离)和随机变化(赌轮选择)，是优化种群的重要步骤。

(2)进一步设计了与路径规划问题相一致的味道浓度计算函数，如式(11)所示。

Smell(n)=D1+D2+…+DD

(11)

式中，D为一条路线中两个相邻节点间的距离。

(3)引入交叉算子，进一步丰富种群多样性以发现性能更优的解。本文中采用比较基础的单点交叉形式。如对两条路径：

A：[1,3,6,5,7,11,4,10]

(12)

B：[1,2,8,9,5,4,10]

(13)

判断路径间是否有重合点，如本例中[5,4]，随机选择节点[5]，则交叉后路径为：

C：[1,3,6,5,4,10]

(14)

相较于经典遗传算法，本文所设计的改进果蝇算法利用了蝇群的“视觉搜寻”、“聚集”机制，即对参与交叉的果蝇进行筛选，仅对当前最优序列和部分次优序列进行交叉操作。

2.3 算法步骤

文中设计的改进果蝇算法基本步骤如下。

Step 1超参数确定，即种群大小N、最大迭代代数Max等；

Step 2按照2.2所述，构建初始种群即N只果蝇、N条路径；

Step 3依据式(11)计算味道浓度，选取味道最佳的路径序列；

Step 4种群向味道最佳序列聚集，在最佳序列、与最佳序列存在共同节点的次优序列、与最佳序列存在共同节点的随机某一条序列间进行交叉操作；

Step 5按照10%的概率进行变异操作，即对味道浓度不佳的10%的果蝇进行变异，按照2.2所述，利用嗅觉搜索重新构建序列；

Step 6采用基于味道浓度的轮盘赌方法选取N只果蝇，重复Step 3至Step 6，直至达到Max。

需要说明的是，文中构建待选序列时，需达到终点。规定每个节点仅可通过一次。如构建过程中出现当前点周围无可走节点的情况，则该路线构建不成功。规定城市存在环路，即汽车能够以绕城一周的形式抵达终点，不会出现驶离城市的情况。

3 实验分析

结合第1节中构建的唐山市某街区道路环境，开展仿真实验。实验中果蝇规模为10，最大迭代代数为200，变异概率为10%，采用单点交叉的形式。

文中采用车载导航路径规划的常用算法，遗传算法[1]作为对比，其种群规模为10，最大迭代代数为200，选择60%的个体进行交叉，变异概率为10%。采用基于适应度的轮盘赌方法进行个体选择。变异概率为10%。变异操作为将某点替换为可行驶点，需检查变异操作后新节点是否能够与变异前的路径相连接。

在所选街区环境中，分别设定不同的起点—终点，算法运行5次进行规划，其规划结果如表2所示。

表2 不同起点-终点情况下两种算法的规划结果Tab.3 Length of the routes with different starting points and terminus

由表2中的数据可以看出，在5组实验中，文中所设计的果蝇算法与遗传算法在3组实验中取得了一致的最优规划路线。在起点为14、终点为22，起点为29、终点为12的实验中，果蝇算法取得了优于遗传算法的解。

起点为4，终点为22时，果蝇算法所得最优路线为4-3-2-1-38-18-36-35-21-22，如图2中黑色路线；遗传算法所求得的最优路线为4-5-7-15-14-17-19-21-22，如图2中红色路线。

图2 起点为4终点为22时两种算法所得路线Fig.2 Route obtained by 2 algorithms from node 4 to node 22

起点为29，终点为12时，果蝇算法所得最优路线为29-28-27-26-25-35-36-18-17-14-13-12，如图3中黑色路线；遗传算法所得最优路线为29-28-27-26-34-36-18-17-14-13-12，如图3中红色路线。

图3 起点为29终点为12时两种算法所得路线Fig.4 Route obtained by 2 algorithms from node 29 to node 12

4 结束语

文中结合车载导航路径规划问题，设计了一种改进的果蝇算法。对唐山市人大/政协街区进行建模后，采用该改进果蝇算法求解路径规划问题。在本文试验中，选取了多组起点-终点，并进行规划，对结果进行统计。实验结果表明，该算法能够高效地为车辆构建从起点到终点的行车路线，降低行车成本。