Multiple Ant Colony Algorithms Research And Application

Ant colony algorithm is a new type of simulated evolutionary algorithm in the early 90's, which absorbed the idea of the behavior of real ants, by simulating the real ant colony's searching for food to complete the process of solving the problem. It uses artificial ants, which have memories, to find the shortest path to food source through the exchange of information between individuals with mutual cooperation from formicary. This method is firstly promoted by several scholars including Dorigo M from Italian. They named it the Ant Colony System (ACS). Based on the characteristics of ant colony algorithm, solving a series of classical problems like Traveling Salesman Problem (TSP), Assignment Problem and Job-Shop scheduling problem can lead to a series of certified good laboratory test results. Thus, the ant colony algorithm is widely used in the field.Based on the ant colony algorithm's weakness like slow convergence and vulnerable, also through the careful study about ant colony society, the study of Polymorphic Ant Colony Algorithm found that in the real ant colony society, despite all the ants perform their respective duties, they still need mutual collaboration to form into an organic integrity. In the implementation of a task, individuals are interlinked and mutually cooperative through their secretion of pheromones. 'Polymorphism' refers to a variety of ant society that is with various statuses of groups of ants and pheromone. According to the different division of labors, ants will be divided into reconnaissance ant, search and worker ants, and they will perform their respective duties. Among them, the reconnaissance ant is responsible for local surveillance reconnaissance, and search ant is responsible for global search. This can greatly enhance the effectiveness of cooperation between groups, and can enhance the effectiveness of the ant colony algorithm as well.Simulated Annealing Algorithm is put forward by S. Kirkpatrick in 1982. It is a stochastic optimization methods set up by simulating annealing mechanism of metal which is derived from simply simulating the annealing process of solid to set up of a common random search technology that has strong local search ability, and can avoid falling into local optimal solution. Because of the existence of such advantages, it is successfully introduced into Combinatorial Optimization Theory. In recent years, it caused a wide range of great importance in areas such as large-scale optimization algorithm design, numerical analysis and the complex layout.More systematic analysis and research of ant colony algorithm, especially multiple ant colony algorithms are proposed in this paper. Three improved algorithms are proposed and applied to solve the complex maze of the path. The specific research and innovation are as follows:(1) The overview of the ant colony algorithm. It is introduced the research background and significance of the ant colony algorithm, its functions, its ideological source, its research at home and abroad, as well as its typical applications, and so on.(2) The research of the ant colony algorithm. Three basic models of the ant colony algorithm are introduced. The ant colony algorithm has been first applied to the traveling salesman problem. It is briefly introduced the traveling salesman problem, realization steps of the ant colony algorithm based on the traveling salesman problem, as well as analysis of algorithm complexity.(3) The model and implementation of the multiple ant colony algorithm. It is introduced the background of the multiple ant colony algorithm, the model of the multiple ant colony algorithm, as well as its inadequacies.(4) The basic ant colony algorithm and the improved multiple ant colony algorithm. According to inadequacies of the basic ant colony algorithm and the improved multiple ant colony algorithm, three improved algorithms are proposed: Converse Ant Algorithm Basis of Adjust Information Element Hangover Coefficient, Multiple Converse Ant Colony Algorithm Based on Simulated Annealing, as well as Polymorphic Ant Colony Algorithm Based on Pheromone Diffusion. Test results of the improved algorithm are proved to improving the convergence speed and the capacity to finding the optimal solution.(5) Combined advantages of the ant colony algorithm in the search for the optimal path, the improved multiple ant colony algorithm is applied to solve the optimal path problem of the complex maze. Theoretical analysis and experimental results show that the algorithm can find the optimal path.