Parallelization strategies for the ant system

Bernd Bullnheimer, Gabriele Kotsis, Christine Strauß

Publication: Working/Discussion PaperWU Working Paper

46 Downloads (Pure)

Abstract

The Ant System is a new meta-heuristic method particularly appropriate to solve hard combinatorial optimization problems. It is a population-based, nature-inspired approach exploiting positive feedback as well as local information and has been applied successfully to a variety of combinatorial optimization problem classes. The Ant System consists of a set of cooperating agents (artificial ants) and a set of rules that determine the generation, update and usage of local and global information in order to find good solutions. As the structure of the Ant System highly suggests a parallel implementation of the algorithm, in this paper two parallelization strategies for an Ant System implementation are developed and evaluated: the synchronous parallel algorithm and the partially asynchronous parallel algorithm. Using the Traveling Salesman Problem a discrete event simulation is performed, and both strategies are evaluated on the criteria "speedup", "efficiency" and "efficacy". Finally further improvements for an advanced parallel implementation are discussed. (author's abstract)

Publication series

SeriesReport Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
Number8

WU Working Paper Series

  • Report Series SFB \Adaptive Information Systems and Modelling in Economics and Management Science\

Cite this