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 problems. 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
- Seiten
- 87-100
- Anzahl der Seiten
- 13
- DOI
- https://doi.org/10.1007/978-1-4613-3279-4_6
- Publikationsdatum
- 1997
- Peer-reviewed
- Ja
- ÖFOS 2012
- 101015 Operations Research, 202005 Computer Architektur, 102029 Praktische Informatik
- Link zum Portal
- https://ucrisportal.univie.ac.at/de/publications/66b729fb-4f67-4922-9996-12c407b3206a