关键词: 评估奖惩, 邻域退化, Tanimoto相关系数, 协同进化, 蚁群算法, 旅行商问题

Abstract:

To address the slow convergence and the tendency to fall into local optimality in solving TSP, a cooperative ant colony algorithm combining evaluation reward and punishment mechanism and neighborhood dynamic degradation (ENCACO) is proposed. The paths are classified into active and abandon paths according to the path evaluation value, and with the path evaluation value as the weight, the different pheromone reward and punishment strategies are adopted for the two types of paths to accelerate the convergence speed of the algorithm. Through the neighborhood dynamic degradation strategy, and the neighborhood radius is used to divide the set of cities into exploration and degradation zones. The search range of ants is adaptively reduced, some cities in the degradation zone are dynamically refined by retention probability, and the state transfer probability is calculated together with the population to balance the convergence speed and the population diversity of the algorithm. The interspecies co-evolution mechanism is adopted to determine the interaction period betweenpopulations according to Tanimoto correlation coefficient, and the appropriate interaction is selected at different stages of the algorithm to help the algorithm jump out of the local optimum and improve the solution accuracy to achieve the purpose of effective communication between populations.

Key words: evaluation of rewards and punishment, neighborhood degradation, Tanimoto correlation coefficient, co-evolution, ant colony algorithm, TSP