Ant Colony Optimization
- Martin Middendorf (Institut für Informatik der Universität Leipzig)
Abstract
Ant Colony Optimization (ACO) ist eine vom Wegfindungsverhalten realer Ameisen inspirierte iterative Metaheuristik, die mittlerweile zur Lösung einer Vielzahl von kombinatorischen Optimierungsproblemen erfolgreich eingesetzt worden ist.
Im ersten Teil des Vortrags diskutieren wir Aspekte, die für die Anwendung von ACO wichtig sind. Dabei geht es beispielsweise um die geeignete Nutzung der Information, die zwischen den Iterationen weitergegeben wird (die sogenannte Pheromoninformation), um multikriterielle Optimierung und um Varianten von ACO-Algorithmen.
Im zweiten Teil des Vortrags stellen wir Modellierung als eine Methode vor, die dazu dient, ein besseres Verständnis der Dynamik von ACO zu gewinnen. Anhand eines deterministischen Modells zeigen wir, wie das Optimierungsverhalten in sehr komplexer Weise von der Pheromoninformation und vom Grad der Konkurrenz zwischen den Ameisen beeinflusst wird. Als Resultat dieser Untersuchungen ergeben sich praktische Vorschläge, um das Optimierungsverhalten von ACO-Algorithmen zu verbessern.