Algorithmen

Pheromonmenge getroffen. Ist eine Ameise am nächsten Knoten angekommen, wird die Pheromonmenge der zuletzt zurückgelegten Strecke erhöht. Dabei steigt auf Wegen mit einer kürzeren Strecke die Pheromonkonzentration schneller.
    Dieser Such- und Updateprozess wird solange wiederholt, bis eine künstliche Ameise den Zielort gefunden hat und wieder zum Ausgangsort zurückgekehrt ist. Zur Vermeidung lokaler Optima wird mithilfe einer so genannten Verdunstungsfunktion die Pheromonmenge bei jeder Iteration um eine vorgegebene Menge reduziert. Weitere Informationen zu diesem Verfahren können unter [11] nachgelesen werden.

2.2Praktische Programmierung
    Nach so viel Theorie betrachten wir jetzt einige Möglichkeiten, die Konzepte im eigenen Programm anzuwenden. Grundsätzlich bieten sich zwei Lösungsansätze an:
Der Rückgriff auf eine fertige Bibliothek. Metaheuristiken arbeiten (weitgehend) problemunabhängig. Eine Softwarebibliothek, die den Algorithmus bereitstellt, kann ein guter Lösungsansatz sein. Die eigene Problemstellung ist einzubinden und das Lösungsverfahren wird dann über diese Metaheuristik gesteuert. Die Parameter sollten gut an die Besonderheit der Problemstellung anpassbar sein. Wichtige andere zu beachtende Punkte sind: Lizenzgebühren, Verfügbarkeit des Quellcodes und der Dokumentation und die verwendete Programmiersprache, in der die Bibliothek implementiert wurde.
Durchführung einer vollständigen eigenen Programmierung. Damit ist eine optimale Problemanpassung möglich. Anderseits genügt es nicht, das grundsätzliche Vorgehen der Metaheuristik verstanden zu haben, entsprechendes Detailwissen ist notwendig.
    Einen interessanten Ansatz stellt die Bibliothek Open Metaheuristic (oMetah) dar [13]. Sie wurde in C++ entwickelt und stellt den Ameisenalgorithmus, Genetische Algorithmen und das Simulated-Annealing-Verfahren zu Verfügung. Auch für andere Betriebssysteme stehen fertige Implementierungen in Form von Bibliotheken zur Verfügung. Beispielsweise The Genetic Algorithm Utility Library (GAUL) die für Linux-Betriebssysteme zum Einsatz kommen kann. Sie enthält allgemeinen Code zur Programmierung von primär Genetischen oder Evolutionären Algorithmen. Darüber hinaus sind weitere Implementierungen vorhanden, zum Beispiel Ansätze zur Programmierung von Tabu-Suche, Simulated-Annealing-Verfahren bzw. zur Lösung von Gleichungssystemen mittels Simplex-Algorithmus. Mehrere Technologien werden von der Bibliothek OptiGen Library - Genetic Software [14] bedient. Angeboten werden Implementierungen für die Verwendung in C++, .Net und als Zugriff über COM-Schnittstelle (als ActiveX).
    Wir zeigen die Implementierung eines Simulated-Annealing-Verfahrens in C# und .Net in Grundzügen. Zu entwickeln ist der Rahmencode, in der später das problemspezifische Lösungsverfahren eingebettet wird. Die Demonstration der Arbeitsweise einer Metaheuristik setzt die Lösung eines konkreten Problems voraus. Aus Gründen der Einfachheit wird das bekannte Traveling-Salesman-Problem gelöst. Ein sehr kompaktes Beispiel für die Lösung des TSP mithilfe des SA-Algorithmus stammt von [15] und wird hier verwendet. Den entscheidenden Quellcodeausschnitt der implementierten Metaheuristik zeigt Listing 1. Nach der Initialisierung der Variablen folgt eine while -Schleife. Innerhalb dieser Schleife wird nach neuen Lösungen gesucht (Methode GetNextArrangement ). Eine Lösung wird dann akzeptiert, wenn sie besser ist als die bisher beste Lösung oder wenn das Akzeptanzkriterium (unter Berücksichtigung der aktuellen Temperatur im Vergleich mit einer Zufallsvariable) erfüllt ist. Die Reduzierung der Temperatur bei jedem Schleifendurchlauf ( temperature *= coolingRate ) führt dazu, dass mit weiterem Fortschritt des Verfahrens die Wahrscheinlichkeit für die Akzeptanz einer Lösung – die schlechter als die bisher beste Lösung ist – abnimmt.
    Das Programm ist eine Konsolenanwendung und erzeugt für eine Problemkonstellation (Koordinaten von Orten innerhalb der Datei Cities.txt ) eine Lösung. Dass es sich teilweise um ein zufallsgesteuertes Verfahren handelt, wird deutlich, wenn das Programm mehrfach gestartet wird. Sowohl die Lösungen als auch die Lösungsgüte (Reihenfolge der Orte, Entfernung zwischen den Orten) ist unterschiedlich. Bei der Weiterentwicklung in der Praxis kommt es nun darauf an, das Verfahren so zu gestalten, dass die wiederholte Anwendung des Verfahrens zu Lösungen führt, die eine ähnliche Qualität