动态混沌蚁群系统及其在机器人路径规划中的应用

doi:10.11772/j.issn.1001-9081.2017061326

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 126-131.DOI: 10.11772/j.issn.1001-9081.2017061326

动态混沌蚁群系统及其在机器人路径规划中的应用

李娟¹, 游晓明¹, 刘升², 陈佳¹

1. 上海工程技术大学电子电气工程学院, 上海 201600;
2. 上海工程技术大学管理学院, 上海 201600

收稿日期:2017-05-31 修回日期:2017-08-31 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 游晓明
作者简介:李娟(1991-),女,安徽六安人,硕士研究生,主要研究方向:嵌入式控制系统、智能算法、机器人系统;游晓明(1963-),女,江苏兴华人,教授,博士,主要研究方向:智能信息处理、模式识别、人工智能、分布式并行智能处理;刘升(1966-),男,湖北大冶人,教授,博士,主要研究方向:智能信息处理;陈佳(1993-),女,江苏南京人,硕士研究生,主要研究方向:嵌入式控制系统、智能算法、机器人系统。
基金资助:
国家自然科学基金资助项目（61673258，61075115，61403249，61603242）。

Dynamic chaotic ant colony system and its application in robot path planning

LI Juan¹, YOU Xiaoming¹, LIU Sheng², CHEN Jia¹

1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201600, China;
2. School of Management, Shanghai University of Engineering Science, Shanghai 201600, China

Received:2017-05-31 Revised:2017-08-31 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61673258, 61075115, 61403249, 61603242).

摘要/Abstract

摘要： 针对蚁群系统（ACS）解决机器人路径规划问题时种群多样性与收敛速度的不足，对蚁群系统引入动态混沌算子，从而平衡种群多样性和收敛速度之间的关系。动态混沌蚁群系统的核心是在传统蚁群系统引入Logistic混沌算子来增加种群多样性，从而提高解的质量。在迭代前期加入混沌算子，以调整路径中的全局信息素值，增加算法的种群多样性，从而避免算法陷入局域优化解；在后期则转为蚁群系统，来确保动态混沌蚁群系统的收敛速度。仿真结果表明，对于机器人路径规划问题，与蚁群系统相比，动态混沌蚁群系统具有更好的种群多样性、更高的解的质量和更快的收敛速度；与精英蚁群系统（EAS）和基于排序的蚂蚁系统（ASrank）相比，动态混沌蚁群系统能够平衡解的质量与收敛速度之间的关系，即使在复杂障碍物的环境下，动态混沌蚁群系统也能较好地找到最优解。动态混沌蚁群系统能够提升移动机器人路径规划中的效率。

关键词: 蚁群系统, 混沌映射, 动态混沌算子, 路径规划, 精英蚁群系统, 基于排序的蚂蚁系统

Abstract: To solve problems of population diversity and convergence speed when an Ant Colony System (ACS) is used to robot path planning, a dynamic chaos operator was introduced in the ACS. The dynamic chaotic ACS can balance population diversity and convergence speed. The core of dynamic chaotic ACS is that a Logistic chaotic operator was added to the traditional ACS to increase population diversity and improve the quality of the solutions. First, the chaotic operator was added to the pre-iteration to adjust the global pheromone value in the path to increase the population diversity of the algorithm, so as to avoid the algorithm to fall into the local optimal solution. Then, in the later stage, the ACS was used to ensure convergence speed of the dynamic chaotic ACS. The experimental results show that the dynamic chaotic ACS has better population diversity compared with the ACS for the robot path planning problem. The solution quality is higher and the convergence speed is faster. Compared with the Elitist Ant colony System (EAS) and the rank-based Ant System (ASrank), the dynamic chaotic ACS can balance the relationship between the quality of the solutions and the convergence speed. The dynamic chaotic ACS can find better optimal solutions even in the complex obstacle environment. The dynamic chaotic ACS can improve the efficiency of mobile robot path planning.

Key words: Ant Colony System (ACS), chaotic map, dynamic chaos operator, path planning, Elitist Ant System (EAS), rank-based Ant System (ASrank)

