基于回溯蚁群-粒子群混合算法的多点路径规划

doi:10.11959/j.issn.1000-436x.2019039

通信学报 ›› 2019, Vol. 40 ›› Issue (2): 102-110.doi: 10.11959/j.issn.1000-436x.2019039

基于回溯蚁群-粒子群混合算法的多点路径规划

刘丽珏,罗舒宁,高琰,陈美妃

中南大学信息科学与工程学院，湖南长沙 410083

修回日期:2018-10-23 出版日期:2019-02-01 发布日期:2019-03-04
作者简介:刘丽珏（1973- ），女，湖南长沙人，博士，中南大学副教授，主要研究方向为智能计算、人工智能、机器学习。|罗舒宁（1993- ），女，山东泰安人，中南大学硕士生，主要研究方向为多点路径规划。|高琰（1973- ），女，湖南长沙人，博士，中南大学副教授，主要研究方向为智能信息处理。|陈美妃（1998- ），女，广西壮族自治区，主要研究方向为大数据、云计算。
基金资助:
国家科技重大专项基金资助项目(2013FY110800);长沙计划科技基金资助项目(kq1606004)

Multi-point path planning based on the algorithm of colony-particle swarm optimization

Lijue LIU,Shuning LUO,Yan GAO,Meifei CHEN

School of Information Science and Engineering,Central South University,Changsha 410083,China

Revised:2018-10-23 Online:2019-02-01 Published:2019-03-04
Supported by:
National Science and Technology Major Project(2013FY110800);Planned Science and Technology Project of Changsha(kq1606004)

摘要/Abstract

摘要：

景区多点路径规划问题是一个NP-hard问题，相当于寻找经过起始点和特定节点的最短路径。针对多点路径规划问题，提出了回溯蚁群-粒子群混合算法，该算法运用弗洛伊德（Floyd-Warshall）算法将图进行转换并且结合了蚁群算法和粒子群算法寻找最短路径。实验结果表明，此算法可以在小规模数据下快速找到精确解，同时，在较大规模数据量下，可以得到比最大最小蚁群算法和遗传算法更好的结果。

关键词: NP-hard问题, 最大最小蚁群系统, 弗洛伊德算法, 粒子群算法

Abstract:

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.

Key words: NP-hard problem, max-min ant system, Floyd-Warshall, particle swarm algorithm

中图分类号:

TP399

刘丽珏,罗舒宁,高琰,陈美妃. 基于回溯蚁群-粒子群混合算法的多点路径规划[J]. 通信学报, 2019, 40(2): 102-110.

Lijue LIU,Shuning LUO,Yan GAO,Meifei CHEN. Multi-point path planning based on the algorithm of colony-particle swarm optimization[J]. Journal on Communications, 2019, 40(2): 102-110.

图/表 8

图1

图2

图3

表1

表2

图4

图5

表3

参考文献 12

[1]	朱庆, 王烨萍, 张骏骁 ,等. 综合导航网格模型及其在智慧旅游寻径中的应用[J]. 西南交通大学学报, 2017,52(1): 195-201.
	ZHU Q , WANG Y P , ZHANG J X ,et al. Integrated navigation grid model and its applications in smart tourism routing[J]. Journal of Southwest Jiaotong University, 2017,52(1): 195-201.
[2]	吕琼艺 . 基于改进的 Dijkstra算法的旅游规划线路研究与实践[J]. 柳州职业技术学院学报, 2017,17(2): 32-36.
	LV Q Y . Research and practice of tourism planning line based on improved Dijkstra algorithm[J]. Journal of Liuzhou Vocational ＆Technical College, 2017,17(2): 32-36.
[3]	胡军国, 祁亨年, 董峰 ,等. 一种改进蚁群算法研究和旅游景区路径规划问题求解[J]. 计算机应用研究, 2011,28(5): 1647-1650.
	HU J G , QI H N , DONG F ,et al. Improved ant colony algorithm for path planning of tourist scenic are[J]. Application Research of Computers, 2011,28(5): 1647-1650.
[4]	蒋仲安, 王明, 陈雅 . 基于地理坐标和轨迹数据的路径推荐方法[J]. 通信学报, 2017,38(5): 165-171.
	JIANG Z A , WANG M , CHEN Y . Path recommendation based on geographic coordinates and trajectory data[J]. Journal on Communications, 2017,38(5): 165-171.
