基于滑动窗口和蚁群优化算法的二次路径规划算法

doi:10.11772/j.issn.1001-9081.2015.01.0172

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 172-178.DOI: 10.11772/j.issn.1001-9081.2015.01.0172

基于滑动窗口和蚁群优化算法的二次路径规划算法

赖智铭^1,2, 郭躬德^1,2

1. 福建师范大学数学与计算机科学学院, 福州350007;
2. 福建师范大学网络安全与密码技术福建省重点实验室, 福州350007

收稿日期:2014-08-11 修回日期:2014-09-17 出版日期:2015-01-01 发布日期:2015-01-26
通讯作者: 郭躬德
作者简介:赖智铭(1988-),男,福建龙岩人,硕士研究生,主要研究方向:人工智能、数据挖掘;郭躬德(1965-),男,福建龙岩人,教授,博士生导师,主要研究方向:人工智能、数据挖掘.
基金资助:
国家自然科学基金资助项目(61070062, 61175123);福建高校产学合作科技重大项目(2010H6007).

Quadratic path planning algorithm based on sliding window and ant colony optimization algorithm

LAI Zhiming^1,2, GUO Gongde^1,2

1. College of Mathematics and Computer Science, Fujian Normal University, Fuzhou Fujian 350007, China;
2. Fujian Key Laboratory of Network Security and Cryptography, Fujian Normal University, Fuzhou Fujian 350007, China

Received:2014-08-11 Revised:2014-09-17 Online:2015-01-01 Published:2015-01-26

摘要/Abstract

摘要：

针对蚁群优化(ACO)算法在复杂环境下规划能力较弱的问题,提出了一种基于滑动窗口和蚁群优化算法的二次路径规划(QACO)算法.对回退蚁群优化(ACOFS)算法的回退策略进行改进,通过降低回退路径上的信息素量,减少回退次数.第一次规划中,使用改进后的ACO算法对栅格环境进行全局路径规划;第二次规划中,滑动窗口沿着全局路径滑动,通过ACO算法规划出滑动窗口中的局部路径,并使用局部路径对全局路径进行优化,直至滑动窗口中包含目标位置.仿真实验表明:相比ACO、ACOFS算法,QACO算法的平均规划时间分别下降了26.21%、52.03%,平均路径长度下降了47.82%、42.28%,因此在复杂环境下QACO算法具有将强的路径规划能力.

关键词: 滑动窗口, 蚁群优化算法, 二次路径规划, 栅格法

Abstract:

A Quadratic path planning algorithm based on sliding window and Ant Colony Optimization (QACO) algorithm was put forward on the issue of weak planning ability of Ant Colony Optimization (ACO) algorithm in complex environments. The feedback strategy of the ACO based on Feedback Strategy (ACOFS) algorithm was improved, and the feedback times were reduced through the decrease of pheromone along feedback path. In the first path planning, the improved ACO algorithm was applied to make a global path planning for the grid environment. In the second path planning, the sliding windows slid along the global path. Local path in sliding windows was planned with ACO algorithm. Then the global path could be optimized by local path until target location was contained in the sliding window. The simulation experiments show that, the average planning time of QACO algorithm respectively reduces by 26.21%, 52.03% and the average length of path reduces by 47.82%, 42.28% compared with the ACO and QACO algorithms. So the QACO algorithm has a relatively strong path planning ability in complex environments.

Key words: sliding window, Ant Colony Optimization (ACO) algorithm, quadratic path planning, grid method

中图分类号:

TP242.6
TP18

赖智铭, 郭躬德. 基于滑动窗口和蚁群优化算法的二次路径规划算法[J]. 计算机应用, 2015, 35(1): 172-178.

LAI Zhiming, GUO Gongde. Quadratic path planning algorithm based on sliding window and ant colony optimization algorithm[J]. Journal of Computer Applications, 2015, 35(1): 172-178.

参考文献

