Vorzeitige Konvergenz
Mathematik, Evolution
Definition
Als vorzeitige Konvergenz[1] oder der Falle des lokalen Optimums[2] bezeichnet man ein unerwünschtes Verhalten des sogenannten Gradientenverfahrens beim Aufsuchen eines absoluten oder mehrer verschiedener lokaler Optima. Die Optima können sowohl Hoch- wie auch Tiefpunkte eines Graphen sein. Dabei kann ein schwerwiegendes Problem auftreten.
Zur Idee der vorzeitigen Konvergenz
Die Kernidee ist, dass man bei der Suche nach einem Hoch- oder Tiefpunkt von einem momentanten Standpunkt aus immer der größten Steigung aufwärts (HP suchen) oder abwärts (TP suchen) folgt. Hat man so zum Beispiel einen lokalen Hochpunkt erreicht, wird man mit diesem Verfahren keinen weiter entfernten, noch höheren Punkte auffinden können.
=-x^4+0,5x^3+2x^2.png)
Findet man mit dem Gradientenverfahren durch Zufall zuerst den linken Hochpunkt, bleibt der Algorithmus ohne geeignete Gegenmaßnahmen dort hängen: die Falle des lokalen Optimums.
Man ist auf dem zuerst gefundenen lokalen Hochpunkt gefangen. Dasselbe Problem hat auch ein sogenannter genetischer Algorithmus. Zur Veranschaulichung dient oft eine sogenannte Erfolgslandschaft ↗
Das Dilemma mit der Mutationsweite
Eine Möglichkeit zur Verhinderung einer vorzeitigen Konvergenz ist die Vergrößerung der Mutationsweite. Als Mutationsweite bezeichnet man in der Biologie den Wertebereich, in dem von einer zur nächsten Generation die neuen Ausprägungen eines Individuum liegen können.[2] Je größer nun die Mutationsweite, desto weiter entfernt vom momentan bekannten und vielleicht bewährten Bereich liegen die neuen Versuche. Damit erhöht sich die Wahrscheinlichkeit für drastisch minderwertige Individuen im Sinne einer Optimierung. Umgekehrt, engt man die Mutationsweite stark ein (konservative Strategie), so kann unmöglich weiter entferntere bessere Bereiche finden. Welche Strategie die Bessere ist, kann man ohne Kenntnis der Erfolgslandschaft nicht im Voraus sagen. Siehe mehr unter Mutationsweite ↗
Fußnoten
- [1] Von einer vorzeitigen Konvergenz (premature convergence) sprechen zum Beispiel: Yee Leung, Yong Gao, Zong-Ben Xu: Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. In: IEEE Transactions on Neural Networks. Band 8, Nr. 5, September 1997, ISSN 1045-9227, S. 1165–1176, doi:10.1109/72.623217
- [2] Von einer "Falle des lokalen Optimums" sprechen am Beispiel eines technischen Optimierungsproblem: A. Alshahrani, N. M. Namazi, M. Abdouli, M. A. Alqarni: Escaping the local optima trap caused by PSO by hybridization scheme for elongate the WSN's lifetime. 2017 8th IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), Vancouver, BC, Canada, 2017, pp. 121-127, doi: 10.1109/IEMCON.2017.8117166.
- [3] "Die Mutationsweite bestimmt den Wertebereich, in dem die Individuen mutieren." In: Maria Trommer: Beitrag zur Anwendung von