摘要
针对蚁群算法在求解最短路径问题时收敛速度慢,容易陷入局部最优解的问题,提出基于启发式机制的改进蚁群算法.在蚁群系统(ant colony system,ACS)算法基础上通过候选节点到目标点的距离动态调整启发函数,提高收敛速度;算法陷入局部最优时,引入惩罚函数,使当前最优路径上的信息素快速下降而降低蚂蚁下一次搜索正反馈的影响,避免算法陷入局部最优.仿真实验表明,在复杂环境中,包括终点处存在凹形障碍物时,该算法在解的质量和收敛速度上都显示出了良好的性能.
Considering that the traditional ant colony algorithm converges slowly when solving the shortest path problem and easily falls into the local optimal solution, we propose an improved ant colony algorithm based on a heuristic mechanism. On the basis of the ant colony system (ACS) algorithm, the heuristic function is dynamically adjusted according to the distance between the candidate node and the target point to improve the convergence speed. When the algorithm falls into a local optimum, a penalty function is introduced so that the pheromone on the current optimal path decreases rapidly, and the effect of the positive feedback reduces at the ant's next search to prevent the algorithm from falling into a local optimum. Simulation experiments show that in a complex environment, including concave obstacles at the end point, the algorithm exhibits good performance in both the quality and convergence speed of the solution.
作者
朱艳
游晓明
刘升
ZHU Yan;YOU Xiaoming;LIU Sheng(College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China;School of Management, Shanghai University of Engineering Science, Shanghai 201620, China)
出处
《信息与控制》
CSCD
北大核心
2019年第3期265-268,269-271,共7页
Information and Control
基金
国家自然科学基金资助项目(61673258)
关键词
蚁群算法
启发式机制
蚁群系统(ACS)算法
惩罚函数
ant colony algorithm
heuristic mechanism
ACS (ant colony system) algorithm
penaltyfunction
