Ant colony optimization algorithm combining entropy clustering and augmented neighboring strategy
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 en-tropy 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 optimi-zation,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 phero-mones 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.
ant colony algorithmtraveling salesman problementropy clusteringaugmented variable neighborhoodpath similarity
NETL
NSTL
万方数据
