Information Technology Reference
In-Depth Information
f
Abbildung 12.3: Prinzip des simulierten Ausglühens. Anfängliche Lösungskandida-
ten haben u. U. noch so viel Energie, dass „Täler“ der zumaximierenden Fitnessfunk-
tion überwunden werden können.
3. Setze
s
falls
f
(
s
)
>
f
(
s
t
),
s
t
+
1
=
s
t
sonst.
4. Wiederhole Schritte 2 und 3 bis ein Abbruchkriterium erfüllt ist.
Der Pseudocode für die
Akzeptanzbedingung
im Basisalgorithmus der lokalen Su-
che (Algorithmus 7) ist wie folgt:
Algorithmus 8
A
KZEPTANZBEDINGUNG
-Z
UFALLSAUFSTIEG
Eingabe:
Elterngüte
f
(
s
t
),Kindgüte
f
(
s
), Generation
t
Ausgabe: true
,falls
s
übernommen werden soll, sonst
false
1:
return
f
(
s
)
f
(
s
t
)
Das große Problem dieses naiven Verfahrens ist das Hängenbleiben in lokalen
Maxima. Alle folgenden Verfahren versuchen, dieses Problem zu verringern.
12.2.2 Simuliertes Ausglühen
Simuliertes Ausglühen kann man als Erweiterung des Zufalls- und Gradientenab-
stiegs sehen, die ein Hängenbleiben vermeidet. Die Idee des simulierten Ausglühens
ist, dass Übergänge von niedrigeren zu höheren (lokalen) Maxima wahrscheinlicher
sein sollen als umgekehrt. Das Prinzip des simulierten Ausglühens ist wie folgt (sie-
he Abbildung 12.3). Wir erzeugen zufällige Varianten der aktuellen Lösung, so wie
auch beim Zufallsaufstieg. Bessere Lösungen übernehmen wir immer. Schlechtere
Lösungen übernehmen wir mit einer bestimmten Wahrscheinlichkeit, die abhängt
von der Qualitätsdifferenz der aktuellen und der neuen Lösung und einem Tempe-
raturparameter, der im Laufe der Zeit verringert wird.
Die Motivation dieses Verfahrens wurde von uns bereits im Abschnitt 8.5 ab Sei-
te 137 behandelt. Wir erinnern nur noch einmal daran, dass es auch mit simuliertem
Ausglühen keine Garantie gibt, dass das globale Optimum gefunden wird. Der Ab-
lauf des Verfahrens ist wie folgt:
1. Wähle einen (zufälligen) Startpunkt
s
0
.
