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.
Kommentare (12)