Random landscape

A random scenery referred to mathematics a value system that anywhere in the value system a random number assigns. The neighborhood function of the random landscape is often defined in such a way that for each point of the random landscape all those points are considered to be neighbors whose binary representation has a Hamming distance of 1 to the binary representation of . ${\displaystyle x}$ ${\displaystyle x}$

Random landscapes have the property of not allowing any statements about the height of neighboring locations at their locations. This makes them the worst-case for many optimization processes , because most optimization processes build on the redundancy that places usually have compared to their neighboring places.

example

• We choose one . ${\displaystyle n\in \mathbb {N} }$
• ${\displaystyle D=\left\{0,1\right\}^{n}}$
• We define ${\displaystyle \forall \left(x\in D\right)\colon \left(f\left(x\right):=\operatorname {random} \left(\right)\right)}$
• We define ${\displaystyle \forall \left(x\in D\right)\colon \left(\operatorname {nachbarn} \left(x\right)=\left\{d\vert \left(d\in D\right)\land \left(\operatorname {hammingDistance} \left(d,x\right)=1\right)\right\}\right)}$

The following applies to a random landscape generated in this way:

• Every point in has neighbors. ${\displaystyle D}$ ${\displaystyle n}$
• The probability for a point to be local maximum with respect to is . ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle {\tfrac {1}{n+1}}}$
• This means that there are local maxima , for example . ${\displaystyle {\tfrac {2^{n}}{n+1}}}$
• The average number of steps until a local maximum by means of hill climbing ( hill climbing was) found is . ${\displaystyle \ln(n)}$