中图分类号:

TP18
TP242

李娟, 游晓明, 刘升, 陈佳. 动态混沌蚁群系统及其在机器人路径规划中的应用[J]. 计算机应用, 2018, 38(1): 126-131.

LI Juan, YOU Xiaoming, LIU Sheng, CHEN Jia. Dynamic chaotic ant colony system and its application in robot path planning[J]. Journal of Computer Applications, 2018, 38(1): 126-131.

参考文献

[1] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.(ZHU D Q, YAN M Z. Summary of mobile robot path planning technology[J]. Control and Decision, 2010, 25(7):961-967.)
[2] 许亚.基于改进的人工势能场的移动机器人路径规划研究[J].科技展望,2016,26(33):77-78.(XU Y. Research on mobile robot path planning based on improved artificial potential field[J]. Science and Technology, 2016, 26(33):77-78.)
[3] DORIGO M, MANIEZZO V, COLORNI A. The ant system:optimization by a colony of cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1):1-13.
[4] 夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27-36.(XIA X Y, ZHOU Y R. Theoretical research progress of ant colony optimization algorithm[J]. Journal of Intelligent Systems, 2016, 11(1):27-36.)
[5] 李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004:112-126.(LI S Y. Ant Colony Algorithm and Its Application[M]. Harbin:Harbin Institute of Technology Press, 2004:112-126.)
[6] THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool[J]. International Journal of Production Economics, 2014, 149(3):131-144.
[7] GHUMMAN N S, KAUR R. Dynamic combination of improved max-min and ant colony algorithm for load balancing in cloud system[C]//Proceedings of the 6th International Conference on Computing, Communication and Networking Technologies. Piscataway, NJ:IEEE, 2015:1-5.
[8] BOUSSAID I, LEPAGNOT J, SIARRY P. A survey on optimization metaheuristics[J]. Information Science,2013, 237(19):82-117.
[9] GANDOMI A H, YANG X-S. Chaotic bat algorithm[J]. Journal of Computational Science, 2014, 5(2):224-232.
[10] JAVIDI M, HOSSEINPOURFARD R. Chaos genetic algorithm instead genetic algorithm[J]. The International Arab Journal of Information Technology, 2015, 12(2):163-168.
[11] WANG Y. Application of chaos ant colony algorithm in Web service composition based on QoS[J]. International Forum on Information Technology and Applications, 2009, 172(2):25-227.
[12] TAO W Q, YANG G, ZHANG J Y. Fault section locating for distribution network with DG based on improved ant colony algorithm[C]//Proceedings of the 2016 Power Electronics and Motion Control Conference. Piscataway, NJ:IEEE, 2016:1985-1989.
[13] PRAKASAM A, SAVARIMUTHU N. Metaheuristic algorithms and probabilistic behaviour:a comprehensive analysis of ant colony optimization and its variants[J]. Artificial Intelligence Review, 2016, 45(1):97-130.
[14] BULLNHEIMER B, HARTL R F, STRAUB C. A new rank based version of ant system-a computational study[J]. Central European Journal of Operations Research, 1999, 7(1):25-38.
[15] LORENZ N. Deterministic non periodic flow[J]. AMS Journal, 1963, 20(2):130-141.
[16] WANG Y, YAO M.A new hybrid genetic algorithm based on chaos and PSO[C]//Proceedings of the 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway, NJ:IEEE, 2009:699-703.
[17] SHAHRZAD S, SEYEDALI M, ANDREW L. Biogeography-based optimisation with chaos[J]. Neural Computing and Applications, 2014, 25(5):1077-1097.

动态混沌蚁群系统及其在机器人路径规划中的应用

Dynamic chaotic ant colony system and its application in robot path planning

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[3]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[4]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[5]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[6]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[7]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[8]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[9]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[10]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[11]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[12]	刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.
[13]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.
[14]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.
[15]	袁蒙恩, 陈立家, 冯子凯. 基于单目视觉的多种群粒子群机械臂路径规划算法[J]. 计算机应用, 2020, 40(10): 2863-2871.