关键词: 动态学习, 奖惩模型, 双种群, 旅行商问题

Abstract: Aiming at the deficiencies of ant colony algorithm that can easily fall into the local optimum and the convergence speed is slow, a dual population ant colony algorithm based on dynamic learning mechanism is proposed. This algorithm focuses on the reward penalty model. The reward operator improves the convergence speed of the algorithm, and the penalty operator improves the diversity of the algorithm. Two populations SA-MMAS (adaptive simulated annealing ant colony algorithm based on max-min ant system) and MMAS (max-min ant system) coopera-tively search paths, and then the ant colonies dynamically communicate pheromone according to different city sizes. After communication between the two colonies, the incentive penalty model is used to give dynamic feedback to the learning cooperative behavior between the two colonies, thus balancing the diversity and convergence speed of the algorithm. Verified by 17 classic TSP (traveling salesman problem) instances, the results show that the algorithm can obtain the optimal solution or near optimal solution with fewer iterations. It is more effective for medium and large-scale TSP, thus verifying the efficiency and feasibility of the algorithm.

Key words: dynamic learning, reward penalty model, dual population, traveling salesman problem (TSP)