关键词: 蚁群算法, 信息熵, 旅行商人问题

Abstract: Aiming at the fact that the ant colony algorithm is prone to fall into local optimum, the convergence speed is slow, and it is difficult to solve large-scale problems, this paper proposes an ant colony algorithm based on dynamic pheromone update strategy dependent on the information entropy and the number of stagnation  and the reward and punishment strategy based on the optimal path set. In the dynamic pheromone update strategy, the convergence coefficient is used to dynamically adjust the pheromone, so as to effectively balance the diversity and convergence of the algorithm. During the search process, the convergence speed is accelerated by continuously increasing the convergence coefficient. When the information entropy decreases or the number of stagnation reaches a certain value, the local optimum can be jumped out by reducing the convergence coefficient. At the same time, based on the optimal path set, the optimal path is rewarded and other paths are penalized, thereby reducing the number of cities that ants can choose at each step, and speeding up the convergence speed. And three local optimization methods are used to further improve the accuracy of the solution. After experimental tests, the algorithm is used to solve the traveling salesman problem（TSP）, which has a high solution accuracy and can effectively balance the contradiction between the solution accuracy and the convergence speed.

Key words: ant colony algorithm, information entropy, traveling salesman problem