基于蚁群优化算法的TSP问题研究

TSP问题(traveling salesman problem)是一个组合优化方面的问题，已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的优化算法应运而生了，本文所用到的蚁群优化算法也在其中。 蚁群算法作为一类启发式算法，已经成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上的信息素的强度，同时按照路径上的信息素强度来选择下一步所选择的路径，好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径，最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。 首先，本文对蚁群系统算法(ACS)的全局收敛性和关键参数的设置进行了深入的研究。ACS寻优性质优良，但搜索时间长、收敛速度慢、容易收敛到局部最优解，从而使其进一步推广应用受到局限。我们通过对算法的全局收敛性以及算法的全局搜索能力进行深入的理论研究，从改善算法全局收敛性的角度提出了一系列改良途径；同时对蚁群算法中参数α、β、ρ的作用作了理论上的研究，对算法参数的最优化配置进行丁分析，并利用Ei151这一典型的TSP问题进行了仿真实验，得出了比较适当参数配置方案。 在此之后，本文介绍了蚁群算法中一种新的信息素更新和路径选择机制并应用于求解TSP问题。在ACS基础上，改良的蚁群算法采用了更为高效的信息素更新和路径选择机制，使得改进后算法的全局收敛速度得到明显的提高；通过增加全局最小信息素强度的设置以及对权函数进行自适应调整改进了算法的搜索能力，扩宽了算法的搜索空间，使改进后算法更容易收敛到全局最优解；并通过实验证明了其有效性。 最后，本文对改进后的蚁群算法的实现进行了简单阐述，并针对蚁群算法的前景进行了展望。