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.

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

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

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