基于改进免疫遗传优化蚁群算法的移动机器人路径寻优研究
|
摘要
针对移动机器人路径规划中使用蚁群算法(ACO)易陷入局部最优和收敛速度慢的问题,提出了一种适用于机器人静态路径寻优的改进免疫遗传优化蚁群算法(IMGAC)。该算法可以根据实际情况自动调整变异概率和变异方式,以及自动调节个体免疫位的长度,将通过改进的变异算子和免疫算子嵌入蚁群算法来提高全局寻优能力与收敛速度。仿真及实验表明:相比于经典ACO算法以及最大最小蚂蚁系统,IMGAC算法收敛速度更快,全局寻优能力更强。利用该算法寻找移动机器人最优路径,提高了静态路径寻优的效果和效率。
Aiming at the problem that the ant colony algorithm( ACO) is easy to fall into the local optimum and the convergence speed is slow in the path planning of mobile robots,an improved algorithm is proposed for the static path optimization of robots,which is called as improved immune genetic algorithm( IMGAC). The algorithm can automatically adjust the mutation probability and mutation mode according to the actual situation and automatically adjust the length of individual immunization bits. The improved mutation operator and immune operator are embedded in ant colony algorithm to improve the global optimization ability and convergence speed. Simulation and experiment show that compared with the classical ACO algorithm and the maximum and minimum ant system,the IMGAC algorithm can converge faster and have better global search ability. The IMGAC algorithm also improves to the result and efficiency of robot path optimization.
Aiming at the problem that the ant colony algorithm( ACO) is easy to fall into the local optimum and the convergence speed is slow in the path planning of mobile robots,an improved algorithm is proposed for the static path optimization of robots,which is called as improved immune genetic algorithm( IMGAC). The algorithm can automatically adjust the mutation probability and mutation mode according to the actual situation and automatically adjust the length of individual immunization bits. The improved mutation operator and immune operator are embedded in ant colony algorithm to improve the global optimization ability and convergence speed. Simulation and experiment show that compared with the classical ACO algorithm and the maximum and minimum ant system,the IMGAC algorithm can converge faster and have better global search ability. The IMGAC algorithm also improves to the result and efficiency of robot path optimization.
引文
[1]Liang H,Ge Y.GACA-VMP:Virtual machine placement scheduling in cloud computing based on genetic ant colony algorithm approach[C]//IEEE Intl Conf on Autonomic and Trusted Computing,Beijing,China,2015:1008-1015.
[2]张兆军,冯祖仁,任志刚.采用序优化的改进蚁群算法[J].西安交通大学学报,2010,44(2):15-19.Zhang Z J,Feng Z R,Ren Z G.Novel ant colony optimization algorithm based on order optimization[J].Journal of Xi'an Jiao Tong University,2010,44(2):15-19.
[3]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.Liu C A,Yan X H,Liu C Y,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224.
[4]邱莉莉.基于改进蚁群算法的机器人路径规划[D].上海:东华大学,2015.Qiu L L.Path planning for mobile robot based on improved ant colony optimization algorithm[D].Shanghai:Donghua Universiy,2015.
[5]梁晓丹,蔺娜,陈瀚宁,等.基于细菌觅食行为的移动机器人动态路径规划[J].仪器仪表学报,2016,37(6):1316-1324.Liang X D,Lin N,Chen H N,et al.Mobile robot dynamic path planning based on bacterial foraging behavior[J].Chinese Journal of Scientific Instrument,2016,37(6):1316-1324.
[6]Shen X L,Sang J S,Sun Y B,et al.Application of improved ant colony algorithm in distribution network patrol route planning[C]//7th IEEE International Conference on Software Engineering and Service Science.Beijing,China,2016:560-563.
[7]Hu Y,Li D,Ding Y.A path planning algorithm based on genetic and ant colony dynamic integration[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation.Shenyang,China,2015:4881-4886.
[8]Liu C Y,Zou C M,Wu P.A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing[C]//International Symposium on Distributed Computing and Applications to Business,Engineering and Science.Xian Ning,China,2014:68-72.
[9]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.Li Q,Zhang C,Chen P,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-878.
[10]Byerly A,Uskov A.A new parameter adaptation method for genetic algorithms and ant colony optimization algorithms[C]//IEEE International Conference on Electro Information Technology.Shanghai,China,2016:0668-0673.
[11]Huang C H,Huang C C,Lee M R,et al.Contingencies security control with hybrid genetic-ant colony algorithm[C]//IEEE 3rdInternational Conference on Communication Software and Networks.Xi'an,China,2011:761-765.
[12]Zhou H F.An improved ant colony algorithm combined with genetic algorithm and its application in image segmentation[J].Intelligence Computation and Evolutionary Computation,2013,180:389-393.
[13]张维泽,林剑波,吴洪森,等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报(工学版),2008,42(4):574-52.Zhang W Z,Lin J B,Hong-Sen W U,et al.Optimizing logistic distribution routing problem based on improved ant colony algorithm[J].Journal of Zhejiang University,2008,42(4):574-52.
[14]王晶,王雪锋,王肖杰等.基于改进型MMAS算法的微电源容量优化布址[J].电力系统自动化,2015,39(21):73-80.Wang J,Wang X F,Wang X J,et al.Optimal siting and sizing of DGS for microgrid based on improved MMAS algorithm[J].Automation of Electric Power Systems,2015,39(21):73-80.
[15]Mac T T,Copot C,Tran D T,et al.A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J].Applied Soft Computing,2017,59:68-76.
[2]张兆军,冯祖仁,任志刚.采用序优化的改进蚁群算法[J].西安交通大学学报,2010,44(2):15-19.Zhang Z J,Feng Z R,Ren Z G.Novel ant colony optimization algorithm based on order optimization[J].Journal of Xi'an Jiao Tong University,2010,44(2):15-19.
[3]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.Liu C A,Yan X H,Liu C Y,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224.
[4]邱莉莉.基于改进蚁群算法的机器人路径规划[D].上海:东华大学,2015.Qiu L L.Path planning for mobile robot based on improved ant colony optimization algorithm[D].Shanghai:Donghua Universiy,2015.
[5]梁晓丹,蔺娜,陈瀚宁,等.基于细菌觅食行为的移动机器人动态路径规划[J].仪器仪表学报,2016,37(6):1316-1324.Liang X D,Lin N,Chen H N,et al.Mobile robot dynamic path planning based on bacterial foraging behavior[J].Chinese Journal of Scientific Instrument,2016,37(6):1316-1324.
[6]Shen X L,Sang J S,Sun Y B,et al.Application of improved ant colony algorithm in distribution network patrol route planning[C]//7th IEEE International Conference on Software Engineering and Service Science.Beijing,China,2016:560-563.
[7]Hu Y,Li D,Ding Y.A path planning algorithm based on genetic and ant colony dynamic integration[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation.Shenyang,China,2015:4881-4886.
[8]Liu C Y,Zou C M,Wu P.A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing[C]//International Symposium on Distributed Computing and Applications to Business,Engineering and Science.Xian Ning,China,2014:68-72.
[9]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.Li Q,Zhang C,Chen P,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-878.
[10]Byerly A,Uskov A.A new parameter adaptation method for genetic algorithms and ant colony optimization algorithms[C]//IEEE International Conference on Electro Information Technology.Shanghai,China,2016:0668-0673.
[11]Huang C H,Huang C C,Lee M R,et al.Contingencies security control with hybrid genetic-ant colony algorithm[C]//IEEE 3rdInternational Conference on Communication Software and Networks.Xi'an,China,2011:761-765.
[12]Zhou H F.An improved ant colony algorithm combined with genetic algorithm and its application in image segmentation[J].Intelligence Computation and Evolutionary Computation,2013,180:389-393.
[13]张维泽,林剑波,吴洪森,等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报(工学版),2008,42(4):574-52.Zhang W Z,Lin J B,Hong-Sen W U,et al.Optimizing logistic distribution routing problem based on improved ant colony algorithm[J].Journal of Zhejiang University,2008,42(4):574-52.
[14]王晶,王雪锋,王肖杰等.基于改进型MMAS算法的微电源容量优化布址[J].电力系统自动化,2015,39(21):73-80.Wang J,Wang X F,Wang X J,et al.Optimal siting and sizing of DGS for microgrid based on improved MMAS algorithm[J].Automation of Electric Power Systems,2015,39(21):73-80.
[15]Mac T T,Copot C,Tran D T,et al.A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J].Applied Soft Computing,2017,59:68-76.