Information Technology Reference
In-Depth Information
Lokale Suchalgorithmen sind ein Sonderfall der evolutionären Algorithmen. Ei-
ne Population besteht stets nur aus einem Lösungskandidaten, was mehrere Konse-
quenzen nach sich zieht. So ist natürlich die Verwendung eines Rekombinationsope-
rators nicht sinnvoll, da nur ein Individuum vorhanden ist. Veränderungen werden
nur anhand des Mutations- bzw. Variationsoperators erzeugt. Das Selektionsverfah-
ren entscheidet nach Variation des bestehenden Individuums, ob das neu erzeugte
Individuum anstelle des Elternindividuums in die nächste Generation kommt.
Es gibt einen Basisalgorithmus für alle lokalen Suchverfahren. Dieser ist imAlgo-
rithmus 7 aufgelistet. Die Methode
Akzeptanz
entspricht dabei dem Selektionsverfah-
ren. Sie unterscheidet in ihrer Implementierung die einzelnen lokalen Suchverfahren
voneinander. Die verschiedenen Varianten entstehen also durch unterschiedliche Ak-
zeptanzkriterien. Der Genotyp
G
ist, wie bei einem EA auch, problemabhängig.
Algorithmus 7
L
OKALE
-S
UCHE
Eingabe:
Zielfunktion
f
Ausgabe:
Lösungskandidat
s
(
t
)
1:
t
0
2:
s
(
t
)
erzeuge Lösungskandidat
3: bewerte
s
(
t
)
durch
f
4:
while
Terminierungsbedingung nicht erfüllt
do
5:
s
variiere
s
(
t
)
bewerte
s
durch
f
6:
t
t
+ 1
7:
if
Akzeptanz
(
f
(
s
(
t
1)),
f
(
s
),
t
)
then
8:
// A k z
e p t a n z b e d i n g u n g
9:
s
(
t
)
s
10:
else
11:
s
(
t
)
s
(
t
1)
12:
end if
13:
end while
14:
return
s
(
t
)
Mit demGradientenabstieg aus Abschnitt 10.5 haben wir bereits ein lokales Such-
verfahren vorgestellt. Dabei war allerdings der Suchraum restriktiert auf Differen-
zierbarkeit, was die Auswahl der Probleme stark einschränkt. Die folgenden Verfah-
ren sind für beliebige, auch nicht differenzierbare Suchräume anwendbar.
12.2.1 Zufallsaufstieg
Wenn d i e Funk t i on
f
nicht differenzierbar ist, kann man versuchen, eine Richtung,
in der die Funktion
f
ansteigt, durch Auswerten zufälliger Punkte in der Umgebung
des aktuellen Punktes zu bestimmen. Der
Zufallsaufstieg
ist das wohl einfachste loka-
le Suchverfahren und läuft in folgenden Schritten ab.
1. Wähle einen (zufälligen) Startpunkt
s
0
.
2. Wähle einen Punkt
s
„in der Nähe“ von
s
t
.(z.B.durchzufällige,aber
nicht zu große Veränderung von
s
t
).
