MEDAL Report 2007007
cAS: The Cunning Ant System
Shigeyoshi Tsutsui and Martin Pelikan  (2007)

Abstract. This paper describes the cunning ant system (cAS), which can be used to optimize problems with candidate solutions represented by permutations. cAS generates new candidate solutions from a combination of the pheromone density and the archive of past candidate solutions. Performance of cAS is demonstrated on two important classes of permutation problems: (1) the traveling salesman problem and (2)~the quadratic assignment problem. In both problem classes, cAS is shown to perform very well and outperform other techniques for solving these problems. The paper also discusses how the efficiency of cAS can be further improved by combining cAS with local search and by parallelizing cAS using a master-slave architecture. Finally, the paper presents a pheromone-density entropy measure, which can be used to measure the potential of cAS and other ACO algorithms to generate novel, fitter solutions.

Download PDF

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan