Improvement And Application Of Ant Colony Algorithm

Ant colony algorithm (AC) has emerged recently as a new meta-heuristic for NP-hard problems in combinatorial optimization. This meta-heuristic also includes evolutionary algorithms, neural networks, simulated annealing which all belong to the class of problem-solving strategies derived from nature. Dorigo, Maniezzo, and Colorni [Dorigo M, Maniezzo V, Colorni A., 1996], using the Traveling Salesman Problem (TSP) [Dorigo M, Gambardella L. M.,1997] as example, introduced the first AC algorithm. With the further study in this area, ant colony algorithm is widely applied to the problems of Job-shop Scheduling Problem (JSP)[ Colorni A., Dorigo M, Maniezzo V.,1994], the Quadratic Assignment Problem (QAP)[ Maniezzo V,1999, Maniezzo V, Carbonaro A.,2000], the Sequential Ordering Problem (SOP)[Gambardella L. M., Dorigo M.,1997] and some other NP complete problems. It demonstrates its superiority of solving complicated combinatorial optimization problems.But,there are still some faults in ant colony algorithm. Firstly, the diversity and stability of the solutions searched by ant colony are in conflict with convergence speed of the algorithm. The reason is that the movements of the individuals in ant colony are stochastic though they can evolve to the optimal path by interchange information, and they can hardly find a optimum one from a mass of paths within a short time when the problem scale is large enough, eyelessly accelerate the convergence speed will make the ants' local search and lead to premature and stagnation of the algorithm easily. Secondly, classical ant colony algorithm demands of discrete solution space since each ant only can selete limitedly at each step, so this algorithm is useful for discrete optimization problems such as combinational optimization problem, but not suitable for solving optimization problems with continuous space such as linear or non-linear programming problems.In this paper, we first introduce classical ant colony algorithm and give a summary about its current research work. In chapter four, we analyze the essence of its search processe , produce four kinds of new unproved algorithms, and discuss our intending research work in this area.The first algorithm is based on the equilibrium of ant distribution, in this method,the distribute area of ants in the interation were adjusted automaticly, and the pheromone on the trail was updated differently according the quality of the solution it constructed. The second algorithm is produced according to the sensor and consciousness behavior of ants, the optimization process was looked as three distinguished phase, and in each phase we use different optimiazation mechanism. Thus, the blindness trail selection only by pheromone was avoided successfully. The third algorithm is an improved augment ant colony optimization method.it uses the operations of crossover and mutation of GA and has higher capacity of global optimization. The fourth algorithm introduces density control mechanism in immunogenetics to adjust the distribute of ants, and the ant colony is devided into some small independent colonies using niche technology in the iteration process. The experimental results show that these four algorithms overcome the conflict between the convergence speed and solution diversity, and avoid the premature and phenominon efficiently.In our research work, we find a noteworthy defect of basic ant colony algorithm that it is not suitable for solving continuous optimization problem. So, in chaper five, we bring forward a new novel algorithm to which crossover and mutation operation is added , and the experimental results tested on non-linear programming problems demenstrate the superiority of our method ,it shows that this algorithm is suitable for solving continus problems especially such problems with large scale.Meanwhile,, we also make full use of the ants' capability of finding optimal solutions, applicate the ant colony algorithm to 0-1 Knapsack problem ,Weapon Target Assignment problem, Flow-Shop problem. Particularly, we produce an improved...