Um die Theorie, die wir gerade verinnigt haben, im Einsatz zu sehen, schauen wir uns folgendes simples Problem an:
Wir haben die Zahlen 0 bis 9 und die Operanten +, -, * und /; unser genetischer Algorithmus soll nun einen Term finden, der eine bestimmte Nummer als Ergebnis hat. Die Operationen werden dabei von links nach rechts ausgeführt, wie man sie auch liest.
Wenn man zB die Nummer 23 hat, wäre der Term 6+5*4/2+1 eine mögliche Lösung.
Wäre die Zahl jedoch 75,5 dann wäre 5/29*7-5 eine mögliche Lösung.
Vergewissere dich bitte, dass du das Problem wirklich verstanden hast, bevor du weiter liest. Ich weiß, es ist sehr an den Haaren herbeigezogen, dafür ist es jedoch sehr simpel.
Zunächst müssen wir eine mögliche Lösung als String aus Bits codieren... ein Chromosom. Aber wie machen wir das? Zunächst müssen wir die verschiedenen Zeichen zur Lösung unseres Problems darstellen... dies wären die Zahlen 0 bis 9 und die Rechenzeichen +, -, * und /. Jedes dieser Zeichen ist ein Gen und ein Chromosom ist die Verbindung mehrerer Gene.
Um alle Zeichen darstellen zu können muss jedes Zeichen aus 4 Bits bestehen:
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
+: 1010
-: 1011
*: 1100
/: 1101
Die oben aufgeführten Gene werden benötigt um unser Problem zu codieren. Die Gene 1110 & 1111 bleiben dabei ungenutzt und werden einfach ignoriert.
Eine codierung des Terms für die oben Aufgeführte 23 (6+5*4/2+1) würde also so ausshene:
0110 1010 0101 1100 0100 1101 0010 1010 0001
6 + 5 * 4 / 2 + 1
Die Gene zu einem Chromosom zusammengezogen so:
011010100101110001001101001010100001
Noch ein paar Worte zur decodierung
Da der Algorithmus zufällig generierte Bitreihen (Anm.d.Ü.: Chromosome) benutzt, wird er des öfteren über Strings stolpern, die z.B. so aussehen könnten:
0010001010101110101101110010
Decodiert sähe das wie folgt aus:
0010 0010 1010 1110 1011 0111 0010
2 2 + n/a - 7 2
Dieser Term ergibt natürlich keinen Sinn. Deshalb muss unser Algorithmus Gene, die nicht in das Muster "Zahl -> Operant -> Zahl -> Operant -> usw" passen beim decodieren einfach ignorieren. Wenn wir dies beachten würde das oben gezeigte Sinnlose Chromosom wie folgt gelesen werden:
2 + 7
Eine richtige Fitenss-Funktion zu finden kann das komplizierteste an einem genetischen Algorithmus sein. Natürlich kommt es darauf an, welches Problem du lösen willst, aber als Faustregel kann man sagen, dass je näher ein Chromosom an die Lösung des Problems kommt, desto höher sollte seine Fitness werden. Für unser genanntes Problem wäre also eine Fitness-Funktion sinnvoll, die einen Wert erzeugt, der proportional dazu ist, wie nah die Funktion an den Zielwert gekommen ist.
Für den Rest des Tutorials sagen wir, dass unsere Zielnummer die 42 ist. Das oben gezeigte Chromosom
011010100101110001001101001010100001
hätte einen Fitness Wert von 1/(42-23) bzw 1/19.
Im Moment würde ein "Division by Zero" (A.d.Ü.: Division durch Null) Fehler auftreten, wenn die Zielzahl erreicht wird, denn die Fitness wäre 1/(42-42). Das sollte aber kein Problem sein, denn wir haben dann ja bereits gefunden was wir gesucht haben: Eine Lösung für unser Problem! Der Algorithmus kann nun dementsprechend gestoppt werden.
Bitte lese an dieser Stelle das Tutorial erst ein weiteres mal.
Falls du der Meinung bist du verstehst genug von der Materie, schlage ich dir vor, du fängst am besten gleich an einen eigenen genetischen Algorithmus zu schreiben. Es gibt keinen besseren Weg etwas zu lernen. Falls es dir noch immer nicht ganz klar geworden ist, habe ich hier ein wenig einfachen Code vorbereitet. Bitte spiele etwas an der Mutationsrate, der Rekombinationsrate und der Länge der Chromosome usw herum um ein Gefühl dafür zu bekommen wie sich die einzelnen Parameter auf das Endergebnis auswirken. Ich hoffe der Code ist ausreichend kommentiert, so dass du auch verstehst was passiert. Falls das nicht der Fall ist, schreib mir eine eMail und ich werde versuchen die Kommentare zu verbessern![Anm.d.Ü.: Der Code ist auf Englisch kommentiert]
Achtung: Der Code decodiert die Bit-Strings genau, wie oben besprochen und versucht eine Lösung zu finden indem es den gesamten Term abarbeitet. Falls also die Zielnummer 42 ist, dann wäre + 6 * 7 / 2 keine Lösung, obwohl die ersten paar Zeichen + 6 * 7 eine gültige Lösung wären.
(Delphi Code eingeschickt von Asbjørn kann hier gefunden werden und Java Code eingeschickt von Tim Roberts kann hier gefunden werden))
Schluß
Ich hoffe dieses Tutorial hat dir geholfen den Einstieg in die genetischen Algorithmen zu finden. Bitte beachte, dass ich nur die Grundlagen behandelt habe. Falls du dich weitergehend für genetische Algorithmen interessierst, dann gibt es noch eine Menge zu lernen. Es gibt verschiedene Auswahlverfahren, verschiedene Rekombinations- und Mutationsfunktionen die man einsetzen kann und auch ne ganze Menge esoterischer Sachen, wie zB Fitnesswert Teilung und Spezialisierung, an der man rumspielen könnte. Viele dieser Techniken können die Performance deines genetischen Algorithmus stark erhöhen.
Zeugs zum ausprobieren
Falls du deinen genetischen Algorithmus programmiert und das im Tutorial gestellte Problem gelöst hast, dann kannst du dich ja mal an folgenden Aufgaben versuchen:
In einem Gebiet gibt es eine Anzahl von sich nicht überlappenden, zufällig verteilten Scheiben, wie auf Screenshot 1 zu sehen ,
Screenshot 1
Benutze nun einen genetischen Algorithmus um die größtmögliche Scheibe zu ermitteln, die du zwischen die Anderen legen kannst, ohne, dass sich die Scheiben überschneiden. Schau dir dazu Screenshot 2 an.
Screenshot 2
Wie du evtl schon gemerkt hast, habe ich dazu schon etwas Code geschrieben. Falls du also stecken bleibst und nicht weiter kommst, dann kannst du diesen Code hier finden (zuvor aber probierst du es mal schön alleine, ja? ;0)). Für die unter euch ohne Compiler, gibt es hier eine ausführbare Version.