Research On Improved Ant Colony Optimization

Ant Colony Optimization (ACO) is a novel algorithm which is proposed by Italian scholars Dorigo whose inspiration is sparkled by watching ants searching for food. After lots of experiments ACO has exhibited its excellent performance and efficiency in experiments for solving a great lot of combinatorial optimization problems, and now it is used in many areas. But compare to other bionics evolution algorithms ACO has disadvantages such as long-time searching and local best solution and so on. This paper offers three improved algorithms in order to overcome these disadvantages, and TSP can be solved by using these improved algorithms. The main works of this paper include:1. A novel ACO algorithm which is an improved algorithm based on adaptively adjusting parameterα,βhas been proposed. When best solution has not changed after several generations, the novel ACO algorithm adaptively adjusts the parameterα,βto improve the global ability of the solution. The simulations for TSP show that the improved ACO algorithm can find better best solution and have better convergence than basic ACO.2. A novel ACO algorithm which is based on adaptively adjusting pheromone decay parameterρhas been proposed. When best solution has not changed after several generations, the novel ACO algorithm adaptively adjusts the parameterρto improve the global ability of the solution and it has been proved that for a sufficiently large number of iterations, the probability of finding the global best solution tends to 1. The simulations for TSP problem show that the improved ACO can find better routes than basic ACO.3. A novel hybrid algorithm which is a combination of GA (Genetic Algorithm) and ACO has been proposed. The algorithm imports cross operator and mutation operator after reserving the intersection of the first best solution and the second best solution in every evolution. The manipulation of reserving the intersection accelerates convergence speed. The manipulation of importing cross operator and mutation operator broads the solution space and improves the global ability of the algorithm and by using Markov progress. It has been proved that for a sufficiently large number of iterations, the probability of finding the satisfied solutions tends to 1.The simulations for TSP problem show that the improved algorithm has better convergence effective and global ability.Finally, the work of this thesis is summarized and the prospective of future research is discussed.