Abstract: To overcome the problem of the slow convergence speed and low precision of ant colony algorithm in solving Travelling Salesman Problem(TSP),a co-evolutionary ant colony system based on random convergent neighborhood strategy was proposed.In the random convergent neighborhood strategy,the ant colony was randomly divided into elitist ants and exploration ants by the random hierarchical strategy that could dynamically adjust the number of the two types of ants for effectively regulating the diversity and convergence of the algorithm.Then,exploration ants were helpful to expand the search in the vicinity of the better solution by convergent neighborhood search to improve the accuracy of the solution.In addition,the co-evolution strategy was introduced to promote the interactive evolution of the whole ant colony.The Jaccard index was used to judge the similarity of the respective optimal paths of the two types of ants,the communicational frequency between two types of the ants was dynamically adapted,and the pheromones on the common path that a public tour obtained by these two types of ants was smoothed,so that the accuracy of the algorithm was improved further.Finally,the simulation experimental results showed that the improved algorithm could not only balance the relationship between the diversity and convergence of the algorithm effectively,but also improve the accuracy of the solution for large-scale problems.

Key words: ant colony algorithm, random convergent neighborhood, co-evolution, traveling salesman problem

摘要： 针对蚁群算法在求解旅行商问题时收敛速度慢、求解精度低等问题,提出一种融合随机趋邻策略的协同演化蚁群算法。随机趋邻策略首先采用随机分级策略将蚁群随机分为精英蚁和探索蚁,其中随机分级策略能够通过动态调控两类蚂蚁的数量来有效调节算法的多样性和收敛性;然后探索蚁通过趋邻搜索扩大较优解附近的搜索范围,以提高解的精度。协同演化策略采用Jaccard系数判断两类蚂蚁各自最优路径的相似程度,以动态调整两类蚂蚁的交流周期,并平滑其各自最优解公共路径上的信息素,从而实现两类蚂蚁交互进化,进一步提高解的精度。最后通过仿真实验表明,在大规模旅行商问题中,改进算法不仅能够有效平衡算法多样性与收敛性之间的关系,还能提高解的精度。

关键词: 蚁群优化算法, 随机趋邻, 协同演化, 旅行商问题