Research On Several Issues In Ant Colony Optimization Approach

Ant colony optimization (ACO) is a metaheuristic, which was inspired from thecollectively foraging behavior of ant colonies in nature. It has been used widely for solv-ing many complex optimization problems in the field of various engineering and science.Examples are dynamic routing control in networks, a variety of classical combinatorialoptimization problems, and so on. ACO consists of a colony of artificial ants with a fewsimple operations, but can solve very complex optimization problems to a satisfactorylevel. This made ACO to become one of hot research topics in the field of artificial in-telligence. Many scholars improved the performance of ACO, built the theory of ACO,applications of ACO, and so on. However there are still many open problems on ACO tobe solved. For example, how should the parameters be set? And how does the pheromonerepresent the problem under consideration? And what type of problems can ACO solve?This thesis systematically analyzed the research works about ACO, and researched onthe performance of ACO, analysis of ACO model, multi-colony ACO and pheromonerepresentation.Firstly, two technologies improving Max-Min Ant System (MMAS) were studied.A new pheromone updating technology was supposed for MMAS when solving the staticcombinatorial optimization problems. The new updating rules were operated on the totalinformation, and could remove the operations of calculating the total information andcheck the pheromone bounds at each iteration in MMAS. A construction rule based onthe evidence of the optimum of the small-scale instances was presented to quickly guidethe ant colony to the subspace which may contain the optimal solutions of the large-scaleinstances being solved. However, this constructing rule weakened the learning capacityof MMAS. To overcome this question a two-stage construction rule was presented. Ex-perimental results showed that these technologies could reduce significantly the elapsedtime and improve the performance of MMAS when solving the large-scale instances.Secondly, two information exchange technologies among colonies were studied formulti-colony ACO algorithm. One was supposed by introducing the moving rule of the'particle'in the particle swarm optimization (PSO) metaheuristic. This method onlyneeds to exchange a small amount of data and a few of pheromone updating operations.The other was inspired from the moving rule of the'probe'in the central force optimiza-tion (CFO) metaheuristic. Averagely, this technology needs to exchange the data and pheromone updating operations less than of the best method reported before. And ex-change information was different for different colonies. Experimental results showed thatthis two exchange information technologies outperform slightly the classical method.Thirdly, ACO algorithms for solving the strongly NP-hard knapsack problem werestudied. An improved ACO algorithm for solving the multidimensional knapsack prob-lem (MdKP) was supposed. A simple pheromone representation was used. And thislowered the time complexity of constructing a solution of MdKP. To use the structureknowledge of MdKP in the representation, a new heuristic information based on a sort ofall knapsack items was supposed. Experimental results showed that our new algorithmperformed significantly over those ACO algorithms published before. The multidimen-sional multichoice knapsack problem (MdMcKP) is the extension of MdKP, which hasstronger constraints. However, MdMcKP has a particular structure which can be usedby ACO metaheuristic. Thus an ACO algorithm was supposed for solving MdMcKP.Compared with other heuristic algorithms published before, the ACO algorithm was oneof two best algorithms.Finally, the search behaviors and time complexity of ACO models were studied.A deterministic ACO model for solving the k minimum spanning tree (kMST) prob-lem was built, which was competitive-balance. The convergence of models using typicalpheromone updating technologies were analyzed by experiments. Then, several modelsfor solving the general combinatorial optimization problems were built. And the con-vergence of them proved strictly. At last, the time complexity of a ACO model whichcould converge to the optimal solution was presented. And a lower bound of the timecomplexity of ACO algorithms was obtained as a corollary.