【作者】 孙骏；

【导师】 熊盛武；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2005， 硕士

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

【Abstract】 TSP (Traveling Salesman Problem) is a problem of combination optimization with simple definition but difficult to be solved, which attracts many researchers in various fields including mathematics, physics, biology and artificial intelligence (AI). It has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. But to all computers nowadays, it’s hardly to obtain its best answer in such huge researching space by using common enumeration. Therefore, all kinds of algorithms to solve TSP emerged because of demand. Among of them, ant colony algorithm (ACA) is one of advanced technologies.Ant colony algorithm is a class of heuristic search algorithms that have been successfully applied to solving NP hard problems. Ant algorithms are biologically inspired from the behavior of colonies of real ants, and in particular how they forage for food. We can find that when ants are looking for food from nest, some chemical trails (we call this trail as pheromone) are laid by all ants, the ants moving around form a network of these trails, and information is laying around, waiting to be used. Good information tends to be reused over and over again, leading to more reinforcement, leading to more use. This is a form of behavior called autocatalytic behavior, and it is the key to the success of the ant colony. ACA has many good features in optimization, but it has the limitations of stagnation and poor convergence, and is easy to fall in local optima, which are the bottlenecks of its wide application. A detailed theoretical research on the global convergence of ACA is performed. A series of improvement schemes are also proposed. Meanwhile, this paper studies and analyses the function and influence of parameter α, β, ρ in the model of ant algorithm theoretically, and then a typical example of TSP Eil51 is calculated.Then, this paper presents a new pheromone updating strategy which is used to optimize ACS (Ant Colony System) in solving the Traveling Salesman Problem. The improved ant colony optimization algorithm is using a new pheromone updating strategy. The pheromone trail of each edge is set with a lower limit at the beginning iterations of thealgorithm, and the worst ant judged by its tour length like the best ant used in ACO is allowed to perform global trail updating. And we demonstrate the efficiency of the algorithm by means of experimental study.Finally, the paper explained the implement of the improved algorithm. and we indicate the future research directions.更多还原