Research On Combined Multi-strategy And Mutation Operator Based Ant Colony Algorithm For Path Planning

Optimization methods and its application on route planning is a research focus in Artificial Intelligence, and ant colony algorithm is a representative method in route planning problem research. From a different perspective, the ant colony algorithm based routing planning exist some problems can be improved in convergence time,individual fitness, average path length and falling into local optimal solution. To solve these problems, we deal 2-D and 3-D routing planning problems with combined multi-strategy optimization method and mutation operators and proposed two improved ant colony algorithms in this thesis.The main research works of the thesis show as follows:1. We proposed an Ant Colony Algorithm based on Combined multi-strategy(ACA-CMs for short) to solve 2-D routing planning problems. This algorithm can fix the problems of long convergence time and easy to fall into local optimal solution with pheromone update strategy, 2-opt local optimization strategy and limited pheromone concentration range strategy. The simulation on 2-D Traveling Salesman Problems(TSP for short) and the comparative experiments on the basic Ant Colony Algorithm and the Genetic Mechanism based Ant Colony Algorithm show that the ACA-CMs has good performance to solve the convergence time reducing and global optimal solution searching.2. We proposed an Ant Colony Algorithm based on Mutation Operator(ACA-MO for short) to solve 3-D routing planning problems. ACA-MO is a heuristic search algorithm, and it introduces reversal mutation and insertion mutation operator on the basis of the improved heuristic function design, selecting probability and pheromone updating strategy. Through selecting turning point to array the nodes in reverse order and inserting random nodes to find the non-collision path, and the optimization of ant colony algorithm is partly improved. A mass of simulations on TSPLIB compared with the Basic Ant Colony Algorithm and the Genetic Mechanism based Ant Colony Algorithm show that ACA-MO not only has better effectiveness and feasibility, but also it is improved in the areas of path length, convergence speedand fitness.The main contribution of our research work include improving the basic ant colony algorithm by using the pheromone update strategy and 2-opt local optimization strategies, limiting concentration range of pheromone, heuristic algorithm design, determining the probability of selection, and introducing mutation operator, in the meanwhile, we also applied it to the two-dimensional and three-dimensional path planning problem solving.