Parallelization strategies for the ant system

Autor(en)

Bernd Bullnheimer, Gabriele Kotsis, Christine Strauss

Abstrakt

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.

Organisation(en)

Institut für Rechnungswesen, Innovation und Strategie

Band

8

Anzahl der Seiten

15

Publikationsdatum

10-1997

ÖFOS 2012

101015 Operations Research, 502052 Betriebswirtschaftslehre, 102025 Verteilte Systeme

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/404ec079-2622-4196-b5af-feace85c316d