摘要： 在ACS-3-opt算法求解中，大规模TSP问题易于停滞。该文提出一种改进的算法，在ACS-3-opt算法停滞后，自适应地调整具有局部搜索能力蚂蚁的数量，并通过提高最小信息素的阈值扩大搜索空间，当算法再次停滞时，增强算法两次停滞时最优路径的公共路径上的信息素，为算法的运行提供较好的初始信息，并引导算法朝最优解的方向进行求解。大中型规模TSP问题的求解结果表明，该算法能够有效地跳出局部最优，解的质量优于ACS-3-opt算法。

关键词: 蚁群算法, 信息素阈值, 公共路径

Abstract: To overcome the drawbacks of solving middle-scale and big-scale TSP problem such as easy to stagnation, when using ACS-3-opt(Ant Colony System plus 3-opt), an improved algorithm is proposed, whose cores are that after stagnation of ACS-3-opt increase the quantity of ants with local search ability and enhance minimum pheromone threshold to enlarge search space. When algorithm stagnates again, it reinforces the pheromone of the common path of the two best tours generated. The reinforcement for the common path provides a good initial information for later running, guiding the algorithm to the best tour. The results of solving middle-scale and big-scale TSP problem show that the algorithm can skip from local optimum effectively and the solution is better than ACS-3-opt.

Key words: ant colony algorithm, pheromone threshold, common path

中图分类号: 

• TP18