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.
Forschungs-