Genetische Operatoren

2 Genetische Operatoren

Unter Genetischen Operatoren versteht man die Möglichkeiten, die zur Kreuzung und Mutation von Individuen zur Verfügung stehen. Im Beispiel des Rucksackproblems wurden schon einige genannt: Ein-Punkt-Kreuzung, Mutation und Fitnessfunktion. Da die kleinste Informationseinheit in dem Fall die Länge 1 Bit besitzt, sind Kreuzung, Mutation und Fitnessfunktion recht einfach zu gestalten.

Selektion

Werfen wir wieder zuerst einen Blick auf die Natur: Es ist zwar im Großen und Ganzen so, dass Darwins Lehre sich als richtig erwies, d.h. der Stärkere, oder auch „Fittere\\\’\\\‘ macht das Rennen in Sachen Fortpflanzung. Man muss jedoch auch bemerken, dass durchaus auch weniger starke Lebewesen die Möglichkeit bekommen, ihr Erbgut weiter zu geben. Dieser Mechanismus macht durchaus Sinn, denn ohne ihn würde sich die Population schnell angleichen, nahezu identisches Erbgut könnte in allen Lebewesen einer Population gefunden werden. Wir kennen dieses Phänomen als „Darwin-Finken\\\’\\\‘.

In der GP wollen wir ähnlich vorgehen und nicht nur die N besten Individuen zur Fortpflanzung heranziehen, sondern auch mit geringerer Wahrscheinlichkeit schlechte Individuen vermehren. Das sichert der Population die nötige Vielfalt und vermeidet die Konvergenz auf ein lokales Maximum, indem weite Teile des Suchraums erforscht werden.

Wettkampf-Strategie

Bei der Wettkampf-Selektion werden in jedem Schleifendurchlauf N Individuen einer Population ausgewählt. Das Beste von diesen Individuen wird gespeichert und der Durchlauf wiederholt. Die Rekursion wird so oft durchgeführt, wie Individuen ausgewählt werden sollen. Jedes ausgewählte Individuum sollte aus dem Pool entfernt werden, um zu gewährleisten dass nicht zweimal das gleiche Individuum ausgewählt wird.

Elitismus(n,m-Wettkampf)

Aus der Population der Größe m sollen n Individuen ausgewählt werden. Ist die Zahl der zum Wettkampf herangezogenen Individuen n gleich der Größe der Population m, so werden nur die besten Individuen ausgewählt und man spricht von einer n,m-Wettkampf-Selektion. Diese ist gleichzusetzen mit der einfachsten Form der Auslese: Elitismus. Dabei wird die Population nach den Fitnesswerten(größter zuerst) der Individuen sortiert und die ersten N Individuen ausgewählt.

Mehr-Punkt-Kreuzung

Unter Multipoint-Crossover versteht man im einfachsten Fall(Ein-Punkt-Kreuzung) das „zerschneiden\\\’\\\‘ zweier Gencodes,die danach zu zwei neuen Kind-Individuen zusammengefügt werden, wobei die beiden Hälften der Eltern vertauscht werden(siehe Rucksack).

Man kann diesen Fall erweitern und zwei oder mehr Bruchpunkte bestimmen. Zwei Bruchpunkte erzeugen somit drei Teile, die sich vertauschen lassen und zu theoretisch drei Kind-Individuen führen könnten usw.
Wir wollen aber immer nur zwei Kind-Individuen erzeugen und gehen daher folgendermaßen vor:
Der Gencode bestehe aus N Allelen, mit N=(1,2,3,…). MP-Crossover kann auf maximal N Allele angewendet werden, d.h. es darf an höchstens N-1 Stellen im Gencode geschnitten werden, um keinen Index-Fehler im Programm zu erzeugen. Ein Gencode bestehe aus 5 Allelen, welcher an vier Stellen gekreuzt werden soll. (Allele mit Buchstaben gekennzeichnet)

Elter 1: A | B | C | D | E
Elter 2: F | G | H | I | J

Es entstehen pro Elternteil(Elter) 5 Teile, die nun neu zusammengefügt werden müssen. Um flexibel in der Anzahl der Kreuzungspunkte zu bleiben, habe ich mich dafür entschieden, jedes ungerade Allel des ersten Elters und jedes gerade des zweiten Elters in das erste Kind-Gen zu kopieren. Für das zweite Kind-Gen wird der Ablauf umgekehrt.

