Genetische Programmierung

3 Genetische Programmierung

Aufbau Turingmaschine

Man stelle sich einen Kassenttenrecorder vor. Er verfügt über ein Band und einen Schreib-/Lesekopf, welcher mit dem Band arbeiten kann.
Das Band T(Tape) ist theoretisch unendlich lang und enthält Zeichen eines Alphabets Es wird mit 0 beginnend indiziert und nach links mit negativen und nach rechts mit positiven Indizes markiert. Somit befindet sich der Anfang in der Mitte des Bandes.

Arbeitsweise:

StartPosition: 0, StartZustand: 0, HaltZustand: H
1. Lies Zeichen an Position 0
2. Lies aktuellen Zustand aus
3. Suche aus Regelwerk eine passende Regel
4. Wende Regel an,d.h. Schreibe ein Zeichen S, wechsle in Zustand Z und bewege Band eine Position nach links oder rechts.
5. wenn Z ungleich Haltzustand, beginne wieder bei 1., sonst Halte an(Verarbeitung abgeschlossen)
Hier ein Beispiel:
Das Band enthält folgende Zeichen an den Positionen(0-9) :
_______111+11111=_______
…10123456789….(Positionsnummern)

Die Unterstriche stehen für das Leere Zeichen(Leerzeichen). Ich habe mich für den Unterstrich als Symbol für das Leere Zeichen entschieden, weil er am deutlichsten ist und selten gebraucht wird. Beispielsweise kann man für die Addition folgendes Regelwerk erstellen:
Eingabezeichen Akt. Zustand Ausgabezeichen Folgezustand Bewegungsrichtug
\\\‘ 1 \\\‘ 0 1 0 R
\\\‘ + \\\‘ 0 1 1 R
\\\‘ = \\\‘ 1 _ 2 L
\\\‘ 1 \\\‘ 1 1 1 R
\\\‘ 1 \\\‘ 2 _ H L

In Kurzform: (weitere Möglichkeit:)
1,0 : 1,0,L
+,0 : 1,1,R
=,1 : _,2,L
1,1 : 1,1,R
1,2 : _,H,L
1,0 : 1,0,R
+,0 : 1,0,R
=,0 : _,1,L
1,1 : _,H,L

Beide Regelwerke erzeugen aus einem Ausdruck der Form: 111+11111=
einen Ausdruck der Form: 11111111__
Man kann das als unäre Addition verstehen,d.h. 111 steht für drei, 11111 für fünf. In dezimaler Schreibweise also „3+5= \\\’\\\‘.
Das Ergebnis kann wieder durch Zählen der Einsen ermittelt werden: acht Einsen=8, d.h. 3+5=8.

Damit ergeben sich fünf Alphabete: $ \\\\Sigma_I $Eingabe-Alphabet
$ \\\\Sigma_O $Ausgabe-Alphabet
$ \\\\Sigma_{ZA} $Alphabet aller lesbaren Zustände
$ \\\\Sigma_{ZF}$ Alphabet aller möglichen Folgezustände $ \\\\left( \\\\Sigma_{ZF}=\\\\Sigma_{ZA}+\\\\Sigma_{Ze}\\\\right) ;Ze=Endzustand$
$ \\\\Sigma_M $Alphabet aller möglichen Bewegungsrichtungen

Nun kann man sich einen Vektor zurechtdefinieren, der eine vollständige Turing-Regel darstellt:

$ \\\\vec T_R=\\\\left\\\\lbrace S_{I} ,\\\\; S_{ZA} , \\\\;S_{O} , \\\\;S_{ZF} , \\\\;S_M\\\\right\\\\rbra… …\\\\Sigma_{ZA} , \\\\;S_{O}\\\\in \\\\Sigma_O , \\\\;S_{ZF}\\\\in \\\\Sigma_{ZF} , \\\\;S_M\\\\in \\\\Sigma_M$

Ein weiterer Vektor kann definiert werden, der die Anzahl der Zeichen jedes Alphabets enthält.
$ \\\\vec T_A=\\\\left\\\\lbrace \\\\vert\\\\Sigma_I\\\\vert , \\\\;\\\\vert\\\\Sigma_{ZA}\\\\vert , \\\\;\\\\vert\\\\Sigma_O\\\\vert , \\\\;\\\\vert\\\\Sigma_{ZF}\\\\vert , \\\\;\\\\vert\\\\Sigma_M\\\\vert\\\\right\\\\rbrace $

