ℜ
Physik Chemie Grundschule Mathematik I Mathematik II Wissen
Kurze Worte Worte nach Alter Terme Rechner
Mathfeed Physfeed Philfeed
Das Lexikon Die Mission Die Autoren Copyright Impressum
Physik 5-10 Physik 11-13 Chemie 5-13 Mathe 5-8 Mathe 9-10 Mathe 10-13
☰
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.

Bergsteigeralgorithmus

Evolution

Basiswissen


Der Bergsteigeralgorithmus ist ein Verfahren der Mathematik, mit dem sich lokale Hochpunkte von Funktionen durch eine Art intelligentes Probieren finden lassen. Dieser Algorithmus wird oft auch als einfachst mögliche Variante eines genetischen Algorithmus betrachtet.

Einführendes Beispiel


Wenn eine biologische Art durch Variation neue Körperformen oder Verhaltensweisen ausprobiert[2], so tut sie das immer unter einem gewissen Risiko. Weniger gut an die Umwelt angepasste Individuen sind wie eine Fehlinvestition in der Wirtschaft. Wenn ein Vogelpaar Nachkommen mit stark unterschiedlichen Flügelformen ausbrütet, und sind manche der Küken letztendlich flugunfähig, so hat dieses Vogelpaar unter bestimmten Umweltbedingungen einen Nachteil gegenüber einem Vogelpaar, dessen Küken alle flugfähig sind. Nach dieser Logik entsteht ein "Druck", dass einerseits neue Flügelformen ausprobiert werden, um mögliche Verbesserungen zu finden. Andererseits aber sollten diese Versuche selbst gleichzeitig auch selbst möglichst erfolgreich sein. Der nötigen Kreativität entgegen wirkt also gleichzeitig ein gewisser Erfolsgdruck. Mit welcher Strategie sollte man also vorgehen?

Eine Möglichkeit, einen Ausgleich zwischen Kreativität und Erfolg herzustellen ist die Strategie, dass man neue Versuche in der Nähe bekannter Erfolge platziert. Man könnte diese Strategie auch als konservativ bezeichnen. Angenommen man kennt den Verlauf einer Funktion nicht, soll aber mit möglichst wenigen Fehlversuchen möglichst hohe Punkte auf dem Graphen finden.[3] Wie würde man dann am besten vorgehen?


Dieses Bild ist für das Verständnis des Textes nicht wichtig. Das Bild wird im Text nicht erwähnt.
Man stelle sich vor, man kennt diesen Graphen noch nicht, aber man will mit stichprobenartigen Abfragen einzelner Punkte möglichst hohe Punkte finden. Man darf nur insgesamt 2 Fehlversuche machen.


Um die Logik und die Zwänge bei diesem Verfahren zu verstehen, lohnt es sich, die Versuche selbst einmal durchzuführen. Die Funktionswerte fragt man zum Beispiel mit einem Taschenrechner oder einem zweiten Mitspieler ab. Dazu sind hier drei weitere Funktionen, die im Intervall von x=-2 bis x=2 einen interessanten Kurvenverlauf haben:


Der Bergsteigeralgorithmus als Programm


Der Bergesteigeralgorithmus wird in verschiedenen Abwandlungen häufig als kleines Computerprogramm umgesetzt. Anders als im Beispiel oben, wird für jeden Zeitpunkt nicht immer nur ein Punkt ausprobiert, sondern es wird eine Population von Punkten erzeugt. Die Punkte mit den niedrigsten Funktionswerten, die also tiefer liegen, dürfen sich bei einem Generationswechsel dabei weniger stark vermehren als Punkte mit einem hohen Funktionswert. Der Kern der Programmlogik ist in den folgenden wenigen Zeilen enthalten:

ymax=ay
xmax=ax
if by>ymax then ymax=by : xmax=bx
if cy>ymax then ymax=cy : xmax=cx
ax=xmax
bx=xmax+rand*suchweite
cx=xmax-rand*suchweite

Visualiert man solche Programme, kann man beobachten, wie eine Population von Punkte wie eine wabernde Wolke langsam aber zielstrebig dem steilsten Weg bergauf hin zu einem Gipfel strebt. Den Quellcode für das vollständige Basic-Programm findet man auf der Seite Basic256 Programme genetischer Gipfelsucher 01 ↗

Die vorzeitige Konvergenz


Ein tiefer in die Logik evolutionärer Strategien führendes Problem ist die sogenannte vorzeitige Konvergenz: so bezeichnet man ein Hinlaufen auf eine nur lokal in enger Umgebung gute Lösung, während es etwas weiter entfernt vom momentanten Ort der Suche noch deutlich höhere Punkte gibt. Um das Problem zu verstehen hilft wieder die Metapher vom Wanderer im Nebel.

Man stelle sich vor, man versucht im dichten Nebel den Gipfel eines hohen Berges zu erwandern. Man kennt sich aber in der Landschaft nicht gut aus und weiß auch nicht, wie der Berg im einzelnen geformt ist. Hat der Gipfel dann einen oder mehrere niedrigere Nebengipfel, dann kann es gut sein, dass man im Nebel auf einen Nebelfipfel aufsteigt und von diesem nicht mehr wegkommt. Da man ja immer nur bergauf geht, würde man nicht weitsichtig handelnd erst herab steigen, dann ein Tal oder eine Senke durchschreiten, um letztendlich mit höherem Gewinn einen noch höheren Gipfel zu erklimmen. Tatsächlich droht mit dem Bergsteigeralgorithmus immer, dass man vorzeitig, vor dem Erreichen des wirklich höchsten Gipfels, mathematisch dem absoluten Hochpunkt, auf einem niedrigeren Nebengipfel, einen nur lokalen aber nicht absoluten Hochpunkt verharrt.[4]

Vorzeitige Konvergenz in der Evolution


In der biologischen Evolution veranschaulicht man sich die Suche der Individuen und Arten nach immer besser angepassten Phänotypen, also Körpern und Verhaltensweisen, mit Hilfe einer Erfolgslandschaft.[5] Wenn zum Beispiel die Nachkommen einer Art eine nur geringe Mutationsweite[6] haben, die genetischen Veränderungen also gering sind, entspricht dies einem eher lokalen Suchen in der Nähe der momentanen Aufenthaltspunkte. Siehe auch vorzeitige Konvergenz ↗

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.