Tsp Problem Based On The Evolution Of Ant Colony Algorithm Research And Applications

The ant colony algorithm (ACA) is a new kind of bionics optimization algorithms, which was first proposed by M.Dorigo, V.Mahiezzo, A.Colorni. They had simulated the ant individual's mutual cooperation and the communication in the process of searching food to find the shortest path from its lair to the food, they had apply the principle to Traveling Salesman Problem(TSP), and has made the good progress in the end. Because its has many merits such as the strong parallel and robustness, the eximious distributed computing mechanism, easy unifies with other algorithm, the algorithm has aroused the domestic and foreign scholar's enormous interest. In the past ten years,the algorithm has been widely applied to the fields of combinatorial optimization, date mining, network routing, path planning of robot, successive function optimization etc, demonstrates its superiority in the solution complex optimization question. So the research of the algorithm has great merits both in theory and application.As a novelty optimization algorithm, not liked Genetic Algorithm and Simulated Annealing Algorithm, ACA has not formed systematic analysis approach and the solid mathematic foundation, many theory questions wait for further studying, for example, long searching time, slow convergent speed and low searching efficiency and cannot expand the hunting zone etc. In view of these flaws, in recent years the domestic and foreign scholars proposed the massive corrective methods to the ant colony algorithm.Traveling Salesman Problem (TSP) is a combinatorial optimization problem, it has became and will be still became a standard problem to test combinatorial optimization algorithm. The paper focuses on the principles, theory and its application in the TSP, after studying a great amount of relevant literatures, some possibility methods of the ACS improvements are presented in this thesis.The contributions of the thesis are as following:First, on the mode of updating pheromone mechanism, the paper introduces a new parameter (feedback factor) to take advantage of previous feedback information, try to avoid unnecessary searching. When updating pheromone, the thesis adopts the different solution to do different treatment according to the feedback factor. We enhance the pheromone of general solution, and further enhance the optimal solution's pheromone but weaken the worst solution, which will make search to concentrate on the round of the optimal solution. Second, a heuristic crossover operator will be imported in iteration; the heuristic crossover is not a simple random crossover, but a heuristic approach which synthesized the gene of parents and also took into account connection relationship among various cities. After complete iteration, we choose randomly an ant to carry out the heuristic crossover with the best ant. The offspring which get by the crossover can inherit excellent gene from their parents, which is good for finding the optimal solution and speed up convergence rate.Third, to further prevent the algorithm premature from falling into local optimization, the thesis uses a strategy based on determinacy and random in choosing next city to obtain the multiple solutions.Fourth, using the algorithm to solve TSP, the experiments show that, compared with the traditional ant system algorithm, using this new algorithm to solve complex TSP problems has not only better searching ability but also can accelerates convergent speed, and the algorithm performance is improved greatly .In the end, the work of the thesis is summarized and the prospective of future research is discussed.