Research On The Theory And Performance Of Ant Colony Optimization

Ant colony optimization is a new meta-heuristic to solve complicated problems in combinatorial optimization. Inspired by the nature behavior of real ants in finding food, Dorigo M et al first advanced an ant colony system and the ant colony optimization algorithm(ACO) to solve several discrete optimization problems. Because of its properties of robustness, global optimization, universality and distributed computation, the theoretical research is involved increasingly deep and the application becomes increasingly large. ACO has exhibited its excellent performance and efficiency in experiments for solving a great lot of combinatorial optimization problems. After being extended and improved by many researchers, ACO is in its boosting stage.Although ant colony optimization algorithm has shown efficient performance through solving a large number of problems in the application, its success is still at the experimental level. There is little theory to explain why ant colony algorithm can solve these problems successfully. Can the algorithm ensure that the solution it got is the global optimal solution? Are there any other problems which can not be solved using ant colony algorithm? If the problem can be resolved, what is the complexity of its time? Therefore, it's necessary to do some research on the deceptive problem of ant colony optimization. Because ant colony algorithm has the nature of parallel features, we need to study how to achieve the algorithm in parallel efficiently and how to balance the relationship between the overhead of communication and speed-up ratio. One shortcoming of ant colony optimization is that it is difficult to apply it on continuous optimization problems directly. Most of the methods of solving these problems in the past have changed the basic structure of the classical ant colony algorithm.They can't make full use of the advantage of positive feedback mechanism in ant colony algorithm. It's necessary to study how to solve continuous optimization problem using ant colony algorithm without changing its model in nature and how to make full use of pheromone and heuristic information to ensure the accuracy of the solution and the speed of the convergence at the same time. In this paper, we study the problem of ant colony optimization. The main contributions of this paper include the following aspects:(1) This paper presents a first attempt towards the convergence and time complexity analysis of ACO on the deceptive systems. We prove that the first order deceptive problem of ant colony algorithm satisfies value convergence under certain initial pheromone distribution, but does not satisfy solution convergence, taking the n-bit trap problem as the test instance under consideration. In addition, we also prove that time complexity of MMAS, which is an ACO with limitations of the pheromone on each edge, on n-bit trap problem is O(n2m.logn), here n is the size of the problem and m is the number of artificial ants. Our experimental results confirm the correctness of our conclusions.(2) We present an efficient adaptive parallel ant colony algorithm (PACO). We also propose a strategy for information exchanging between processors, which is based on distance and makes each processor choose its partner to communicate and update the pheromone adaptively. In order to increase the ability of optimization and avoid early convergence, we also propose a method of adaptively adjusting the time interval according to the diversity of the solutions. Convergence of the parallel ant colony algorithm is analyzed and proved. These techniques are applied to the traveling salesman problem on the massive parallel processors (MPP) Shenteng 1800. Experimental results confirm our theoretical conclusion and show that our algorithm PACO has high convergence speed, high speedup and efficiency.(3) We propose a new approach for solving continuous optimization problems using ant colony algorithm. The method maintains the framework of the classical ant colony algorithm, and replaces discrete summation by the continuous integral, replaces discrete frequency distribution by continuous probability distribution in the ant selecting probability formula. We also use the direction towards the maximum in each dimension as the heuristic information guiding the ants'searching. Experimental results on benchmarks show that our algorithm not only has faster convergence speed than other similar methods, but also effectively improves the accuracy of solution and enhances its robustness.