Ant Colony Algorithm And Its Application

A wonderful self-organization behavior will usually be produced from the collective behavior of social animals. Take a colony of ants for example, simple and blind ants can find the shortest routing path from their nest to food source. Biologists had studied the phenomenon carefully and found that ants cooperate to find the shortest routing path by means of indirect communications using a kind of substance call "pheromone" . Inspired by this phenomenon, a population-based simulated evolutionary algorithm called ant colony algorithm (ACA for short) was proposed by Italian researchers M. Dorigo, V. Maniezzo and A. Colorni. Many scholars are attracted to study ACA and in the past ten years than more the algorithm has been widely applied to the fields of combinatorial optimization, function optimization, system identification, network routing, path planning of robot, data mining and premises distribution of large scale integrated circuit etc, and good effects of application are gained.This paper focuses on the principles, theory, and applications of ACA, especially, an in-deep and systemic study on how to improve the basic ACA algorithm, parallel implementation of ACA, solving the problems such as combinatorial optimization, function optimization, and main-steam temperature control system at power plant. The main achievements of this paper include:1. A backtracking ant system (BAS) was proposed. In BAS, a new type of ants that is called backtracking ants (BA) is used to find mew routes, in a manner similar to the sampling of the surrounding subregion in the NP algorithm. In addition to using maximum and minimum values for the pheromone's trails to avoid stagnation, the BAS algorithm obliged the ants to select new routes by random selecting an edge of the best solution and forcing the ants to avoid this edge and then update the pheromone matrix using a tour different than the best found. Simulated experiments show that the results obtained by the BAS algorithm are comparable to the MMAS in case of the symmetric TSP instances and the asymmetric instances.2. An ant colony optimization with multiple ant clan (ACOMAC) was proposed. Inspired by the concept from parallel genetic algorithm, this algorithm searches solutions space that using different islands to avoid local minima and so as to obtain global minimum for solving the TSP problem. Simulated experiments for the TSP on several bench show the validity and the feasibility of the proposed algorithm, and that the algorithm performs better than the ant system (AS) and the ant colony system (ACS).3. A parallel ant colony system (PACS) was proposed to solve the large traveling salesman problem. Other than the prevenient parallelization strategy, we apply the concept of parallel processing to the ant colony system. In the algorithm the artificial ants are separated into several groups, and the ant colony system is then applied to each group, and each group may communicate each other, that is to say each group updates their pheromone level for each route according to the best route found by neighboring groups. This algorithm not only reduces the computation time but also obtains a better solution. Experimental results based on the traveling salesman problem confirm the efficiency and effectiveness of the proposed PACS, and it also confirm that the proposed PACS is superior to the existing ant colony system (ACS) and ant system (AS).4. A hybrid algorithm for function optimization called genetic algorithm and ant algorithm (GAAA) was proposed. The algorithm is based on genetic algorithm and ant algorithm. The basic idea is that we adopt genetic algorithm with its properties of speediness, randomicity and global convergence to give information pheromone to distribute firstly, and then we adopt ant algorithm with its properties of parallelization, positive feedback mechanism and high efficiency to enhance the efficiency under the condition of having some initial pheromone distribution. Experimental results show that the proposed GAAA is a effective algorithm for function optimization with good time efficiency and solving efficiency.5. An algorithm for parameter optimization of the cascade PID control system of main-steam at power plant was proposed. The algorithm adopts the moment integral of absolute error as the assessment index to optimized the control system; Then we add neighboring searching mechanism to find better solution during the course of ant searching. Experimental results show that the proposed algorithm for parameter optimization of main-steam control system is effective and feasible, moreover it performs better than the traditional methods and genetic algorithm.Finally, the work of this paper is summarized and the prospective of future research is discussed.