基于改进的启发式蚂蚁算法求解最短路径
|
摘要
针对复杂环境中机器人路径规划问题,为了提高蚁群算法的寻优能力和收敛速度,基于A~*算法的距离评价函数,对算法中的启发式函数进行改进,提出一种启发式的蚂蚁算法,并对新算法进行仿真测试.结果表明:改进后的启发函数可以有效改善蚂蚁算法搜索的盲目性,解决了传统蚁群算法收敛速度慢、易陷入局部最优解的问题.与传统蚂蚁算法相比,启发式蚂蚁算法在20×20网格下的相关系数提高了0.4722,40×40网格下的相关系数提高了0.226 5,说明改进算法的规划能力和收敛效率均有所提高,整体上优于传统蚂蚁算法.
In order to improve the optimization ability and convergence speed of the algorithm,a heuristic ant algorithm was proposed according to improve the heuristic function in the algorithm based on the distance evaluation function of A~* algorithm for the problem of the robot path planning in the complex environment,and the simulation experiment was taken to prove the effect. The results show that the new heuristic function can improve the blindness of the traditional ant algorithm,and solve the problems such as the slow convergence rate and algorithm easily falling into the local optimal solution. The correla-tion coefficient of the heuristic ant algorithm in 20 × 20 grid is increased 0.472 2 higher than the traditional algorithm,and the correlation coefficient in 40 × 40 grid is increased 0.226 5 higher than the traditional one. The results illustrate that the planning ability and the convergence rate of the new heuristic ant algorithm is better than that of the traditional ant algorithm,and excel than that of traditional ant algorithm in general.
In order to improve the optimization ability and convergence speed of the algorithm,a heuristic ant algorithm was proposed according to improve the heuristic function in the algorithm based on the distance evaluation function of A~* algorithm for the problem of the robot path planning in the complex environment,and the simulation experiment was taken to prove the effect. The results show that the new heuristic function can improve the blindness of the traditional ant algorithm,and solve the problems such as the slow convergence rate and algorithm easily falling into the local optimal solution. The correla-tion coefficient of the heuristic ant algorithm in 20 × 20 grid is increased 0.472 2 higher than the traditional algorithm,and the correlation coefficient in 40 × 40 grid is increased 0.226 5 higher than the traditional one. The results illustrate that the planning ability and the convergence rate of the new heuristic ant algorithm is better than that of the traditional ant algorithm,and excel than that of traditional ant algorithm in general.
引文
[1]刘雄,雷勇,涂国强.基于蚁群算法的移动机器人路径规划[J].计算机仿真,2011,28(11):185-188.LIU X,LEI Y,TU G Q.Path planning of mobile robot based on ant colony algorithm[J].Computer Simulation,2011,28(11):185-188(in Chinese).
[2]郭玉,李士勇.基于改进蚁群算法的机器人路径规划[J].计算机测量与控制,2009,17(1):187-189.GUO Y,LI S Y.Robot path planning based on improved ant colony algorithm[J].Computer Measurement and Control,2009,17(1):187-189(in Chinese).
[3]万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18):63-66.WAN X F,HU W,FANG W Y,et al.Robot path planning based on improved ant colony algorithm[J].Computer Engineering and Applications,2014,50(18):63-66(in Chinese).
[4]肖本贤,齐东流,刘海霞,等.动态环境中基于模糊神经网络的AGV路径规划[J].系统仿真学报,2006,18(9):2401-2404.XIAO B X,QI D L,LIU H X,et al.AGV path planning based on fuzzy neural network in dynamic environment[J].Journal of System Simulation,2006,18(9):2401-2404(in Chinese).
[5]徐庆征,柯熙政.求解最短路径的遗传算法中若干问题的讨论[J].计算机工程与设计,2008(6):1507-509.XU Q Z,KE X Z.Discussion on several problems in genetic algorithm for solving the shortest path[J].Computer Engineering and Design,2008(6):1507-509(in Chinese).
[6]曹鲁寅,罗斌,钦明浩.用遗传算法求解最短路径问题[J].合肥工业大学学报:自然科学版,1996(3):112-116.CAO L Y,LUO B,QIN M H.Genetic algorithm for solving shortest path problem[J].Journal of Hefei University of Technology:Natural Science,1996(3):112-116(in Chinese).
[7]王玥,张志强,曹晓文.A*改进算法及其在航迹规划中的应用[J].信息系统工程,2014(1):89-90.WANG Y,ZHANG Z Q,CAO X W.A*algorithm and its application in track planning[J].China CIO News,2014(1):89-90(in Chinese).
[8]DORIGO M,MANIEZZO V,COLORNI A.Ant system:Optimization by a colony of cooperating agents[J].Systems Man&Cybernetics Society,1996,26(1):29-41.
[9]周之平,华路.复杂环境路径规划的改进蚁群算法[J].计算机工程与设计,2011,32(5):1773-1776.ZHOU Z P,HUA L.An improved ant colony algorithm for path planning in complex environment[J].Computer Engineering and Design,2011,32(5):1773-1776(in Chinese).
[10]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.DUAN H B.Ant colony algorithm principle and its application[M].Beijing:Science Press,2005(in Chinese).
[11]HO S L,YANG S Y,NI G Z,et al.A modified ant colony optimization algorithm modeled on tabu-search methods[J].Magnetics,2005,42(4):1195-1198.
[12]ELLABIB I,CALAMAI P,BASIR O.Exchange strategies for multiple ant colony system original research article[J].Information Sciences,2007,177(5):1248-1264.
[13]NAIMI H M,TAHERINEJAD N.New robust and efficient ant colony algorithms:Using new interpretation of local up dating process[J].Expert Systems with Applications,2009(36):481-488.
[14]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.LIU C G,YAN X H,LIU C Y.Dynamic path planning method for mobile robot based on improved ant colony algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224(in Chinese).
[2]郭玉,李士勇.基于改进蚁群算法的机器人路径规划[J].计算机测量与控制,2009,17(1):187-189.GUO Y,LI S Y.Robot path planning based on improved ant colony algorithm[J].Computer Measurement and Control,2009,17(1):187-189(in Chinese).
[3]万晓凤,胡伟,方武义,等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用,2014,50(18):63-66.WAN X F,HU W,FANG W Y,et al.Robot path planning based on improved ant colony algorithm[J].Computer Engineering and Applications,2014,50(18):63-66(in Chinese).
[4]肖本贤,齐东流,刘海霞,等.动态环境中基于模糊神经网络的AGV路径规划[J].系统仿真学报,2006,18(9):2401-2404.XIAO B X,QI D L,LIU H X,et al.AGV path planning based on fuzzy neural network in dynamic environment[J].Journal of System Simulation,2006,18(9):2401-2404(in Chinese).
[5]徐庆征,柯熙政.求解最短路径的遗传算法中若干问题的讨论[J].计算机工程与设计,2008(6):1507-509.XU Q Z,KE X Z.Discussion on several problems in genetic algorithm for solving the shortest path[J].Computer Engineering and Design,2008(6):1507-509(in Chinese).
[6]曹鲁寅,罗斌,钦明浩.用遗传算法求解最短路径问题[J].合肥工业大学学报:自然科学版,1996(3):112-116.CAO L Y,LUO B,QIN M H.Genetic algorithm for solving shortest path problem[J].Journal of Hefei University of Technology:Natural Science,1996(3):112-116(in Chinese).
[7]王玥,张志强,曹晓文.A*改进算法及其在航迹规划中的应用[J].信息系统工程,2014(1):89-90.WANG Y,ZHANG Z Q,CAO X W.A*algorithm and its application in track planning[J].China CIO News,2014(1):89-90(in Chinese).
[8]DORIGO M,MANIEZZO V,COLORNI A.Ant system:Optimization by a colony of cooperating agents[J].Systems Man&Cybernetics Society,1996,26(1):29-41.
[9]周之平,华路.复杂环境路径规划的改进蚁群算法[J].计算机工程与设计,2011,32(5):1773-1776.ZHOU Z P,HUA L.An improved ant colony algorithm for path planning in complex environment[J].Computer Engineering and Design,2011,32(5):1773-1776(in Chinese).
[10]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.DUAN H B.Ant colony algorithm principle and its application[M].Beijing:Science Press,2005(in Chinese).
[11]HO S L,YANG S Y,NI G Z,et al.A modified ant colony optimization algorithm modeled on tabu-search methods[J].Magnetics,2005,42(4):1195-1198.
[12]ELLABIB I,CALAMAI P,BASIR O.Exchange strategies for multiple ant colony system original research article[J].Information Sciences,2007,177(5):1248-1264.
[13]NAIMI H M,TAHERINEJAD N.New robust and efficient ant colony algorithms:Using new interpretation of local up dating process[J].Expert Systems with Applications,2009(36):481-488.
[14]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.LIU C G,YAN X H,LIU C Y.Dynamic path planning method for mobile robot based on improved ant colony algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224(in Chinese).