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)