Random Search

Going way back to basics today with a look at Random Search. In this simple algorithm, the solution space is sampled purely at random, with no attempt to learn from previous samples.

The approach is described as follows.

  • Given fitness function “f”
  • Select a starting point x at random within the solution space.
  • Let best = x.
  • Sample a new position x at random within the solution space.
  • If f(x) < f(best), replace best with x.
  • Continue until termination criteria is reached.

In the worst case, random search may perform worse than full enumeration. The reason for this is that this search method has no memory, and will certainly sample the same “x” multiple times.

This type of search, sometimes called “true random search” or “pure random search”, is often used as a point of reference in literature.

Variants

  • Rastrigin (1963) presents an improved variant FSSRS which samples the previous best around a hyperspace of fixed radius “r”.

Further Reading

References

Rastrigin, L.A (1963), “About Convergence of Random Search Method in Extremal Control of Multi-Parameter Systems” L.A. Rastrigin (mathnet.ru, includes PDF, russian language).