[1] DORIGO M, BIRATTARI M. Ant colony optimization [M]// Encyclopedia of Machine Learning. Berlin: Springer, 2010: 36-39.
[2] FORSATI R, MOAYEDIKIA A, JENSEN R, et al. Enriched ant colony optimization and its application in feature selection [J]. Neurocomputing, 2014, 142: 354-371.
[3] ZHANG F, LIU M, ZHOU Z, et al. Quantum ant colony algorithm-based emergency evacuation path choice algorithm [C]// CSCWD 2013: Proceedings of the 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design. Piscataway: IEEE, 2013: 576-580.
[4] GEORGE A, RAJAKUMAR B R. Fuzzy aided ant colony optimization algorithm to solve optimization problem [C]// ISI'12: Proceedings of the International Symposium on Intelligent Informatics. Berlin: Springer, 2013: 207-215.
[5] BUNIYAMIN N, SARIFF N, WAN N, et al. Robot global path planning overview and a variation of ant colony system algorithm [J]. International Journal of Mathematics and Computers in Simulation, 2011, 5(1): 9-16.
[6] LEE J-W, LEE J-J. Novel ant colony optimization algorithm with path crossover and heterogeneous ants for path planning [C]// ICIT 2010: Proceedings of the 2010 IEEE International Conference on Industrial Technology. Piscataway: IEEE, 2010: 559-564.
[7] WANG P, TANG G, LI Y, et al. Ant colony algorithm using endpoint approximation for robot path planning [C]// CCC 2012: Proceedings of the 2012 31st Chinese Control Conference. Piscataway: IEEE, 2012: 4960-4965.
[8] ZHANG Y, CAO Y, HAN Z. Path planning of vehicle based on improved ant colony algorithm [C]// ICMIC 2012: Proceedings of the 2012 International Conference on Modelling, Identification & Control. Piscataway: IEEE, 2012: 797-801.
[9] OLEIWI B K, ROTH H, KAZEM B I. A hybrid approach based on ACO and GA for multi objective mobile robot path planning [J]. Applied Mechanics and Materials, 2014, 527: 203-212.
[10] HAMZHEEI M, FARAHANI R Z, RASHIDI-BAJGAN H. An ant colony-based algorithm for finding the shortest bidirectional path for automated guided vehicles in a block layout [J]. The International Journal of Advanced Manufacturing Technology, 2013, 64(1/2/3/4): 399-409.
[11] KHAN S, BAIG A R, SHAHZAD W. A novel ant colony optimiza-tion based single path hierarchical classification algorithm for predicting gene ontology [J]. Applied Soft Computing, 2014, 16: 34-49.
[12] ZHANG X, WU Z. Optimization planning based on improved ant colony algorithm for robot [J]. Journal of Networks, 2014, 9(6): 1542-1549.
[13] ZHANG J, FAN X, DENG Z. Improved urban transport optimal path based on ant colony algorithm [J]. Applied Mechanics and Materials, 2014, 433: 1366-1369.

[1]	景兴红, 孙国栋, 何世彪, 廖勇. 基于滑窗滤波和多项式拟合的时变信道估计方法[J]. 计算机应用, 2021, 41(9): 2699-2704.
[2]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[3]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[4]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[5]	汪虹余, 张彧, 杨恒, 穆楠. 基于蚁群优化算法的弱光图像显著性目标检测[J]. 计算机应用, 2021, 41(10): 2970-2978.
[6]	熊勇, 张加, 余嘉俊, 张本任, 梁萱卓, 朱奇舸. 船舶三维管路智能布局优化算法[J]. 计算机应用, 2020, 40(7): 2164-2170.
[7]	仇媛, 常相茂, 仇倩, 彭程, 苏善婷. 基于长短期记忆网络和滑动窗口的流数据异常检测方法[J]. 计算机应用, 2020, 40(5): 1335-1339.
[8]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[9]	杨世强, 罗晓宇, 乔丹, 柳培蕾, 李德信. 基于滑动窗口和动态规划的连续动作分割与识别[J]. 计算机应用, 2019, 39(2): 348-353.
[10]	王庆荣, 王瑞峰. 基于改进粒子群算法的配电网重构策略[J]. 计算机应用, 2018, 38(9): 2720-2724.
[11]	陈暄, 徐见炜, 龙丹. 基于蚁群优化蛙跳算法的云计算资源调度算法[J]. 计算机应用, 2018, 38(6): 1670-1674.
[12]	刘张虎, 程春玲. 面向大规模数据主题建模的方差减小的随机变分推理算法[J]. 计算机应用, 2018, 38(6): 1675-1681.
[13]	韩明, 刘教民, 吴朔媚, 王敬涛. 粒子群优化的移动机器人路径规划算法[J]. 计算机应用, 2017, 37(8): 2258-2263.
[14]	王鑫, 刘方爱. 改进的多数据流协同频繁项集挖掘算法[J]. 计算机应用, 2016, 36(7): 1988-1992.
[15]	段峰峰, 王永滨, 杨丽芳, 潘淑静. 基于主成分分析方向深度梯度直方图的立体视觉深度图特征提取[J]. 计算机应用, 2016, 36(1): 222-226.

基于滑动窗口和蚁群优化算法的二次路径规划算法

Quadratic path planning algorithm based on sliding window and ant colony optimization algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics