Improved Ant Colony Algorithms For Two Classes Of Combinatorial Optimization Problems

Combinatorial optimization is the important branch in the field of optimization. It has wide applications in practical. Inspired by the behavior of real ants, a population-based metaheuristic algorithm, called Ant Colony Algorithm (ACA), was proposed by Italian researchers M. Dorigo etc in 1991. In the past ten years, ACA has been successfully applied to the combinatorial optimization problems such as TSPs.This paper first describes some concepts about combinatorial optimization problems and computational complexity. Then we focus on the principles, theory and applications of ACA, especially, an in-deep study on how to improve the basic ACA. The main achievements of this paper include:1. Based on convergence theory of ACOb s,τminalgorithm, we prove the convergence of Ant Colony System (ACS). Then three improvements are presented, that is candidate sets strategy, local search and initialization of pheromone trails. Finally, we discuss their influences on the convergence of ACS.2. Three improved ACS for TSP are proposed:①The first algorithm is called ACS based on restricted candidate list (RCL). In this one, the novel candidate list is introduced into ACS. It adjusts the size of candidate lists randomly and avoids setting lists repeatedly.②The second is called ACS base on TSPs'geometry structure. We define a quadrant neighbor candidate list according to the TSPs'geometry. In the initial stage, we design a dual quadrant neighbor method to initialize the pheromones.③The third one is called ACS based on dynamic candidate sets of minimum spanning 1-tree. The concept of minimum 1-tree is presented to constructα-dynamic candidate list. Under MATLAB, the experiments show that three algorithms are better than the basic ACS algorithm. Moreover, the second algorithm is the best of the three.3. An improved ant algorithm for DCMST is proposed. In this algorithm, we design the degree-based tabu list and propose the concept of degree information to improve transition probability that makes solutions feasible. Then we use mutation as local search to improve obtained trees. The computational results indicate that the algorithm not only improve the quality of the solution but also avoid stagnation. Finally, we develop our algorithm to solve MTSP and give the concrete method.