文章检索

复杂系统与复杂性科学 >

2024 , Vol. 21 >Issue 3: 93 - 99

DOI: https://doi.org/10.13306/j.1672-3813.2024.03.013

研究论文

基于改进蚁群算法的复杂环境路径规划

  • 杨俊起 ,
  • 刘飞洋 ,
  • 张宏伟 ,
  • 杨俊起 ,
  • 刘飞洋 ,
  • 张宏伟
展开
  • 河南理工大学 a.电气工程与自动化学院; b.河南省煤矿装备智能检测与控制重点实验室,河南 焦作 454003
杨俊起(1979-),男,河南濮阳人,博士,教授,主要研究方向为智能学习控制、逻辑动态系统、状态估计与故障诊断等。

收稿日期: 2022-12-07

  修回日期: 2023-01-27

  网络出版日期: 2024-11-07

基金资助

国家自然科学基金(61973105);河南省高校基本科研业务费专项基金(NSFRF180335)

收起

Complex Environment Path Planning Based on an Improved Ant Colony Algorithm

  • YANG Junqi ,
  • LIU Feiyang ,
  • ZHANG Hongwei ,
  • YANG Junqi ,
  • LIU Feiyang ,
  • ZHANG Hongwei
Expand
  • School of Electrical Engineering and Automation, Henan Key Laboratory of Intelligent Detection and Control of Coal Mine Equipment, Henan Polytechnic University, Jiaozuo 454003, China

Received date: 2022-12-07

  Revised date: 2023-01-27

  Online published: 2024-11-07

Fold

摘要

针对蚁群算法在复杂环境下难以收敛、最优值差的问题,提出了一种改进蚁群算法。引入修正策略,提出两种局部修正方法以减少无效路径。提出一种自适应信息素更新机制,将初始信息素与蚂蚁所释放的信息素区分挥发;针对每次迭代蚂蚁所释放的信息素,通过设计时变挥发因子的变化律单独挥发,得到自适应挥发强度的信息素挥发机制。最后,将算法应用到不同复杂环境,与已有改进蚁群算法对比分析,研究结果说明改进算法在有效时间、平均距离、最短距离的优越性。

关键词： 蚁群算法; 改进蚁群算法; 全局优化; 路径规划

本文引用格式

杨俊起 , 刘飞洋 , 张宏伟 , 杨俊起 , 刘飞洋 , 张宏伟 . 基于改进蚁群算法的复杂环境路径规划[J]. 复杂系统与复杂性科学, 2024 , 21(3) : 93 -99 . DOI: 10.13306/j.1672-3813.2024.03.013

Abstract

This paper proposes an improved ant colony algorithm to solve the problem of slow and poor convergence. First, a correction strategy is introduced, which includes two local correction methods to reduce invalid paths. Second, an adaptive pheromone updating mechanism is developed to distinguish and volatilize the initial pheromone from the pheromone released. For the pheromone released in each iteration, a change law of time-varying volatilization factor is designed to volatilize independently and obtain pheromone volatilization mechanism with adaptive volatilization intensity. Finally, the proposed algorithm is applied to mobile robot path planning. Compared with the existing improved ant colony algorithms, the results show that the improved algorithm is excellent in terms of effective time, average distance and shortest distance.

Key words： ant colony algorithm; improved ant colony algorithm; global optimization; path planning

参考文献

