摘要： 已有求解子旅行商问题的蚁群算法存在容易早熟、易于陷入局部最优的问题。为此，提出一种改进的蚁群算法。将拥挤因子嵌入到蚁群算法的状态转移和信息素更新过程中，增强全局搜索能力，设计邻域搜索技术和局部变异技术，以提高解的质量和加快收敛速度。实验结果表明，该算法的求解质量和稳定性较好。

关键词: 旅行商问题, 局部最优, 拥挤因子, 邻域搜索, 局部变异, 蚁群算法

Abstract: Existing ant colony algorithm is easy precocious and easy to fall into local optimum when the Subset Traveling Salesman Problem (STSP) is solved through it. In order to solve this problem, the crowding factor is embedding into the state transition and the pheromone update according to the characteristic of the STSP. It makes its global searching ability enhance remarkably. An efficient neighborhood searching technique and a simple and effective local mutation technique are introduced into this algorithm to improve further the quality of solution. Experimental results show that the improved algorithm has much higher quality and stability than that of existing ant colony algorithm.

Key words: Traveling Salesman Problem(TSP), local optimum, crowding factor, neighborhood searching, local mutation, ant colony algorithm

中图分类号: 

• TP18