Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | High Performance Algorithms and Software in Nonlinear Optimization, Kluwer International Series in Applied Optimization, Volume 24 |
| Place of Publication | Dordrecht |
| Publisher | Kluwer Academic Publishers |
| Volume | 24 |
| ISBN (Print) | 0-7923-5483-4 |
| Publication status | Published - 1998 |
Fields of science
- 102 Computer Sciences
- 102002 Augmented reality
- 102006 Computer supported cooperative work (CSCW)
- 102013 Human-computer interaction
- 102015 Information systems
- 102021 Pervasive computing
- 102025 Distributed systems
- 102027 Web engineering
- 202038 Telecommunications