Genetische Algorithmen

Grundlagen

Kurzeinführung

V 1.0d

Genetische Algorithmen zählen zu den stochastischen Suchverfahren. Diese versuchen ausgehend von einer oder mehreren zulässigen Lösungen (Punkten im Lösungsraum/Suchraum), sich Schritt für Schritt der optimalen Lösung zu nähern.
GA arbeiten mit einer Menge solcher Punkte/zulässiger Lösungen. Diese bezeichnet man auch als künstliche Individuen.
Alle unter Genetische Algorithmen - Anwendungsbeispiele zusammengefaßten Beispiele wurden auf Basis eines einfachen binärcodierten GA programmiert (JSGA: JAVA based simple Genetic Algorithm). GA arbeiten auf Basis künstlicher Individuen, die (in Anlehnung an die Natur) aus einem Chromosomensatz und einem Fitneßwert bestehen. In der Natur kann der Fitneßwert eine komplexe Größe sein, die wirklich die Anpassung des Individuums an die Umwelt beschreibt. Er kann aber auch eine einzelne Größ sein (wie Länge, Augenfarbe,..). Je nachdem, was Gegenstand der Betrachtung ist. Im Zusammenhang mit Genetischen Algorithmen geht man von der einfachen Annahme aus, daß ein Zusammenhang zwischen dem Chromosomensatz und dem Fitneßwert existiert und daß jede Änderung des Chromosomensatzes zu einer Änderung des Fitneßwertes führt. Liegen identische Chromosomensätze vor, so führen gleiche Änderungen an den Chromosomensätzen zu identischen Fitneßwertveränderungen.

Die nachfolgenden Ausführungen beziehen sich auf das Anwendungsbeispiel Maximumsuche. Hier soll das Maximum einer 2D-Funktion (y=f(x)) mit Hilfe eines Genetischen Algorithmus ermittelt werden. Im Anwendungsbeispiel können verschiedene Funktionen ausgewählt werden. Wir wollen uns für die nachfolgenden Beispiele der Selektion, Kreuzung und Mutation auf die Funktion F0 des Anwendungsbeispieles beziehen (nebenstehende Abbildung).

mit 0.0 <= x <= 10 ; Maximum bei x=5.0 mit y= 0.79788

In diesem einfachen Fall besteht ein künstliches Individuum lediglich aus einem einzelnen binärcodierten x-Wert (aus dem Definitionsbereich der Funktion) und dem zugehörigen y-Wert (y = f(x)). Der binärcodierte x-Wert (xc-Wert) übernimmt hierbei die Rolle eines Chromosoms; der y-Wert die Rolle des Fitneßwertes.

künstliches Individuum

::=

I = {xc,f(x)}

Eine Menge von Individuen wird als Population bezeichnet.

Population

::=

P = {I₁,I₂,..,I_n}
n: Anzahl der Individuen

Kodierung
Der zugrunde liegende binärcodierte GA arbeitet nicht mit den reellen x-Werten, sondern mit einer codierten Form. In diesem Fall mit einer Codierung des jeweiligen x-Wertes in eine Folge von 0 und 1. Nachfolgend sind einige einfache Beispiele für die Kodierung angegeben. Zur Vereinfachung wird hier von einer festen Länge von 8 Zeichen und von positiven ganzen Zahlen ausgegangen.

Codierungsbeispiele
x	xc (codierte Folge)
114	01001110
132	00100001

Gesamtalgorithmus
Ein GA versucht ein Optimum zu finden, indem er ausgehend von einer zufällig erzeugten Anfangspopulation von künstlichen Individuen eine Kindergeneration durch Anwendung der Genetischen Operatoren Selektion, Kreuzung und Mutation erzeugt. Diese wird dann zur neuen Elternpopulation und bildet die Basis für die nächste Kinderpopulation, usw.. Im Verlaufe der Bildung immer neuer Kinderpopulationen sollte man sich dem gesuchten Optimum immer weiter nähern.
Die nachfolgende Abbildung zeigt schematisch einen Iterationsschritt des GA zur Bildung von 2 neuen Individuen einer Kinderpopulation. Dieser Schritt wird so oft wiederholt, bis die Kinderpopulation vollständig ist.

