A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 9 Ω
Das Banner der Rhetos-Website: zwei griechische Denker betrachten ein physikalisches Universum um sie herum.

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.


Dieses Bild ist für das Verständnis des Textes nicht wichtig. Das Bild wird im Text nicht erwähnt.
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


Support-Vektor-Maschinen zur robusten nichtlinearen Klassifikation komplexer biologischer Daten. Dissertation. Fakultät für Informatik und Automatisierung der Technischen Universität Ilmenau. 2016. Siehe auch Mutationsweite ↗