Random Walk

Description

Hill climbers work under the assumption that there is some structure in the search space.

The chance that a good solution is neighboring another good solution should be higher than that it is surrounded by only bad solutions or at a random location.

Based on this idea, the hill climber generates modified copies of the current solution and accepts them if they are better than the old solution.

Random walks are also known as Drunkard’s walks

Also do not utilize the information gathered during the search

Start at a (random) location and take random steps

The stopping criterion for a random walk might be a preset maximum number of iterations or some other problem-dependent criterion. With luck, a random walk will find the minimum quicker than can be done with a brute force search. Like both the classical and the brute force methods, the random walk suffers from the step size problem because it is very difficult to choose the right standard deviations when the objective function is not sufficiently well known.

Mutation Function

New points are generated by adding a random deviation, ∆x, to a given base point, x0. In general, each coordinate, ∆xi, of the random deviation follows a Gaussian distribution

References

Thomas Weise - Metaheuristic Optimization

Th.Bäck A.E.Eiben J.N.Kok H.P.Spaink - Natural Computing Series

Pseudo Code

\begin{algorithm}
\caption{RW Algorithm}
\begin{algorithmic}
                \STATE $f \gets \text{the objective function subject to minization}$
                \STATE $shouldTerminate \gets \text{the termination criterion}$
                \STATE $x \gets \text{the new solution to be tested}$
                \STATE $\textit{Best} \gets \text{the best individual ever discovered}$
                \STATE $\textit{Best} \gets random()$
                \WHILE{$shouldTerminate$}
                    \STATE $x \gets mutation(\textit{Best})$
                    \IF{$f(\textit{Best}) \leq f(x)$}
                        \STATE $\textit{Best} \gets x$
                    \ENDIF
                \ENDWHILE
                \RETURN $\textit{Best}$
\end{algorithmic}
\end{algorithm}