计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (12): 2820-2831.DOI: 10.3778/j.issn.1673-9418.2107086
收稿日期:
2021-07-22
修回日期:
2021-09-29
出版日期:
2022-12-01
发布日期:
2021-10-18
通讯作者:
+E-mail: lifan.sun@gmail.com作者简介:
张松灿(1973—),男,河南郑州人,博士研究生,主要研究方向为群智能算法、移动机器人智能控制。基金资助:
ZHANG Songcan1,2, SUN Lifan1,+(), SI Yanna1, PU Jiexin1
Received:
2021-07-22
Revised:
2021-09-29
Online:
2022-12-01
Published:
2021-10-18
About author:
ZHANG Songcan, born in 1973, Ph.D. candidate. His research interests include swarm intelligence algorithms and intelligent control of mobile robot.Supported by:
摘要:
针对多种群蚁群算法存在结构复杂、优化速度慢及适应性不足等问题,提出一种单种群自适应异构蚁群算法,并用于机器人路径规划。该算法采用单种群结构,避免多蚁群算法结构复杂的问题;种群内每只蚂蚁都有自己的控制参数,实现蚂蚁的行为异构,增加种群的多样性;在首次迭代时,仅用启发因子构建候选解,提高了初始化种群的质量;根据蚁群优化过程中种群信息熵的变化,自适应确定信息交换周期;所设计的信息交换策略将最优蚂蚁的控制参数传递给最差蚂蚁,增强最优蚂蚁的引导作用;参数突变操作有助于在更大的参数空间探索更优的控制参数,提高算法逃离局部最优的能力。仿真实验与统计检验的结果验证了所提算法的有效性、稳定性和优越性。
中图分类号:
张松灿, 孙力帆, 司彦娜, 普杰信. 单种群自适应异构蚁群算法的机器人路径规划[J]. 计算机科学与探索, 2022, 16(12): 2820-2831.
ZHANG Songcan, SUN Lifan, SI Yanna, PU Jiexin. Single-Colony Adaptive Heterogeneous Ant Colony Algorithm for Mobile Robot Path Planning[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(12): 2820-2831.
算法 | |||||
---|---|---|---|---|---|
MMAS | 1.1 | 7 | 0.200 | — | — |
ACS | 1.1 | 7 | 0.200 | 0.2 | 0.8 |
CACS | 1.0 | 4 | 0.100 | 0.3 | 0.8 |
PS-ACO | 1.0 | 2 | 0.015 | — | — |
AHACO | 1.1 | 7 | 0.200 | — | — |
表1 算法参数设置
Table 1 Parameter setting of algorithms
算法 | |||||
---|---|---|---|---|---|
MMAS | 1.1 | 7 | 0.200 | — | — |
ACS | 1.1 | 7 | 0.200 | 0.2 | 0.8 |
CACS | 1.0 | 4 | 0.100 | 0.3 | 0.8 |
PS-ACO | 1.0 | 2 | 0.015 | — | — |
AHACO | 1.1 | 7 | 0.200 | — | — |
信息交换周期 | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|
2 | 45.698 5 | 45.891 8 | 0.356 4 | 25.13 | 76.67 |
4 | 45.698 5 | 45.891 8 | 0.356 4 | 24.97 | 76.67 |
6 | 45.698 5 | 45.891 8 | 0.356 4 | 27.03 | 76.60 |
8 | 45.698 5 | 45.891 8 | 0.356 4 | 25.50 | 76.67 |
10 | 45.698 5 | 45.891 8 | 0.356 4 | 25.90 | 76.67 |
12 | 45.698 5 | 45.891 8 | 0.356 4 | 25.17 | 76.67 |
Adaptive | 45.698 5 | 45.792 8 | 0.248 6 | 37.03 | 86.67 |
表2 map1环境不同信息交换周期的实验统计结果
Table 2 Statistical results of different periods for information exchange in map1
信息交换周期 | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|
2 | 45.698 5 | 45.891 8 | 0.356 4 | 25.13 | 76.67 |
4 | 45.698 5 | 45.891 8 | 0.356 4 | 24.97 | 76.67 |
6 | 45.698 5 | 45.891 8 | 0.356 4 | 27.03 | 76.60 |
8 | 45.698 5 | 45.891 8 | 0.356 4 | 25.50 | 76.67 |
10 | 45.698 5 | 45.891 8 | 0.356 4 | 25.90 | 76.67 |
12 | 45.698 5 | 45.891 8 | 0.356 4 | 25.17 | 76.67 |
Adaptive | 45.698 5 | 45.792 8 | 0.248 6 | 37.03 | 86.67 |
信息交换周期 | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|
2 | 73.982 8 | 74.671 7 | 0.592 2 | 53.63 | 33.33 |
4 | 73.982 8 | 74.605 1 | 0.550 7 | 54.57 | 36.67 |
6 | 73.982 8 | 74.605 1 | 0.550 7 | 54.03 | 36.67 |
8 | 73.982 8 | 74.605 1 | 0.550 7 | 52.73 | 36.67 |
10 | 73.982 8 | 74.605 1 | 0.550 7 | 54.00 | 36.67 |
12 | 73.982 8 | 74.605 1 | 0.550 7 | 57.70 | 36.67 |
Adaptive | 73.982 8 | 74.384 1 | 0.468 8 | 51.43 | 53.33 |
表3 map2环境不同信息交换周期的实验统计结果
Table 3 Statistical results of different periods for information exchange in map2
信息交换周期 | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|
2 | 73.982 8 | 74.671 7 | 0.592 2 | 53.63 | 33.33 |
4 | 73.982 8 | 74.605 1 | 0.550 7 | 54.57 | 36.67 |
6 | 73.982 8 | 74.605 1 | 0.550 7 | 54.03 | 36.67 |
8 | 73.982 8 | 74.605 1 | 0.550 7 | 52.73 | 36.67 |
10 | 73.982 8 | 74.605 1 | 0.550 7 | 54.00 | 36.67 |
12 | 73.982 8 | 74.605 1 | 0.550 7 | 57.70 | 36.67 |
Adaptive | 73.982 8 | 74.384 1 | 0.468 8 | 51.43 | 53.33 |
Environment | Algorithm | best | mean | std | fbest | rate/% | Environment | Algorithm | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
map3 | MMAS | 29.799 0 | 29.909 4 | 0.286 4 | 14.97 | 86.67 | map5 | MMAS | 92.526 9 | 95.153 4 | 2.267 4 | 35.93 | 10.00 |
ACS | 29.799 0 | 29.799 0 | 0 | 32.57 | 100.00 | ACS | 91.698 5 | 93.848 2 | 1.094 4 | 117.10 | 3.33 | ||
CACS | 29.799 0 | 29.951 8 | 0.296 9 | 38.10 | 76.67 | CACS | 95.598 0 | 99.154 4 | 1.731 9 | 70.17 | 3.33 | ||
PS-ACO | 30.627 4 | 32.694 9 | 1.689 1 | 16.53 | 10.00 | PS-ACO | 95.840 6 | 100.912 0 | 3.260 0 | 40.00 | 3.33 | ||
AHACO | 29.799 0 | 29.799 0 | 0 | 19.20 | 100.00 | AHACO | 90.041 6 | 92.268 9 | 0.910 3 | 79.93 | 6.67 | ||
map4 | MMAS | 58.083 3 | 58.102 8 | 0.106 9 | 44.30 | 96.67 | map6 | MMAS | 90.468 0 | 92.562 0 | 0.813 7 | 37.10 | 3.33 |
ACS | 58.083 3 | 58.083 3 | 0 | 16.40 | 100.00 | ACS | 90.124 9 | 91.820 0 | 0.848 7 | 74.63 | 3.33 | ||
CACS | 58.083 3 | 59.841 4 | 0.855 9 | 61.33 | 6.67 | CACS | 94.953 3 | 97.408 5 | 1.261 2 | 22.00 | 6.67 | ||
PS-ACO | 59.497 4 | 63.837 5 | 2.038 0 | 19.00 | 3.33 | PS-ACO | 93.781 7 | 99.417 4 | 3.162 2 | 90.66 | 3.33 | ||
AHACO | 58.083 3 | 58.259 0 | 0.273 0 | 44.13 | 70.00 | AHACO | 89.296 5 | 91.213 9 | 0.824 2 | 66.00 | 3.33 |
表4 不同环境下路径规划统计结果
Table 4 Statistical results of path planning under different grid maps
Environment | Algorithm | best | mean | std | fbest | rate/% | Environment | Algorithm | best | mean | std | fbest | rate/% |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
map3 | MMAS | 29.799 0 | 29.909 4 | 0.286 4 | 14.97 | 86.67 | map5 | MMAS | 92.526 9 | 95.153 4 | 2.267 4 | 35.93 | 10.00 |
ACS | 29.799 0 | 29.799 0 | 0 | 32.57 | 100.00 | ACS | 91.698 5 | 93.848 2 | 1.094 4 | 117.10 | 3.33 | ||
CACS | 29.799 0 | 29.951 8 | 0.296 9 | 38.10 | 76.67 | CACS | 95.598 0 | 99.154 4 | 1.731 9 | 70.17 | 3.33 | ||
PS-ACO | 30.627 4 | 32.694 9 | 1.689 1 | 16.53 | 10.00 | PS-ACO | 95.840 6 | 100.912 0 | 3.260 0 | 40.00 | 3.33 | ||
AHACO | 29.799 0 | 29.799 0 | 0 | 19.20 | 100.00 | AHACO | 90.041 6 | 92.268 9 | 0.910 3 | 79.93 | 6.67 | ||
map4 | MMAS | 58.083 3 | 58.102 8 | 0.106 9 | 44.30 | 96.67 | map6 | MMAS | 90.468 0 | 92.562 0 | 0.813 7 | 37.10 | 3.33 |
ACS | 58.083 3 | 58.083 3 | 0 | 16.40 | 100.00 | ACS | 90.124 9 | 91.820 0 | 0.848 7 | 74.63 | 3.33 | ||
CACS | 58.083 3 | 59.841 4 | 0.855 9 | 61.33 | 6.67 | CACS | 94.953 3 | 97.408 5 | 1.261 2 | 22.00 | 6.67 | ||
PS-ACO | 59.497 4 | 63.837 5 | 2.038 0 | 19.00 | 3.33 | PS-ACO | 93.781 7 | 99.417 4 | 3.162 2 | 90.66 | 3.33 | ||
AHACO | 58.083 3 | 58.259 0 | 0.273 0 | 44.13 | 70.00 | AHACO | 89.296 5 | 91.213 9 | 0.824 2 | 66.00 | 3.33 |
地图 | AHACO vs. MMAS | AHACO vs. ACS | AHACO vs. CACS | AHACO vs. PS-ACO |
---|---|---|---|---|
map3 | 4.55E-02 + | 1.00E+00 = | 1.39E-02 + | 1.57E-06 + |
map4 | 1.14E-02 + | 2.70E-03 + | 1.17E-05 + | 1.17E-05 + |
map5 | 6.60E-06 + | 3.55E-05 + | 1.73E-06 + | 1.73E-06 + |
map6 | 3.43E-05 + | 3.05E-02 + | 1.73E-06 + | 1.73E-06 + |
+/=/- | 4/0/0 | 3/1/0 | 4/0/0 | 4/0/0 |
表5 Wilcoxon符号秩检验结果
Table 5 Results of Wilcoxon sign rank test
地图 | AHACO vs. MMAS | AHACO vs. ACS | AHACO vs. CACS | AHACO vs. PS-ACO |
---|---|---|---|---|
map3 | 4.55E-02 + | 1.00E+00 = | 1.39E-02 + | 1.57E-06 + |
map4 | 1.14E-02 + | 2.70E-03 + | 1.17E-05 + | 1.17E-05 + |
map5 | 6.60E-06 + | 3.55E-05 + | 1.73E-06 + | 1.73E-06 + |
map6 | 3.43E-05 + | 3.05E-02 + | 1.73E-06 + | 1.73E-06 + |
+/=/- | 4/0/0 | 3/1/0 | 4/0/0 | 4/0/0 |
AHACO | MMAS | ACS | CACS | PS-ACO | |
---|---|---|---|---|---|
0.006 | 1.625 | 2.750 | 1.625 | 4.000 | 5.000 |
表6 Friedman检验结果
Table 6 Results of Friedman test
AHACO | MMAS | ACS | CACS | PS-ACO | |
---|---|---|---|---|---|
0.006 | 1.625 | 2.750 | 1.625 | 4.000 | 5.000 |
[1] |
PEYER S, RAUTENBACH D, VYGEN J. A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing[J]. Journal of Discrete Algorithms, 2009, 7(4): 377-390.
DOI URL |
[2] | GURUJI A K, AGARWAL H, PARSEDIYA D. Time-efficient A* algorithm for robot path planning[J]. Procedia Tech-nology, 2016, 23: 144-149. |
[3] | 黄鲁, 周非同. 基于路径优化D* Lite算法的移动机器人路径规划[J]. 控制与决策, 2020, 35(4): 877-884. |
HUANG L, ZHOU F T. Path planning of moving robot based on path optimization of D* Lite algorithm[J]. Control and Decision, 2020, 35(4): 877-884. | |
[4] | SINGH M K, PARHI D R. Path optimisation of a mobile robot using an artificial neural network controller[J]. Inter-national Journal of Systems Science, 2011, 42(1): 107-120. |
[5] | KARAMI A H, HASANZADEH M. An adaptive genetic algorithm for robot motion planning in 2D complex environ-ments[J]. Computers & Electrical Engineering, 2015, 43: 317-329. |
[6] |
LEE H Y, SHIN H, CHAE J. Path planning for mobile agents using a genetic algorithm with a direction guided factor[J]. Electronics, 2018, 7(10): 212.
DOI URL |
[7] |
PRADHAN S K, PARHI D R, PANDA A K. Fuzzy logic tech-niques for navigation of several mobile robots[J]. Applied Soft Computing, 2009, 9(1): 290-304.
DOI URL |
[8] |
LI G, CHOU W. Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences, 2018, 61(5): 052204.
DOI URL |
[9] | 王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781. |
WANG X Y, YANG L, ZHANG Y, et al. Robot path plan-ning based on improved ant colony algorithm with poten-tial field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781. | |
[10] |
朱佳莹, 高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
DOI |
ZHU J Y, GAO M T. AUV path planning based on particle swarm optimization and improved ant colony optimization[J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
DOI |
|
[11] | 陈雄, 袁杨. 一种机器人路径规划的蚁群算法[J]. 系统工程与电子技术, 2008, 30(5): 952-955. |
CHEN X, YUAN Y. Novel ant colony optimization algori-thm for robot path planning[J]. Journal of Systems Enginee-ring and Electronics, 2008, 30(5): 952-955. | |
[12] |
BAI J, YANG G K, CHEN Y W, et al. A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J]. Applied Soft Computing, 2013, 13(3): 1365-1375.
DOI URL |
[13] |
LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. International Journal of Control, Automation and Systems, 2017, 15(4): 1754-1769.
DOI URL |
[14] |
SREEJA N, SANKAR A. A hierarchical heterogeneous ant colony optimization based approach for efficient action rule mining[J]. Swarm and Evolutionary Computation, 2016, 29: 1-12.
DOI URL |
[15] |
张德惠, 游晓明, 刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891.
DOI URL |
ZHANG D H, YOU X M, LIU S. Dynamic grouping ant colony algorithm combined with cat swarm optimization[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 880-891.
DOI URL |
|
[16] |
ZHANG D, YOU X, LIU S, et al. Dynamic multi-role adap-tive collaborative ant colony optimization for robot path planning[J]. IEEE Access, 2020, 8: 129958-129974.
DOI URL |
[17] |
GÜLCÜ Ş, MAHI M, BAYKAN Ö K. et al. A parallel coope-rative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem[J]. Soft Computing, 2018, 22(5): 1669-1685.
DOI URL |
[18] | 万正宜, 彭玉旭. 求解旅行商问题的改进型量子蚁群算法[J]. 计算机工程与应用, 2016, 52(22): 59-63. |
WAN Z Y, PENG Y X. Improved quantum ant colony algo-rithm for traveling salesman problem[J]. Computer Enginee-ring and Applications, 2016, 52(22): 59-63. | |
[19] |
MAHI M, BAYKAN Ö K, KODAZ H. A new hybrid met-hod based on particle swarm optimization, ant colony opti-mization and 3-opt algorithms for traveling salesman pro-blem[J]. Applied Soft Computing, 2015, 30: 484-490.
DOI URL |
[20] |
STÜTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.
DOI URL |
[21] |
张松灿, 普杰信, 司彦娜, 等. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
DOI |
ZHANG S C, PU J X, SI Y N, et al. Adaptive improved ant colony algorithm based on population similarity and its appli-cation[J]. Computer Engineering and Applications, 2021, 57(8): 70-77. | |
[22] | 刘广瑞, 刘军, 孔令云. 移动机器人路径规划蚁群算法及其收敛性分析[J]. 郑州大学学报(工学版), 2012, 33(2): 24-27. |
LIU G R, LIU J, KONG L Y. Ant colony algorithm of path planning for robot and its convergence analysis[J]. Journal of Zhengzhou University (Engineering Science), 2012, 33(2): 24-27. | |
[23] |
SHUANG B, CHEN J, LI Z. Study on hybrid PS-ACO algo-rithm[J]. Applied Intelligence, 2011, 34(1): 64-73.
DOI URL |
[24] |
DERRAC J, GARCÍA S, MOLINA D, et al. A practical tuto-rial on the use of nonparametric statistical tests as a metho-dology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
DOI URL |
[1] | 张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7): 1516-1528. |
[2] | 赵家波, 游晓明, 刘升. 结合价格波动策略与动态回溯机制的蚁群算法[J]. 计算机科学与探索, 2022, 16(6): 1390-1404. |
[3] | 陈达, 游晓明, 刘升. 引入特征迁移和匹配学习的双蚁型蚁群算法[J]. 计算机科学与探索, 2022, 16(12): 2797-2808. |
[4] | 莫亚东, 游晓明, 刘升. 融合奖惩学习策略的动态分级蚁群算法[J]. 计算机科学与探索, 2021, 15(9): 1703-1716. |
[5] | 曹凯, 陈阳泉, 高嵩, 高佳佳. 涡流人工势场引导下的RRT*移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(4): 723-732. |
[6] | 孟静雯,游晓明,刘升. 结合协同机制与动态调控策略的双蚁群算法[J]. 计算机科学与探索, 2021, 15(11): 2206-2221. |
[7] | 张庆,刘旭,彭力,朱凤增. 融合JPS和改进A*算法的移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(11): 2233-2240. |
[8] | 殷绍伟, 彭力, 戴菲菲. 融合改进A*蚁群和滚动窗口法的平滑路径规划[J]. 计算机科学与探索, 2021, 15(10): 1969-1979. |
[9] | 潘晗,游晓明,刘升. 考虑动态导向与邻域交互的双蚁型算法[J]. 计算机科学与探索, 2020, 14(6): 1005-1016. |
[10] | 张德惠,游晓明,刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891. |
[11] | 冯志雨,游晓明,刘升. 分层递进的改进聚类蚁群算法解决TSP问题[J]. 计算机科学与探索, 2019, 13(8): 1280-1294. |
[12] | 刘新宇,谭力铭,杨春曦,翟持. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857. |
[13] | 郭羽含,胡芳霞. 考虑匹配可行性的长期合乘问题建模与求解[J]. 计算机科学与探索, 2019, 13(11): 1894-1910. |
[14] | 朱宏伟,游晓明,刘升. 协同过滤策略的异构双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(10): 1754-1767. |
[15] | 任珂欣,王兴伟,马连博,黄敏. 蚁群分工启发的ICN负载均衡机制[J]. 计算机科学与探索, 2018, 12(7): 1109-1116. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||