关键词: 商旅问题（TSP）, 异构双种群, 偏离度系数, 启发式强化学习

Abstract:

A heterogeneous two-population ant colony algorithm based on heuristic reinforcement learning is pro-posed to solve the problem that traditional ant colony algorithm is prone to fall into local optimum and convergence speed is slow when solving TSP. Ant colony can be divided into main population and sub-population.The main population is responsible for solution construction and pheromone update. The sub-population replaces the solution set of the main population while constructing the solution. At the beginning of the algorithm, heuristic operator is used to control the communication frequency of two populations adaptively, and the solution exchange mode is controlled by the deviation degree coefficient. At the early stage, the optimal solution of the subpopulation is allowed to replace the random solution of the main population, increasing the diversity of solutions. Meanwhile, the reinforcement learning mechanism is introduced to reward the pheromones in the optimal path of the main population adaptively, so as to increase the probability of the optimal public path selected later. In the later stage, the optimal solution of the sub-population is controlled to replace the worst solution of the main population, the quantity of pheromones in the optimal path is strengthened, and the pheromones in the optimal path of the main population are rewarded, so as to further improve the convergence speed of the algorithm. The simulation results show that the algorithm can effectively jump out of the local optimum, and the quality of the solution is obviously improved in the large-scale test set.

Key words: travelling salesman problem (TSP), heterogeneous dual population, deviation coefficient, heuristic reinforcement learning