@techreport{f877e8fd67b0484c943e04d2da4f5689,
title = "Parallelization strategies for the ant system",
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)",
author = "Bernd Bullnheimer and Gabriele Kotsis and Christine Strau{\ss}",
year = "1997",
doi = "10.57938/f877e8fd-67b0-484c-943e-04d2da4f5689",
language = "English",
series = "Report Series SFB {"}Adaptive Information Systems and Modelling in Economics and Management Science{"}",
number = "8",
publisher = "SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business",
edition = "October 1997",
type = "WorkingPaper",
institution = "SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business",
}