Information Technology Reference
In-Depth Information
Algorithmus 11
A
KZEPTANZBEDINGUNG
-
REKORDORIENTIERTES
-W
ANDERN
Eingabe:
Elterngüte
f
(
s
t
)
,Kindgüte
f
(
s
)
,
t
,bestegefundeneGüte
f
best
Ausgabe: true
,falls
s
übernommen werden soll, sonst
false
,sowie
f
best
1:
if
f
(
s
)
f
best
then
f
best
f
(
s
)
3:
return true
,
f
best
4:
else
5:
if
f
(
s
)
f
best
<
T
then
6:
return true
,
f
best
7:
end if
8:
end if
9:
return false
,
f
best
2:
12.2.6 Beispiel am Problem des Handlungsreisenden
Um eine Beispielanwendung der lokalen Suchalgorithmen zu geben, erwähnen wir
noch einmal das Problem des Handlungsreisenden. Dieses haben wir formell mit
der Definition 11.1 im Abschnitt 11.1.2 auf Seite 172 eingeführt. Es geht hierbei um
das Finden einer Rundreise minimaler Länge bzw. Kosten durch alle
n
Städte, auf
der keine Stadt mehr als einmal besucht werden darf. Wir wollen hier das simulierte
Ausglühen und den Zufallsaufstieg im Vergleich betrachten.
Das simulierte Ausglühen läuft nach folgendem Algorithmus ab:
1. Bringe die Städte in eine zufällige Reihenfolge (zufällige Rundreise).
2. Wähle zufällig zweimal zwei Städte, die in der aktueller Rundreise aufeinan-
der folgen (alle vier Städte verschieden). Trenne die Rundreise zwischen den
Städten jedes Paares auf und drehe den dazwischen liegenden Teil um.
3. Wenn die so entstehende Rundreise besser (kürzer, billiger) ist als die alte, dann
ersetze die alte Rundreise auf jeden Fall durch die neue. Ansonsten ersetze die
alte Rundreise nur mit Wahrscheinlichkeit
p
= exp
Q
kT
wobei
Q
der Qua-
litätsunterschied zwischen alter und neuer Rundreise ist,
k
die Spannweite der
Rundreisequalitäten und
T
der Temperaturparameter, der mit der Zeit redu-
ziert wird, z. B.
T
=
1
/
t
.
4. Wiederhole die Schritte 2 und 3 bis ein Abbruchkriterium erfüllt ist.
Gegebenenfalls muss man
k
zu schätzen, z. B. durch
k
t
=
t
+
t
max
i
=
1
Q
i
,wobei
Q
i
der Qualitätsunterschied im
i
-ten Schritt und
t
der aktuelle Schritt sind. Der
verwendete Variationsoperator entspricht exakt der im Abschnitt 11.3.1 behandelten
Inversion (siehe Abbildung 11.11).
Ein reiner Zufallsaufstieg kann in einem lokalen Minimum hängenbleiben. Dazu
geben wir ein einfaches Beispiel mit 5 Städten wie in Abbildung 12.4 an. Die an-
fänglich erzeugte Rundreise hat eine Länge von 2
5
+
4
11.30. Mögliche
Teilungen, die für das Invertieren aus der anfänglichen Rundreise entstehen können,
sind in Abbildung 12.5 dargestellt.
2
+
2
