Parallelization strategies for the ant system

Bernd Bullnheimer, Gabriele Kotsis, Christine Strauss

Veröffentlichungen: Working Paper

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.
OriginalspracheEnglisch
ErscheinungsortWien
HerausgeberSFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, Vienna.
Seitenumfang15
Band8
PublikationsstatusVeröffentlicht - Okt. 1997

ÖFOS 2012

  • 101015 Operations Research
  • 502052 Betriebswirtschaftslehre
  • 102025 Verteilte Systeme

Fingerprint

Untersuchen Sie die Forschungsthemen von „Parallelization strategies for the ant system“. Zusammen bilden sie einen einzigartigen Fingerprint.
  • Parallelization Strategies for the Ant System

    Bullnheimer, B., Kotsis, G. & Strauss, C., 1998, High Performance Algorithms and Software in Nonlinear Optimization. De Leone, R., Murli, A., Pardalos, P. & Toraldo, G. (Hrsg.). Boston, MA: Springer, Band 24. S. 87-100 (Applied optimization).

    Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

Zitationsweisen