Ein vollständiges Turingregelwerk kann wiederum als Vektor verstanden werden:
$ \\\\vec T_A=\\\\left\\\\lbrace \\\\vert\\\\Sigma_I\\\\vert , \\\\;\\\\vert\\\\Sigma_{ZA}\\\\vert , \\\\;\\\\vert\\\\Sigma_O\\\\vert , \\\\;\\\\vert\\\\Sigma_{ZF}\\\\vert , \\\\;\\\\vert\\\\Sigma_M\\\\vert\\\\right\\\\rbrace $

Codierung im Gencode

Turing-Regeln sind blockweise angeordnet, wobei jeder Block einem Codon entspricht und somit eine Informationseinheit kodiert. Hier ein Beispiel einer Bitkette:
(Addition)
benötigte Alphabete:
$ \\\\Sigma_{Eingabe}=\\\\{1,+,=\\\\}\\\\\\\\ \\\\Sigma_{Akt. Zustand}=\\\\{1,2,3,4\\\\}\\\\\\\\ \\\\Sigma_{Aus… …\\\\}\\\\\\\\ \\\\Sigma_{Folgezustand}=\\\\{1,2,3,4,H\\\\}\\\\\\\\ \\\\Sigma_{Bewegungsrichtung}=\\\\{R,L\\\\}$

Regelformat:
[<Input> \\\‘,\\\‘ <akt. Zust> \\\‘:\\\‘ <Output> \\\‘,\\\‘ <Folgezust.> \\\‘,\\\‘ <Bew.-richtung>]
… … Regel k Regel k+1 … … (Formal)
… … 011 00 101 00 1 101 10 010 01 0 … … (Genotyp)
… … \\\’1\\\‘ \\\’3\\\‘ \\\’_\\\‘ \\\’H\\\‘ \\\’R\\\‘ \\\’+\\\‘ \\\’1\\\’\\\’1\\\‘ \\\’2\\\’\\\’L\\\‘ … … (Phänotyp)
… … 1 , 3 : _ , H , R + , 1 : 1 , 2 , L … … (Turing-Programm)

Um den Genotyp in den Phänotyp zu konvertieren, wird der Gencode codonweise, jedes Codon wiederum Blockweise für jedes Zeichen bearbeitet. (Als Block wird hier jeweils ein Untercodon eines Codons bezeichnet)
Ist das getan, kann der Binärcode jedes Blocks in Dezimalcode umgewandelt und als Indexnummer genutzt werden. Ist diese Zahl größer, als die Anzahl der für die aktuelle Information möglichen Zeichen, so wird der Modulo gebildet und ein neuer Index innerhalb des Alphabets ausgewählt. Wie sie sehen, ergibt sich hierbei eine doppel-Codierung, welche man vorteilhaft für seine Zwecke nutzen, die aber auch störend wirken kann.

Wir wollen Gene weiterhin in Form von Bitketten darstellen, d.h. jedes Zeichen eines Alphabetes muss mittels einer Kombination aus Nullen und Einsen dargestellt werden. Dabei ergeben sich zwei Probleme:
1. Wieviele Bits sind notwendig, damit alle Zeichen eines Alphabets codiert werden können?
2. Davon ausgehend, dass man mit einer Bitkette der Länge c genau $ 2^c$ Kombinationen erhält, kann man auch genausoviele Zeichen damit codieren. Was passiert, wenn die Anzahl der Zeichen nicht genau einer ganzzahligen Potenz von 2 entspricht?
Sind alle Alphabete ermittelt und als Variable vorliegend, so kann man mittels einer Schleife die Anzahl der zur Codierung nötigen Bits bestimmen:

k…Anzahl der Zeichen
n=0;
while(k>=$ 2^n$ AND k<$ 2^(n+1)$) do:(n=n+1)

Wenn die Schleife abbricht, wird (n+1) zurückgegeben.
Man könnte jetzt der Einfachheit halber jedem Zeichen eine fortaufende, ganze Zahl j zuordnen und diese dann in binären Code umsetzen. Damit erhält man die gewünschte Menge an Codierungs- Kombinationen. Sollte j dabei größer werden, als die Anzahl der Zeichen k, wird einfach der Modulo von k und j gebildet( Index=k mod j ). Dabei kann man sicher sein, dass höchstens k-1 Zeichen doppelt codiert sind, weil k immer zwischen zwei Zweierpotenzen a und b liegt, und der Modulo laut Definition nie ein Ergebnis größer als b liefern kann. Sind z.b. 5 Zeichen zu codieren, so braucht man mindestens drei Bits, was aber 8 Kombinationen ermöglicht. Leider gibt es keine halb-, oder drittel-Bits, die uns genau 5 Kombinationen ermöglichen würden, also muss man sich ein wenig Hilfe bei der Natur holen.
Wenn mehr Kombinationen existieren, als Zeichen, ordnen wir einigen Zeichen einfach mehrere Bitkombinationen zu:

