B. Bullnheimer, C. Strauss, Gabriele Kotsis,
"Parallelization Strategies for the ANT System"
: High Performance Algorithms and Software in Nonlinear Optimization, Kluwer International Series in Applied Optimization, Volume 24, Vol. 24, Kluwer Academic Publishers, Dordrecht, 1998, ISBN: 0-7923-5483-4

Original Titel:

Parallelization Strategies for the ANT System

Sprache des Titels:

Englisch

Original Buchtitel:

High Performance Algorithms and Software in Nonlinear Optimization, Kluwer International Series in Applied Optimization, Volume 24

Original Kurzfassung:

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.

Sprache der Kurzfassung:

Englisch

Englischer Titel:

Parallelization Strategies for the ANT System

Englische Kurzfassung:

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.