A New Rank Based Version of the Ant System

Autor(en)

Bernd Bullnheimer, Richard Hartl, Christine Strauss

Abstrakt

The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph colouring.
In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior.

Organisation(en)

Institut für Rechnungswesen, Innovation und Strategie, Institut für Business Decisions and Analytics

Externe Organisation(en)

Universität Wien

Journal

Central European Journal of Operations Research

Band

7

Seiten

25-38

ISSN

1435-246X

Publikationsdatum

1999

Peer-reviewed

Ja

ÖFOS 2012

502052 Betriebswirtschaftslehre, 101015 Operations Research, 502028 Produktionswirtschaft

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/77d81370-f4fc-4922-ba76-4eb38ac13d17