| Ant Colony Algorithm is a new evolution optimization algorithm based on bionics, and is another intelligent optimal algorithm after the fire out simulation, the inheritance, and the prohibition search etc. Ant Colony Algorithm was first proposed by Marco Dorigo and his colleagues. Now it has been successfully applied to solve a series of NP-complete combination optimization problems, such as Traveling Salesman Problem, Quadratic Assignment Problem, Vehicle Routing Problem, Graph Coloring Problem and so on. Ant Colony Algorithm with the discrete combination optimization problems with an outstanding performance has attracted people's attention since it was proposed just a dozen years ago.In this dissertation, against to the drawbacks of a slow converges and an easy stagnation with the Ant Colony Optimization Algorithms, two new improved algorithms was proposed. The two algorithms are described as below:1. Improved ant algorithm for TSP problem. Based on MAX-MIN ant system with roulette wheel (MMAS+RW),a subsection mutation ant system (SMAS) of solving TSP is put forward. It combines ant colony algorithm with subsection and mutation of genetic algorithms (GA). On the condition of falling in local best solutions of ant colony algorithm, it can improve the precision. The simulation results show that better effects are obtained.2. Improved ant algorithm for multi-dimensional 0-1 knapsack problem (MKPACA). 0-1 knapsack problem is a typical of NP-complete problem, as well as the ant colony algorithm has successfully resolved many combinatorial optimization problems. Therefore, in this dissertation, a multi-dimensional solution has been proposed to the 0-1 knapsack problem and it has achieved a better quality of the solution when the number of items is large than the classical ant algorithm. By optimizing it, it greatly reduces the searching time of ant colony algorithm. It also effectively ameliorates the disadvantage of easily falling in local best of ant colony algorithm. |
PDF Full Text Request