[1] DORIGO M, MANIEZZO V, COLORNI A. Positive feedback as a search strategy[J]. Technical Report, 1991, 1(1):91-016.
[2] WANG Y H, GAO D M, WANG X D. Shortest path planning based on improved ant colony algorithm[J]. ASP Transactions on Computes, 2021, 1(3):6-11.
[3] AKKA K, KHABER F. Mobile robot path planning using an improved ant colony optimization[J]. International Journal of Advanced Robotic Systems, 2018, 15(3):1-7.
[4] BULLNHEIMER B, HARTL R F, STRAUSS C. An improved ant system algorithm for the vehicle routing problem[J], Annals of Operations Research, 1999, 89:319-328.
[5] CARO D. Antnet: distributed stigmergetic control for communications networks[J]. Journal of Artificial Intelligent Research, 1999, 9(1): 317-365.
[6] HOU W B, XIONG Z H, WANG C S, et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning[J]. Robotics and Autonomous Systems, 2022,148: 103949.
[7] LU L C, YUE T W. Mission-oriented ant-team ACO for min-max MTSP[J]. Applied Soft Computing, 2018, 76:436-444.
[8] MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021,156:107230.
[9] XUE T, LIU L, LIU S, et al. Path planning of mobile robot based on improved ant colony algorithm for logistics[J]. Mathematical Biosciences and Engineering, 2021, 18(4): 3034-3045.
[10] 孔珊,仲昭林,张纪会.多路径选择变速双目标物流配送路径规划[J].复杂系统与复杂性科学, 2022, 19(1):74-80.
KONG S, ZHONG Z L, ZHANG J H. Bi-objective vehicle routing problems with path choice and variable speed[J]. Complex System and Complexity Science, 2022, 19(1):74-80.
[11] 江明,王飞,葛愿,等.基于改进蚁群算法的移动机器人路径规划研究[J].仪器仪表学报, 2019, 40(2): 113-121.
JIANG M, WANG F, GE Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40(2): 113-121.
[12] 王晓燕,杨乐,张宇,等. 基于改进势场蚁群算法的机器人路径规划[J].控制与决策, 2018, 33(10): 1775-1781.
WANG X Y, YANG L, ZHANG Y, et al, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781.
[13] 徐兴,钱誉钦,赵芸,等.基于改进蚁群算法的立体仓库三维空间路径优化[J].计算机集成制造系统, 2021, 27(1): 207-214.
XU X, QIAN Y Q, ZHAO Y, et al.3D spatial path optimization of stereo warehouse based on improved ant colony algorithm[J].Computer Integrated Manufacturing Systems, 2021, 27(1): 207-214.
[14] 徐小斐,陈婧,饶运清,等.迁移蚁群强化学习算法及其在矩形排样中的应用[J].计算机集成制造系统, 2020, 26(12): 3236-3247.
XU X F, CHEN J, RAO Y Q, et al. Transfer ants reinforcement learning algorithm and its application on rectangular packing problem[J]. Computer Integrated Manufacturing Systems, 2021, 36(7): 1581-1591.
[15] 徐菱,付文浩,江文辉,等.基于16方向24邻域改进蚁群算法的移动机器人路径规划[J].控制与决策, 2021, 36(5): 1137-1146.
XU L, FU W H, JIANG W H, et al. Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm[J]. Control and Decision, 2021, 36(5): 1137-1146.
[16] DEBORA D C, ALI E, HAMIDREZA A, et al. A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights[J]. Alexandria Engineering Journal, 2022, 61: 3403-3415.
[17] 张恒,何丽,袁亮,等.基于改进双层蚁群算法的移动机器人路径规划[J].控制与决策, 2022, 37(2): 303-313.
ZHANG H, HE L, YUAN L, et al. Mobile robot path planning using improved double-layer ant colony algorithm[J]. Control and Decision, 2022, 37(2): 303-313.
[18] 张玮,马焱,赵捍东,等.基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J].控制与决策, 2019, 34(2): 335-343.
ZHANG W, MA Y, ZHAO H D, et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J]. Control and Decision, 2019, 34(2): 335-343.
[19] 邓丽娟,张纪会.混合蚁群算法求解双目标时间窗VRP[J].复杂系统与复杂性科学,2020,17(4):73-84.
DENG L J, ZHANG J H. A hybrid ant colony optimization for bi-objective VRP with time windows[J]. Complex System and Complexity Science, 2020, 17(4): 73-84.
[20] HOU W B, XIONG Z H, WANG C S, et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning[J]. Robotics and Autonomous Systems, 2022, 148:103949.
Options
文章导航

/

〈 〉

版权所有 © 2017 《复杂系统与复杂性科学》编辑部
地址：青岛市宁夏路308号 青岛大学《复杂系统与复杂性科学》编辑部　邮编：266071
　 电话：0532-85953597   E-mail:fzkxbjb@qdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发