Resource title

Parallelization strategies for the ant system

Resource image

image for OpenScout resource :: Parallelization strategies for the ant system

Resource description

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) ; Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Resource author

Bernd Bullnheimer, Gabriele Kotsis, Christine Strauß

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://epub.wu.ac.at/1362/1/document.pdf

Resource license

Adapt according to the license agreement. Always reference the original source and author.