[5]	STüTZLE T , HOOS H H . Max-min ant system[J]. Future Generation Computer Systems, 2000,16(08): 889-914
[6]	EBERHART R C , KENNEDY J . A new optimizer using particle swarm theory[C]// The 6th International Symposium on Micro Machine And Human Science, 1995: 39-43.
[7]	FLOYD R W . Algorithm 97:shortest path[J]. Communications of the ACM, 1962,5(6):345.
[8]	LETCHFORD A N , NASIRI S D , THEIS D O . Compact formulations of the Steiner traveling salesman problem and related problems[J]. European Journal of Operational Research, 2013,228(01): 83-92
[9]	JEPSEN M K , PETERSEN B , SPOORENDONK S . A branch-and-cut algorithm for the capacitated profitable tour problem[J]. Discrete Optimization, 2014,14(C): 78-96.
[10]	ROSTAMI B , MALUCELLI F , BELOTTI P . Lower bounding procedure for the asymmetric quadratic traveling salesman problem[J]. European Journal of Operational Research, 2016,253(03): 584-592
[11]	普兴成, 李俊杰, 吴慧超 ,等. 基于改进粒子群算法的移动机器人多目标点路径规划[J]. 智能系统学报, 2017,12(3): 301-309.
	PU X C , LI J J , WU H C ,et al. Mobile robot multi-goal path planning using improved particle swarm optimization[J]. CAAI Transactions on Intelligent Systems, 2017,12(3): 301-309.
[12]	郑继明, 杨坤, 柳慧鹏 ,等. 基于0-1线性规划的多点路由规划模型研究[J]. 通信技术, 2017,50(7): 1443-1446.
	ZHENG J M , YANG K , LIU H P ,et al. Multicast routing model based on 0-1 linear programming[J]. Communications Technology, 2017,50(07): 1443-1446.

名称	参数值
蚁群大小	m=city
起始信息素	τ₀=τ_min
信息素相关参数	α= 1
启发因子相关参数	β= 5
信息素削减因子	ρ=0.98
用于τ_min的参数	p_best=0.005
参数ω	ω=0.000 1

数据	各算法间比较
	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

景点序号	景点名称	经度	纬度
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°

基于回溯蚁群-粒子群混合算法的多点路径规划

Multi-point path planning based on the algorithm of colony-particle swarm optimization

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 12

相关文章 12

Metrics

推荐阅读 0

[1]	戴翠琴,唐煌,郭林峰. 卫星网络中基于双向寻优粒子群优化算法的连接计划设计[J]. 通信学报, 2019, 40(8): 189-199.
[2]	王汝言,杨衍,吴大鹏. QoE感知的FiWi视频分发机制[J]. 通信学报, 2018, 39(1): 1-13.
[3]	金鑫,李龙威,季佳男,李祉歧,胡宇,赵永彬. 基于大数据和优化神经网络短期电力负荷预测[J]. 通信学报, 2016, 37(Z1): 36-42.
[4]	刘勤让,戴启华,沈剑良,赵博. 基于动态自适应离散粒子群算法的3D NoC低功耗映射方法[J]. 通信学报, 2016, 37(11): 23-30.
[5]	王娟，李飞，张路桥. PSO应用于QoS偏好感知的云存储任务调度[J]. 通信学报, 2014, 35(3): 27-238.
[6]	王娟,李飞,张路桥. PSO应用于QoS偏好感知的云存储任务调度[J]. 通信学报, 2014, 35(3): 231-238.
[7]	朱喜华1，李颖晖1，李宁1，范炳奎2. 基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J]. 通信学报, 2014, 35(2): 22-189.
[8]	朱喜华,李颖晖,李宁,范炳奎. 基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J]. 通信学报, 2014, 35(2): 182-189.
[9]	夏纯中1,2，宋顺林1. 基于商空间的层次式数据网格资源调度算法[J]. 通信学报, 2013, 34(6): 18-155.
[10]	夏纯中,宋顺林. 基于商空间的层次式数据网格资源调度算法[J]. 通信学报, 2013, 34(6): 146-155.
[11]	张春发,赵晓晖. 基于公平度门限的多用户OFDM系统自适应资源分配算法[J]. 通信学报, 2011, 32(12): 65-71.
[12]	黄肖玲,杨华龙. 大约束度卷积码快速译码方法的研究[J]. 通信学报, 2010, 31(3): 57-64.