A service provided by the WU Library and the WU IT-Services

Parallelization strategies for the ant system

Bullnheimer, Bernd and Kotsis, Gabriele and Strauß, Christine (1997) Parallelization strategies for the ant system. Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science", 8. SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, Vienna.

[img]
Preview
PDF
Download (199Kb) | Preview

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. (author's abstract)

Item Type: Paper
Keywords: kombinatorische Optimierung / Parallelverarbeitung / paralleler Algorithmus / Travelling-salesman-Problem
Divisions: Departments > Informationsverarbeitung u Prozessmanag. > Produktionsmanagement > Taudes
Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Departments > Marketing > Service Marketing und Tourismus
Departments > Informationsverarbeitung u Prozessmanag. > Informationswirtschaft
Depositing User: Repository Administrator
Date Deposited: 07 Mar 2002 17:11
Last Modified: 14 Sep 2010 23:37
URI: http://epub.wu.ac.at/id/eprint/1362

Actions

View Item