INVESTOX-Forum

Wie genetische Algorithmen funktionieren

Bevor man mit der Evolution von Problem! sangen beginnen kann, müssen Problemlösungen als eigenständige Gebilde definiert werden. Man muß, mit anderen Worten, "Individuen" schaffen, deren Eigenschaften durch Chiffre-Ketten (den auf Chromosomen oder DNA-Strängen aufgereihten Genen vergleichbar) bestimmt sind. Die aufgereihten Chiffren müssen sich auf Regeln oder Regelfragmente (in "fuzzy" oder "harter" Logik), Verbindungsgewichte oder Neuraiarchitekturen, Parameter (numerische Größen) oder andere Elemente beziehen, die Teile von Problemlösungen sind. Mit anderen Worten: Man braucht die Bestimmungsfaktoren der Eigenschaften individueller Lösungen. Außerdem braucht man eine Methode der Klassifizierung oder Rangeinteilung für potentielle Lösungen,wobei ihre Eignung für spezielle Aufgaben das entscheidende Kriterium ist.Ausgedrückt wird dies in einer Bewertungs- oder Fitneßfunktion. Vonnöten sind ferner Algorithmen (die zuvor genannten Chiffre-Ketten), die sozusagen das potentiell auf die nächste Generation übergehende Erbgut von Elternpaaren darstellen. Schließlich braucht man noch eine Methode zur Auswahl von Eltern­paaren für die Nachzucht der folgenden Generation» sowie zur Bestimmung der zulässigen Kinderzahl und zum Ausmerzen der weniger geeigneten Nachkommenschaft bei gleichzeitiger Ermunterung der Fortpflanzung "lebenstüchtiger" Individuen. Es handelt sich um einen der "natürlichen Auswahl" vergleichbaren Evolutionsprozeß. Er läuft folgendermaßen ab:

1. Es wird ein Bestand willkürlicher, aber sich deutlich voneinander unter­scheidender (virtueller) Individuen geschaffen. Bei diesen handelt es sich um potentielle Lösungen, die zum größten Teil wahrscheinlich unbrauchbar sind. Aber über ihre Qualität braucht man sich zu diesem Zeitpunkt noch keine Gedanken zu machen.

2. Dieser Bestand wird durch Paarung ausgewählter Individuen um weitere Mitglieder vergrößert. Dabei sorgt man durch Mutation, Kreuzung und womöglich andere genetische Manipulationen für Veränderungen des Erbgefüges. Mutation ringt neue Elemente oder Variationen ins Spiel, während Kreuzung in der Bevölkerung bereits vorhandene Elemente rekombiniert. Diese Elemente sind hier Chiffren oder Reihen von Chiffren, die Fragmente potentieller Lösungen darstellen. Es könnte ratsam sein, die Zahl der einem Elternpaar zugestandenen Kinder von dessen "Fitneß" abhängig zu machen, damit sich die besser geeigneten Fragmente in der Bevölkerung anhäufen und bessere Rekombinationschancen haben.

3. Selektion. Weniger geeignete Lösungen werden aus dem Bestand ausgemerzt.

4. Die Fitneß der verbleibenden Lösungen wird überprüft. Erweist sie sich als unzulänglich, so geht es zurück zu Schritt 2. Züchtung und Selektion werden wiederholt, gegebenenfalls so lange, bis diese Art der Evolution entweder die erwünschten Resultate liefert, oder bis der Entwickler die Nase voll hat und das Experiment abbricht.

Die Grundidee bei alledem ist, daß sich durch Paarung und Selektion im Laufe der Generationen gute Lösungsfragmente in der Bevölkerung ansammeln und die noch besseren rekombinieren, während der Anteil der weniger guten oder ausgesprochen schlechten Lösungen abnimmt.

Mutation führt ständig neue Problemlösungs-Elemente (neue Gene oder Chif­fren) in die evolvierende Bevölkerung individueller Problemlösungen ein und verhütet somit, daß ihre Entwicklung rasch in einer Sackgasse steckenbleibt

Dies ist in groben Umrissen, wie sich Optimierungsprozesse mittels genetischer Algorithmen nachvollziehen lassen. Sie simulieren den von Charles Darwin entdeckten Optimierungsprozeß der biologischen Evolution.