Optimierung mit Ameisen

Diese Seite entstand im Wintersemester 2005/2006 im Laufe des Hauptseminars „Naturinspiriertes Rechnen“, das an der Abteilung für formale Konzepte der Fakultät für Informatik, Elektrotechnik und Informationstechnik der Universität Stuttgart durchgeführt wurde.

Die dazugehörige Ausarbeitung ist hier verfügbar: ameisen.pdf (Dateigröße: 589kByte)

Vortragsfolien zum Seminar: ameisen-folien.pdf (Dateigröße: 3.6MByte)

Vorbemerkungen

Bei hier herunterladbaren Software handelt es sich um eine in Java programmierte Machbarkeitsstudie, die nur dazu dienen soll, das Verhalten der Ameisen besser nachvollziehen zu können. Die Implementierung ist nicht auf hohe Effizienz ausgelegt und deshalb bei ziemlich langsam. Eine hocheffiziente Implementierung in C oder C++ ist mit Sicherheit um Größenordnungen schneller.

Fehler durch Fehlbedienung werden in der aktuellen Version noch nicht abgefangen.

Die Software

Die Software ist als Public Domain anzusehen. Die Verwendung und der Download der Software sind – außer den anfallenden Onlinekosten – demzufolge kostenlos.

Es wird keinerlei Garantie in Bezug auf die Software übernommen. Die Verwendung erfolgt auf eigene Gefahr. Durch das Herunterladen des Programms stimmen Sie dieser Vereinbarung implizit zu!

Download

Kompilierte Version: aco.zip (Dateigröße: 73kByte)
Die Quellen kommen, sobald diese ausreichend dokumentiert sind. :-)

Installation und Bedienung

Installation

Voraussetzung ist eine installierte Java-Laufzeitumgebung in Version 5 oder höher.

Damit die Skripte funktionieren, muss die Laufzeitumgebung muss im Pfad enthalten sein.

Bei Verwendung der vorkompilierten Version genügt es, das Archiv an beliebiger Stelle zu entpacken. Dabei ist darauf zu achten, die Verzeichnisstruktur des Archivs zu erhalten.

Programmstart

Gestartet wird das Programm über java de.jwertenauer.aco.ACO, oder über die enthaltenen Dateien aco.bat, bzw. aco.sh.

Bedienung

Die Bedienung sollte weitestgehend selbsterklärend sein. Bei Änderung der Parametereinstellungen müssen Sie in der Regel neu initialiseren. Der Parameter τ₀ muss größer als Null sein!

Sie können entweder einen einzelnen Schritt ausführen, oder meherere Schritte direkt hintereinander. Wenn Sie mehrere Schritte direkt hintereinander ausführen lassen, wird normalerweise nur das Ergebnis nach Ausführung aller Schritte angezeigt. Haben Sie die Schaltfläche jedoch mit gedrückter Umschalt-Taste angeklickt, werden in der Resultatstabelle auch die Ergebnisse aller Zwischenschritte angezeigt.

Wenn Sie beim Start der Ausführung mehrerer Schritte zusätzlich die Strg-Taste gedrückt halten, wird vor der Ausführung automatisch neu initialisiert.

Die Graphdarstellung ist wie folgt zu interpretieren: Die Kanten werden abhängig von der Menge der vorhandenen Pheromone gezeichnet. Die Kante(n) mit der höchsten Pheromonintensität werden dick und rot gezeichnet. Die übrigen Kanten werden relativ zu ihrer Pheromonintensität dünner, dunkler und transparenter gezeichnet. Da nach der Initialisierung alle Kanten die gleichen Pheromonwerte haben, sind alle Kante dick und rot dargestellt.

Wenn Sie die Maus über einen Knoten oder eine Kante bewegen, werden zusätzliche Informationen angezeigt.

Die optimalen Lösungen für die vorhandenen Probleme lauten:

Burma14: 3461 (bedingt durch eine nicht nachvollziehbare Rundung unterscheidet sich dieser Wert vom in der TSPLIB angegebenen)
Berlin52: 7542
Bier127 (eine Tour durch 127 Biergärten in Augsburg): 118282

Parameterbelegungen

Um eine brauchbare Parameterbelegung zu ermitteln, wurden einige Tests durchgeführt. Die gemessenen Werte sind hier als OpenOffice.org 2.0 Tabellendokument verfügbar: tests.ods (Dateigröße: 49kByte)

Die in der Software vorgegebenen Default-Parameter-Werte entsprechen den Werten, die als am brauchbarsten ermittelt wurden.

Screenshots


(Größe: 141kByte)	(Größe: 68kByte)	(Größe: 172kByte)