Information Technology Reference
In-Depth Information
2. Wähle einen Punkt
s
„in der Nähe“ des aktuellen Punktes
s
t
(z. B. durch
zufällige, aber nicht zu große Veränderung von
s
t
).
3. Setze
s
falls
f
(
s
)
f
(
s
t
),
mit Wahrscheinlichkeit
p
=
e
f
s
t
+1
=
s
kT
sonst.
s
t
mit Wahrscheinlichkeit 1
p
wobei
f
=
f
(
s
t
)
f
(
s
)
die Qualitätsverringerung der Lösung ist,
k
=
f
max
eine Schätzung des Umfangs der Funktionswerte und
T
der Temperaturpara-
meter ist, der im Laufe der Zeit sinkt.
4. Wiederhole Schritte 2 und 3 bis ein Abbruchkriterium erfüllt ist.
Für kleine
T
geht das Verfahren nahezu in einen Zufallsaufstieg über. Die Akzep-
tanzbedingung des simulierten Ausglühens für Algorithmus 7 lautet:
Algorithmus 9
A
KZEPTANZBEDINGUNG
-
SIMULIERTES
-A
USGLÜHEN
Eingabe:
Elterngüte
f
(
s
t
)
,Kindgüte
f
(
s
)
, Generation
t
Ausgabe: true
,falls
s
übernommen werden soll, sonst
false
1:
if
f
(
s
)
f
(
s
t
)
then
2:
return true
3:
else
4:
u
wähle zufällig aus
U
([
0, 1
])
// Z u f a
s z
a h l
z w i
s c h e n
0
u n d
1
f
(
s
t
)
f
(
s
)
kT
t
1
if
u
exp
5:
then
6:
return true
7:
else
8:
return false
9:
end if
10:
end if
12.2.3 Schwellenwertakzeptanz
Die Idee der Schwellenwertakzeptanz ist ähnlich wie beim simulierten Ausglühen.
Auch hier akzeptieren wir schlechtere Lösungen, allerdings nur mit einer oberen
Schranke für die Verschlechterung. Der Ablauf lautet wie folgt:
1. Wähle einen (zufälligen) Startpunkt
s
0
.
2. Wähle einen Punkt
s
„in der Nähe“ des aktuellen Punktes
s
t
(z. B. durch
zufällige, aber nicht zu große Veränderung von
s
t
).
3. Setze
s
falls
f
(
s
)
f
(
s
t
)
,
s
t
+
1
=
s
t
sonst,
wobei
der Schwellenwert für das Akzeptieren schlechterer Lösungen ist, der
im Laufe der Zeit (langsam) gesenkt wird.
=
0entsprichtdemnormalem
Zufallsaufstieg.
