基于回溯蚁群-粒子群混合算法的多点路径规划
Multi-point path planning based on the algorithm of colony-particle swarm optimization
通讯作者:
修回日期: 2018-10-23 网络出版日期: 2019-02-25
基金资助: |
|
Revised: 2018-10-23 Online: 2019-02-25
Fund supported: |
|
作者简介 About authors
刘丽珏(1973-),女,湖南长沙人,博士,中南大学副教授,主要研究方向为智能计算、人工智能、机器学习 。
罗舒宁(1993-),女,山东泰安人,中南大学硕士生,主要研究方向为多点路径规划 。
高琰(1973-),女,湖南长沙人,博士,中南大学副教授,主要研究方向为智能信息处理 。
陈美妃(1998-),女,广西壮族自治区,主要研究方向为大数据、云计算 。
景区多点路径规划问题是一个NP-hard问题,相当于寻找经过起始点和特定节点的最短路径。针对多点路径规划问题,提出了回溯蚁群-粒子群混合算法,该算法运用弗洛伊德(Floyd-Warshall)算法将图进行转换并且结合了蚁群算法和粒子群算法寻找最短路径。实验结果表明,此算法可以在小规模数据下快速找到精确解,同时,在较大规模数据量下,可以得到比最大最小蚁群算法和遗传算法更好的结果。
关键词:
The problem of multi-point path planning is a NP-hard problem,which is equivalent to finding the shortest path of a starting point and some specific node.Aiming at the problem of multi-point path planning,a retrospective ant colony-particle swarm optimization algorithm was proposed.This algorithm used Floyd-Warshall to transform the graph and combined ant colony algorithm and particle swarm algorithm to find the shortest path.The experimental results show that this algorithm can find the precise solution under small data,at the same time,under a large amount of data,can be better than the maximum minimum ant colony algorithm and genetic algorithm.
Keywords:
本文引用格式
刘丽珏, 罗舒宁, 高琰, 陈美妃.
LIU Lijue.
1 引言
随着智慧旅游的兴起,为了向游客提供更精准的导游服务,不少景区推出了官方App。单一基于道路网的导航方式已经难以满足游客对精准化、个性化导航寻径的需求。针对旅游景区个性化导航需求,不少论文提出了路径规划算法。文献[1]通过改进A*算法,融合多维动态环境信息,提出了景点间动态路径规划的解决方案。文献[2]以鼓浪屿景区为例,改进 Dijkstra 算法,实现了对该景区旅游线路的规划。文献[3]考虑了景区路径的复杂性,将景区路径分为全景区图和子景区图,改进蚁群算法实现了景区路径规划。文献[4]运用混合密度聚类方法识别景点热度,改进传统蚁群算法,提出了一种新型的热门游览景点路径规划方法。这些算法和模型仅仅解决了从起点到终点之间的最优路径规划问题。但在实际的旅游需求中,游客或旅游大巴进行路径规划时,更希望能得到一条从起点出发,经过某些必去的景点(必经点)的最短规划路线,以便游客无遗漏且更省时间地进行游览。
鉴于此问题,本文参考TSP(traveling salesman problem)问题解决方法,提出了一种回溯蚁群-粒子群混合算法(BAPM,backtracking ant colonyparticle swarm method),可用于解决景区中从某个旅游景点开始经过一些特定旅游点的多点路径规划问题,该问题的解决对旅游景区多点路径规划具有一定的参考价值。
本文将景区景点抽象为点,将景区路径抽象为有向线段,将景区图抽象为非完全有向图,从而对该图模型进行描述,并且利用该图模型,实现本文提出的BAPM算法。
2 基本知识
2.1 最大最小蚁群系统
最大最小蚁群系统(MMAS,max-min ant system)[5]是目前众多蚁群算法中效率较高的算法之一,它模拟了蚂蚁在觅食过程中寻找路径的场景,对当前路径不断地进行优化,从而找到最短觅食路线。该算法中,节点i到节点 j路径上的启发因子记作ηij;在第t次迭代中,节点i到节点j路径上的信息素记作τij(t);ηij与τij(t)的占比将会成为第t次迭代中蚂蚁k站在节点i选择下一个节点 j所走路径的重要因素,记作
2.2 粒子群优化算法
粒子群优化(PSO,particle swarm optimization)算法[6]模拟鸟群或鱼群的觅食方法,不断地更新当前位置及下一时刻的方向及速度,使其不断逼近目标。在PSO算法中,每个粒子通过不断的自我学习与向迭代最优粒子学习来改进自身的速度及位置,从而达到一个最优结果。
MMAS算法相对于传统的蚁群算法来说,极大程度地避免了局部最优情况的发生,并且增加了该模型找到最优值的概率,但是在节点数量非常多的情况下,MMAS仍然容易陷入局部最优,它的最大最小值的限制在避免算法快速陷入局部最优的同时,也降低了其寻找到最优路径的可能性,即忽略了信息素中的优越因子。为了增强算法寻找最优路径的能力,本文结合PSO算法和MMAS算法,对信息素τij(t)进行局部及全局更新,突出了对优越路段的标记,实现了对多点路径规划问题的有效处理。
3 回溯蚁群-粒子群混合算法
本文提出运用回溯蚁群-粒子群混合算法(BAPM)解决旅游景区中的多点路径规划问题。该算法结合了MMAS算法和PSO算法,增强了路径寻优能力,避免了算法过早陷入局部最优,并改善了算法寻优能力弱的问题,在对比实验部分,也达到了较为理想的测试结果。该算法如算法1所示。
算法1 回溯蚁群-粒子群混合算法
1) 使用Floyd-Warshall算法将图G转换成
2) 建立
3) 设置迭代次数num和蚂蚁数量m
4) 初始化信息素τ、启发因子η、信息素和启发因子的相关重要性参数α与β、学习因子中的可调参数ω、衰减因子ρ、最小信息素可调参数pbest、迭代代数i=1、全局最优路径pathgb、局部最优路径pathlb及蚂蚁所处当前节点startpoint
5) while i≤ num
6) 初始化path记录每只蚂蚁走过的路径
7) for j= 1:m
8) startpoint=s
9) 设置city × city 的矩阵
10)
11) if count(tabu_node (startpo int))>0
12) 计算tabu_node(startpo int)中的所有路段的被选择概率
13) 运用轮盘赌的概率选择方法选择下一步路段
14) 更新变量,startpo int=b、if b∉ node,node={node,b}
15) else
16) 回溯到tabu_arc的上个状态,删除path j中的最后一条路段,更新startpo int、node,并在tabu_node中对当前不可行路段进行标记
17) end if
18) end while
19) 对局部最优路径
20) 用改进PSO算法局部更新信息素τ
21) end for
22) 对全局最优路径pathgb进行更新
23) 对信息素τ进行全局更新
24) i=i+ 1
25) end while
本文所提 BAPM 算法中关键的几个部分为:原始图G转换成完全图
3.1 图模型转换
从景区地图中抽象获得的图G是一个非完全有向图,它存在以下2种特殊情况:1) 2个节点之间没有一条直接连接的路径,2) 直接连接路径的权值比间接路径的权值大。因此在处理图G之前,本文重新构建图模型,以便更好地计算出多点最短路径。
假设 N 为非完全连通图G=(V,A)中所有节点的个数,其中有n(n≤N-1)个节点为必经节点,从节点s出发,寻找一条经过这n个必经节点一次且仅一次,再返回起始节点s的最短路径。将起始点s 看作固定点,s∈V,必经点集为M ⊆V-{s}。本文通过以下步骤实现问题的转换。
步骤 1 生成新的顶点集合
步骤 2 生成新的边集合
步骤 3 计算图
很明显,通过以上3个步骤建立了一个完全图
图1
图2
引理 1 在 STSP 最佳解决方案中,任何一条有向边仅能遍历一次。
也就是说,在图
3.2 寻找可行路径
3.2.1 路径编码
将景区地图按照3.1节步骤1~步骤3进行转换后,问题转变为从转换后的图中给定的起始点s出发,需要找到一条经过所有必经点的可行路径。
由3.1节可知,
其中,
将路径patha中包含的所有不重复节点的集合记作node;使用禁忌表
3.2.2 可行路径的寻找与路段的选择
根据图2,初始化的权值矩阵
其中,
寻找一条可行路径的方法如下。蚂蚁a从起始点 startpo int=s 开始寻找路径,根据 tabu_node (startpo int)得到下一时刻的所有可选路段,选择其中一条路段
上述寻找可行路径的过程可简化表示为图3。
图3
在非完全有向图中,运用回溯方法查询路径可以避免产生非可行性路径,提高选择路径的效率。
Tabu_node 表中,确定可选路段是该算法中的一个重要环节。在第k次迭代中,蚂蚁a在寻找路径时,会根据 startpo int 对应的 tabu_node (startpo int)中每条路段的可行概率
选择路段的概率计算式如式(1)所示。
其中,
3.3 更新信息素
3.3.1 信息素的全局更新
根据上述寻路方法,可以得到所有蚂蚁的可行路径path,找出其中权值最小的路径,记作pathgb,并且记录每只蚂蚁的可行路径,记作pathlb。在迭代过程中,找出权值最小的路径并且将其权值与pathgb的权值进行比较,将pathgb替换成权值最小的路径,本文将pathgb称作全局最优路径,同理,将pathlb替换成每只蚂蚁寻找到的权值最小的路径,称作局部最优路径。
当所有蚂蚁均寻找到一条可行路径后,需要更新图中每个路段对应的信息素。信息素τij(t)描述了蚂蚁经过各个路段所留下的痕迹,本文将τij(t)值较大的路段称为优越路段,信息素更新如式(2)所示。
其中,参数ρ(0≤ρ≤1)为衰减因子,用于冲淡信息素的浓度;
其中,
为了避免信息素过快地陷入局部最优,设置最大信息素τmax和最小信息素τmin,如式(4)和式(5)所示,则信息素更新范围为τmin≤τij (t)≤τmax。
如果τij (t)≥τmax (t),则τij (t)=τmax (t)。
其中,city表示点集
3.3.2 信息素的局部更新
设置最大最小信息素后,随着迭代次数的增多,优越路段得不到有效的突出,使算法容易陷入局部最优,造成最终得到的最短路径与期望路径存在较大差距。本文结合改进后的PSO算法,突出路径中较优路段的信息素,以保证算法能产生更为接近最短路径的结果。
基本的 PSO 算法通常用于连续函数寻找最优解的问题,粒子从随机的初始位置出发,不断改变自身的速度和位置,每次迭代均飞向自身最优和全局最优位置的加权中心,以达到自我认知和信息共享的目的。本文建立了所讨论问题和PSO算法之间的映射关系,将问题空间映射到粒子空间,将问题离散化。
将每只蚂蚁a的可行路径patha看作一个粒子,将当前的信息素τ看作粒子的当前位置,将信息素的增量看作PSO算法中的速度变化量。
本文定义了 2 个变量——全局最优路径片段pgb和局部最优路径片段plb,用于计算粒子的运动速度。全局最优路径片段为蚂蚁当前找到的路径与全局最优路径中相同的路径片段集合,局部最优路径片段为蚂蚁当前找到的路径与其自身曾找到的最优路径中相同的路径片段集合。若蚂蚁a找到当前路径为patha,其计算式为
全局最优路径为
局部最优路径为
则全局最优路径片段为
pgb={pi|pi为边构成的位串,并且pi同时存在于patha和pathgb中}
局部最优路径片段为
plb={pi | pi为边构成的位串,并且 pi同时存在于patha和pathlb中}
假设蚂蚁a在本次迭代中寻找到的可行的路径为
在蚂蚁a寻找到可行路径patha后,得到pgb和plb,增加pgb、plb对应路段的信息素,信息素增长式如式(6)~式(9)所示。
其中,
在迭代过程中,不断地更新pathlb和pathgb,从而更新plb和pgb对应的信息素,使信息素不断地向有益于获取最优路径的方向增长,从而使算法能够更加快速有效地得到图中的最短路径。
4 实验结果与分析
4.1 TSPLIS数据库实验
为了验证 BAPM 算法有效地改进了局部最优问题并且能找到更为接近的最短路径,本文使用MMAS算法和GA算法作为对比算法,3种算法均在 MATLAB(R2014a)上进行实现,且迭代次数相同。BAPM算法的参数设置如表1所示。
表1 BAPM算法参数
名称 | 参数值 |
蚁群大小 | m=city |
起始信息素 | τ0=τmin |
信息素相关参数 | α= 1 |
启发因子相关参数 | β= 5 |
信息素削减因子 | ρ=0.98 |
用于τmin的参数 | pbest=0.005 |
参数ω | ω=0.000 1 |
分别运用BAPM算法、MMAS算法和GA算法对TSPLIS数据库中提供的14组数据进行实验,每种算法各运行10次,获取每组数据在不同算法中运行得到的最大路径长度、最小路径长度以及10组数据值与精确解之间的平均偏差百分比,如表2所示。
表2 TSPLIB数据库对比实验
数据 | 各算法间比较 | ||||||||||
BAPM算法 | MMAS算法 | GA算法 | |||||||||
平均偏差 | max | min | 平均偏差 | max | min | 平均偏差 | max | min | |||
ft17 | 0.0% | 39 | 39 | 0.0% | 39 | 39 | 0.0% | 39 | 39 | ||
ft53 | 1.9% | 7 344 | 6 905 | 3.2% | 7 344 | 6 905 | 4.1% | 7 372 | 6 095 | ||
ft70 | 1.0% | 39 102 | 38 673 | 2.9% | 40 109 | 38 673 | 3.3% | 40 109 | 38 673 | ||
ftv33 | 0.0% | 1 286 | 1 286 | 0.0% | 1 286 | 1 286 | 0.0% | 1 286 | 1 286 | ||
ftv35 | 0.0% | 1 473 | 1 473 | 0.02% | 1 477 | 1 473 | 0.0% | 1 473 | 1 473 | ||
ftv38 | 0.0% | 1 530 | 1 530 | 0.05% | 1 549 | 1 530 | 0.0% | 1 530 | 1 530 | ||
ftv44 | 0.0% | 1 613 | 1 613 | 0.01% | 1 615 | 1 613 | 0.0% | 1 613 | 1 613 | ||
ftv47 | 0.4% | 1 791 | 1 776 | 0.8% | 1 791 | 1 791 | 0.4% | 1 791 | 1 776 | ||
ftv55 | 0.1% | 1 613 | 1 608 | 1.0% | 1 643 | 1 608 | 0.7% | 1 631 | 1 608 | ||
ftv64 | 0.2% | 1 844 | 1 839 | 1.6% | 1 893 | 1 844 | 0.2% | 1 844 | 1 844 | ||
ftv70 | 1.9% | 2 078 | 1 950 | 7.5% | 2 114 | 1 950 | 6.2% | 2 078 | 2 078 | ||
kro124 | 3.4% | 37 693 | 37 287 | 3.5% | 37 739 | 37 287 | 4.2% | 37 804 | 37 739 | ||
p43 | 0.0% | 5 620 | 5 620 | 0.1% | 5 647 | 5 620 | 0.2% | 5 647 | 5 620 | ||
ry48p | 0.4% | 14 507 | 14 459 | 1.1% | 14 603 | 14 570 | 0.8% | 14 603 | 14 459 |
4.2 仿真实验
为验证BAPM算法的正确性,本文建立了一个仿真系统。该系统可随机构建不同的图。这些图都可以看作景区地图的抽象图结构,图中的顶点对应景区的景点,边则表示景点之间的路径。假设必经节点数量为 9,寻找图中从某一起始点出发经过这些点的最短路径,就对应为从景区的当前位置出发,规划一条包含9个游览景点的最短路径问题。第一种情况,随机构建一个包括100个随机生成的节点的图,任意两节点之间均有路径。在产生的路径中随机删除4 000条路径,将其转换为一个稀疏图,从而模拟景区路线网络的布局,然后在图中选择10个必经点(包含起点),如图4所示。第二种情况,随机产生 10 个点及其之间的路径,构成一个有向非完全图,随机选择一个起始点,寻找经过这10个点的最短路径,如图5所示。
图4
图5
以上2种情况下本文方法得到的结果与分支定界法找到的路径相同。
4.3 橘洲景区游览路线规划
橘洲景区是长沙的著名旅游景区,本文算法被应用于橘洲景区智能导览系统中。该系统中的橘洲地图是借助GPS设备、GOOGLE卫星地图等,通过实地打点,遍历景区道路并测量记录后自行建立的电子地图,橘洲景区景点的位置信息如表3所示。
以表3中标注*的6个景点为实验1必经景点,采用BAPM算法规划出的最佳路径为:枕江观光车售票处—沁园春诗词碑—毛泽东青年艺术雕像—望江亭—指点江山石碑—问天台,全程645 m,为最短游览路径。
以表3中标注#的10个景点为实验2必经景点,采用BAPM算法规划出的最佳路径为:地铁站西站口—原长沙海关旧址—婚庆园—橘子洲古董钢琴博物馆—沁园春·长沙橘洲 1925 —橘子洲人行入口—美孚洋行旧址—财神古殿—游客服务中心西站点—橘子洲西大门,全程1 218 m,为最短游览路径。
表3 橘子洲景区景点信息
景点序号 | 景点名称 | 经度 | 纬度 |
1 | 问天台* | 112.966 631° | 28.171 271° |
2 | 指点江山石碑* | 112.966 793° | 28.171 637° |
3 | 望江亭 * | 112.966 811° | 28.171 796° |
4 | 毛泽东青年艺术雕像* | 112.966 802° | 28.173 412° |
5 | 沁园春诗词碑* | 112.968 028° | 28.187 983° |
6 | 长株潭两型社会展览馆 | 112.966 938° | 28.178 382° |
7 | 竹园 | 112.967 779° | 28.179 878° |
8 | 朱张渡 | 112.966 456° | 28.180 764° |
9 | 唐生智公馆旧址站点 | 112.966 919° | 28.183 873° |
10 | 潇湘名人旧址 | 112.967 835° | 28.183 717° |
11 | 江神庙 | 112.969 802° | 28.204 733° |
12 | 桃园 | 112.967 844° | 28.184 935° |
13 | 桂园 | 112.968 208° | 28.186 169° |
14 | 桂园诗词碑 | 112.968 033° | 28.187 964° |
15 | 九州龙骧码 | 112.967 482° | 28.189 632° |
16 | 百米高喷 | 112.967 913° | 28.190 228° |
17 | 婚庆园# | 112.968 614° | 28.199 179° |
18 | 美孚洋行旧址# | 112.968 347° | 28.193 838° |
19 | 枕江亭观光车售票处*# | 112.968 865° | 28.196 559° |
20 | 财神古殿# | 112.967 534° | 28.196 197° |
22 | 橘子洲古董钢琴博物馆 | 112.968 69° | 28.196 961° |
23 | 橘子洲入口 | 112.969 148° | 28.197 757° |
24 | 橘子洲人行入口# | 112.968 542° | 28.197 793° |
25 | 橘子洲西大门# | 112.967 535° | 28.198 004° |
26 | 原长沙海关旧址# | 112.968 614° | 28.199 179° |
27 | 地铁站西站口# | 112.967 998° | 28.200 396° |
注:*表示实验1必经景点,#表示实验2必经景点。
实验1与实验2均找到了包含必经景点的最短游览路径。
4.4 实验总结
本文使用了3组实验,验证了提出的BAPM算法的有效性及优越性。在第一组实验中,选用了TSPLIB数据库中的TSP数据,将本文提出的BAPM 算法与 MMAS 算法及 GA 算法进行了比较,结果显示BAPM算法可以在数据量较大的条件下,找出更接近最小路径的结果。在第二组实验中,随机生成点和路径,模拟景区地图和景点,该组实验的必经点数设置较小(10 个必经点),验证了在点数较少的情况下,BAPM 算法可以有效地找到准确的最短路径。第三组实验对实际的景区景点进行规划,所有景点位置和景点间路径长度均为实测数据,验证了算法在景点路径规划中的有效性。
通过实验验证了BAPM算法的有效性。实验结果表明,BAPM算法可以处理非完全图问题和完全图问题,并且在必经点个数较小的情况下,可以准确并且快速地寻找到最短路径。
5 结束语
参考文献
综合导航网格模型及其在智慧旅游寻径中的应用
[J]. ,
Integrated navigation grid model and its applications in smart tourism routing
[J].
基于改进的 Dijkstra算法的旅游规划线路研究与实践
[J]. ,
Research and practice of tourism planning line based on improved Dijkstra algorithm
[J].
一种改进蚁群算法研究和旅游景区路径规划问题求解
[J]. ,
Improved ant colony algorithm for path planning of tourist scenic are
[J].
基于地理坐标和轨迹数据的路径推荐方法
[J]. ,
Path recommendation based on geographic coordinates and trajectory data
[J].
A new optimizer using particle swarm theory
[C]//
Compact formulations of the Steiner traveling salesman problem and related problems
[J]. ,
A branch-and-cut algorithm for the capacitated profitable tour problem
[J]. ,
Lower bounding procedure for the asymmetric quadratic traveling salesman problem
[J]. ,
基于改进粒子群算法的移动机器人多目标点路径规划
[J]. ,
Mobile robot multi-goal path planning using improved particle swarm optimization
[J].
/
〈 | 〉 |