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.

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 🙂