Zufallslandschaft
aus Wikipedia, der freien Enzyklopädie
Eine Zufallslandschaft bezeichnet in der Mathematik eine Wertelandschaft, die jedem Ort der Wertelandschaft eine Zufallszahl zuordnet. Häufig ist die Nachbarschaftsfunktion der Zufallslandschaft so definiert, dass für jeden Punkt x der Zufallslandschaft alle diejenigen Punkte als Nachbar gelten, deren binäre Repräsentation die eine Hamming-Distanz von 1 zur binären Repräsentation von x aufweist.
Zufallslandschaften haben die Eigenschaft, an ihren Orten keinerlei Aussage über die Höhe von Nachbarorten zuzulassen. Damit sind sie für viele Optimierungsverfahren der Worst-case, denn die meisten Optimierungsverfahren bauen auf die Redundanz, die Orte gegenüber seinen Nachbarorten üblicherweise haben.
[Bearbeiten] Beispiel
- Wir wählen ein
. 
- Wir definieren
- Wir definieren
Für eine so generierte Zufallslandschaft gilt:
- Jeder Punkt aus D hat n Nachbarn.
- Die Wahrscheinlichkeit für einen Punkt aus D, lokales Maximum bezüglich f zu sein, ist
. - Damit gibt es etwa
lokale Maxima. - Die durchschnittliche Schrittanzahl, bis ein lokales Maximum mittels Bergsteigeralgorithmus (hill climbing) gefunden wurde, ist
.
