Ameisenalgorithmen. Optimierung und Modellierung [online]

Kurzfassung

Ameisenalgorithmen gehören zur Klasse der populationsbasierten
zufallsgesteuerten Suchverfahren für die Lösung kombinatorischer
Optimierungsprobleme und sind inspiriert von Vorgehensweisen,
die Ameisenkolonien bei der Suche nach Nahrung verwenden. Durch
indirekte Kommunikation mittels Duftstoffmarkierung gelangen die
Ameisen in einem Prozess der Wegoptimierung schnell zu
Nahrungsquellen. Im algorithmischen Analogon wählen künstliche
Ameisen im Entscheidungsgraphen des zugrunde liegenden
Optimierungsproblems iterativ Wege, die zunehmend besseren
Lösungen entsprechen.
In dieser Arbeit werden gezielt Verfahrensmodifikationen und
Erweiterungen der herkömmlichen Ameisenalgorithmen vorgestellt,
die für bestimmte Problemklassen zu einem deutlich besseren
Optimierungsverhalten führen.
Insbesondere betrifft dies die Auswertung der gespeicherten
Duftstoffinformation und die Entscheidungsreihenfolgen, die eine
künstliche Ameise beim Aufbau einer Lösung durchläuft. Die
erfolgreiche Anwendung der entwickelten Methoden wird jeweils
anhand einfacher Probleme gezeigt, die charakteristische
Eigenschaften schwieriger Probleme widerspiegeln, und
... mehranschließend auf NP-vollständige Probleme übertragen. Die
Betrachtung des Problems der Projektplanung bei beschränkten
Ressourcen bezieht empirische Tests der Methoden an
Probleminstanzen einer bekannten Benchmark-Bibliothek ein. In
den Tests wurden die oberen Schranken für viele Instanzen
verbessert und im Vergleich zu anderen Verfahren im Durchschnitt
die besten Ergebnisse erzielt.
Probleme der Maschinenbelegung bei Beachtung mehrerer
konkurrierender Zielkriterien werden durch die Entwicklung von
Kooperationsmechanismen zwischen mehreren Kolonien von
künstlichen Ameisen erfolgreich gelöst.
Es wird ein deterministisches Modell für Ameisenalgorithmen
vorgestellt, das auf den erwarteten Aktualisierungswerten der
Duftstoffinformation basiert. Anhand dieses Modells können mit
Hilfe einer Fixpunktanalyse der in einer Matrix gespeicherten
Duftstoffinformation Aussagen über die Dynamik von
Ameisenverfahren für Permutationsprobleme getroffen werden. Das
Modellverhalten entspricht in vieler Hinsicht sehr gut dem
zufallsgesteuerten Ameisenalgorithmus und ermöglicht auch für
komplexe Optimierungsprozesse analytische Vorhersagen.