Zufallslandschaft

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.

Beispiel

• Wir wählen ein $n \in \mathbb{N}$.
• $D=\left\{0,1\right\}^n$
• Wir definieren $\forall \left(x \in D \right):\left( f\left( x \right):= random \left( \right)\right)$
• Wir definieren $\forall \left(x \in D \right):\left( nachbarn \left( x \right) = \left\{ d \vert \left( d \in D\right) \and \left( hammingDistance \left( d,x \right) = 1 \right) \right\}\right)$

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 $\frac {1}{n+1}$.
• Damit gibt es etwa $\frac {2^n}{n+1}$ lokale Maxima.
• Die durchschnittliche Schrittanzahl, bis ein lokales Maximum mittels Bergsteigeralgorithmus (hill climbing) gefunden wurde, ist $ln \left( n\right)$.