Bsp: 5 Zeichen = 3 Bit = 8 Kombinationen, binär aufsteigend geordnet(000=0,001=1,..,110=6,111=7)

Zeichen Kombination
a 000;101
b 001;110
c 010;111
d 011
e 100

Im Falle der GP soll einer gegebenen Bitkette ein ganzes Regelwerk zugeordnet werden. Daher muss sein Gencode blockweise interpretiert werden, was einen schematischen Aufbau erfordert. Aufgrund der o.g. Definitionen der Turing-Alphabete, kann man exakt bestimmen, wieviele Bits benötigt werden, um ein Zeichen zu codieren.
Hat man die für jedes Alphabet benötigte Bitzahl ermittelt, kann man errechnen, aus wievielen Bits eine Regel(ein Codon) bestehen muss, indem man alle Elemente des Vektors $ \\\\vec T_A $aufsummiert. Daraus wiederum ergibt sich die Gesamtlänge der Gencodes, wenn die Zahl der Regeln bekannt ist. Die Startpopulation muss demnach so initialisiert werden, dass genau n*(Codonlänge) Bits generiert werden. Eine Schleife, die bei jedem Durchlauf zufällig eine Eins oder Null an den Gencode anhängt, erfüllt diesen Zweck sehr gut.
Man könnte die Initialisierung der Population noch verfeinern, indem man keine feste Codon- Anzahl benutzt, sondern diese für jedes Individuum zufällig(immer als ganzes Vielfaches der Codonlänge) bestimmt, aber wir begnügen uns mit einer festen Start-Größe.

Anpassung der Operatoren

Da es sich bei der Genetischen Programmierung um größere Informationsblöcke handelt werden wir einzelne Informationen in einem Codon codieren. Dadurch können o.g. Operatoren fast vollständig übernommen werden. Es werden neue Operatoren für die Mutation eingeführt und der Aufbau der Fitnessfunktion verdeutlicht.

Kreuzung

Da die meisten Anwendungen Genetischer Algorithmen, wie auch die der Gewnetischen Programmierung nicht so einfacher Art sind wie im Beispiel des Rucksackproblems, werden wir den Begriff des Codons einführen. Ein Codon ist eine Mehrstellige, informationscodierene Einheit im Gencode, d.h. es werden mehrere Bits zusammengefasst, um eine Information zu codieren. Dieses Prinzip ist hier von der Natur direkt übernommen und kann auf Seite [*] am Anfang des Kapitels „Natürliche Kodierung der Erbinformationen\\\’\\\‘ nachgelesen werden.
Angewandt auf die Kreuzung zweier Individuen, die ein komplettes Turing-Regelwerk darstellen, darf ein Genom nur an ganz bestimmten Stellen geteilt werden, nämlich an den Grenzen eines ganzen Codons. Das ist nötig, um zu gewährleisten, dass nur syntaktisch korrekte Programme entstehen, da jede einzelne Regel eines Regelwerkes der Turingmaschine eine Informationseinheit darstellt. Das Genom bestehe aus N Codons. Dadurch dürfen maximal N-1 Bruchpunkte existieren, an denen gekreuzt wird. Da es zusätzliche Operatoren gibt, die den Gencode Codonweise kürzen, muss vor jedem Kreuzungsprozess die Codonanzahl des Genoms ermittelt oder wie im Programm in einer eigenen Individuum-Klasse gespeichert werden.

Mutation

Die einfache, bitweise Mutation des Gencodes ist für Zwecke der GP nicht ausreichend. Da Programme bekanntermaßen unterschiedliche Längen haben, müssen Mutationsoperatoren eingeführt werden, die Teile in den Code einfügen oder aus ihm heraustrennen.

Kürzen des Gencodes

Es wird zufällig ein Codon ausgewählt, welches aus dem Code entfernt wird. Der Operator kürzt das Programm und sorgt somit dafür, dass evtl. sinnfreie Informationen aus dem Programm verschwinden, bzw. dass der Gencode darauf vorbereitet wird, ein kürzeres Programm entwickeln zu müssen. Die entsprechenden Änderungen der einzelnen Regeln sollen dann erfolgen, indem Mutationsoperatoren ausgeführt werden.

