Improvement And Optimization Of Polymorphic Ant Colony Algorithm's Application In TSP Problems

Ant Colony Algorithm (ACA) simulates ants' behavior to find the shortest path between food and anthill in the natural world based on ants' group behavior characteristics so as to find the best solution. ACA is a novel bionic evolutionary algorithm, which is widely used in various complicated combination optimization problems. ACA adopts positive feedback and autocatalytic mechanism. It is easy to be integrated with various heuristic algorithms and has strong robustness, while ACA also has shortages that cannot be overlooked, such as the algorithm convergence rate is slow and the ant search can easily fall into local optimum and leads to algorithm stagnation.This paper probes into the application of polymorphic ant colony algorithm in TSP problems and proposes user-defined optimized algorithm. Polymorphic ant colony algorithm optimizes the basic ACA and classifies the ants that have formed a whole via respective interdependent roles and cooperation. Through simulation experiment, this paper finds the weakness of polymorphic ant colony algorithm's application in route selection and universal search. It is easy to stick in local optimum. This paper has done lots of research and analysis on ACA, especially the polymorphic ant colony algorithm and proposes two optimization methods to improve the algorithm performance.Main contents of this research include:I. Summary and research of ACA. Introduce the origin of ACA, introduce mathematics model and algorithm steps, and analyze on the advantages and disadvantages of the algorithm.II. Explain the principles of polymorphic ant colony algorithm, introduce the model and steps of algorithm, and find the pheromone upgrade and route selection problems.III. Put forward weighted value polymorphic ant colony algorithm. Enable a faster and more comprehensive universal ant search by adding weighted value q1 and q2, and verify the validity of this algorithm by simulation experiment.IV. Propose BDB polymorphic ant colony algorithm. Reclassify ants and define walking mechanism for each class. Find the shortest path by simulating anneal arithmetic. The algorithm's stability and effectiveness have been proved by simulation experiment results.