Information Technology Reference
In-Depth Information
können wir weder Dominanz noch Rezessivität von Genen ausdrücken. Es kann also
keine heterozygoten oder homozygoten Individuen geben. Für einen EA benötigen
wir nur ein Chromosom, um einen Lösungskandidaten zu kodieren. Die Lösung ent-
spricht dem Phänotyp. Ein diploider Chromosomensatz also zwei unterschiedliche
Chromosomen in einem Lösungskandidaten wären nicht sinnvoll, da im Gegensatz
zur Natur die phänotypische Ausprägung (Lösung) dann nicht mehr klar wäre.
Es gibt jedoch eine freie Kombinierbarkeit der Gene. Durch den „mächtigen“
Crossover-Operator sind Gene nicht gekoppelt. In den Individuen der Folgepopu-
lationen sind beliebige Kombinationen der Eigenschaften (also der Gene) möglich.
Schon nach einer Generation liegen Gene zweier Eltern auf einem Chromosom der
Kinder und können — analog zur sexuellen Fortpflanzung — eine Kombination gu-
ter Eigenschaften mit anderen guten Eigenschaften darstellen. Ein evolutionärer Al-
gorithmus mit diploidem Chromosomensatz stellt demnach keine sinnvolle Erwei-
terung dar.
10.5 Vergleich mit klassischen Optimierungsverfahren
Im Bereich der klassischen Optimierung gibt es viele Verfahren, deren Prinzipien
denen von evolutionären Algorithmen sehr ähneln. Zu diesen klassischen Optimie-
rungsverfahren zählen u. a. der Gradientenabstieg, der Zufallsaufstieg, das simulier-
te Ausglühen, das Akzeptieren mit Schwellenwert sowie der Sintflut-Algorithmus.
Alle diese und die evolutionären Verfahren setzen voraus, dass es keine großen
Sprünge in den Funktionswerten der zu optimierenden Funktion gibt. D. h. also,
dass für ähnliche Elemente s 1 , s 2 sich die Funktionswerte f ( s 1 ) und f ( s 2 ) nicht
zu sehr unterscheiden. Hier betrachten wir nur der Gradientenabstieg. Die weite-
ren o. g. Verfahren besprechen wir später detailiert als lokale Suchverfahren anhand
einer Gegenüberstellung im Abschnitt 12.2.
Soll mit dem Gradientenabstieg ein Optimum in gefunden werden, müssen
zwei Bedingungen vorausgesetzt werden.
1. muss eine Teilmenge aus dem n -dimensionalen Raum der reellen Zahlen IR n
sein.
2. Die zu optimierende Funktion f : IR m u s s d i f f e r e n z i e r b a r s e i n .
Der Gradient ist eine Differentialoperation, die ein Vektorfeld erzeugt. Er liefert
den Vektor in Richtung der stärksten Steigung einer Funktion. Auf Seite 59 in Teil I
im Abschnitt 5.4 ist der Gradienten von z = f ( x , y ) am Punkt ( x 0 , y 0 ) verdeutlicht.
Der Gradient an diesem Punkt ist definiert durch
z
x
| ( x 0 , y 0 ) , z
z | ( x 0 , y 0 ) =
| ( x 0 , y 0 )
.
y
Die Grundidee des Gradientenabstiegs ist, dass ausgehend von einem zufälligen
Startpunkt, kleine Schritte im Suchraum jeweils in Richtung des stärksten An-
stiegs der Funktion gemacht werden, bis ein (lokales) Maximum erreicht ist.
x (0)
1
,..., x (0)
n
1. Wähle einen (zufälligen) Startpunkt x (0) =
.
Search WWH ::




Custom Search