Algorithmen

Die Suche erfolgt durch eine wiederholte Anwendung von Operationen auf die codierten Lösungen. Ein wichtiger Operator ist der so genannte Crossover-Operator, der durch den Austausch codierter Lösungsbestandteile zwischen zwei Lösungen eine neue Lösung erzeugt. Die Wahrscheinlichkeit, dass eine erzeugte Lösung im weiteren Reproduktionsprozess verwendet wird, steigt mit der individuellen Fitness dieser Lösung. Das verwandte Konzept der Evolutionären Strategien wurde von Reichenberg und Schwefel entwickelt [7], [8]. Auch hier wird mit Populationen von Lösungen gearbeitet. Dabei erfolgt keine Codierung der Lösungen. In einer ersten Initialisierungsphase wird eine Elterngeneration mit einer bestimmten Zahl μ von Individuen erzeugt. Es schließt sich der eigentliche Reproduktions- und Selektionsprozess an, der wiederholt ausgeführt wird. Dieser gliedert sich in mehrere Schritte: In einem ersten Schritt erfolgt die Auswahl der Eltern aus der Ausgangspopulation, aus der die Nachkommen gebildet werden. Dies geschieht stochastisch mit der gleichen Wahrscheinlichkeit für alle Individuen. Ist eine Rekombination vorgesehen, wird sie auf die ausgewählten Lösungen angewendet. Im nächsten Schritt wird auf die entstandenen Lösungen ein Mutationsoperator angewendet. Dabei handelt es sich um eine zufällige und geringfügige Veränderung. Der Umfang der Mutation wird durch die Mutationsschrittweite bestimmt, die selbst einer dynamischen Anpassung während des Suchprozesses unterliegen sollte (Selbstadaption). Die durch die Mutation erzeugten Nachkommen werden mithilfe der Fitnessfunktion bewertet und einer vorläufigen Zwischenpopulation zugeordnet. Der Vorgang aus Auswahl, Rekombination und Mutation wird solange wiederholt, bis die Zwischenpopulation λ Nachkommen enthält.
    Der folgende Selektionsprozess wählt aus diesen λ Nachkommen wieder eine Zahl von μ Individuen für die Erzeugung der nächsten Generation aus. Die gewählte Selektionsstrategie legt fest, welche Lösungen die nächste Elternpopulation bilden. Eine typische Vorgehensweise ist die (μ, λ)-Strategie. Hier werden λ (mit λ ≥ μ) Kinder erzeugt, die die Elternpopulation vollständig ersetzen. Sicherzustellen ist, dass die bisher am besten bekannte Lösung (mit dem höchsten Fitnesswert) separat gespeichert wird. Damit soll vermieden werden, dass diese durch das teilweise zufallsbasierte Selektionsverfahren verloren geht. Die grundsätzliche Vorgehensweise ist in Abbildung 3 dargestellt.

    Abbildung 3: Prinzipielle Vorgehensweise genetischer Algorithmen [17]

2.1.3Simulated Annealing, Threshold Accepting und verwandte Verfahren
    Während bei Evolutionären Strategien und Genetischen Algorithmen die Erkenntnisse aus der Biologie eine größere Rolle spielten, wird bei diesen Verfahren auf eine andere Naturwissenschaft zurückgegriffen. Es geht um die Nachbildung physikalischer Prozesse. Simulated Annealing (SA) ist ein stochastisches Verfahren, dessen Ursprung in der Thermodynamik liegt. Studiert wird das energetische Verhalten von Teilchen bei einer gegebenen Temperatur. Annealing (Abkühlung) bezeichnet den gesteuerten Erstarrungsvorgang eines aufgeheizten Körpers in einem Molekülgitter, der einen Zustand minimaler freier Gitterenergie im Festkörper zum Ziel hat. Die Idee wurde aufgegriffen und daraus die Metaheuristik Simulated Annealing, die zur Lösung kombinatorischer Optimierungsprobleme eingesetzt werden kann, entwickelt. Die Terminologie ist zum Teil der Thermophysik entlehnt.
    SA steuert eine Nachbarschaftssuche nach folgendem Muster: Ausgehend von einer zulässigen Lösung x , wird eine weitere zulässige Lösung x’ in der Nachbarschaft von x ausgewählt. Besitzt x’ einen besseren Zielfunktionswert als x , so wird im nächsten Schritt die Suche mit x’ fortgesetzt. Besitzt x’ jedoch einen schlechteren Zielfunktionswert, so wird x’ nicht unter allen Umständen abgelehnt. Ob die schlechtere Lösung dennoch akzeptiert wird, hängt vom Ausmaß der Verschlechterung und einen weiteren Parameter ab, der in Anlehnung an die Herkunft des Verfahrens mit Temperatur bezeichnet wird. Die Berechnung der Akzeptanzwahrscheinlichkeit p erfolgt unter Anwendung der Gleichung:

    Dabei ist ∆f die Änderung des Zielfunktionswerts und T die aktuelle Temperatur. Die Temperatur T dient somit als Steuerungsparameter der Akzeptanzwahrscheinlichkeit. Der Ausgangswert wird am Anfang des Verfahrens so gewählt, dass durchaus auch Verschlechterungen