Der Vorgang der Erzeugung von Kinderpopulationen wird so lange fortgesetzt, bis eine Abbruchbedingung erfüllt ist. Als Abbruchbedingung eignet sich die Anzahl der berechneten Generationen oder auch der Fitneßwert der Population (mittlerer oder bester). Wird keine Verbesserung des Fitneßwertes mehr erreicht, so kann die Suche abgebrochen werden.
Im Nachfolgenden sollen die genetischen Operatoren kurz beschrieben werden.

Selektion
In der Phase der Selektion werden aus der Elterngeneration zwei geeignete Individuen ausgewählt (Vaterindividuum, Mutterindividuum), die zwei Kinderindividuen erzeugen. Geeignete Elternindividuen sind solche mit hohem Y-Wert, da das Ziel ja das Auffinden des x-Wertes mit dem größten Y-Wert ist.

Selektionsbeispiel (Basis: Funktion F0 ; 0.0 < x < 10)
Eltern	x	xc (codierte Folge)	Y-Wert
E1	4	00100000	0.108
E2	8	00010000	1.22 E-08
E3	7	11100000	2.68 E-04

Das obige Beispiel stellt z.B. einen Ausschitt aus der Elterngeneration dar. Aus diesen 3 Elternindividuen könnte man z.B. E1 und E3 als Vater- bzw. Mutterindividuum auswählen. Sie haben die höhsten Y-Werte.

Kreuzung
Der Selektion von Vater- und Mutterindividuum folgt als nächster Schritt die Kreuzung. Hier werden die binärcodierten x-Werte der Eltern zu zwei neuen Zeichenfolgen kombiniert.
Der implementierte GA verwendet ein 1-Punkt Kreuzungsverfahren. In Abhängigkeit von einem Steuerparameter, der Kreuzungswahrscheinlichkeit (P_c; 0 <= P_c <= 1.0), werden die xc-Werte der Elternindividuen gekreuzt oder unverändert an die Kinderindividuen weitergegeben.
Sollen die xc-Werte von Vater (EV) und Mutter (EM) gekreuzt werden, so werden die entsprechenden xc-Zeichenfolgen an einer zufällig ausgewählten Stelle der Zeichenfolge auseinandergetrennt und wechselseitig neu zusammengesetzt (siehe Beispiel).

Kreuzungsbeispiel
(Basis: Funktion F0 ; 0.0 < x < 10; Kreuzungspunkt= 1)

Eltern	x	xc (codiert)	Y-Wert
EV	1	00100000	0.108
EM	7	11100000	2.68 E-04

xc (getrennt)	xc (gedreht)
0 0100000	1 0100000
1 1100000	0 1100000

xc (codiert)	x	Y-Wert	Kinder
10100000	5	0.798	K1
01100000	6	0.108	K2

Mutation
Im letzten Schritt wird, wieder in Abhängigkeit von einem Steuerparameter, hier der Mutationswahrscheinlichkeit (P_m; 0 <= P_m <= 1.0), die xc-Zeichenfolge zufällig verändert. Diesen Prozeß bezeichnet man als Mutation.
Es wurde ein 1-Punkt Mutationverfahren implemtiert. Das bedeutet, daß lediglich eine Stelle der betroffenen Zeichenkette in ihrem Wert umgekippt wird: 0 wird zu 1 und umgekehrt.
Im nachfolgenden Beispiel bestimmt der Algorithmus, daß der xc-Wert von K1 nicht mutiert wird. Der xc-Wert von K2 wird mutiert. Es wird die Stelle 3 der Zeichenfolge gekippt.

Mutationsbeispiel
(Basis: Funktion F0 ; 0.0 < x < 10; Mutationsstelle= 3)

vor Mutation	xc (codierte Folge)	x	Y-Wert
K1	10100000	5	0.798
K2	01100000	6	0.108

xc (codierte Folge)	x	Y-Wert	nach Mutation
10100000	5	0.798	K1 (nicht mutiert)
01000000	2	1.22 E-08	K2 (mutiert)

Institut f. Technische Chemie (ITC)
der Universität Leipzig
Linne-Str. 3-4 D-04103 Leipzig

Ralf Moros
Telefon: 0341 / 9736 329
Fax: 0341 / 9736 349

E-Mail bitte direkt an:
moros@sonne.tachemie.uni-leipzig.de

V 1.0d - 20.04.1999
letzte Aktualisierung: 14.12.1999
© 1999 ITC-Leipzig/ Ralf Moros	Zugriffe seit dem 01.01.2000: 20.04. - 31.12.1999: 140