多策略组合蚁群算法研究及其应用

作     者：冯志雨 

作者单位：上海工程技术大学 

学位级别：硕士

导师姓名：游晓明

授予年度：2020年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主      题：蚁群算法 旅行商问题 机器人路径规划 自适应 信息素更新 密度峰聚类 Turtlebot2机器人 

摘      要：蚁群算法是一种模拟自然蚂蚁觅食过程来搜索最优解的启发式智能算法,由于该算法具有正反馈机制、良好的全局寻优能力和丰富的种群多样性,所以被广泛用于解决复杂的优化问题,例如旅行商问题（Travelling salesman problem,TS P）和移动机器人路径规划问题。其中,TSP问题是经典的NP-hard组合优化问题,具有理论可行性研究价值;移动机器人路径规划问题是机器人技术中的核心问题,具有实际应用性研究价值。因此,本文将对蚁群算法的改进及其在优化问题上的运用进行研究,主要工作内容如下:针对经典蚁群算法存在收敛速度过慢、算法容易陷入局部最优的状况,故本文提出了自适应更新策略的蚁群算法（Adaptive update-Ant colony system,AU-ACS）,改进策略包含:自适应的局部信息素更新策略、改进的全局信息素更新策略、改进的子路径贡献度。首先,AU-ACS算法是通过保持算法的种群多样性与收敛速度之间的平衡,从而获取TSP问题的最优解。其次,AU-ACS算法通过改进的局部信息素更新策略增加种群搜索的多样性。然后,AU-ACS算法通过改进的全局信息素更新策略加快算法的收敛速度。接着,通过改进的子路径贡献度去优化种群找到的最优路径。最后,将提出的AU-ACS算法应用到解决TSP问题,分析AU-ACS算法较经典蚁群算法的改进效果,从而验证AU-ACS算法的有效性。针对经典蚁群算法在处理大规模TSP问题时,增加了算法的运算时间,并且解精度会下降,故本文提出了分层递进的改进聚类蚁群算法（Density peak clustering algorithm-ant colony system,DP-ACS）,DP-ACS算法主要由改进的密度峰聚类算子、改进的信息素更新策略、3-Opt（3-optimization）算子组成。首先,DP-ACS算法运用改进的密度峰聚类算子选取聚类中心,其次,算法按照聚类中心将TSP问题切割形成新的小规模TSP问题群落。然后,运用改进的信息素更新策略的蚁群算法解决小规模TSP问题群落,从而形成多个不关联的子路径回路。接着,通过近邻原则的重连处理以及3-Opt算子的优化形成原TSP问题的全局路径。最后,通过仿真进一步分析DP-ACS算法的种群多样性以及算法运算的迭代效果,得出DP-ACS算法对解决大规模TSP问题具备有效性,从而验证了DP-ACS算法的性能。最后,本文为了进一步验证改进蚁群算法在实际应用中的作用效果,将提出的AU-ACS算法和DP-ACS算法应用到Turtlebot2机器人路径规划问题中。通过分析AU-ACS算法、DP-ACS算法处理机器人路径规划问题的效果,验证了改进蚁群算法解决机器人路径规划问题的可行性。