Hinzufügen eines Codons

Per Zufallsgenarator wird eine Position P im Gencode ermittelt. Danach wird eine Bitkette zufällig erzeugt und an der ermittelten Stelle P eingefügt. So gelangt neue Information in den Genpool. Der Operator ändert die Programmlänge und bringt neue Informationen in das Chromosom.

Invertieren eines Codons

Das Invertierungssystem wurde auch in der natürlichen Mutation nachgewiesen und sollte daher Einzug in die GP halten. Es wird zufällig ein Codon aus dem Gencode ausgewählt und herausgetrennt. Alle Bits werden in umgekehrter Reihenfolge wieder an die gleiche Codon-Position geschrieben.

Anpassung der Fitnessfunktion

Um eine wirksame Fitnessfunktion zu finden, die ein Turingprogramm sachgemäß einstuft, bedarf es einiger Überlegung und ein wenig Probierarbeit.
Es muss überprüft werden, wie gut das produzierte Ergebnis an das gesuchte herankommt. Dazu braucht man eine statistische Funktion, die das Maß der Übereinstimming zweier Strings misst.
Weiterhin muss bei Ausführung des Turingprogramms mitgezählt werden, wieviele Rechenschritte benötigt wurden, um das gesamte Programm auszuführen.
Dabei kann auch gleich ermittelt werden, wieviele verschiedene Programmzeilen(Regeln) zur Ausführung benötigt wurden. Natürlich muss man auch über das Wissen verfügen, wieviele Regeln das gesamte Regelwerk nun eigentlich umfasst.

auch ist es notwendig, sog. Nullbedingungen einzuführen. Diese dienen dazu, keinesfalls lauffähige Programme mit einer Fitnes von Null zu belegen. Dazu gehört die Syntaktische Korrektheit der Regeln, d.h. die Alphabete der geforderten und der produzierten Ausgabe werden verglichen. Sollten nicht alle gewünschten Zeichen in der produzierten Ausgabe vorkommen, wird die Fitness auf Null gesetzt. Weiterhin dürfen keine Zeichen der Eingabe auf dem Band verbleiben, sofern sie nicht auch im Alphabet der Ausgabe vorkommen. Sollte sich keine einzige Regel anwenden lassen, soll auch dies entsprechende negative Auswirkungen auf die Fitness haben.
Natürlich ist es wichtig, Programme zu honorieren, die ein Ergebnis liefern, dass völlig mit dem gewünschten übereinstimmt. der Faktor 5000 hat sich hierbei als ausreichend deutlich erwiesen.
Hilfreich ist es auch, das völlige Fehlen falscher Regeln mit einer Verdopplung der Fitness zu honorieren.

Mit diesen Informationen und einigen Gewichtungsfaktoren(durch Probieren ermittelt) kann man eine Fitnessfunktion gestalten, die nach durchschnittlich 600 Generationen(Additon) bzw. 450(Multiplikation) ein funktionierendes Programm ausgibt.
$ 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)$

$ a_1$… Übereinstimmung des Zeichensatzes auf dem Band mit gewolltem Output-Zeichensatz
$ a_2$… Zahl der benötigten Rechenschritte $ a_2=a_2^{-1}$
$ a_3$… Anzahl der Regeln $ a_3=\\\\^{a}a_3$

Nullbedingungen:(unerlaubte Programme etc.)
$ n_1$… Zeichen, die vorkommen sollen, aber nicht produziert werden
$ n_2$… mindestens ein unerlaubtes Zeichen aus Input auf Band verblieben
$ n_3$… keine gültige Regel enthalten

Gewichte der Faktoren :
$ g_1=100$
$ g_1=100$
$ g_1=1$
Algorithmus zur Fitness-Ermittlung eines Individuums: $ \\\\lbrace$ Für jeden Trainingsdatensatz : $ WENN \\\\left( n_1\\\\; ODER \\\\;n_2\\\\; ODER \\\\;n_3 \\\\;erf\\\’ullt\\\\right) \\\\; DANN \\\\;:\\\\; Fitn… …utzten Zeilen=a_3\\\\right) DANN : L\\\’\\\’osung gefunden ! \\\\left(GA\\\\^{a}Abbruch\\\\right)$

Schreibe einen Kommentar