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)