Bei der Erforschung der Evolution hat man das Problem, dass sie relativ langsam abläuft und daher nur in kleinem Ausmaß und über längere Zeiträume betrachtet werden kann. Einfacher ist es da natürlich, die Auswirkungen der Evolution zu untersuchen, so wie es zum Beispiel Charles Darwin unter anderem bei den berühmten Darwinfinken (Bild links) tat und was am Ende auch zur Entwicklung seiner Theorie über die Entwicklung der Arten beigetragen hat. Parallel dazu kann natürlich auch das Erbgut erforscht werden, da es die biologische Grundlage für die Evolution bildet. Beide Themenbereiche – Evolution und Genetik – sind überaus interessante Forschungsgebiete, auf denen große Personen wie Charles Darwin, Ernst Haeckel und Gregor Mendel tätig waren. Nun mag sich allerdings der ein oder andere fragen (und tut es auch), wo denn der Sinn derartiger Forschungen liegt, insbesondere in Bezug auf die Evolution. Unabhängig von der allgemeinen Bedenklichkeit dieser Frage (die kann dann nämlich in ihrer Naivität auf sehr viele Bereiche angewendet werden) haben Erkenntnisse auf beiden Forschungsgebieten auch Auswirkungen auf komplett andere Tätigkeitsfelder gehabt; insbesondere sei hier die Informatik zu nennen: aufbauend auf den (allgemeinen) Theorien der Evolution und Genetik wurde hier nämlich eine spezielle Gruppe von Verfahren zur Problemlösung entwickelt, nämlich die evolutionären Algorithmen, und über die möchte ich heute etwas schreiben.
Biologische Grundlagen
Bevor es zu den evolutionären Algorithmen geht, muss allerdings noch einmal ein kurzer Ausflug in die Biologie erfolgen, und zwar zu den Grundlagen von Evolution und Genetik (nur, damit die Begrifflichkeiten einigermaßen geklärt sind). Wichtig ist hier unter anderem der Begriff des Individuums. Im Folgenden wollen wir (unabhängig von existierenden Definitionen) unter einem Individuum einen unabhängig von seiner Umgebung existierenden Repräsentanten einer Art mit einem eigenen Erbgut verstehen (wobei sich die “Unabhängigkeit” natürlich nicht auf Nahrungsabhängigkeiten, Symbiosen und dergleichen bezieht). Ein Individuum in der Biologie ist also alles, worauf wir mit dem Finger zeigen und sagen können: Das dort!
Die Eigenschaften eines Individuums werden durch sein Erbgut, das Genom bestimmt, welches sich aus den einzelnen Genen zusammensetzt (rechts zum Beispiel ein menschliches Genom, [via Wikipedia]). Das gesamte Genom eines Individuums beschreibt seinen Genotyp (wichtiger Begriff für später, bitte merken), das Erbbild. Die Gesamtheit aller Eigenschaften eines Individuums (also Aussehen, Verhalten usw.) wird dagegen als Phänotyp bezeichnet (auch wichtig, auch merken). Man kann also sagen, dass der Genotyp eines Individuums seinen Phänotyp bestimmt.
Der Genotyp ist über die Lebensdauer eines Individuums mehr oder weniger fest und kann sich nur durch externe Einflüsse verändern. Zudem gibt ein Lebewesen sein Genbild an seine Nachkommen weiter; da aber die Nachkommen in der Regel doch von ihrem Erzeuger abweichen (vom Klonen einmal abgesehen), muss während der Fortpflanzung eine Veränderung des Genotyps stattfinden. Die beiden hieran hauptsächlich beteiligten Mechanismen sind die Mutation und – bei mehrgeschlechtlicher Fortpflanzung – die Rekombination. Ohne jetzt allzu sehr auf Details einzugehen: Mutation bezeichnet die Veränderung des Erbgutes einer Zelle, die entweder spontan oder durch äußere Einfluss stattfindet. Treten diese Mutationen in den Keimzellen auf, werden sie an die Nachkommen weitergegeben. Die Rekombination tritt (unter anderem) auf, wenn während der Befruchtung bei der Fortpflanzung die Ei- und die Samenzelle und damit ihr Erbgut verschmelzen und somit einen neuen Genotyp ausbilden.
Durch Vorgänge auf der Ebene der Gene wird also der Genotyp eines Individuums bestimmt. Dies hat, wie bereits geschrieben, Auswirkungen auf seinen Phänotyp, also seine nach außen hin sichtbaren Merkmale – und an dieser Stelle greifen die Mechanismen der Evolution. Der Phänotyp eines Individuums bestimmt, wie gut es in einer Umgebung zurecht kommt – man spricht von der Anpassung eines Individuums an seine Umgebung. Je besser es angepasst ist, das heißt, je stärker sein Phänotyp auf ein Überleben in seiner Umgebung ausgerichtet ist, desto größer ist auch die Wahrscheinlichkeit, dass es länger überlebt und seine Gene an Nachkommen (vor allem an mehr Nachkommen) weitergibt. Dieser Mechanismus wird als natürliche Selektion bezeichnet und ist einer der Grundpfeiler der Evolutionstheorie.
Evolution zur Problemlösung in der Informatik
Jetzt stellt sich natürlich die Frage, wie die Mechanismen von Mutation, Rekombination und Selektion genutzt werden können, um Probleme in der Informatik zu lösen. Zuerst einmal: ein Problem kann jede Fragestellung sein, die sich mit Hilfe computergestützter Methoden beantworten lässt. Bekannte Problemstellungen sind etwa die Suche nach einer möglichst kurzen Route durch verschiedene Orte (bekannt als Rundreiseproblem), die optimale Auswahl von Objekten aus einer Menge nach bestimmten Kriterien (das Rucksackproblem) oder die platzsparendste Anordnung von Objekten auf einem Trägermaterial (was zum Beispiel besonders wichtig bei der Entwicklung von Prozessoren ist). Insbesondere die sogenannten Optimierungsprobleme sind von Interesse; damit sind Probleme gemeint, die nicht nur eine eindeutige Lösung besitzen, sondern deren verschiedene Lösungen nach ihrer Güte eingeteilt werden können. So gibt es etwa bei der Suche nach einer Rundreise vielleicht eine optimale Route, aber die anderen möglichen Routen sind ebenfalls Lösungen des Problems – nur eben nicht so gute.
Der Trick ist nun, eine möglichst gute Lösung eines Problems zu suchen, indem verschiedene Lösungskandidaten zufällig generiert und diese dann in einer künstlichen Umgebung unter der Einwirkung der Mechanismen von Evolution und Genetik zu modifizieren, um sich so einer optimalen Lösung anzunähern. Und genau das ist es, was die evolutionären Algorithmen machen. Im Groben sieht das Vorgehen dabei wie im Folgenden beschrieben aus:
Zu Beginn wird (manuell oder automatisch) eine Menge von zufälligen Lösungskandidaten – jeder Lösungskandidat ist ein einzelnes Individuum – erstellt, welche die Ausgangsbasis der Suche bilden. Diese Individuen haben nun die Möglichkeit, sich unter einem gewissen Selektionsdruck so lange “fortzupflanzen”, bis ein hinreichend guter Lösungskandidat entstanden ist (oft genug reicht das nämlich schon zur Lösung eines Optimierungsproblems). Für gewöhnlich wird dabei noch ein Alterungskonzept zugrunde gelegt, durch welches alte Individuen “sterben” und durch ihre Nachkommen ersetzt werden; die Individuen werden dabei meist in aufeinanderfolgende Generationen (oder – biologisch ungenau – in Populationen) eingeteilt.
Die Vermehrung der Individuen geschieht, indem etwa die Eigenschaften zweier nach bestimmten Kriterien ausgesuchter (selektierter) Individuen miteinander (re-)kombiniert und der so entstehende Nachfahre noch einmal zufällig mutiert wird. Dies wird für verschiedene Individuen einer Generation mehrmals ausgeführt, wodurch die Nachfolgegeneration entsteht, welche ihre Vorgänger für den nächsten Iterationsschritt im Algorithmus ersetzt. Der Prozess wird insgesamt so lange wiederholt, bis oben genanntes Abbruchkriterium – ein hinreichend guter Lösungskandidat – erreicht wurde. Wenn wir das ganze in Pseudocode notieren, erhalten wir folgenden Algorithmus (g0 ist die Ausgangsgeneration,
T ist der Typ eines Lösungskandidaten):
(2) t ∈ T
(3) g ∈ Tn, g ← g0
(4) do:
(5) g’, g” ∈ Tn
(6) g’ ← select individuals from g
(7) g” ← recombine individuals in g’
(8) mutate individuals in g”
(9) t ← select best individual in g”
(10) while t not good enough
(11) return t
Durch diesen Algorithmus kann auf ziemlich elegante Weise eine gute Lösung für
ein ansonsten
recht schwierig zu lösendes Problem gefunden werden. Jetzt muss natürlich aber auch noch geklärt werden, wie denn nun die Mutation, Rekombination und Selektion der Individuen genau stattfindet, was das ganze mit den anfänglich erwähnten Begriffen von Genotyp und Phänotyp zu tun hat und – so ehrlich wollen wir sein – wo die Probleme des Verfahrens liegen. Aber das hebe ich mir für das nächste mal auf.
Kommentare (24)