Evolutionäre Algorithmen - Computational Intelligence - page 156

Definition 10.2 (Dekodierungsfunktion) Eine Dekodierungsfunktion dec : G ist
eine Abbildung vom Genotyp G auf den Phänotyp .
Wie Lösungskandidaten dekodiert werden, ist problemspezifisch. Es gibt demnach
keine allgemeinen Regeln bei der Erstellung einer Dekodierungsvorschrift. Später
im Abschnitt 11.1 werden wir jedoch einige Aspekte besprechen, die bei der Wahl
einer Kodierung beachtet werden sollten.
Um Ausgangsmaterial im Genpool zu erzeugen, muss es eine Methode geben,
die eine Anfangspopulation erzeugt. Meist werden einfach zufällige Zeichenketten er-
zeugt. Je nach gewählter Kodierung können aber auch komplexere Verfahren nötig
sein. Unumgänglich ist eine Bewertungsfunktion f (auch Güte- oder Fitnessfunktion
genannt) für die Individuen. Die Bewertungsfunktion f repräsentiert die simulier-
te Umgebung und gibt die Güte der Individuen an. Sie ist definiert auf dem Such-
raum .MeististdieBewertungsfunktion f mit der zu optimierenden Funktion
identisch. Sie kann aber auch zusätzliche Elemente enthalten, die z. B. einzuhalten-
de Nebenbedingungen darstellen. In jedem EA muss es auch eine Auswahlmethode
auf der Grundlage der Fitnessfunktion geben. Die Auswahlmethode bestimmt, wel-
che Individuen zur Erzeugung von Nachkommen herangezogen werden oder auch
unverändert in die nächste Generation gelangen. Genauere Details zur Bewertungs-
funktion und eine Reihe an Auswahlmethoden behandeln wir im Abschnitt 11.2.
Des Weiteren besteht ein EA aus genetischen Operatoren ,diedieLösungskandi-
daten genetisch verändern. Wir unterscheiden i. Allg. Mutation und Crossover .Beide
Operatoren sind auf dem Genotyp G definiert. Eine Mutation stellt die zufällige Ver-
änderung einzelner Gene des Chromosoms eines Individuums dar. Ein Crossover ist
eine Rekombination der Chromosomen von mindestens zwei Individuen der Popu-
lation. Dieser Operator heißt eigentlich “crossing over”, nach einem Vorgang in der
Meiose (einer Phase der Zellteilung), bei demChromosomen zerteilt und überkreuzt
wieder zusammengefügt werden. Genetische Operatoren besprechen wir im Detail
im Abschnitt 11.3.
Aufgrund des modularen Aufbaus und der Variabilität eines jeden Moduls gehö-
ren ebenfalls die Werte der genutzten Parameter zu den Bausteinen eines EA. Diese
Parameter betreffen beispielsweise die Populationsgröße, die Mutationswahrschein-
lichkeit, usw. Schlussendlich benötigt jeder EA ein Abbruchkriterium ,dasnachjeder
erzeugten Generation entscheidet, ob eine weitere erstellt werden soll. Typische Kri-
terien für einen Abbruch sind z. B.: eine festgelegte Anzahl von berechneten Genera-
tionen, eine festgelegte Anzahl von Generationen ohne jegliche Verbesserung, oder
das Erreichen einer vorgegebenen Mindestgüte eines Lösungskandidaten.
10.3 Das n-Damen-Problem
Das n -Damen-Problem beschreibt die Aufgabe, n Damen auf ( n n ) -großes Schach-
brett so zu platzieren, dass in keiner Reihe (Zeile), keiner Linie (Spalte) und keiner
Diagonale mehr als eine Dame steht. Vereinfacht können wir schreiben, dass die Da-
men so platziert werden muss, dass keine einer Anderen imWeg steht. Die verschie-
denen Zugmöglichkeiten einer Dame und eine Lösung des 8-Damen-Problems sind
in Abbildung 10.1 dargestellt.