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. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
| Identifer | oai:union.ndltd.org:VIENNA/oai:epub.wu-wien.ac.at:epub-wu-01_1c4 |
| Date | January 1997 |
| Creators | Bullnheimer, Bernd, Kotsis, Gabriele, StrauĂ, Christine |
| Publisher | SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business |
| Source Sets | Wirtschaftsuniversität Wien |
| Language | English |
| Detected Language | English |
| Type | Working Paper, NonPeerReviewed |
| Format | application/pdf |
| Relation | http://epub.wu.ac.at/1362/ |
Page generated in 0.0018 seconds