|
The ant colony algorithm is only in recent years raised a new bionic optimization algorithm, it is by Italian scholars M.Dorigo, V.Mahiezzo, A.Colorni al groups looking for food process inspired by real ants in nature and the first raised. They take advantage of the ants search for food among the traveling salesman problem, through the artificial simulated ants search for food on the process of mutual collaboration and exchange of information between the ants individuals, and ultimately find the principle from the nest to a food source shortest path to solve The traveling salesman problem (TSP), and achieved good results. The algorithm has a high degree of essentially parallel, robustness, excellent distributed computer system, easy combination with other methods, etc.. Since the ant colony algorithm proposed, has caused great concern of scholars at home and abroad, in ten years time, combinatorial optimization, data mining, network routing, robot path optimization, continuous function optimization problems on a wide range of applications shows its superiority in solving complex optimization problems. Therefore, the study of the ant colony algorithm, both from the theory and application of high value. As a recently proposed new optimization algorithm, but also did not like genetic algorithms, simulated annealing algorithm as a system analysis methods and a solid mathematical foundation, many theoretical issues to be studied, such as the algorithm searches for a longer time, the running process is prone to convergence prematurely or stagnation, not to broaden the search range of solutions. In response to these deficiencies, the domestic and foreign scholars in recent years have made a lot of improvements on ant colony algorithm. TSP is a combination of wide application background and important theoretical value optimization problems, has become and will continue to be a test combinatorial optimization algorithm standard. Principle, theory and applications of the papers around the ant colony algorithm, for some of the defects in the presence of the ant colony algorithm to solve TSP, read a lot of literature based on several improvements. The main findings of the paper include: First, in pheromone updating the way, the introduction of the feedback factor, using the previous feedback, and try to avoid unnecessary search, unified, all solutions do not use information in the pheromone update pheromone updating mode, but take different solutions of different treatment strategies according to the feedback factor, the optimal solution in each cycle, the worst solution and the general solution to the implementation of the different pheromone update, and enhance the general solution of the pheromone, optimal solution to a greater extent the enhanced weakened poor Solutions, is further increased so that the edges belonging to the optimum path are poor path difference between the edges of the amount of pheromone, in order to better use of the ant previous feedback information search behavior of ants is more concentrated in the vicinity of the optimal solution, the solution of the problem in order to guide the direction of evolving toward the global optimum. Second, we propose a new heuristic evolution crossover operator, this evolution cross is not just a simple random cross, but the parent gene, a heuristic crossover based on the connection between the various cities. . This crossover operator applied to the ant algorithm implementation of this heuristic crossover, randomly select a path with the optimal path through the progeny of this cross will be valid succession of parent genes preferably, thus beneficial to find the optimal solution to accelerate the speed of convergence of the algorithm. Third, in order to further prevent the algorithm into a local optimum prematurely, the thesis using deterministic and stochastic combined strategy to choose the path, the combination of randomness and exploratory, to get a diversity of solutions. Fourth, this algorithm is applied to the TSP, experiments show that, compared with traditional ant colony algorithm, using the evolutionary algorithm based on heuristic crossover operator to solving complex TSP problem not only has the stronger global search capability , but also improve the convergence rate of the algorithm, and ultimately makes the algorithm performance to be significantly improved. Finally, the work of this thesis are summarized and looking forward to the ant colony algorithm further research.
|