Information Technology Reference
In-Depth Information
Abgesehen von der jeweils gewählten Abkühlungsfunktion besteht die einfachste Form der
Abkühlung darin, dass nach jeder Selektion einer Lösung die Temperatur reduziert wird. Pro
Temperaturstufe werden jeweils zwei Lösungen miteinander verglichen. Das ist jedoch nicht
unbedingt notwendig. Auf jeder Stufe können auch mehrere Lösungen nach dem obigen Ver-
fahren sozusagen paarweise miteinander verglichen werden und die endgültig ausgewählte
wird für die nächste Stufe übernommen. Ebenso ist es auch möglich, mehrere Lösungen auf die
nächste Stufe zu übernehmen.
Zusätzlich kann man schließlich eine „adaptive“ Abkühlung vorsehen, bei der auf jeder Tem-
peraturstufe, solange iterativ neue Lösungen gesucht werden, bis keine Verbesserungen mehr
eintreten. Man wartet also auf jeder Stufe von T, bis der Algorithmus konvergiert und senkt
erst dann die Temperatur. Dies Verfahren ist „adaptiv“ in dem Sinne, dass die Anzahl der neu
berücksichtigten Lösungen von Temperaturstufe zu Temperaturstufe im Allgemeinen verschie-
den ist und gewissermaßen vom Algorithmus selbst bestimmt wird. Dies hat offensichtlich
starke Ähnlichkeiten mit der mutativen Schrittweitensteuerung bei den ES. Ebenso ist es mög-
lich, kurzfristig die Temperatur auch wieder zu erhöhen, um lokale Energieminima verlassen
zu können, was in der angelsächsischen Literatur als „restart“ bezeichnet wird. Ob man die
einfachste Abkühlungsmöglichkeit wählt oder eine der komplizierteren, hängt natürlich vom
Problem ab. Empfehlenswert vor allem für Anfänger ist immer, mit den einfachsten Verfahren
anzufangen und erst bei unbefriedigenden Ergebnissen kompliziertere zu wählen.
(2) Die Berechnung der Wahrscheinlichkeit, gemäß der entschieden wird, ob auch eine
schlechtere Lösung ausgewählt wird, folgt, wie oben schon bemerkt, entsprechend dem ther-
modynamischen Gesetz der Boltzmann-Verteilung. Dabei gilt offenbar, dass bei sinkender
Temperatur die Wahrscheinlichkeit für die Selektion einer schlechteren Lösung immer geringer
wird und bei minimaler Temperatur gleich Null wird (vgl. das entsprechende Heiratsschema
beim GA).
Damit folgt der SA-Algorithmus dem thermodynamischen Gesetz, dass bei sehr hohen Tempe-
raturen Zustände mit erheblich höher liegender Energie möglich sind - die Übergangs-
wahrscheinlichkeit p ist äußerst hoch -, und dass bei sehr niedrigen Temperaturen praktisch
nur noch Wechsel in Zustände möglich sind, die niedrigere oder allenfalls geringfügig höhere
Energieniveaus haben. Ähnlich wie evolutionsbiologische Modelle bei den evolutionären Al-
gorithmen zum Teil wörtlich übernommen werden, wird auch hier ein etabliertes physikali-
sches Prinzip buchstäblich übernommen und eingesetzt.
Mathematisch ist dies natürlich nicht zwingend. Bei der Wahrscheinlichkeitsberechnung geht
es ja letztlich nur darum, dass bei sinkenden Temperaturwerten die Wahrscheinlichkeit p
eben-
falls sinkt. Dieser Effekt ließe sich am einfachsten auch dadurch erzielen, dass man zu Beginn
der Berechnung T = maximaler Wert von 'E setzt und gleichzeitig p = 1. Trivialerweise führt
damit eine Reduzierung von T automatisch zu einer Reduzierung von p. Andere weniger trivia-
le Berechnungen von p lassen sich leicht vorstellen.
M.a.W., man will erreichen, dass „schlechtere“ Lösungen, die aber geeignet sein können, aus
einem lokalen Minimum herauszuführen, akzeptiert werden; die Wahrscheinlichkeit dafür soll
im Laufe des Optimierungsverfahrens systematisch abgesenkt werden. Man könnte im Prinzip
außerdem auf eine „Temperatur“ verzichten, und p direkt als Kontrollparameter verwenden,
der in einem geeigneten Verfahren schrittweise abgesenkt wird.
Ungeachtet dieses relativierenden Hinweises empfehlen wir, bei eigenen Verwendungen eines
SA die etablierte „thermodynamische“ Berechnungsformel für p einzusetzen. Diese hat sich in
zahlreichen Anwendungen von SA-Verfahren durchaus bewährt und es gibt keinen praktischen
Search WWH ::
Custom Search