Projects per year
Abstract
Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.
Original language  English 

Title of host publication  Proceedings of the 12th annual conference on Genetic and evolutionary computation 
Pages  13931400 
Number of pages  8 
DOIs  
Publication status  Published  11 Jul 2010 
Event  Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10)  New York, United States Duration: 11 Jul 2010 → … 
Conference
Conference  Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) 

Country/Territory  United States 
City  New York 
Period  11/07/10 → … 
Fingerprint
Dive into the research topics of 'Ant Colony Optimization and the Minimum Cut Problem'. Together they form a unique fingerprint.Projects
 2 Finished

Postdoctoral Research Fellowship  Rigorous Runtime Analysis of Nature Inspired Metaheuristics
Oliveto, P.
Engineering & Physical Science Research Council
1/08/10 → 30/09/13
Project: Research Councils

SEBASE: Software Engineered By Automated SEarch
Engineering & Physical Science Research Council
29/06/06 → 28/12/11
Project: Research Councils