1 Biologische Grundlagen
Aufbau und Funktionsweise der DNA
DNS/DNA(Desoxyribonukleinsäure/-Acid[engl. Acid: Säure]) codiert Aminosäuren, die Bestandteile des Lebens. DNA besteht hauptsächlich aus vier Grundmolekülen, den Basen: Adenin, Guanin, Thymin und Cytosin(A,T,G,C) Jeweils zwei von ihnen können miteinander eine Verbindung eingehen: A und T, C und G. Wie wir hoffentlich alle noch aus dem Biologieunterricht wissen, (ansonsten:[Wiki1]-Kapitel 7), besteht DNA aus vielen dieser Brückenbausteine(Basenpaare), der Reihe nach angeordnet.
… ATC GGA ATC CCT …
… | | | | | | | | | | | | …
… TAG CCT TAG GGA …
Drei dieser “Stufen“ bilden ein sog. Codon, also die kleinste Informationseinheit im Gencode. Eine Mutation eines Codons wird Allel genannt. Da man jede Stufe in jeder Richtung in den Genstrang einfügen kann(A-T,T-A;C-G,G-C), ergeben sich 4^3 = 64 mögliche Kombinationen, um eine Informationseinheit zu codieren. Da es aber nur 20 Aminosäuren gibt, müssen einige von ihnen mehrfach codiert sein! Biologen haben herausgefunden, welche Kombination welche Aminosäure codiert. Das Ergebnis: Einige sind einfach codiert, einige mehrfach, bis zu sechs mal, um genau zu sein. In der Informatik nennt man dies Form der Kodierung gemeinhin “Redundanz“ und wird benutzt, um zum Beispiel häufige Tippfehler zu korrigieren, indem man verschiedene Schreibweisen eines Wortes eindeutig einer richtigen Schreibweise zuordnet. Sicherlich wird die Natur auch hier korrigieren “wollen“ und häufig benutzte Aminosäuren bevorzugt auswählen bzw. häufig auftretende Fehler vermeiden.
Natürliche Kodierung der Erbinformationen
Die Informationen über Aminosäuren werden in unseren Genen auf recht einfache Art und Weise kodiert. Jedes Basen-Triplett(drei eufeinanderfolgende Basenpaare) codiert eine Aminosäure:
… ATC GGA ATC CCT …
… | | | | | | | | | | | | …
… TAG CCT TAG GGA …
… Ile Gly Ile Pro …
(Ile: Isoleucin,Gly: Glycosin, Pro: Prolin)
Aminosäuren sind komplexe Kohlenstoffverbindungen, die, tausendfach zusammengesetzt, einzelne Zellen oder Flüssigkeiten bilden. Die Struktur eines Lebewesens ist sehr komplex, wobei sich der Grad der Komplexität zwischen Tieren/Menschen und Pflanzen um einige Potenzen unterscheidet. Nach genaueren Untersuchungen der Genome verschiedenster Spezies ist man zum vorläufigen Schluss gekommen, dass sich der Aufbau und das Zusammenspiel der Zellen und Organe von Pflanzen sowie Tieren allein aus der Reihenfolge der Basen-Tripletts ergeben. Spricht man über Bakterien und einige Pflanzen, so mag das stimmen. Wendet man sich aber tierischen Genomen zu, so wird man sich schnell klar werden, dass die alleinige Anordnung der Gene, was gleichbedeutend wäre mit dem einfachen sequentiellen Ausführen einiger “Bauvorschriften“, bei weitem nicht fähig ist, derartig komplexe Strukturen, wie z.B. die eines Gehirns hervorzubringen. Das belegt auch die Tatsache, dass die Reispflanze über weitaus mehr Gene verfügt, als der Mensch. und wenn wir sie uns genauer ansehen, werden wir feststellen, dass sie keine derartige Komplexität erreicht hat, wie der Mensch.
Forscher haben bei ihren Untersuchungen sog. “Müll/Junk-DNS“ gefunden, die in allen tierischen Genomen vorkommt. Diese Form der DNS tritt im Wechsel mit gewöhnlicher, proteinkodierender DNS auf und wird Intron genannt, abgeleitet von der Tatsache, dass sie zwischen die kodierenden Teile, die Exons eingeschoben sind. Dieser angebliche Müll füllt 99% unseres Genoms aus. Hier wird deutlich, dass die Forschung bisher in die falsche Richtung verlief. Warum sollte die Natur so viel unnütze Erbinformationen mit sich herumtragen? Neueste Theorien deuten darauf hin, dass diese Informationen keineswegs unnütz sind, sondern eine entscheidende Rolle bei der Herausbildung unterschiedlicher Zellen spielt. Um den Gegenstand der Diskussion zu verdeutlichen folgt nun der schematische Aufbau unserer DNS:
Intron|Exon|Intron|Exon|Intron|Exon|Intron|Exon|Intron|Exon|…
Intronsequenzen werden vor der Herstellung eines Proteins ausgelesen und dafür genutzt, festzulegen, an welcher Stelle das Protein abgelegt werden soll. Man kann diesen Vorgang damit vergleichen, ein Haus zu bauen. Dafür braucht man zwei Dinge: eine Materialliste und einen Bauplan. Würde man diese Liste nach Art der Genomcodierung aufschreiben würde das wohl ungefähr so aussehen:
Material|Ort|Material|Ort|Material|Ort|…
Zement|Boden unter erste und zweite Ziegelposition|Stein|unterste Reihe, erste Position|Stein|unterste Reihe, zweite Position|Zement|unterste Reihe, zwischen erste und zweite Position|…
nach diesem Schema wird ersichtlich, dass viel weniger Information dafür gebraucht wird, welches Material genommen werden muss, als dafür, wohin das Material zu legen ist. Daraus lässt sich schnell erklären, warum der Anteil der Introns in unseren Genen so enorm ist. Wollen wir das Thema hier beenden und die weitere Forschung den Genetikern überlassen.
Begriffe
Man unterscheidet in der Genetik zwischen Genotyp und Phänotyp eines Individuums.
* Genotyp bezeichnet nichts anderes, als die Darstellung des Lebewesens in verschlüsselter Form, also den Genstrang, der in einer jeden Zelle enthalten ist.
* Phänotyp wird die äußere Form genannt, die entsteht, wenn man Moleküle, wie sie im Genstrang beschrieben sind, anordnet. Damit wird also das fertige “Produkt“ Lebewesen bezeichnet.
In der Natur wird diese Übersetzung innerhalb der Zelle vorgenommen und in lange Molekülketten umgesetzt. Die Zelle kann also als molekularer Computer angesehen werden, dessen Eingabedaten die Gene sind und der als Output Proteine produziert. Wir wollen hier ncht klären, woher diese Mechanismen kommen und wozu sie der Natur nutzen sollen, sondern überlassen das lieber der Biologie und Philosophie.
Man kann dieses Modell in zweierlei Richtungen für eigene, informatische, Zwecke gebrauchen. Erstens ließen sich damit “Computer im Reagenzglas“ ([StoStu]-Kapitel 7) bauen, die ihrerseits auch mit Molekülen als Input und Output arbeiten. Da wir jedoch nur beschränkt über die Chemie herrschen können, sollte für unser Ziel ein anderer Weg favorisiert werden: Man ahmt den Evolutionsprozess auf heutigen digitalen Computern nach und versucht damit komplexe Problem zu lösen.
Abstraktion eines Algorithmus
Um die Mechanismen der Evolution nutzen zu können, bedarf es natürlich eines Algorithmus. Da wir diesen ja frei abstrahieren können, werden wir ihn so einfach wie möglich gestalten.
1. erstelle einige zufällige Genketten
2. bestimme den Phänotyp der Genketten
3. ermittle, wie gut die Phänotypen ihre Aufgabe erfüllen
4. wähle die besten Individuen aus
5. Kreuze die Gene dieser Individuen und erstelle daraus Kindgene. Mutiere gegebenenfalls
6. Ersetze die schlechtesten Individuen durch die neuen Kindindividuen.
7. Falls Abbruchbedingung nicht erfüllt, Weiter bei Schritt 2, sonst Ende.
Im siebten Schritt muss eine Abbruchbedingung vorliegen. Die Natur hat soetwas natürlich nicht, aber sie ist ja auch kein Programm, das gewisse Probleme lösen und am Ende stehenbleiben soll. Im nachfolgenden Beispiel wird der Algorithmus besser veranschaulicht.
Einführungsbeispiel Rucksackproblem
Sie werden folgendes sicherlich kennen: der Urlaub steht bevor. Neben Kühlschrank, Fernseher, Hifi-Anlage und dem gesamten Kleiderschrank wollen sie auch noch einige Nahrungsmittel, Verbandszeug, Zeitungen, Seife, Töpfe, Waschmittel, Ersatzschuhe etc. in ihrem Rucksack mitnehmen? Das wird problematisch, da Sie als normaler Mensch selten mehr als 20 kg auf dem Rücken tragen wollen. Nun könnten sie den Kühlschrank zu Hause lassen und dafür den Verbandskoffer mitnehmen oder auch den Fernseher stehen lassen und dafür ein gutes Buch mitnehmen. Welche Kombination nun aber die gescheiteste ist, können sie aufgrund der vielen Gegenstände nicht sofort einschätzen.
Der sicherste Weg, die ideale Kombination herauszufinden ist, jedem Gegenstand einen persönlichen Wert zu geben, z.B. einen Wert zwischen 0 und 10 oder zwischen 0 und 100, wie sie wollen. Danach legen sie jedes Stück auf eine Waage und schreiben das Ganze in einer Tabelle auf. Die Letzte Spalte der Tabelle sagt uns, ob wir den Gegenstand mitnehmen(1), oder nicht(0). Unser Ziel ist es nun, die Kombination herauszufinden, die mit 20kg Gesamtmasse den höchsten Wert erreicht. Um eindeutig die beste Kombination an Gegenständen zu ermitteln, müsste man von allen möglichen Bepackungen diejenige finden, die am wertvollsten ist(Summe aller Wertigkeiten der mitzunehmenden Gegenstände), aber nur 20kg wiegt. Das macht bei nur 30 Gegenständen genau $ 2^30$ verschiedene Kombinationen. Ein moderner Computer vermag evtl. $ 2^9$ Rechenoperationen pro Sekunde auszuführen. Das macht bei $ 2^30$ Rechenoperationen $ 2^22$ Sekunden, was wiederum rund 48 Tagen entspricht. Schon bei 50 Gegenständen wächst die Rechenzeit auf gewaltige Siebzigtausend Jahre! Wir wollen hier einen wesentlich schnelleren Weg beschreiben. Tabelle zum Beispiel:
Gegenstand Persönlicher Wert Gewicht Mitnehmen?
Taschenmesser 8 0,2 kg Ja(1)
Kühlschrank 2 40kg Nein(0)
Verbandskasten 10 0,6 1
… … … …
Man kann diese Tabelle auch als Kette von Nullen und Einsen darstellen:
Gegenstand 1 2 3 4 …
Mitnehmen? 1 0 1 1 …
Sehen wir uns nur die unterste Zeile an, so könnte man diese als Gencode eines Binär-Lebewesens interpretieren, welches eine gepackten Rucksack beschreibt.
Genotyp: 1011101010001101110001100100
Phänotyp(Rucksack):
1. Taschenmesser: mitnehmen
2. Kühlschrank: nicht mitnehmen
3. Verbandskasten: mitnehmen
4. … :mitnehmen
…
Im ersten Schritt bedeutet das für unser Beispiel: wir erstellen einige zufällige Bitketten, z.B. acht Ketten der Länge 30, wenn 30 Gegenstände zur Auswahl stehen.
Diese werden im zweiten Schritt übersetzt, d.h. Die Bitkette wird Bit für Bit geprüft und im dritten Schritt wird die Wertigkeit und das Gewicht jedes Individuums(Rucksacks) ermittelt.. Findet das Programm an der aktuellen Position Pos eine 1, dann bedeutet das, der Gegenstand an Pos soll mitgenommen werden. Nun sucht man sich in der Tabelle an der angegebenen Stelle Gewicht und Wertigkeit des Gegenstandes heraus und speichert beide Werte. An Pos+1 wird sich evtl. wieder eine Eins finden, also muss auch dieser Gegenstand mitgenommen werden. Sein Gewicht wird auf das bisherige Rucksackgewicht aufaddiert, seine Wertigkeit auf den bisher erreichten Wert. Wenn die Bitkette vollständig geprüft wurde, wird zur nächsten übergegangen und der Vorgang wiederholt. Am Ende haben alle Rucksäcke ein spezifisches Gewicht und einen Wert.
Im dritten Schritt wird für jedes Individuum ein Fitness-Wert errechnet. Dieser gibt an, wie gut, oder fit ein Individuum ist. In unserem Fall entspricht die Fitness eines Rucksacks genau seinem Wert, d.h. je höher der Wert eines Rucksacks ist, desto fitter ist er.
Viertens werden alle Individuen nach ihrer Fitness geordnet und die N besten für die Fortpflanzung ausgewählt. Uns genügen erst einmal 4 Individuen.
Im fünften Schritt wird die Kreuzung vollzogen. Einfaches Bsp:
Kette 1: 0101011110011001010100001100
Kette 2: 0111010110100011101011001001
Es wird zufällig ein Schnittpunkt ausgesucht.(z.b. die Mitte), dann wird der erste Teil der ersten Bitkette und der zweite Teil der zweiten zu Kind Nr. 1 zusammengebaut. Aus den anderen Hälften wird ein zweites Kind erstellt:
Kette 1: 010101111001100|101010000110011
Kette 2: 011101011010001|110101100100101
Kind 1: 010101111001100|110101100100101
Kind 2: 011101011010001|101010000110011
Mutation wird realisiert, indem man für jede Stelle im Gencode zufällig eine Zahl A zwischen 0 und 1 bestimmt. Sollte $ A \\\\leq 0,5$ sein(was bei gleichverteilten Zufallszahlen in 50% der Versuche der Fall sein sollte), wird an der aktuellen Position ein Bitflip durchgeführt, d.h. Aus einer Eins wird eine Null und umgekehrt. Mit A kann man die Anzahl der Mutationen in einem Gen steuern. Wenn A klein ist( 0,03) dann wird selten mutiert, ist es groß, dann häufiger. Mutationen dienen dazu, neue Informationen in das Gen zu bringen.
Im sechsten Schritt werden die schlechtesten Individuen aus der Population entfernt und die Kindgene hinzugefügt. Normalerweise sollte die Zahl der aus der Population entfernten Individuen der Anzahl der Kind-Individuen entsprechen, um einen konstanten Fortlauf der Evolution zu gewährleisten.
Im siebten Schritt wird eine Abbruchbedingung abgefragt. In unserem Beispiel soll nach 500 Generationen Schluss sein und das bis dahin beste gefundene Individuum als Ergebnis präsentiert werden. Natürlich könnte man auch kompliziertere Abbruchbedingungen festlegen, wie z.B. dass erst aufgehört werden soll, wenn der beste Fitnesswert in der Population nach einer gewissen Zahl von Durchläufen keine oder nur geringe Änderungen erfährt.
Ein Beispieldokument, mit Openoffice-Calc und der integrierten Makro-Programmiersprache erstellt, liegt dem Aiccbot-Paket bei[OOoMak]7. Das Dokument bietet die Möglichkeit, Gegenstände und deren zugehörige Wertigkeit und Gewicht einzutragen. Ein GA wird nun damit beauftragt, geeignete Kombinationen zu finden. Dabei kann man mit der Anzahl der Durchläufe experimentieren. Ein Diagramm stellt die teilweise starken Fitnesssprünge dar und verdeutlicht so die relative Zufälligkeit aber auch die stetige Verbesserung der Ergebnisse.
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.
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)$
4 Optimierung
Kodierungsprobleme
Die Interpretation der Bits als Dualzahl kann im Falle der GP einige Gefahren bergen. Da der Gencode eines Individuums nur mit geringer Wahrscheinlichkeit mutiert wird, werden sich demnach auch nur wenige Bits durch Mutation verändern. Wie man aber deutlich sehen kann, muss man für die Änderung der Kombination von Zeichen \\\’d\\\’(011) zu Zeichen \\\’e\\\’(100) drei Bits verändern, obwohl man in der Tabelle nur um einen Platz nach unten rückt. Das macht es fast unmöglich, dass durch Mutation eine kleine Änderung im Phänotyp, also im resultierenden Turing-Programm, hervorgerufen wird. Die Anzahl der sich ändernden Bits von einer Bitkombination auf eine andere nennt man “Hamming-Klippe\\\’\\\’. Im Beispiel von d nach e beträgt sie drei bits. Je länger die Bitketten werden, desto mehr fällt dieser Effekt ins Gewicht und beeinflusst die Lauffreudigkeit des GA negativ.
Gray-Code
Messgeräte, die mit binärer Codierung arbeiten, haben ebenfalls ein großes Problem damit, Änderungen von mehr als einem Bit auf einem Messstreifen zu registrieren. Daher wurde einst der Gray- Code entwickelt.(Frank Gray, Patent: 1947)
Er besitzt die Eigenschaft, dass er zwar auch eine binäre Darstellung natürlicher Zahlen ist, jedoch ändert sich beim Sprung von einem Wert auf den nächsten grundsätzlich nur ein Bit.
Man geht dazu von dualer Codierung aus und übersetzt diese in Graycode, indem man immer zwei Bit mittels XOR vergleicht und das Ergebnis des Vergleichs als neues Gray-Bit setzt. Das erste Bit wird immer als erstes Gray-Zeichen übernommen. Im Nachhinein wird die Bitkette noch invertiert, um die Gray-typische Darstellung herzustellen. Bsp: (Gray to Bin):
$ g_i \\\\rightarrow b_j$
0. 1 $ \\\\rightarrow $ $ \\\\left(b_0=b_0=1\\\\right)$
1. 0 $ \\\\rightarrow $ $ \\\\left(b_1=\\\\left( 0 \\\\;XOR \\\\;1\\\\right)=1\\\\right)$
2. 1 $ \\\\rightarrow $ $ \\\\left(b_2=\\\\left( 1 \\\\;XOR \\\\;1\\\\right)=0\\\\right)$
3. 1 $ \\\\rightarrow $ $ \\\\left(b_3=\\\\left( 1 \\\\;XOR \\\\;0\\\\right)=1\\\\right)$
4. 0 $ \\\\rightarrow $ $ \\\\left(b_4=\\\\left( 0 \\\\;XOR \\\\;1\\\\right)=1\\\\right)$
$ invert\\\\left( Gray\\\\right)\\\\Rightarrow Bin\\\’ar : 11011\\\\newline$
Bei der Umwandlung von Gray- nach Binär-Code wird nicht innerhalb der Gray-Bitkette, sondern immer das aktuelle Gray-Bit mit dem zuletzt erzeugten Binär-Bit mittels XOR verglichen. Vorher muss der Gray-Code invertiert werden, um die umgekehrte Anordnung der Bits einfach zu realisieren.
Einführung verschiedener Spezies
In der Natur kann man ein grundsätzliches Vorgehen beobachten: jede Tier- und Pflanzenart hat ihren Zweck. Betrachtet man die Überlebensstrategien von Ameisen, die sich Läuse “halten\\\’\\\’ um sich von deren zuckerhaltigen Ausscheidungen zu ernähren, dann wird klar, dass jede Spezies eine eigene Aufgabe hat und diese als hochspezialisierter Profi erfüllt.
Um dieses System auf GP zu übertragen, ist es sinnvoll, eine art “Welt\\\’\\\’ zu programmieren, die unterschiedlichsten Spezies und deren Untergattungen Platz bietet. Dazu werden für jede Spezies u Unterpopulationen erstellt. Individuen zweier Unterpopulationen können sich nicht direkt durchmischen, d.h. ihre Entwicklung läuft getrennt ab. Weiterhin bedarf es einer Elite-Population, die die besten Individuen aller Unterpopulationen enthält. Führt man den GA auch auf dieser Elite-Population aus, sollte sich dort die beste, globale Lösung finden. Alle Versuche mit dem GP-System haben die Wirksamkeit dieses Systems belegt.
Kindergarten-Schema
Um die Konvergenzgeschwindigkeit des GA weiter zu erhöhen, wird ein sog. Kindergarten-Pool eingeführt. In jeder Generation werden k Individuen in den KiGa-Pool kopiert. Diese werden p Generationen lang darin aufbewahrt, ohne dass sie am Selektionsprozess teilnehmen dürfen. In jeder Generation wird versucht, die gespeicherten “Kinder\\\’\\\’ durch Mutation zu verbessern. Sollte sich eine Verbesserung einstellen, wird ein schlechtes Individuum in der “richtigen\\\’\\\’ Population durch das mutierte Kind ersetzt. Es befinden sich demnach stets p*k Individuen im Kindergarten.
Seniorenunterkunfts-Schema
Wie im richtigen Leben sollte es Älteren, aber fitten Individuen erlaubt sein, etwas länger am Selektionsprozess teilnehmen zu dürfen. Dazu wird ein Pool, ähnlich dem Kindergarten erstellt, in den in jeder Generation die m besten Individuen eingefügt werden. Diese werden über n Generationen aufbewahrt und dürfen in jedem Evolutions-Schritt am Selektionsprozess teilnehmen. Somit befinden sich stets m*n Individuen im Pool. Die Praxis zeigt auch hier, das ein solcher Pool die Konvergenzgeschwindigkeit erhöht, jedoch erwies sich die Implemetierung von Kindergarten und Seniorenunterkunft als fehlerträchtig und wurde deshalb in der Endversion nicht eingebunden.
5 Aufbau des Programmcodes
Das Projekt unterliegt der GNU General Public License. Die Lizenz liegt im Verzeichnis `Programmcode’ in der Datei License.txt
Diese Dokumentation unterliegt der GNU Free Documentation License, zu finden im Verzeichnis “Dokumentation“ in der Datei “gfdl\\\’\\\’
Das gesamte Projekt wurde in Pakete(Packages) aufgeteilt um die Übersichtlichkeit zu wahren.
Packages:
java: Nutzung JAVA-Eigener Funktionen, wie java.io.*,ArrayList, Math…
GenAlg: Klassen des Genetischen Algorithmus, wie Kreuzung, Fitnessbewertung, Population, Individuum, Steuerungsklasse(GAWorldManager)
Turing: Komplette Turingmaschine
ToolPack: Mathematische Werkzeuge (Gray2Bin,…), String-Funktionen, Sonstiges(Array-Größenänderung)
Eingabe der Trainingsdaten
Die Datei “config.aic\\\’\\\’ enthält alle wichtigen Einstellungen zum Programm. Hier finden sich auch Eingabemöglichkeiten für Trainingsdatensätze. Da man ja gewillt ist, die Turingprogramme gleich bei ihrer Entwicklung zu verifizieren, wird nicht nur ein TrainingsInput/Output angegeben, sondern mehrere. Die Anzahl hängt einfach davon ab, wieviele Ihnen zur Verfügung stehen. Bei einfachen Rechenaufgaben sollte es kein Problem darstellen, mehrere Datensätze einzugeben. Da eine Turingmaschine aber auch in der Lage sein soll, komplexe Konvertierungen von Zeichenketten(Chiffrierung/Dechiffrierung) vorzunehmen, wird in einer spräteren Version die Möglichkeit bestehen, reguläre Ausdrücke als Trainingsdaten anzugeben. AiccBot wird dann jede einzelne mögliche Zeichenkette überprüfen und bewerten. Die Fitness eines Programmes ergibt sich dadurch aus dem Durchschnitt aller erzielten Ergebnisse, was die Richtigkeit eines Programms beweisen würde.
6 Literaturverzeichnis
Literaturverzeichnis
[OOoMak] OpenOffice.org-Makro zum Rucksack-Problem(GAKnapSack.sxc)
[Wiki1] Wikipedia – Aufbau der DNA
[StoStu] Stoschek und Sturm – Molecular Computing
MolecularComputing
[WiGenPg] Wikipedie – Genetische Programmierung
[HabilKokai] Gabriella Kokai – Erfolge und Probleme evolutionärer Algorithmen, induktiver logischer Programmierung und ihrer Kombination
Kokai
GNU Free Documentation License
Version 1.2, November 2002
Copyright (C) 2000,2001,2002 Free Software Foundation, Inc.
51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
0. PREAMBLE
The purpose of this License is to make a manual, textbook, or other functional and useful document \\\”free\\\” in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.
This License is a kind of \\\”copyleft\\\”, which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.
We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.
1. APPLICABILITY AND DEFINITIONS
This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The \\\”Document\\\”, below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as \\\”you\\\”. You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law.
A \\\”Modified Version\\\” of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.
A \\\”Secondary Section\\\” is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document\\\’s overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.
The \\\”Invariant Sections\\\” are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none.
The \\\”Cover Texts\\\” are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words.
A \\\”Transparent\\\” copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not \\\”Transparent\\\” is called \\\”Opaque\\\”.
Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only.
The \\\”Title Page\\\” means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, \\\”Title Page\\\” means the text near the most prominent appearance of the work\\\’s title, preceding the beginning of the body of the text.
A section \\\”Entitled XYZ\\\” means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as \\\”Acknowledgements\\\”, \\\”Dedications\\\”, \\\”Endorsements\\\”, or \\\”History\\\”.) To \\\”Preserve the Title\\\” of such a section when you modify the Document means that it remains a section \\\”Entitled XYZ\\\” according to this definition.
The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.
2. VERBATIM COPYING
You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.
You may also lend copies, under the same conditions stated above, and you may publicly display copies.
3. COPYING IN QUANTITY
If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document\\\’s license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.
If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.
If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.
It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.
4. MODIFICATIONS
You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:
* A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.
* B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement.
* C. State on the Title page the name of the publisher of the Modified Version, as the publisher.
* D. Preserve all the copyright notices of the Document.
* E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.
* F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.
* G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document\\\’s license notice.
* H. Include an unaltered copy of this License.
* I. Preserve the section Entitled \\\”History\\\”, Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled \\\”History\\\” in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.
* J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the \\\”History\\\” section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.
* K. For any section Entitled \\\”Acknowledgements\\\” or \\\”Dedications\\\”, Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.
* L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.
* M. Delete any section Entitled \\\”Endorsements\\\”. Such a section may not be included in the Modified Version.
* N. Do not retitle any existing section to be Entitled \\\”Endorsements\\\” or to conflict in title with any Invariant Section.
* O. Preserve any Warranty Disclaimers.
If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version\\\’s license notice. These titles must be distinct from any other section titles.
You may add a section Entitled \\\”Endorsements\\\”, provided it contains nothing but endorsements of your Modified Version by various parties–for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.
You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.
The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.
5. COMBINING DOCUMENTS
You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers.
The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.
In the combination, you must combine any sections Entitled \\\”History\\\” in the various original documents, forming one section Entitled \\\”History\\\”; likewise combine any sections Entitled \\\”Acknowledgements\\\”, and any sections Entitled \\\”Dedications\\\”. You must delete all sections Entitled \\\”Endorsements.\\\”
6. COLLECTIONS OF DOCUMENTS
You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.
You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.
7. AGGREGATION WITH INDEPENDENT WORKS
A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an \\\”aggregate\\\” if the copyright resulting from the compilation is not used to limit the legal rights of the compilation\\\’s users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document.
If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document\\\’s Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate.
8. TRANSLATION
Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail.
If a section in the Document is Entitled \\\”Acknowledgements\\\”, \\\”Dedications\\\”, or \\\”History\\\”, the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.
9. TERMINATION
You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.
10. FUTURE REVISIONS OF THIS LICENSE
The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.
Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License \\\”or any later version\\\” applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.
Alle Dateien des Projektes
Dokumentation: Genetische Programmierung einer Turingmaschine
Source: AICCboT Sourcecode
OpenOffice Makro zum Rucksackproblem: Rucksackproblem als OpenOffice Makro
Komplett: Das komplettpakte mit code, binaries, tex-docs etc. pp