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.

1 / 2 / 3

Kommentare (12)

  1. #1 Andreas
    Januar 22, 2012

    Interessante Reihe, lass dich doch mal verpodcasten.

  2. #2 BreitSide
    Januar 22, 2012

    xxx

  3. #3 Franz
    Januar 22, 2012

    Die Farben in den Bildern sind ziemlich ungünstig gewählt. Da kriegt man ja Augenkrebs, wenn man zu lange drauf guckt.

  4. #4 Marcus Frenkel
    Januar 22, 2012

    @Franz
    Ja, ich weiß. Ich habe die Bilder mal durch andere mit Graustufen ersetzt – vielleicht ist das ja besser.

  5. #5 Phyiker
    Januar 23, 2012

    Danke!
    Sehr interessante Artikelreihe – werd’ demnächst mal so einen EA programmieren.

  6. #6 kereng
    Januar 23, 2012

    In diesem Zusammenhang muss ich einfach https://boxcar2d.com/ verlinken. Das wurde doch noch nicht erwähnt, oder?
    Wenn dort mit ungünstig angebrachten Rädern erste Erfolge erzielt wurden, befindet man sich auch auf einem lokalen Optimum und wirklich gute Rennautos haben kaum noch eine Chance. Unter Umständen hilft es dann, die Mutationsrate raufzusetzen.

  7. #7 Marcus Frenkel
    Januar 23, 2012

    @Physiker
    Ich bin gespannt, ob es klappt. 🙂

    @kereng
    Ah, an die Box Cars habe ich gar nicht mehr gedacht. Schönes Beispiel für einen EA, vielen Dank fürs Posten.
    Allerdings würde ich vermuten, dass die Box Cars keine Rekombination benutzen, was ich ein wenig schade finde – da hätte man bestimmt noch mehr herausholen können.

  8. #8 Silly Human
    Januar 24, 2012

    Sehr interessant, danke.

  9. #9 kereng
    Januar 24, 2012

    Doch, die Boxcars machen Rekombination, und zwar den uns vertrauten Spezialfall mit zwei Elternteilen. Der Erfinder nennt es hier “Crossover”:
    https://boxcar2d.com/about.html#crossover

  10. #10 Marcus Frenkel
    Januar 24, 2012

    Tatsächlich. Wunderlich. Von der Verteilung und dem Aussehen der Nachkommen her hätte ich gesagt, dass keine Rekombination stattfindet, da die Nachkommen immer ähnlich ihren Eltern an der gleichen Position waren und sich die Population nicht gemeinschaftlich in eine bestimmte Richtung bewegt hat. So kann man sich irren.

  11. #11 Man könnte...
    April 11, 2012

    … doch auch einen EA für den EA schreiben. Der die Parameter variiert und so einen deutlich größeren Rahmen ausfüllt. Allerdings hat man dann das Problem “nur” auf eine andere Ebene verschoben. Dennoch denke ich, dass das erfolgreich sein könnte. Spätestens bei der unendlichen Ebene, sollte gute Chance da sein, das globale Optimum zu finden 😉

  12. #12 ich hatte...
    April 20, 2012

    @Man_könnte Lustig! Genau die selbe Idee kam mir auch beim Lesen.
    Einfach das Problem der Parameterwahl mit einem evolutionären Algorithmus lösen 🙂