当前位置>主页 > 期刊在线 > 计算机技术 >

计算机技术2020年22期

基于Bi-A* 的ACO 算法的最快路径推荐
郑永玲,白宇,杨楠,蒋顺英
(贵州民族大学 数据科学与信息工程学院,贵州 贵阳 550025)

摘  要:文章针对ACO 算法收敛速度慢和容易陷入局部最优等问题,利用Bi-A* 算法的代价估计函数优化ACO 算法的启发式函数,增强算法全局搜索能力;再通过引入每次循环得出的最快路径优化ACO 算法的信息素更新规则,加快算法收敛速度;基于Spark 结合真实的大规模出租车轨迹数据,将Bi-A*-ACO 算法应用于最快路径推荐,实验结果表明,Bi-A*-ACO 算法比传统ACO 算法更具有有效性和准确性。


关键词:Bi-A*;ACO 算法;载客路线;信息素;Spark



中图分类号:TP301.6;TP18         文献标识码:A         文章编号:2096-4706(2020)22-0074-08


The Fastest Path Recommendation of ACO Algorithm Based on Bi-A*

ZHENG Yongling,BAI Yu,YANG Nan,JIANG Shunying

(School of Data Science and Information Engineering,Guizhou Minzu University,Guiyang 550025,China)

Abstract:Aiming at the problems of slow convergence of the ACO algorithm and easy to fall into local optimality,the article uses the cost estimation function of the Bi-A* algorithm to optimize the heuristic function of the ACO algorithm to enhance the algorithm’s global search ability;and then optimize the pheromone update rule of the ACO algorithm by introducing the fastest path obtained in each cycle to speed up the algorithm convergence speed;based on Spark combined with real large-scale taxi trajectory data,the Bi-A*-ACO algorithm is applied to the fastest route recommendation. The experimental results show that the Bi-A*-ACO algorithm is more effective and accurate than the traditional ACO algorithm.

Keywords:Bi-A*;ACO algorithm;passenger route;pheromone;Spark


参考文献:

[1] 王迎,赵建军,李兴菊,等. 基于交通大数据的车辆行驶路径规划综述 [J]. 软件导刊,2020,19(10):50-54.

[2] 汤红杰,王鼎,皇攀凌,等. 优化Dijkstra 算法在工厂内物流AGV 路径规划的研究 [J]. 机械设计与制造,2018(S1):117-120.

[3] 邹益民,高阳,高碧悦. 一种基于Dijkstra 算法的机器人避障问题路径规划 [J]. 数学的实践与认识,2013,43(10):111-118.

[4] 程林,王美玲,张毅. 一种基于SuperMap GIS 的改进Dijkstra 算法 [J]. 地球信息科学学报,2010,12(5):649-654.

[5] 李大东,孙秀霞,彭建亮,等. 基于可视图法的改进Dijkstra 算法 [J]. 电光与控制,2010,17(3):40-43.

[6] 朱永强,孙宗涛. 改进蚁群算法在物流机器人路径规划中的应用 [J]. 科学技术与工程,2020,20(30):12467-12471.

[7] 衣麟卓. 海上搜救最优路线规划模型设计与仿真 [J]. 舰船科学技术,2020,42(16):34-36.

[8] 陈建宏,黄晓明. 复杂环境下特种车辆应急机动路径规划研究 [J]. 计算机仿真,2020,37(7):159-162.

[9] 陈敏,李笑,武交峰,等. 基于距离度量学习的智能车辆路径规划 [J]. 计算机仿真,2020,37(7):163-167.

[10] 王磊,孙力帆. 引入必经点约束的路径规划算法研究 [J].计算机工程与应用,2020,56(21):25-29.

[11] 张丹红,陈文文,张华军,等.A* 算法与蚁群算法相结合的无人艇巡逻路径规划 [J]. 华中科技大学学报(自然科学版),2020,48(6):13-18.

[12] 张丽杰,刘建昌,谭树彬. 复杂建筑火灾中的人员疏散路径多目标规划 [J]. 东北大学学报(自然科学版),2020,41(6):761-766.

[13] 王宇,王文浩,徐凡,等. 基于改进蚁群算法的植保无人机路径规划方法 [J]. 农业机械学报,2020,51(11):103-112+92.

[14] 李嘉伟,张激,赵俊才,等. 一种SRIO 网络负载均衡最短路径路由算法 [J]. 计算机工程,2020,46(3):214-221+228.

[15] 王杰,杨坤,孙峰,等. 一种基于GIS 的公交线路规划方法 [J]. 广西大学学报(自然科学版),2019,44(5):1269-1275.


[16] 袁佳泉,李胜,吴益飞,等. 基于模拟退火蚁群算法的机器人路径规划方法 [J]. 计算机仿真,2019,36(10):329-333.

[17] 刘建仁. 考虑交通拥堵的城市物流配送路径规划研究 [J].现代电子技术,2020,43(23):116-119+123.

[18] 张强,陈兵奎,刘小雍,等. 基于改进势场蚁群算法的移动机器人最优路径规划 [J]. 农业机械学报,2019,50(5):23-32+42.

[19] 杜玉红,张岩,赵焕峰. 基于参数优化蚁群算法的机器人路径规划研究 [J]. 现代制造工程,2020(9):7-14.

[20] 李宪强,马戎,张伸,等. 蚁群算法的改进设计及在航迹规划中的应用 [J]. 航空学报,2020,41(S2):213-219.

[21] 胡春阳,姜平,周根荣. 改进蚁群算法在AGV 路径规划中的应用 [J]. 计算机工程与应用,2020,56(8):270-278.

[22] 徐炜,周兰凤,章民融. 三维地形下基于Hopfield 神经网络的路径规划算法 [J]. 计算机应用与软件,2019,36(10):113-116+144.

[23] 孙艺彬,杨慧珍. 基于定向约束的脉冲耦合神经网络路径规划 [J]. 计算机科学,2019,46(S2):28-32.

[24] 陈志军,曾蒸. 基于模糊神经网络和遗传算法的机器人三维路径规划 [J]. 重庆师范大学学报(自然科学版),2018,35(1):93-99.

[25] 金飞虎,郭琦. 基于蚁群算法的Hopfield 神经网络在多空间站路径规划的应用研究 [J]. 计算机应用研究,2010,27(1):51-53.

[26] 卫玉梁,靳伍银. 基于神经网络Q-learning 算法的智能车路径规划 [J] 火力与指挥控制,2019,44(2):46-49.

[27] 张军,詹志辉. 计算智能 [M]. 北京:清华大学出版社,2009.


作者简介:

郑永玲(1995—),女,汉族,贵州毕节人,硕士研究生,研究方向:海量数据统计与分析;

白宇(1994—),女,汉族,贵州仁怀人,硕士研究生,研究方向:海量数据统计与分析;

杨楠(1997—),女,汉族,贵州盘县人,硕研究生,研究方向:海量数据统计与分析;

蒋顺英(1996—),女,汉族,贵州兴义人,硕士研究生,研究方向:海量数据统计与分析。