Algorithmen

des Zielfunktionswerts der neuen Lösung x’ gegenüber der bisher besten Lösung x als zulässig erachtet werden. Im Laufe des Verfahrens wird die Temperatur, nach einem vorher festzulegenden Abkühlungsplan, sukzessive reduziert. Damit sinkt die Wahrscheinlichkeit im Laufe des Verfahrens, dass Verschlechterungen in den Lösungen akzeptiert werden. Die Schwierigkeit der Konfiguration des Verfahrens liegt in der Festlegung der Parameter: Zum einen muss die Starttemperatur festgelegt werden. Diese sollte am Anfang relativ hoch sein, denn nur dann wird ein bestimmtes Ausmaß an „schlechten“ Lösungen akzeptiert, was eine breitere Lösungssuche garantiert. Das wiederum soll verhindern, dass das Verfahren nur auf ein lokales Optimum zusteuert. Die Berechnung der Starttemperatur geschieht in der Weise, dass vorgegeben wird, mit welcher (durchschnittlichen) Wahrscheinlichkeit eine Lösung akzeptiert wird, die um einen bestimmten Prozentsatz schlechter ist als die bislang beste Lösung.
    Als Nachteil des SA wird in der Literatur der relativ hohe Rechenaufwand des Verfahrens genannt, der hauptsächlich durch die Exponentialfunktion hervorgerufen wird. Diese Aussage muss differenziert betrachtet werden: Zum einen sind natürlich Rechenoperationen unter Einbeziehung von Exponentialfunktionen deutlich aufwändiger, als wenn nur die elementaren Grundrechenarten zur Anwendung gelangen. Das gilt insbesondere dann, wenn für die Ausführung einer Lösungssuche und Lösungsverbesserung der Algorithmus vielfach durchlaufen wird. Anfänglich sehr marginal erscheinende Zeitdifferenzen können sich dann sehr schnell zu messbaren zeitlichen Verzögerungen summieren. Anderseits muss man deutlich sagen, dass selbst komplexe Berechnungen durch die heutigen Prozessoren sehr schnell ausgeführt werden. Die zugrunde liegenden Algorithmen in den Basisbibliotheken der Betriebssysteme und Frameworks sind ausgereift und entsprechend optimiert. Daher ist die Aussage bezüglich der Rechenzeiten immer im Einzelfall zu prüfen und die tatsächlichen zeitlichen Engpassstellen sind zu ermitteln.
    Es existieren verschiedene Varianten des SA-Verfahrens. Zwei bekannte Verfahren sind das Threshold-Accepting-Verfahren und die Sintflut-Strategie . Die Sintflut-Strategie kann für Maximierungsprobleme (Suche nach einem größtmöglichen Wert) leicht erläutert werden: Bei dieser Metaheuristik werden Lösungen akzeptiert, solange der Zielfunktionswert den aktuell gültigen Akzeptanzwert nicht unterschreitet. Dieser Akzeptanzwert steigt – bildlich wie der Wasserspiegel einer Sintflut – bis zum Abbruch des Verfahrens. Das Threshold-Accepting-Verfahren wurde um 1990 von Dueck und Scheuer entwickelt [9]. Akzeptiert werden neue Lösungen, deren Zielfunktionswert entweder besser ist oder die Verschlechterung eine vorgegebene Akzeptanzschwelle (threshold) nicht überschreitet. Die Akzeptanzschwelle wird im Laufe des Suchprozesses gesenkt. Erfolgskritisch sind die Festlegung des Ausgangsschwellenwerts und der Prozess des Absenkens des Schwellenwerts.

2.1.4Ameisenalgorithmus
    Der Name ist hier Programm. Es geht tatsächlich um das Verhalten von Ameisen. Dabei handelt es sich um ein relativ neues Verfahren. Erstmalig wurde es von Dorigo u. a. [10] vorgellt. Das Verfahren bildet das natürliche Verhalten von Ameisen bei der Futtersuche nach. Um potenzielle Futterstellen zu finden, suchen die Ameisen ihre Nachbarschaft ab. Auf dem Weg vom Nest zur Futterstelle hinterlässt jede Ameise eine Duftspur (Pheromonspur). Diese Pheromonspur kann von der Ameise selbst auf dem Rückweg, aber auch von anderen Ameisen erkannt werden. Gibt es mehrere mögliche Wege zwischen Nest und Futterstelle, wird mit der Zeit auf dem kürzesten Weg eine höhere Konzentration des Duftstoffs vorliegen, sodass die Ameisen bevorzugt diesen Weg wählen. Kommen wir an dieser Stelle wieder zum praktischen Anwendungsfall der Suche nach dem kürzesten Weg zurück: Die Nachbarschaft, durch die sich die künstlichen Ameisen bewegen, lässt sich als Graph bezeichnen. Die Punkte sind dabei die Knoten und die Verbindungen die Kanten eines gegebenen Routenproblems (Kasten: Ein kleines Lexikon – Begriffe im Überblick). Damit die Ameisen den Weg zum Ziel finden, müssen sie bei jeder Iteration einen Schritt innerhalb ihrer unmittelbaren Nachbarschaft durchführen. Am Anfang wird auf allen Kanten die identische Menge Pheromon platziert. Die Entscheidung über alternative Wege wird anhand der