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}