基于信息素负反馈的超启发式蚁群优化算法
|
摘要
针对蚁群算法应用于自动导引小车路径规划收敛速度慢、极易陷入局部最优的缺点,提出一种基于信息素负反馈的超启发式蚁群优化(ACONhh)算法。该算法充分利用历史搜索信息和持续获得错误经验,较快引导蚁群探索最优路径;分层化选择可行节点,加快算法初期收敛速度;设置挥发因子呈类抛物线变化以及调整信息素更新机制,改善路径全局的随机搜索特性。通过严格的数学方式证明了ACONhh算法具有收敛性。仿真和实验结果表明,该算法的收敛速度以及全局搜索性能显著优于目前流行的ACO、ACOhh和ACOihh算法。
The existing ant colony algorithm is applied to the path planning of automated guided vehicle, which is slow in the convergence and easily fails into the local optimum. To solve these problems, this paper proposes a Hyper Heuristic Ant Colony Optimization algorithm based on pheromone negative feedback(ACONhh)for path planning of mobile robots.The algorithm makes full use of historical search information and continues to gain error experience, thus further leads ant colony to explore optimal path. Hierarchical selection of feasible nodes is adopted to accelerate the initial convergence rate of the algorithm. Meanwhile, the volatility factor changes constantly with an analogous parabola, and pheromone update mechanism is adjusted to improve the randomness of global search. The convergence of ACONhh algorithm is strictly proved. Simulation and experimental results show that the convergence speed and global search performance of the proposed algorithm are outperform those of popular ACO, ACOhh and ACOihh algorithms.
The existing ant colony algorithm is applied to the path planning of automated guided vehicle, which is slow in the convergence and easily fails into the local optimum. To solve these problems, this paper proposes a Hyper Heuristic Ant Colony Optimization algorithm based on pheromone negative feedback(ACONhh)for path planning of mobile robots.The algorithm makes full use of historical search information and continues to gain error experience, thus further leads ant colony to explore optimal path. Hierarchical selection of feasible nodes is adopted to accelerate the initial convergence rate of the algorithm. Meanwhile, the volatility factor changes constantly with an analogous parabola, and pheromone update mechanism is adjusted to improve the randomness of global search. The convergence of ACONhh algorithm is strictly proved. Simulation and experimental results show that the convergence speed and global search performance of the proposed algorithm are outperform those of popular ACO, ACOhh and ACOihh algorithms.
引文
[1]Krug R,Stoyanov T,Tincani V,et al.The next step in robot commissioning:autonomous picking and palletizing[J].IEEE Robotics&Automation Letters,2016,1(1):546-553.
[2]Ignaciuk P.Nonlinear inventory control with discrete sliding modes in systems with uncertain delay[J].IEEE Transactions on Industrial Informatics,2013,10(1):559-568.
[3]Kallasi F,Rizzini D L,Oleari F,et al.A novel calibration method for industrial AGVs[J].Robotics&Autonomous Systems,2017,94(1):75-88.
[4]Tajti F,Burdelis M.A novel potential field method for path planning of mobile robots by adapting animal motion attributes[J].Robotics&Autonomous Systems,2016,82(C):24-34.
[5]Guruji A K,Agarwal H,Parsediya D K.Time-efficient A*algorithm for robot path planning[J].Procedia Technology,2016,23:144-149.
[6]肖云涛,欧林林,俞立.基于线性时序逻辑的最优巡回路径规划[J].自动化学报,2014,40(10):2126-2133.
[7]Khaksar W,Tang S H,Sahari K S M,et al.Samplingbased online motion planning for mobile robots:utilization of tabu search and adaptive neuro-fuzzy inference system[J].Neural Computing&Applications,2017(9/10):1-15.
[8]Mac T T,Copot C,Tran D T,et al.Heuristic approaches in robot path planning:a survey[J].Robotics&Autonomous Systems,2016,86:13-28.
[9]Byrski A,?widerska E,?asisz J,et al.Socio-cognitively inspired ant colony optimization[J].Journal of Computational Science,2017,21:397-406.
[10]万正宜,彭玉旭.求解旅行商问题的改进型量子蚁群算法[J].计算机工程与应用,2016,52(22):59-63.
[11]Williams H L.Intellectual property rights and innovation:evidence from health care markets[J].Innovation Policy and the Economy,2016,16(1):53-87.
[12]Juang C F,Jeng T L,Chang Y C.An interpretable fuzzy system learned through online rule generation and multiobjective ACO with a mobile robot control application[J].IEEE Transactions on Cybernetics,2016,46(12):2706-2718.
[13]Chen Y,Wong M L,Li H.Applying ant colony optimization to configuring stacking ensembles for data mining[J].Expert Systems with Applications,2014,41(6):2688-2702.
[14]侯梦婷,赵作鹏,高萌,等.采用角度因子的蚁群优化多路径路由算法[J].计算机工程与应用,2017,53(1):107-112.
[15]daSilva J F R,Altafim R A C,Hirakawa A R.Crossarms identification with adaptive digital image processing[J].International Journal of Computer Applications,2015,121(23):36-39.
[16]Wilensky G R.The future of the ACA and health care policy in the United States[J].JAMA,2017,317(1):21.
[17]Tang B W,Zhu Z X,Fang Q,et al.Path planning and replanning for intelligent robot based on improved ant colony algorithm[J].Applied Mechanics and Materials,2013,390:495-499.
[18]赵娟平,高宪文,符秀辉,等.移动机器人路径规划的改进蚁群优化算法[J].控制理论与应用,2011,28(4):457-461.
[19]Wang Z,Zhu X,Han Q.Mobile robot path planning based on parameter optimization ant colony algorithm[J].Procedia Engineering,2011,15(1):2738-2741.
[20]Zheng F,Zecchin A C,Newman J P,et al.An adaptive convergence-trajectory controlled ant colony optimization algorithm with application to water distribution system design problems[J].IEEE Transactions on Evolutionary Computation,2017,21(5):773-791.
[21]Chaari I,Koubaa A,Bennaceur H,et al.On the adequacy of tabu search for global robot path planning problem in grid environments[J].Procedia Computer Science,2014,32:604-613.
[22]Zhao J,Fu X.Improved ant colony optimization algorithm and its application on path planning of mobile robot[J].Journal of Computers,2012,7(8):1-4.
[23]Calle J,Rivero J,Cuadra D,et al.Extending ACO for fast path search in huge graphs and social networks[J].Expert Systems with Applications,2017,86:292-306.
[24]何娟,涂中英,牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真,2010,27(3):170-174.
[25]Aziz Z A.Ant colony hyper-heuristics for travelling salesman problem[J].Procedia Computer Science,2015,76:534-538.
[26]Ye K,Zhang C,Ning J,et al.Ant-colony algorithm with a strengthened negative-feedback mechanism for constraintsatisfaction problems[J].Information Sciences,2017,406/407:29-41.
[27]Wang J,Cao J,Sherratt R S,et al.An improved ant colony optimization-based approach with mobile sink for wireless sensor networks[J].Journal of Supercomputing,2017(8):1-13.
[28]周袅,葛洪伟,苏树智.基于信息素的自适应连续域混合蚁群算法[J].计算机工程与应用,2017,53(6):156-161.
[2]Ignaciuk P.Nonlinear inventory control with discrete sliding modes in systems with uncertain delay[J].IEEE Transactions on Industrial Informatics,2013,10(1):559-568.
[3]Kallasi F,Rizzini D L,Oleari F,et al.A novel calibration method for industrial AGVs[J].Robotics&Autonomous Systems,2017,94(1):75-88.
[4]Tajti F,Burdelis M.A novel potential field method for path planning of mobile robots by adapting animal motion attributes[J].Robotics&Autonomous Systems,2016,82(C):24-34.
[5]Guruji A K,Agarwal H,Parsediya D K.Time-efficient A*algorithm for robot path planning[J].Procedia Technology,2016,23:144-149.
[6]肖云涛,欧林林,俞立.基于线性时序逻辑的最优巡回路径规划[J].自动化学报,2014,40(10):2126-2133.
[7]Khaksar W,Tang S H,Sahari K S M,et al.Samplingbased online motion planning for mobile robots:utilization of tabu search and adaptive neuro-fuzzy inference system[J].Neural Computing&Applications,2017(9/10):1-15.
[8]Mac T T,Copot C,Tran D T,et al.Heuristic approaches in robot path planning:a survey[J].Robotics&Autonomous Systems,2016,86:13-28.
[9]Byrski A,?widerska E,?asisz J,et al.Socio-cognitively inspired ant colony optimization[J].Journal of Computational Science,2017,21:397-406.
[10]万正宜,彭玉旭.求解旅行商问题的改进型量子蚁群算法[J].计算机工程与应用,2016,52(22):59-63.
[11]Williams H L.Intellectual property rights and innovation:evidence from health care markets[J].Innovation Policy and the Economy,2016,16(1):53-87.
[12]Juang C F,Jeng T L,Chang Y C.An interpretable fuzzy system learned through online rule generation and multiobjective ACO with a mobile robot control application[J].IEEE Transactions on Cybernetics,2016,46(12):2706-2718.
[13]Chen Y,Wong M L,Li H.Applying ant colony optimization to configuring stacking ensembles for data mining[J].Expert Systems with Applications,2014,41(6):2688-2702.
[14]侯梦婷,赵作鹏,高萌,等.采用角度因子的蚁群优化多路径路由算法[J].计算机工程与应用,2017,53(1):107-112.
[15]daSilva J F R,Altafim R A C,Hirakawa A R.Crossarms identification with adaptive digital image processing[J].International Journal of Computer Applications,2015,121(23):36-39.
[16]Wilensky G R.The future of the ACA and health care policy in the United States[J].JAMA,2017,317(1):21.
[17]Tang B W,Zhu Z X,Fang Q,et al.Path planning and replanning for intelligent robot based on improved ant colony algorithm[J].Applied Mechanics and Materials,2013,390:495-499.
[18]赵娟平,高宪文,符秀辉,等.移动机器人路径规划的改进蚁群优化算法[J].控制理论与应用,2011,28(4):457-461.
[19]Wang Z,Zhu X,Han Q.Mobile robot path planning based on parameter optimization ant colony algorithm[J].Procedia Engineering,2011,15(1):2738-2741.
[20]Zheng F,Zecchin A C,Newman J P,et al.An adaptive convergence-trajectory controlled ant colony optimization algorithm with application to water distribution system design problems[J].IEEE Transactions on Evolutionary Computation,2017,21(5):773-791.
[21]Chaari I,Koubaa A,Bennaceur H,et al.On the adequacy of tabu search for global robot path planning problem in grid environments[J].Procedia Computer Science,2014,32:604-613.
[22]Zhao J,Fu X.Improved ant colony optimization algorithm and its application on path planning of mobile robot[J].Journal of Computers,2012,7(8):1-4.
[23]Calle J,Rivero J,Cuadra D,et al.Extending ACO for fast path search in huge graphs and social networks[J].Expert Systems with Applications,2017,86:292-306.
[24]何娟,涂中英,牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真,2010,27(3):170-174.
[25]Aziz Z A.Ant colony hyper-heuristics for travelling salesman problem[J].Procedia Computer Science,2015,76:534-538.
[26]Ye K,Zhang C,Ning J,et al.Ant-colony algorithm with a strengthened negative-feedback mechanism for constraintsatisfaction problems[J].Information Sciences,2017,406/407:29-41.
[27]Wang J,Cao J,Sherratt R S,et al.An improved ant colony optimization-based approach with mobile sink for wireless sensor networks[J].Journal of Supercomputing,2017(8):1-13.
[28]周袅,葛洪伟,苏树智.基于信息素的自适应连续域混合蚁群算法[J].计算机工程与应用,2017,53(6):156-161.