Parallelization Strategies for the Ant System

Bernd Bullnheimer, Gabriele Kotsis, Christine Strauss

Veröffentlichungen: Beitrag zu KonferenzPaperPeer Reviewed

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 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.
OriginalspracheEnglisch
Seiten87-100
Seitenumfang13
DOIs
PublikationsstatusVeröffentlicht - 1997
VeranstaltungHigh Performance Software for Nonlinear Optimization: Status and Perspectives - Ischia, Italien
Dauer: 4 Juni 19976 Juni 1997

Konferenz

KonferenzHigh Performance Software for Nonlinear Optimization
KurztitelHPSNO'97
Land/GebietItalien
OrtIschia
Zeitraum4/06/976/06/97

ÖFOS 2012

  • 101015 Operations Research
  • 202005 Computer Architektur
  • 102029 Praktische Informatik

Zitationsweisen