Abstract: Aiming at the problems of slow convergence and easy falling into local optimum when ant colony algorithm is used to solve large-scale traveling salesman problem,an ant colony optimization algorithm combining entropy clustering and augmented neighborhood strategy was proposed.A clustering strategy combined with information entropy was proposed,which used entropy to determine the best cut-off distance and divide the population reasonably.The initial path was formed by solving each sub-cluster,and the guiding pheromone was provided for global optimization,which improved the convergence speed.An augmented neighbor strategy was proposed,which divided ants into crawling ants and gliding ants.The augmented neighbor strategy introduced by gliding ants updated the pheromones of nodes and neighbors after iteration,and the number of neighbors dynamically matched with the quality of the optimal solution to strengthen the exploration of neighbor nodes,so as to balance the convergence speed and the quality of the solution.When the algorithm came to a standstill,the path similarity mechanism was used to smooth the non-public path pheromone,which helped the algorithm jump out of the local optimum.The experimental of traveling salesman problem data set showed that the proposed algorithm effectively balanced the convergence speed and the accuracy of the solution,and the quality of the solution was significantly improved especially for large-scale problems.

Key words: ant colony algorithm, traveling salesman problem, entropy clustering, augmented variable neighborhood, path similarity

摘要： 针对蚁群算法求解大规模旅行商问题时存在收敛速度慢、易陷入局部最优的问题,提出一种融合熵聚类和增广变邻策略的蚁群优化算法。首先提出融合信息熵的聚类策略,利用熵确定最佳截断距离对数据集进行合理划分;通过求解每个子簇形成初始路径,并为全局寻优提供导向信息素,从而提升收敛速度。其次提出增广变邻策略,将蚂蚁分为爬行蚁和滑翔蚁,滑翔蚁引入的增广变邻策略在迭代后更新节点和邻居信息素,而且通过邻居数量随最优解质量动态匹配,来强化邻居节点探索,以平衡收敛速度与解的质量。当算法陷入停滞时,利用路径相似性机制平滑非公共路径信息素,帮助算法跳出局部最优。通过对旅行商问题数据集进行实验仿真表明,所提算法有效平衡了收敛速度与解的精度,尤其对于大规模问题,显著提高了解的质量。

关键词: 蚁群算法, 旅行商问题, 熵聚类, 增广变邻, 路径相似性