Kind 1: A | G | C | I | E
Kind 2: F | B | H | D | J

Mutation

Unter Mutation versteht man das zufällige Verändern einzelner Genteile um dadurch neue Informationen in das Genom schleusen zu können.

Bitweise Mutation

Es werden zufällig n Positionen im Gencode ermittelt. An diesen Stellen wird ein Bitflip durchgeführt.(Siehe Rucksack)

Ersetzung

Die Ersetzung der Individuen einer Population wird ebenfalls mittels Wettkampf-Schema durchgeführt. Es werden wiederum n Individuen ausgewählt. Diesmal wird jedoch das Schlechteste ausgewählt und aus dem Pool entfernt, bevor die Schleife wiederholt durchlaufen wird. Wenn ebenfalls N Rekursionen durchgeführt werden, bleibt die Größe der Population konstant und somit kontrollierbar. Die Anwendung hat gezeigt, dass es von Vorteil ist, einige der schlechtesten Individuen nicht sofort aus der Population zu löschen.

Fitnessfunktion

Eine Fitnessfunktion ist eine Gleichung, die festlegt, wie „gut\\\’\\\‘ ein Individuum ist. In der Natur wird dieser Wert ermittelt, indem das Individuum heranwächst und sich in seiner Umwelt behauptet. Im Computer müssen wir ähnlich vorgehen: wir werden den Gencode in seine phänotypische Form umwandeln und daraus seine Fitness ableiten. Beim Rucksackproblem auf Seite [*] wird das gelöst, indem die Wertigkeiten aller mitzunehmenden Gegenstände summiert werden. Um aber ein großes Spektrum der mit GA lösbaren Probleme abzudecken folgt nun eine allgemeine Herangehensweise für Fitnessfunktionen:

Grundsätzlich sollte ein hoher positiver Fitnesswert auf eine gute Fitness schließen lassen. Jeder Einflussfaktor kann einzeln gewichtet werden. Damit erreicht man, dass es in der Fitnessfunktion wichtige und eher unwichtige(und welche dazwischen) Einflüsse gibt. Soll ein zahlenmäßig großer Faktor für einen relativ kleinen Fitnesswert sorgen, so sollte dieser als Kehrwert in die Funktion eingehen.
Allgemein gilt:

$ F\\\\left( a_1,\\\\ldots ,a_n \\\\right) \\\\ldots Fitnessfunktion$
$ g_i \\\\ldots Wichtung \\\\; der\\\\; Faktoren$
$ a_i \\\\ldots Faktoren \\\\; der\\\\;Fitnessfunktion$
$ i=\\\\left(1,2,3,4,\\\\ldots ,n\\\\right)$
$ F\\\\left( a_1,\\\\ldots ,a_n,g_1,\\\\ldots ,g_n \\\\right)=\\\\sum\\\\limits_{i=1}^{n}\\\\left(g_i*a_i\\\\right)$

Die Gewichte sollten so gewählt werden, dass der Fitnesswert den größtmöglichen Zahlenbereich nicht überschreitet. So ist man bei einer Größenordnung von 32 Bit zwar nicht gerade begrenzt, doch wenn sich jemand enscheiden sollte, die Funktion folgendermaßen zu erweitern, stößt man rasch auf Grenzen der 32-Bit-Technik:

$ b_i … Exponenten \\\\;f\\\’\\\’ur\\\\; jeden \\\\;Faktor$
$ i=\\\\left(1,2,3,4,\\\\ldots ,n\\\\right)$
$ F\\\\left( a_1,\\\\ldots ,a_n,g_1,\\\\ldots ,g_n \\\\right)=\\\\sum\\\\limits_{i=1}^{n}\\\\left(g_i*a_i^{b_i}\\\\right)$

Diese Form der Fitnessfunktion hat einen entscheidenden Vorteil: mittels des Exponenten b lässt sich die Streuung der Fitnesswerte weitaus stärker beeinflussen. Die Entropie nimmt drastisch zu, was in einigen Fällen erwünscht ist, beispielsweise, wenn statistische Faktoren die Fitness beeinflussen. Anstelle des Kehrwertes kann ein Wert auch negativ in die Gleichung eingehen, wenn er dafür sorgen soll, die Fitness zu verringern, wenn er groß ist und zu erhöhen, wenn er klein ist.

Schreibe einen Kommentar