Die Modellierung adaptiver Prozesse durch Evolutionäre Algorithmen - Modellierung komplexer Prozesse durch naturanaloge Verfahren - page 85

Sinn hat, ist es üblich, die Konstante k in der physikalischen Boltzmannfunktion gleich 1 zu
setzen, so dass die Formel für die Wahrscheinlichkeit beim SA einfach zu p e 'E/T wird.
Hat man diese Definitionen festgelegt, läuft ein SA-Algorithmus nach einem relativ einfachen
Schema ab:
(a) Definiere eine Menge der möglichen Zustände, d. h. der möglichen Lösungen; diese legen
den Lösungsraum fest. Man kann sich die Menge dieser Lösungen als Mutationen einer an-
fänglichen Lösung vorstellen. 10
(b) Wähle einen Anfangswert für die „Temperatur“ T und lege den Algorithmus für die „Ab-
kühlung“ fest, d. h. das Verfahren, nach dem der Wert für T sukzessive gesenkt werden
soll;
(c) wähle per Zufall eine Lösung s aus und bewerte diese mit der objective function (Energie-
funktion);
(d) wähle aus dem Lösungsraum per Zufall eine „benachbarte“ Lösung s' aus und bewerte
diese ebenfalls. Diese Werte seien E(s) und E(s') - ihre „Energieniveaus“.
(e) Setze E(s) - E(s') = 'E; falls 'E ! 0, ersetze s durch s';
(f) falls 'E d 0, dann ersetze s durch s' gemäß der Wahrscheinlichkeit p e 'E/T ;
(g) reduziere T durch das Abkühlungsverfahren;
(h) iteriere die Schritte (d) - (g) mit der jeweils selektierten Lösung, bis eine Konvergenz auf
einem Energieminimum erreicht ist oder ein anderes Abbruchkriterium erfüllt ist.
Ungeachtet der Einfachheit dieses Standardalgorithmus für SA sind einige Erläuterungen er-
forderlich:
(1) Offensichtlich handelt es sich hier wieder um ein Algorithmusschema wie beim GA und
der ES. Dies ist natürlich kein Nachteil, sondern ermöglicht die vielfältige Einsetzbarkeit dieser
naturanalogen Optimierungsalgorithmen. Allerdings resultiert auch hier daraus, dass ein Be-
nutzer eines SA selbstständig die verschiedenen Parameter und Funktionen bestimmen muss,
die ein SA zur Lösung des jeweiligen Problems erfordert. Wie bei den evolutionären Algorith-
men stellen nämlich gewöhnlich die Codierung der möglichen Lösungen sowie die Festlegung
der „objective function“, also der Bewertungsfunktion, die schwierigsten Probleme dar. Beim
SA kommt noch dazu die Bestimmung eines geeigneten „Abkühlungs-“Algorithmus. Hier gibt
es in der Literatur zahlreiche verschiedene Vorschläge; die einfachste Form ist die einer pro-
zentualen Reduzierung des anfänglichen Temperaturwertes nach einer bestimmten Anzahl von
Schritten, also z. B. immer um 10 %. Als Faustregel kann man sich merken, dass man a) wie
im Beispiel nicht-lineare Funktionen wählen sollte und b) die Abkühlung nicht zu schnell er-
folgen darf. Wie im physikalischen Vorbild braucht natürlich ein SA-Algorithmus eine Min-
destanzahl an Schritten, um die gewünschten Minima zu erreichen. In der Literatur wird des-
wegen bei einer prozentualen Abkühlung vorgeschlagen, die Rate zwischen 1 % und 10 %
festzulegen. Allerdings gilt auch hier, dass es keine Regel ohne Ausnahmen gibt. In manchen
Fällen kann eine lineare Funktion bessere Werte erzielen, also eine Reduzierung der Tempera-
tur um einen konstanten Faktor, in anderen Fällen führen erst kompliziertere, z. B. exponen-
tielle Absenkungen zum Erfolg.
10 In der englischsprachigen SA-Literatur wird für „Mutation“ häufig auch der etwas seltsame Begriff
der „move class“ verwendet.