So, hier nun endlich – mit einiger Verspätung (ich weiß gar nicht, wie Florian neben der Arbeit noch so produktiv im Blog sein kann) – der vorerst letzte Teil der Reihe zu den evolutionären Algorithmen. Wir erinnern uns: in Teil 1 wurde vorgestellt, was sich überhaupt unter evolutionären Algorithmen vorgestellt werden kann. In Teil 2 wurde dann ihre allgemeine Funktionsweise besprochen und in Teil 3 habe ich vorgestellt, wie mit Hilfe aus der Genetik bekannten Mitteln die Arbeitsweise der Algorithmen verbessert und verallgemeinert werden kann. Zum Abschluss soll es heute nun noch darum gehen, welche Probleme bei der Nutzung von evolutionären Algorithmen auftreten können und wie sie sich – zumindest teilweise – vermeiden lassen.
Das generelle Problem evolutionärer Algorithmen (im weiteren auch einfach als EA bezeichnet) ist, dass sie nicht wirklich zielgerichtet arbeiten; nicht zielgerichtet heißt, dass der “Wert” der optimalen Lösung meist nicht bekannt ist und daher auch nicht gezielt danach gesucht werden kann. Es kann lediglich gesagt werden, welche von 2 möglichen Lösungen für ein Problem die bessere ist. Die eigentliche Problemlösung besteht also aus der Suche nach einer möglichst optimalen Lösung (daher der Name Optimierungsproblem) und nicht aus der Suche nach der optimalen Lösung (weil sie eben meist nicht bekannt ist).
Das ganze lässt sich auch grafisch sehr gut veranschaulichen. Ein Optimierungsproblem besitzt eine (endliche oder unendliche, das spielt keine Rolle) Menge an Lösungen (Individuen), wobei jede Lösung einen bestimmten Fitness-Wert hat. Zudem besitzt der Phänotyp – das Erscheinungsbild – der Lösungen eine bestimmt Anzahl von Parametern (im Katzenbeispiel waren es etwa 2: die x- und die y-Koordinate auf dem Bett). Bei nicht allzu vielen Parametern (im Grunde nur bei 1 oder 2) kann man zur Verdeutlichung der Problematik ein Diagramm anlegen, welches für jede Parameterwahl die Fitness anzeigt
Nehmen wir zum Einstieg das Katzenbeispiel; in diesem Fall besitzt der Phänotyp 2 Parameter (die x- und die y-Koordinate), stellt also ein zweidimensionales Problem dar. Zur Darstellung im Diagramm bietet sich hier zum Beispiel die Nutzung von Graustufen an; weiße Bereiche stellen “gute”, im Katzenbeispiel also zentrumsnahe Positionen dar, schwarze Bereiche eher “schlechte Positionen, also solche, die weiter Weg vom Zentrum sind. Für das Katzenbeispiel ergibt sich hier ein relativ homogenes Bild mit einem weißen Zentrum und gleichmäßig dunkler werdenden Bereichen:
Eine Anmerkung noch, bevor es weitergeht: wenn wir nicht nur auf 3 Dimensionen beschränkt wären, ließen sich auch Probleme mit mehr Parametern darstellen; so beschränken wir im Folgenden aber auf Grund physikalischer Gesetzmäßigkeiten auf 1 und 2 Dimensionen – alles gesagt ist aber natürlich ebenso auf komplexere Probleme anwendbar!
Jetzt ist das Katzenbeispiel relativ simpel, da der Kurvenverlauf für die Fitnesswerte relativ eindeutig ist: von jedem Punkt des Koordinatensystems aus werden die Werte zur Mitte hin besser und erreichen genau in der Mitte ihr Optimum. Reale, durch evolutionäre Algorithmen lösbare und gelöste Probleme haben diesen Luxus nicht. Ein (beliebiges) anderes Problem mit 2 Parametern könnte etwa das folgende Fitnessdiagramm aufweisen (welches natürlich so meist überhaupt nicht bekannt ist – wir tun nur einmal so, als würden wir es kennen):
Im Bild erkennen wir, dass neben dem “besten” Optimum links oben noch ein “weniger gutes” Optimum rechts unten existiert (für die Sprachpedanten unter den Lesern: ich weiß, dass es kein “bestes” oder “weniger gutes” Optimum geben kann – die Begriffe sind hier eher umgangssprachlich gemeint; man möge mir verzeihen). Das Optimum oben links wollen wir im Folgenden als globales Optimum bezeichnen, da es global (also im ganzen Diagramm) das beste ist; das Optimum rechts unten ist dementsprechend ein lokales Optimum, da es lokal (unmittelbar in seiner Umgebung) den besten Wert darstellt (das globale Optimum ist somit auch gleichzeitig ein lokales). Gängige Probleme der Realität haben nicht nur 2 lokale Optima, sondern viel viel mehr, und leider weiß man in der Regel nicht, wo denn diese lokalen Optima liegen.
Dieses Problembild nun verdeutlicht sehr gut, welche Probleme bei der Verwendung evolutionärer Algorithmen auftreten können. Wir erinnern uns: es wurde bereits erwähnt, dass bei einem EA mehrere Parameter (die nichts mit den Problemparametern wie der Position der Katze zu tun haben) eingestellt werden können; insbesondere seien hier die Parameter für die Rekombinationsrate, die Mutationsrate und den Selektionsdruck genannt.
Die Rekombinationsrate bestimmt, wie viele für die nächste Generation ausgewählte Individuen miteinander rekombiniert werden sollen, bevor sie in die nächste Generation eingehen. Ein Wert von etwa 0.33 bedeutet, dass jeweils ein Drittel der ursprünglichen Individuen rekombiniert werden sollen und weitere zwei Drittel direkt in die nächste Generation übernommen werden.
Die Mutationsrate kann entweder dafür stehen, wie viele der Individuen der neuen Generation mutiert werden (bei einem Wert von 0.33 würden wieder im Schnitt ein Drittel der Individuen mutiert werden), oder aber auch, wie stark die Mutation ausfällt (ein Wert von 0.33 heißt, dass 33% des Genotyps zu mutieren sind, was ziemlich viel ist) – letztere Bedeutung kann sich aber durchaus auch in einem eigenen Parameter niederschlagen.
Über den Selektionsdruck schließlich wird bestimmt, welche Individuen in die nächste Generation übernommen werden sollen. Ein hoher Selektionsdruck lässt nur die allerbesten Individuen für die Rekombination und Mutation zu, ein etwas geringerer Druck erlaubt auch “schlechtere” Individuen. Dies ist übrigens durchaus mit dem Selektionsdruck in der Biologie zu vergleichen; ein Pflanzenfresser in einer Region mit vielen Fleischfressern unterliegt in Bezug auf den Faktor “Prädator” einem starken Selektionsdruck – durch die Evolution werden insbesondere die Individuen “bevorzugt” (indem sie sich am meisten fortpflanzen können), welche am besten das Gefressenwerden vermeiden können. Sind in der Gegend aber wenige bis keine Prädatoren vorhanden, so ist der Selektionsdruck in Bezug auf diesen Faktor dementsprechend gering. In der natürlichen Welt existieren natürlich weitaus mehr Faktoren, die für die Selektion verantwortlich sind; bei den evolutionären Algorithmen gibt es (meist) nur einen einzigen Faktor, und das ist der Fitnesswert eines Individuums.
Was haben nun aber diese drei Parameter mit den lokalen Optima zu tun? Nun, nehmen wir zum Beispiel eine geringe Rekombinations- und Mutationsrate und einen hohen Selektionsdruck an. In so einem Fall unterscheiden sich aufeinanderfolgende Generationen nur geringfügig voneinander, wobei die Individuen in einer Folgegeneration im Schnitt ein klein wenig besser geworden sind. “Besser” heißt, dass sie sich etwas zum Optimum hin bewegt haben – aber welchem? Bei mehreren lokalen Optima wandern sie für gewöhnlich zum nächstgelegenen Optimum hin. Das impliziert aber auch, dass sie, haben sie einmal ein lokales Optimum erreicht, nicht zu einem anderen wandern werden – man sagt, der EA konvergiert in einem oder mehreren lokalen Optima. Wenn wir nun weiter berücksichtigen, dass die Individuen der ersten Generation zufällig erzeugt werden, lässt sich daraus schließen, dass das Gesamtergebnis des EA stark von dieser Ausgangssituation abhängt – wurden Individuen nahe des globalen Optimums erzeugt (welches man ja eigentlich erhalten möchte), wird dieses auch als Ergebnis der Berechnungen gefunden werden können. Befand sich initial allerdings kein Individuum in der Nähe des globalen Optimums, so wird irgendein lokales Optimum als bester gefundener Wert ermittelt; manchmal kann das ausreichend sein, oft genug ist es das jedoch nicht.
Auf der anderen Seite könnte man natürlich aber auch eine hohe Rekombinations- und Mutationsrate wählen. Aber auch das ist ist nicht optimal; je höher diese Werte nämlich sind, desto größere Sprünge machen die Individuen in aufeinanderfolgenden Generationen, da ja potentiell stärkere Veränderungen in ihrem Genotyp und damit dem Phänotyp auftreten. Ist zudem der Selektionsdruck gering, führt das dazu, dass der EA überhaupt nicht konvergiert, sondern sich die Individuen zufällig im Lösungsraum verteilen. Bei einem stärkeren Selektionsdruck werden sie sich dagegen zwar alle in der Nähe von lokalen Optima aufhalten und eventuell sogar den Sprung von einem lokalen Optimum zum nächsten schaffen können; jedoch konvergiert der Algorithmus auch hier nicht, da die einzelnen Individuen aufeinanderfolgender Generationen durch die starken Änderungen in ihrem Genotyp immer um die lokalen Optima kreisen, ohne jemals eins wirklich zu erreichen. Auch damit ist keinem geholfen.
Fassen wir also noch einmal zusammen: eine geringe Rekombinations- und Mutationsrate, verbunden mit hohem Selektionsdruck führt zu einem Konvergieren des Algorithmus in verschiedenen lokalen Optima, welche mehr oder weniger ausschließlich von der Ausgangskonfiguration abhängen. Eine hohe Rekombinations- und Mutationsrate bei hohem Selektrionsdruck führt dazu, dass die Individuen zwar nicht unbedingt bei wenigen lokalen Optima “hängenbleiben”, sondern auch zwischen mehreren springen können, diese jedoch selten direkt erreichen – der Algorithmus konvergiert nicht. Ein zu geringer Selektionsdruck führt im Allgemeinen dazu, dass der EA nicht konvergiert, da immer wieder schlechte Individuen in die nächste Generation übernommen werden und somit keine zielgerichtete Optimierung stattfinden kann.
Die Schwierigkeit bei der Verwendung von evolutionären Algorithmen liegt also darin, die Parameter für Rekombinationsrate, Mutationsrate und Selektionsdruck so zu wählen, dass sie zum möglichst besten Ergebnis führen. Wie aber lässt sich das erreichen?
Für einen Teil der per EA lösbaren Optimierungsprobleme besteht die Lösung einfach darin, dass mit verschiedenen Parameterkonfigurationen experimentiert wird, bis eine gefunden wird, die zu brauchbaren Ergebnissen führt, das heißt, wo das Verhältnis von Konvergenz zu lokalen Optima und Springen zwischen den Optima ideal ist. Insbesondere Probleme, für welche einmal eine derartige Konfiguration gefunden und dann für verschiedene Probleminstanzen wiederverwendet werden kann, ist dieser Ansatz brauchbar.
Nicht alle Optimierungsprobleme lassen sich allerdings auf diese Art lösen. Der alternative Ansatz besteht in der Verwendung einer adaptiven Parameterwahl. Hierbei wird zuerst eine hohe Mutations- und Rekombinationsrate sowie ein geringer Selektionsdruck gewählt. Im Laufe der Generationen werden diese Parameter allerdings angepasst: die Mutations- und Rekombinationsraten sinken langsam und der Selektionsdruck steigt. Zu Beginn können sich die Individuen also relativ frei im Lösungsraum bewegen, mit fortschreitender Laufzeit des Algorithmus werden sie dagegen immer mehr zur Konvergenz auf ein lokales Optimum hin gezwungen (in diesem Punkt ähneln die evolutionären Algorithmen übrigens dem simulierten Abkühlen, mit dem Unterschied, das bei den EA mehrere Individuen betrachtet werden).
Wir haben nun also kennengelernt, wie die Parameter eines evolutionären Algorithmus gewählt werden können, um eine möglichst optimale Lösung finden zu können. Damit schließt die Reihe zu den evolutionären Algorithmen – das nächste mal geht es aber mit einem ähnlich spannenden Thema weiter.
Kommentare (12)