Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Free Course | Read Online



This is the ad-supported version of the book. Buy it now if you like it.

Random Search

Random Search, RS, Blind Random Search, Blind Search, Pure Random Search, PRS

Taxonomy

Random search belongs to the fields of Stochastic Optimization and Global Optimization. Random search is a direct search method as it does not require derivatives to search a continuous domain. This base approach is related to techniques that provide small improvements such as Directed Random Search, and Adaptive Random Search.

Strategy

The strategy of Random Search is to sample solutions from across the entire search space using a uniform probability distribution. Each future sample is independent of the samples that come before it.

Procedure

Algorithm (below) provides a pseudocode listing of the Random Search Algorithm for minimizing a cost function.

Input: NumIterations, ProblemSize, SearchSpace
Output: Best
Best $\leftarrow \emptyset$
For ($iter_i \in$ NumIterations)
    $candidate_i$ $\leftarrow$ RandomSolution(ProblemSize, SearchSpace)
    If (Cost($candidate_i$) < Cost(Best))
        Best $\leftarrow$ $candidate_i$
    End
End
Return (Best)
Pseudocode for Random Search.

Heuristics

  • Random search is minimal in that it only requires a candidate solution construction routine and a candidate solution evaluation routine, both of which may be calibrated using the approach.
  • The worst case performance for Random Search for locating the optima is worse than an Enumeration of the search domain, given that Random Search has no memory and can blindly resample.
  • Random Search can return a reasonable approximation of the optimal solution within a reasonable time under low problem dimensionality, although the approach does not scale well with problem size (such as the number of dimensions).
  • Care must be taken with some problem domains to ensure that random candidate solution construction is unbiased
  • The results of a Random Search can be used to seed another search technique, like a local search technique (such as the Hill Climbing algorithm) that can be used to locate the best solution in the neighborhood of the 'good' candidate solution.

Code Listing

Listing (below) provides an example of the Random Search Algorithm implemented in the Ruby Programming Language. In the example, the algorithm runs for a fixed number of iterations and returns the best candidate solution discovered. The example problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$.

def objective_function(vector)
  return vector.inject(0) {|sum, x| sum + (x ** 2.0)}
end

def random_vector(minmax)
  return Array.new(minmax.size) do |i|
    minmax[i][0] + ((minmax[i][1] - minmax[i][0]) * rand())
  end
end

def search(search_space, max_iter)
  best = nil
  max_iter.times do |iter|
    candidate = {}
    candidate[:vector] = random_vector(search_space)
    candidate[:cost] = objective_function(candidate[:vector])
    best = candidate if best.nil? or candidate[:cost] < best[:cost]
    puts " > iteration=#{(iter+1)}, best=#{best[:cost]}"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  problem_size = 2
  search_space = Array.new(problem_size) {|i| [-5, +5]}
  # algorithm configuration
  max_iter = 100
  # execute the algorithm
  best = search(search_space, max_iter)
  puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
end
Random Search in Ruby
Download: random_search.rb.

References

Primary Sources

There is no seminal specification of the Random Search algorithm, rather there are discussions of the general approach and related random search methods from the 1950s through to the 1970s. This was around the time that pattern and direct search methods were actively researched. Brooks is credited with the so-called 'pure random search' [Brooks1958]. Two seminal reviews of 'random search methods' of the time include: Karnopp [Karnopp1963] and perhaps Kul'chitskii [Kulchitskii1976].

Learn More

For overviews of Random Search Methods see Zhigljavsky [Zhigljavsky1991], Solis and Wets [Solis1981], and also White [White1971] who provide an insightful review article. Spall provides a detailed overview of the field of Stochastic Optimization, including the Random Search method [Spall2003] (for example, see Chapter 2). For a shorter introduction by Spall, see [Spall2004] (specifically Section 6.2). Also see Zabinsky for another detailed review of the broader field [Zabinsky2003].

Bibliography

[Brooks1958] S. H. Brooks, "A Discussion of Random Methods for Seeking Maxima", Operations Research, 1958.
[Karnopp1963] D. C. Karnopp, "Random search techniques for optimization problems", Automatica, 1963.
[Kulchitskii1976] O. Y. Kul'chitskii, "Random-search algorithm for extrema in functional space under conditions of partial uncertainty", Cybernetics and Systems Analysis, 1976.
[Solis1981] F. J. Solis and J. B. Wets, "Minimization by Random Search Techniques", Mathematics of Operations Research, 1981.
[Spall2003] J. C. Spall, "Introduction to stochastic search and optimization: estimation, simulation, and control", John Wiley and Sons, 2003.
[Spall2004] J. C. Spall, "6. Stochastic Optimization", in Handbook of computational statistics: concepts and methods, pages 169-198, Springer, 2004.
[White1971] R. C. White, "A survey of random methods for parameter optimization", Simulation, 1971.
[Zabinsky2003] Z. B. Zabinsky, "Stochastic adaptive search for global optimization", Kluwer Academic Publishers, 2003.
[Zhigljavsky1991] A. A. Zhigljavsky, "Theory of Global Random Search", Kluwer Academic, 1991.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • ...to read at your own pace
Sign-up Now












Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • ...best practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now




Please Note: This content was automatically generated from the book content and may contain minor differences.

Clever Algorithms: Nature-Inspired Programming Recipes



Do you like Clever Algorithms?
Buy the book now.


© Copyright 2014. All Rights Reserved. | About | Contact | Privacy