Ant Colony Algorithm For TSP Problem

In recent years, people will nature of the many useful features used in engineering practice.Ant colony algorithm is to learn from nature, gregarious insects ability to cooperate through the self-organization resulting from swarm intelligence to solve a classic example of combinatorial optimization problems. Ant colony algorithm is by the Italian scholars Dorigo M, and others in the 20th century and early 90's, through the simulation of nature optimizing behavior of ant groups put forward a new kind of heuristic bionic evolutionary algorithm, which made traveling salesman problem in solving the more good results. In solving the traveling salesman problem (TSP), the first cross-cutting strategy to introduce pre-processing, specific maps abstracted as a common undirected complete graph, that is an abstract for the sake of TSP undirected complete graph of a Hamilton circuit, then use the ant swarm optimization and artificial neural network combining methods to solve. The experimental results show that the method is feasible and efficient. In introducing the principles and characteristics of ant colony algorithm, the emphasis on analysis of the current number of representative ant colony algorithm to improve the mechanism and application of results and a comparative approach pointed out the characteristics of these methods and major applications and so on, concluded the Good ant colony algorithm should have the characteristics and future research strategies and development trend.Ant colony algorithm applied in many areas, if applied to TSP, Job shop scheduling problems, large scale integrated circuit integrated wiring problem, telecommunication network routing problems. Ant colony algorithm for the shortcomings made a number of improved algorithm, and the improved ant colony algorithm applied to a different new areas. Because the basic ant colony algorithm using random selection strategy, making a slow evolution; same time, the ant colony algorithm aimed at harnessing the positive feedback theory and distributed computing models, but failed to speed up the evolutionary process better and to avoid premature convergence, but prone to stagnation. For the ant colony algorithm to accelerate convergence and mature, the stagnation phenomena of the contradictions and the time is too long to find the optimal solution such shortcomings can be improved ant colony algorithm from the following directions.(1)Self-adaptive algorithm ,â‘ Looking from the choice probability, may use the different stage use different choice probability, in seeks in road's process dynamic to adjust the choice probability, and may use the choice probability the different method.â‘¡Information element renewal strategy's auto-adapted, should be able to carry on the dynamic updating and the auto-adapted adjustment to the information element.â‘¢If seeks the road process optimization is several different stages, and uses the different method in the different period, then which stage auto-adapted should analyze the degree which the ant group individual carried on already to arrive, what strategy should the choice carry out and so on.â‘£In ant group algorithm formula each parameter auto-adapted choice.(2)Optimization of the initial solution. Due to differences in the initial pheromone on the path are the same, the initial solution the first time, are likely to choose the path of the evolution of the entire ant colony misleading, the need to improve the quality of the initial solution to maximize the initial stage, we can choose The number of paths in order to increase the diversity of solution.(3)Information usually dynamic updating strategy. Information element density strong and the weak direct relation ant individual optimization process. How to let the information element tendency, renew auto-adapted, how increases and so on methods through information element function's proliferation and the information element type to achieve cooperation between ant's, as well as how to adjust the information element the renewal formula, is very important.(4)The probability of adaptive routing.â‘ Should implement adaptive selection probability; according to different applications,â‘¡Different physical environment such as rational design and adjust the selection probability formula and so on. (5)Threshold design. Information on weight, sensory threshold, for the design of such a threshold value, the ability to define pheromones, play a role in selection probability of the interval or the critical point, the ant colony algorithm is divided into different stages, different strategies to implement, have also assisted adaptive implementation(6) Ants collaboration. More research has been referred to the collaboration among ants, and there are ants, the researchers propose should be divided into multiple categories, and different types implement different strategies to complete different tasks, and then through the ants to achieve better coordination between the strategy. As in the real world of the ant colony, the ants also have been divided classes, different types of ants perform different work. Ant to a certain degree of collaboration to optimize the algorithm, but also increases the complexity of the algorithm.This paper also extends to the following based on ant colony algorithm for related research(1)Ased on ant colony algorithm for map vector of algorithms(2)Dynamic adaptive ant colony algorithm in quadratic assignment problem of applicationAdopting a new algorithm for dynamic adaptive ant colony algorithm can solve quadratic assignment problem, and introduce 3 - involved in problem solving method for local optimization, based on quadratic assignment problem of different example experimental results show that the algorithms solve quadratic assignment problem has better ability, can well solve the large scale of quadratic assignment problem, whereas the algorithm only suitable for dealing with smaller quadratic assignment problem.(3)Based on ant colony algorithm of substantive applicationsAnt colony algorithm was first applied to classic combinatorial optimization problem, with the deepening of research, application scope expands gradually to more combinatorial optimization problem, and so far has been to the ant colony algorithm applied to the continuous optimization problem of research.(1)Static combinatorial optimization problem of applicationAnt colony algorithm has been applied in many fields, such as water resources planning, power system, and the optimization of logistics field, etc. The typical combinatorial optimization problem. From the initial with the ant colony algorithm can solve traveling salesman problem started, the researchers in its application to other typical combinatorial optimization problem: quadratic programming problem, graph coloring problem. These problems have strong engineering representative, ant colony algorithm in typical the combinatorial optimization problem of excellent performances on accelerating its in engineering application fields of development.(2)Dynamic combinatorial optimization problem of applicationIn dynamic combinatorial optimization problem, problem solution change from time to time. Ant colony algorithm in dynamic combinatorial optimization problem of the research on the application of concentrated in communications. Schoonderwoerd waiting for a vice he first will be used for communication network ant colony algorithm of routing problems, and put forward based on ant colony algorithm for routing algorithms. Dic Caro etc were based on ant colony algorithm of adaptive routing algorithm was designed AntNet, each node according to network condition dynamically update routing table item. Hussein advances improved ant colony algorithm is applied to mobile self-organization network routing problem. Communication network of some of the characteristics, such as distributed information storage structure, network dynamic characteristics of ant colony algorithm and the essential characteristic of very similar, so the ant colony algorithm in the field of communications have broad application prospect.(3)Continuous optimization problem of applicationAt present the ant colony algorithm in the continuous optimization problem application is relatively rare. BiIchev first try to use such as ant colony algorithm can solve continuous optimization problems. Ho, etc by improving pheromone refresh strategy proposed for solving the continuous optimization problem of ant colony algorithm, the algorithm used in the optimization design of the electromagnetic device obtained good effect. Now will the ant colony algorithm applied continuous optimization problem of research has just started, continuous optimization problem and combinatorial optimization problem, compared to their ultimate optimization target is different, so need in pheromone refresh strategy, ants state transfer strategy to adapt to the continuous improvement on the continuous optimization problem solving.These are the most important ant colony algorithm to improve and optimize the main direction, of course, ant colony optimization algorithm parameters, such as pheromone evaporation coefficient optimization.For the ant colony algorithm has been neither stopped, the researchers tried a variety of strategies to solve problems and explore its ant colony algorithm can be suitable for a variety of applications. Through the ant colony algorithm described the latest progress and prospects of the development of ant colony algorithm can show the need to address issues and provide food for thought for the use of ant colony algorithm.