Ant Colony Algorithm Based On Path Feature For Solving The Traveling Salesman Problem

The ant colony algorithm is an optimization algorithm simulating ants foragingbehavior, it solves combinatorial optimization problems drawing on self-organizedcooperation ability of ant colony. The Italian scholar proposed the ant colony algorithmsimulating ant colony behavior to solve the traveling salesman problem (TSP), andachieved good results. Ant colony algorithm owns positive feedback mechanism, strongrobustness and excellent distributed computer system, it has shown excellent performanceand great potential for many complex optimization problems. Ant colony algorithm hasbeen successfully applied to production scheduling, wiring and other production problems.Although ant colony algorithm owns the positive feedback mechanism and distributedcomputing mode, it’s random selection strategy and slow convergence procedure stillmakes it is prone to stagnation early. For the contradiction between accelerate convergenceand early stagnation, as well as the shortcoming of long searching time, make analysis fromthe following directions to improved ant colony algorithm.(1) Adaptive pheromone update. Pheromone concentration will affect the searchprocedure, pheromone residual coefficient reacts the evolution state of entire ant colonysystem, its size is directly related to the global search capability and convergence rate of theant colony algorithm. Updating pheromones adaptively and adjusting pheromone diffusionand the update formula can improve the convergence rate.(2) Optimization of the initialization. At the beginning every path own the samepheromone, results got from first iteration may mislead the search procedure of the entireant colony, so we should try to improve the quality of the initial solutions to increase thediversity of solutions.(3) Emphasis on common paths. Ant colony rely pheromone to find the optimal path,when the pheromone is accumulated to a certain extent, there are some short path selectedrepeatedly, these common paths are likely components of better or optimal solution. Takefull advantage of common paths information, not only can improve the solution quality, butalso can speed up the convergence rate of the algorithm.(4) Strengthen mutation operation. Ant colony algorithm easily falls into local optimum, strengthen the variability of the path, it can expand the number of solutions,increase the diversity of the solutions, and improve the quality of solutions.Two improved algorithms are proposed according to the above aspects. The firstmethod: this algorithm use adaptive adjustment mechanism to adjust the speed ofconvergence, it avoids excessive focus on some better paths. Minimize repeat operationsaccording to common paths in searching process, reduce the computation time of antcolony algorithm, and enhanced algorithm global optimization capability. Experimentalresults show that the improved algorithm has better solution quality with relatively smallernumber of iterations. The second method: study mutation operations according tocharacteristics of the path based on the first method, mutation operation can enrich thediversity of solutions, reduce the time complexity of the ant colony algorithm, and enhanceglobal optimization capability. The experimental results show that the improved algorithmcan achieve better solution and convergence rate for TSP.