Parallelizing Ant Colony Optimization Algorithms

Thomas Stützle, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Alexanderstr. 10, 64283 Darmstadt, Germany
Email: , Tel: +49-6151-166651, Fax: +49-6151-165326

Ant Colony Optimization is a new population oriented search metaphor that has been successfully applied to NP-hard combinatorial optimization problems. We discuss parallelization strategies for Ant Colony Optimization algorithms distinguishing between two basic possibilities for the application of parallel processing. One is to improve the computational results by parallel runs of an ACO algorithm, the other possibility is to speed up the execution of a single run. Some preliminary results on the effectiveness of the first aspect using parallel independent runs of an ACO algorithm, suggest that the potential improvement obtained by parallel processing can be substantial.