Leseprobe
Inhaltsverzeichnis
1 Einleitung
2 Die biologische Evolution nach Charles Darwin
2.1 Genotyp und Phänotyp
2.2 Rekombination und Mutation
2.2.1 Crossing-Over
2.2.2 Mutation
2.2.3 Populationsgröße und Selektion
3 Genetische Algorithmen
3.1 Selektion
3.2 Variation
3.2.1 Kreuzung
3.2.2 Mutation
4 Beispiel eines genetischen Algorithmus
5 Genetische Algorithmen - technischer Darwinismus?
6 Fazit
7 Anhang
7.1 Literaturverzeichnis
7.2 Quellcode
1 Einleitung
” Die Naturhatuns 3,7 Milliarden Jahre Forschungszeit voraus. “ [98]
jedes Lebewesen unterliegt einer stetigen Veränderung. Sie passen sich von Generation zu Generation - scheinbar von alleine - immer besser an die Bedingungen ihrer Umgebung an. Grund dafür ist das Prinzip der Evolution, welches hauptsächlich von dem Biologen Charles Darwin geprägt wurde. [Dar[06]]
Das Grundlegende Prinzip der Evolution nach Charles Darwin besteht in der Abfolge von Rekombination, Mutation und Selektion, wobei stärkere und bessere Individuen eine höhere Chance aufs überleben haben. Die Evolution ist ein in der Natur sehr erfolgreicher, wenn auch langwieriger Prozess, welcher letztendlich auch zu der Entwicklung des modernen Menschen führte.
Die Optimierung von Prozessen ist einer der wichtigsten Aufgaben in der Modernen Industrie. Prozesse sollen schneller und sicherer ablaufen, denn nur so haben Firmen im Wettbewerb die besten Überlebenschancen.
Optimierung wird schon seit vielen Jahren als Wissenschaft vor allem im Bereich des Operations Research untersucht. Aber auch in der Mathematik wurden viele Verfahren vorgeschlagen und entwickelt. Ebenso wurden auch Neuronale Netze, die sich an dem Aufbau des Gehirns orientieren eine immer beliebtere Methode für Optimierungsprobleme.
Warum sollte man sich also nicht an dem Prinzip der Evolution bedienen? Wie das Zitat von Toby Simpson - einem Entwickler der Britischen Firma Cyberlife - bereits besagt, ist die Natur uns mit ihrer ”Forschung“voraus.Essprichtalsonichtsdagegendieseserfolg- reiche Prinzip der Natur ebenfalls zur Optimierung technischer Systeme heranzuziehen. Und dies geschieht auch, und zwar in Form von genetischen Algorithmen.
Das Ziel dieser Facharbeit ist es dem Leser das Prinzip genetischer Algorithmen, sowie die Grundlagen des Darwinismus näher zubringen und somit schließlich die Frage zu beantworten, in welchem Maße genetische Algorithmen wirklich nach dem Darwinismus von Charles Darwin arbeiten und ob genetische Algorithmen wirklich in der Lage sind den natürlichen Prozess der Evolution detailgetreu zu simulieren und ob sie sogar als perfekte Kopie der Evolution angesehen werden können.
2 Die biologische Evolution nach Charles Darwin
Die biologische Evolution ist in der Lage, das Leben immer besser an seine Umwelt an- zupassen und weiterzuentwickeln, wobei es aber immer noch flexibel genug ist, um auf Veränderungen dieser zu reagieren. Im Anbetracht der Tatsache, dass sich diese Strategie seit über 3,5 Milliarden Jahren bewährt hat, liegt es nahe, dass es sich bei der Evoluti- on um einen sehr flexiblen Optimierungsprozess handeln muss. Um die Evolutionstheorie nach Charles Darwin zu verstehen, stelle ich diese im folgenden die wesentlichen Elemente der Evolutionstheorie vor.
Jedes Lebewesen, jedes Individuum gehört zu einer Gattung, einer Art von Lebewesen, welche sich nur in kleinen Details unterscheiden. Jedes dieser Lebewesen ist somit Träger und gleichzeitig Tester einer möglichen Ausprägung seiner Gattung. Erreicht das Individu- um ein Fortpflanzungsfähiges Alter und erfüllt die für ihn notwendigen Randbedingungen (Sexualpartner, . . . ), werden seine speziellen Anpassungen an seine Nachkommen weiter- gegeben.
Bei dieser Weitergabe, können Fehler entstehen, sodass ein Individuum niemals einem anderen exakt gleicht. Dieses Verhalten wird insbesondere bei der zweigeschlechtlichen Fortpflanzung noch gravierender deutlich, da dort die Nachkommen durch die Kreuzung eine Mischung der Individuellen Ausprägungen seiner Eltern vererbt bekommt.
ÜbermehrereGenerationen hinweg setzen sich somit Merkmale, die zu einer höheren Fortpflanzungswahrscheinlichkeit führen in der gesamten Gattung durch. (Survival of the Fittest [Dar06, S. 91 f.])
Gleichzeitig führen die Fehler bei der Kreuzung dazu, dass immer wieder neue Merkmale entstehen können, welche sich in der gesamten Gattung ausbreiten oder wieder verschwin- den.
Zusammenfassend lässt sich der Evolutionsprozess nach Darwin wie folgt beschreiben: Ein Individuum wird durch seine Umwelt auf Tauglichkeit geprüft (Selektion) und erzeugt unter den notwendigen Bedingungen eine Anzahl an Nachkommen (Rekombination, Kreuzung), welche sich durch zufällige Veränderungen im Gencode anpassen (Mutation). Dabei wird dieser Prozess mit den Nachkommen immer weiter aufs neue durchlaufen. Da dieser Prozess innerhalb einer Generation mehrere tausend male gleichzeitig passiert, ergibt sich bei der Evolution eine sehr hohe Parallelität.
Im folgenden werde ich eine kurze Einführung in die oben genannten Begriffen und ihrer Rollen im Evolutionsprozess geben.
2.1 Genotyp und Phänotyp
Jede Zelle eines Lebewesen, bis auf wenige Ausnahmen wie Bakterien, tragen in ihrem Zellkern (Nukleus) ihren kompletten Bauplan. Dieser Bauplan beziehungsweise das Erbgut wird im Chromosom, genauer in der der Desoxyribonukleinsäure (DNS) gespeichert. Er besteht aus verschiedenen Abschnitten, den Genen, welche die Merkmale (Augenfarbe, Haarfarbe, . . . ) eines Lebewesens bestimmen.
Die Gesamtheit dieser Genetischen Informationen wird hierbei als Genotyp bezeichnet. Anders ist hierbei der Ph ä notyp, welcher aus der Summe aller beobachtbarer Eigenschaften eines Lebewesens besteht.
2.2 Rekombination und Mutation
Bei der Zellteilung unterscheidet man zwei Arten des Kernteilungsprozesses: die Mitose und die Meiose.
Die Mitose ist hierbei eine erbgleiche Zell- und Kernteilung, welche bei der meist unge- schlechtlichen Fortpflanzung von Pflanzen oder niederen Tieren auftritt. Aufgrund meiner Konzentration auf die Evolution komplexer Lebewesen, werde ich diese also nicht weiter behandeln.
Bei der Meiose werden die Chromosomen nach ihrer Verdoppelung bei dem so genannten crossing-over an einzelnen Stellen aufgetrennt und zufällig neu rekombiniert.
2.2.1 Crossing-Over
Beim crossing-over brechen Chromosomen an einer Stelle auf und binden sich an das jeweilige gegenseitige Chromosomenstück wieder an. Durch diesen Prozess werden Stücke der Erbinformation zwischen Chromosomen ausgetauscht. Somit wird der Genpool der Eltern gemischt und die Varianz in der Gattung erhöht. In Abbildung 4 wird dieser Prozess weiter verdeutlicht.
2.2.2 Mutation
Die Rekombination des Erbgutes durch die Kreuzung ist ein gewollter Vorgang, um das vorhandene Genmaterial neu anzuordnen und Merkmale zu addieren. Anders bei der Mu- tation des Erbgutes. Diese ist rein zufällig und sorgt somit meist für einen Defekt des Genmaterials, wobei diese zufälligen Veränderungen aber auch in der Lage sind das Gen- material zu verbessern und für eine Varianz zu sorgen, welche durch die reine Kreuzung nicht erreichbar wäre.
Dabei lässt sich der Prozess der Mutation in drei Arten unterteilen: Die Chromoso- menmutation, die Genommutationen und die Genmutation. Durch äußere Einwirkungen wie Strahlung oder UV-Licht können in dem Prozess der Chromosomenmutation Chromosomen verändert werden. So entstehen Brüche in den Chromosomen, die zu Verlusten der Endstücke (Defizienz), Ausbrechen von Zwischenstücken (Deletion), Inversionen von Teilen (Inversion), Verlängerungen des Chromosoms (Inserti- on), Verdopplung von Teilstücken (Duplikation), oder der Vertauschungen von Teilstücken (Translokation) führen können. Diese Art der Mutation hat dabei meist schwerwiegen- de nachteilige Auswirkungen auf das betroffene Lebewesen. Allerdings bietet diese Art der Mutation auch eventuelle positive Effekte. So sorgt beispielsweise die Duplikation für mehr Spielraum im Chromosom, wobei die eigentliche Information erhalten bleibt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Schema der Chromosomenmutationen1
Während der Meiose können die Chromosomen fehlerhaft auf die Tochterzellen verteilt werden, so dass eine Zelle zu viele beziehungsweise zu wenige Chromosomen erhält. Diese Art der Mutation wird Genommutation genannt und sorgt meist für einen erheblichen Defekt des betroffenen Individuums.
Die Genmutation stellt eine direkte Veränderung der Basensequenzen der DNS dar. So werden durch äußere Einwirkungen von UV-Licht, Strahlen oder chemischen Substanzen einzelne Basen verändert, eingefügt, oder entfernt. Die Veränderungen einer einzelnen Base hat hierbei meist keine gravierenden Auswirkungen, da der Genetische Code hochgradig redundant ist. Anders ist es bei dem Einfügen oder Entfernen einzelner Basen, wodurch die komplette Gensequenz beeinflusst wird.
Bei der Mutation ist anzumerken, dass einzelne Gene nicht mit derselben Wahrschein- lichkeit mutieren. So gibt es stabilere und labilere Gene. Trotzdem liegt die Wahrschein- lichkeit der Mutation eines Genes (zumindest beim Menschen) zwischen 4 - 10−6 und 4 - 10-4 [Nac54].
2.2.3 Populationsgröße und Selektion
Die Selektion ist für die eigentliche Steuerung der Evolution verantwortlich. Durch die Bevorzugung oder die Benachteiligung einzelner Individuen bei der Fortpflanzung breiten sich dessen Merkmale mehr oder weniger in der Nachfolgegeneration aus, wodurch sich diese positiven Merkmale über die Zeit hinweg durchsetzen.
Die Selektion wird hierbei durch Störungen verschiedenster Art beeinflußt. So könnten möglicherweise durch zufällige Ereignisse, wie dem frühzeitigen Tod eines Individuums hilfreiche Gene aus dem Genpool verloren gehen. Auf der anderen Seite, ist aber auch die sich durchweg veränderne Umwelt eine der wichtigsten Einflussfaktoren auf die Selektion.
Dabei darf die Selektion nicht als Operator auf ein Individuum, sondern eher als Operator auf den gesamten Genpool einer Population angesehen werden. Die Population ist hierbei die Gesamtheit aller theoretisch miteinander rekombinierbaren Individuen, also die Gesamtheit aller lebenden Individuen einer Gattung.
Je größer die Population ist, desto breiter ist der Genpool innerhalb dieser Population gestreut. Durch diesen großen Genpool ist es der Population möglich sich besser an eine Änderung der Umwelt anzupassen. Weiterhin besteht in einer Population mit einem breitgestreutem Genpool ein großer Mutationsdruck. Durch die hohe Anzahl an Rekombinationsmöglichkeiten entstehen somit viele Variationen im Genpool, was zeitgleich auch für eine große Varianz in der gesamten Spezies sorgt, Anders ist es bei kleinen Populationen. Dort kann sich eine zufällige Mutation innerhalb der Population viel schneller ausbreiten als in einer größeren Population. So ist bei einer kleinen Population der Gendrift weitaus größer. Unter Gendrift versteht man hierbei die auf Zufall beruhende signifikante Veränderung von Allelfrequenzen (Merkmalausbildun- gen der gesamten Population). Somit ist der Selektionsdruck in einer kleinen Population größer.
3 Genetische Algorithmen
Genetische Algorithmen ermöglichen es Lösungen selbst für komplexe Optimierungspro- bleme zu finden, bei denen andere Verfahren scheitern. Dabei zeichnen sie sich vor allem durch ihre Variabilität aus, die es dem genetischen Algorithmus ermöglicht sie an viele Probleme anzupassen. Dies hat allerdings den Nachteil, dass es keinen allgemein gültigen ”perfekten“Algorithmusgibt,wodurchsichimLaufederJahrevieleverschiedeneVari- anten von Genetischen Algorithmen gebildet haben. Aus diesem Grund befasse ich mich in dieser Facharbeit mit dem von John Holland entwickelten Basis-Algorithmus [Hol[92]] Genetische Algorithmen lassen sich als randomisierte Algorithmen2 einstufen, die mithilfe einer Population von Individuen P (t) = {a 1(t) , . . . , an (t) } (t: Generation) eine parallele Suche im Suchraum des Optimierungsproblems durchführt. Dabei repräsentiert jedes Individuum ai (t) eine mögliche Lösung des Optimierungsproblems, dessen Fitness mithilfe einer Zielfunktion bestimmt wird.
Für diese Suche verwendet der Genetische Algorithmus im Grunde die vier Elementaroperatoren: Selektion, Rekombination, Mutation und Reproduktion, um sich - wie in der Natur - von Generation zu Generation weiterzuentwickeln.
Durch die Selektion werden Individuen, in Abhängigkeit von ihrer Fitness für die Repro- duktion ausgewählt. Dies sorgt dafür, dass gute Zustände konserviert werden und schlechte Zustände eliminiert werden. Hierdurch wird allerdings die Diversit ä t der Population, al- so der Grad der Verschiedenheit der Individuen reduziert. Um diesem Diversitätsverlust entgegen zu wirken, wird die Variation verwendet, welche sich bei genetischen Algorith- men durch die Rekombination und Mutation ausprägt. Diese verändern die genetischen Informationen der Individuen und erschaffen somit neue, verschiedenartige Individuen.
Abbildung 1 zeigt das Schema eines Genetischen Algorithmus.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Ablaufplan eines Genetischen Algorithmus. [MB04, S. 153] Die einzelnen Komponenten werden im Folgendem beschrieben.
3.1 Selektion
Die Selektion dient dazu, Individuen einer Population P (t) auszuwählen, welche daraufhin im Paarungs Pool landen und dort neue Nachkömmlinge zeugen. Damit der Genetische Algorithmus sich von Generation zu Generation verbessern kann, werden fittere Individuen bevorzugt (Survival of the fittest). Ein bekanntes Selektionsverfahren stellt hierbei die Roulette Wheel Selection dar.
Bei diesem Verfahren, werden im ersten Schritt des Selektionsprozesses jedem Individu- um ein Segment auf einem Roulette-Rad zugewiesen. Dabei ist die Größe des Segmentes proportional zur Fitness des Individuums. Im zweiten Schritt des Selektionsprozesses wird dieses Rad gedreht und somit ein Segment zufällig bestimmt. Das entsprechende Indivi- duum wird dann schließlich in den Paarungs Pool kopiert. Das drehen am Roulette-Rad wird nun für die Erzeugung des Paarungs Pools insgesamt n -mal durchgeführt.
Je besser die Fitness eines Individuums und damit je größer das Segment auf dem Rad ist, desto höher ist die Wahrscheinlichkeit, dass mehr Nachkommen dieses Individuums sich in der neuen Population befinden. Durch den Zufallfaktor dieses Selektionsverfahrens ist es theoretisch wohl möglich, dass jedes mal das jeweils schlechteste Chromosom selektiert wird, jedoch ist die Wahrscheinlichkeit für diesen Fall extrem gering und somit eigentlich vernachlässigbar. [MB04, S. 153]
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3: Graphische Darstellung der Roulette wheel selection. [Joh07]
3.2 Variation
Um aus den selektierten Elternindividuen aus dem Paarungspool Nachkommen zu erzeu- gen, werden Variationsoperatoren verwendet. Diese haben die Aufgabe, durch zufällige Mutationen und der Kreuzung verschiedener Individuen die Vielfalt der Population auf- recht zu erhalten, wodurch sie dem durch die Selektion erzeugten Diversitätsverlust ent- gegenwirken.
3.2.1 Kreuzung
Die Kreuzung ist der wichtigste Variationsoperator. Bei diesem Operator werden je zwei noch nicht gewählte Individuen aus dem Paarungspool ausgewählt und mit einer Wahrscheinlichkeit pc miteinander gekreuzt. Dies wird solange durchgeführt, bis alle Individuen des Paarungspools eine Chance zur Kreuzung hatten.
Für diesen Prozess der Kreuzung, dem sogenannten Crossover, existieren mehrere Ansätze. Im Rahmen dieser Facharbeit beschreibe ich hierbei das bekannteste Verfahren, das sogenannte One-Point-Crossover.
Bei diesem Verfahren wird zunächst ein zufälliger Punkt p ∈ { 1 , . . . , l − 1 } ausgewählt, wobei l der Länge des Chromosoms entspricht. Anschließend werden alle Gene ab dem (p + 1)-ten Gen zwischen den ausgewählten Elternchromosomen ausgetauscht und somit zwei Nachkommen erzeugt. Ein Beispiel dieses One-Point-Crossovers ist in Abbildung 3 zu sehen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4: One-Point-Crossover
3.2.2 Mutation
Während die Kreuzung ein Variationsoperator ist, der große Veränderungen an Individuen vornimmt, so ist die Mutation eine Veränderung im Kleinen. Seine Aufgabe ist es, durch zufällige Veränderungen an den Nachkommen eine gewisse Inhomogenität und Divergenz in die nächste Generation einzubringen. Außerdem ist die Mutation in der Lage potentielle Lösungen zu finden, die durch Kreuzung alleine nicht hätten erzeugt werden können. [Dan]
Bei der Mutation wird jedes Gen eines Chromosoms mit einer so genannten Mutations wahrscheinlichkeit pm (= Mutationsrate) negiert. Nach Mühlenbein [Hei92, S. 9] sei hierbei die optimale Mutationswahrscheinlichkeit, die von der Chromosomenlänge L abhängige Wahrscheinlichkeit pm =1 L.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5: Mutation
4 Beispiel eines genetischen Algorithmus
Um die Funktionsweise eines genetischen Algorithmus besser darzustellen, werde ich die- se nun anhand eines Beispieles in Java mit unter Verwendung der SuM-Bibliotheken3 erläutern.
Als Grundlage für dieses Beispiel dient mein Programm, welches die Ideen des Ap- plets ”Java-Genitor“vonUrsulaundPascalGlauserumsetzt4. Es wird eine fraktale Landschaft, mithilfe eines Perlin-Noise Algorithmus5 generiert. Das Ziel des genetischen Algorithmus ist es hierbei den höchsten Punkt dieser Landschaft in möglichst wenigen Generationen ausfindig zu machen. Dazu wird eine Population von zum Beispiel 100 Käfern(= Individuen) zufällig über die Landschaft verteilt. Der Ort, also die X-Koordinate auf der sich der Käfer befindet, ist hierbei sein Gencode, beziehungsweise sein Chromosom (Der Käfer ist unbeweglich), während die Höhe der Landschaft an seiner Position seiner Fitness entspricht.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 6: Benutzeroberfl ä che des Programms. Die Linie stellt das Terrain dar und die Kreise die zuf ä llig platzierten K ä fer.
Nun laufen die einzelnen Schritte des genetischen Algorithmus durch.
Mithilfe der im vorangegangenen Kapitel erläuterten Roulette-wheel-selection werden eine durch den Benutzer bestimmte Anzahl an Käfern ausgewählt, welche schließlich im Paarungspool landen.
Nun werden aus diesem Paarungspool solange zwei Individuen ausgewählt, die mit einer Wahrscheinlichkeit von 90% Nachkommen zeugen, bis alle Individuen eine Chance zur Fortpflanzung hatten. Das Kind dieser zwei Individuen wird hierbei an einer zufälligen X-Koordinate zwischen den X-Koordinaten seiner Eltern generiert. So würde ein Kind von p 1(x: 20) und p 2(x: 50) auf der X-Koordinate 20 < x < 50 liegen. Nun wird jedes Kind mit einer von dem Nutzer festgelegten Wahrscheinlichkeit (Stan- 1 dard: 100 ) mutiert. Im falle einer Mutation wird hierbei das Kind an eine zufällige X- Koordinate geboren.
Nachdem die Kinder erzeugt, mutiert und zur Population hinzugefügt wurden, wird die Population wieder auf die Ursprungsgröße zurückgesetzt. Dies geschieht auch wieder mit der Roulette-wheel-selection, wobei hierbei schlechtere (also Käfer mit einer geringen Fitness/Höhe) einen größeren Anteil am Rad haben.
Diese Abfolge an Evolutionsschritten wird nun solange wiederholt, bis sich alle Käfer auf derselben selben Höhe befinden. An dieser Stelle befindet sich dann auch (hoffentlich) der höchste Punkt der Landschaft. Dabei kann aufgrund der Zufälligkeit genetischer Algorithmen allerdings nicht garantiert werden, dass auch wirklich der höchste Punkt der Landschaft gefunden wurde.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 7: Die K ä fer sind bereits nach 44 Generationen zum h ö chsten Punkt des Ter- rains konvergiert.
5 Genetische Algorithmen - technischer Darwinismus?
Nach der Betrachtung der Biologischen Evolution, sowie ihrem technischen Pendant, dem genetischen Algorithmus, werde ich nun versuchen die Frage zu beantworten, ob genetische Algorithmen quasi als technischer Darwinismus angesehen werden können. Somit komm ich nun nach meiner Recherche beider Themengebiete zu dem Schluss, dass Genetische Algorithmen dem Vorbild der Natur wohl nahe kommen, sie aber nicht in der Lage sind diese perfekt abzubilden.
Dies fängt schon bei der Grundlagen der biologischen Evolution, wie der Population und deren Rahmenbedingungen an. In der Natur müssen sich Lebewesen an ihre Umwelt anpassen, um ihr Ziel, das Überleben und das erzeugen von Nachkommen zu erreichen. Um Nachkommen erzeugen zu können müssen dafür allerdings auch verschiedene Rahmenbedingungen, wie das erreichen eines Fortpflanzungsfähigen Alters, oder die Existenz eines Sexualpartners erfüllt sein. Somit ist die Fortpflanzung, das überleben der eigenen Spezies das hauptsächliche Ziel des Individuums.
Anders ist dies bei genetischen Algorithmen. Die Individuen haben keinen Drang ihre Spezies zu erhalten. Ihr Ziel ist es die größte Fitness zu erreichen um ein Optimierungspro- blem zu lösen. Dabei sind ihnen auch etwaige Bedingungen der Natur, sowie verschiedene Rahmenbedingungen für die Fortpflanzung nicht geläufig. Die Auswahl der Individuen funktioniert hierbei meist mit einer Fitnessproportionalen Selektion (zum Beispiel Rou- lette wheel selection), bei der die Individuen abhängig von ihrer Fitness eine Chance zur Fortpflanzung bekommen. Die guten Individuen haben somit eigentlich immer die Möglichkeit sich fortpflanzen zu können, nicht wie bei der Biologischen Evolution, wo gu- te Gene aufgrund zum Beispiel eines fehlenden Sexualpartners nicht weitergegeben werden können.
Das gleiche gilt allerdings auch für andere Einflussfaktoren auf die Selektion, zum Bei- spiel durch zufällige Ereignisse, wie dem frühzeitigen Tod eines Individuums. So können In- dividuen in genetischen Algorithmen ”unsterblich“gemachtwerden,sodasssolchezufälligen Faktoren keinen Einfluss auf die erfolgreiche Suche im Suchraum des genetischen Algo- rithmus nehmen können.
Des Weiteren ist auch ein Vergleich der Umsetzung von Rekombination und Mutation zwischen der biologischen Evolution und den genetischen Algorithmen ein interessantes Thema.
Und zwar arbeiten dort die biologische Evolution und die genetischen Algorithmen bei einer Sache nach dem gleichen Prinzip. Und zwar bei der Kreuzung, bei der die biologi- sche Evolution und die genetischen Algorithmen sogar auf genau das gleiche Verfahren zurückgreifen, in diesem Fall kopiert der genetische Algorithmus also exakt die biologische Evolution. (one-point-crossover, two-point-crossover, uniform-crossover [MB04, S. 156]) Anders ist es nun aber bei der Mutation. Dieser ist bei genetischen Algorithmen ein sehr wohl gewollter Prozess, damit die Individuen sich nicht auf eine Lösung festsetzen, sondern die Möglichkeit haben den kompletten Suchraum zu betrachten. So wird in ge- netischen Algorithmen durch diesen Operator die Diversität der Population und somit der Lösung gewahrt. Anders sieht das allerdings bei der biologischen Evolution aus. Dort ist die Mutation ein keineswegs geplanter Prozess, sondern eher das Ergebnis ungewollter äußerer Einflüsse (Strahlung, UV-Licht,. . . ), sowie das Ergebnis einer fehlerhaften Zelltei- lung. Diese Fehler im Gencode sorgen bei dem Individuen somit meist zu einem schwer beschädigten Gencode und somit zu schweren Folgen für das lebende Individuum. Von den drei Arten der Mutation, welche bei der biologischen Evolution beschrieben werden, wird außerdem auch nur das Konzept der Genmutation, bei welcher einzelne Gene verändert werden, realisiert. Während dieser Prozess bei der biologischen Evolution auf- grund der hohen Redundanz des genetischen Codes meist keine gravierenden Folgen hat [Wat08, S. 212], können die Auswirkungen bei Individuen des genetischen Algorithmus aufgrund der fehlenden Redundanz des Gencodes gravierende Veränderungen im Such- raum bewirken.
Die beiden anderen Arten der Mutation fehlen beim genetischen Algorithmus allerdings komplett. Die Chromosomenmutation, bei der in den Chromosomen Brüche entstehen und der Gencode grundlegend verändert, beziehungsweise sogar vergrößert und verkleinert wird. Und die Genommutation, bei der während der Meiose die Chromosomen fehlerhaft auf die Tochterzelle verteilt werden, sodass eine Zelle zu viele beziehungsweise zu wenige Chromosomen erhält. Dies hat allerdings wohl auch den Grund, dass eine derartige Mu- tation des Gencodes in genetischen Algorithmen aus programmiertechnischer Sicht nur schwer umsetzbar ist.
6 Fazit
Aus dem vorangegangenem Kapitel wird klar, dass genetische Algorithmen keineswegs eine ”quasi“KopiederbiologischenEvolutionsind.Stattdessenabstrahierengenetische Algorithmen die Prozesse der Natur um sie möglicherweise auf Optimierungsprobleme anwenden zu können. Allerdings stellt sich hier dann die Frage, ob es überhaupt die Aufgabe von genetischen Algorithmen ist den biologischen Evolutionsprozess detailgetreu nachzubilden. Und genau dies ist in meinen Augen nicht der Fall. Mithilfe genetischer Algorithmen wird versucht ein Prinzip, welches in der Natur bereits sehr erfolgreich ist so zu abstrahieren, dass damit die Lösung von Problemen ermöglicht wird, welche mit normalen deterministischen Algorithmen gar nicht, beziehungsweise kaum lösbar gewe- sen wären. Genau dieser Erfolg ist der Grund für die Beliebtheit genetischer Algorith- men, sowie anderer auf der Natur basierenden Methoden (Deeplearning, Neuronale Netze, ...).Letzendlich sind genetische Algorithmen neben der Erfindung des Klettverschlus- ses oder der Erfindung des Flugzeugs nur ein weiteres Beispiel für Konzepte, welche die Menschheit erfolgreich von der Natur abgeschaut hat, um es für ihre Zwecke nutzen zu können.
[...]
1 https://commons.wikimedia.org/wiki/File:Chromosomenmutationen.png
2 Ein Algorithmus, der durch die Wahl von zufälligen Zwischenergebnissen zu einem näherungsweise korrekten Ergebnis gelangt. [Hro04, S. 51]
3 http://www.mg-werl.de/sum/ (abgerufen 18.3.18)
4 http://www.glauserweb.ch/gentord.htm (abgerufen: 18.3.18)
5 https://patents.google.com/patent/US6867776B2/en (abgerufen: 18.3.18)