Inspired Algorithms: Random Search: A baseline technique

The classical baseline for stochastic optimization is the random search algorithm, also referred to as blind search and stochastic generate and test. The strategy of this algorithm involves randomly generating viable solutions from the problems search space and evaluating them. It is used as a baseline for comparison because it is general enough to be applied to any problem for which candidate solutions can be generated and tested.

Each new randomly generated candidate solution is independent of the generated candidate solutions that came before it. Importantly, the algorithm keeps track of the candidate solution found so far using a simple ratcheting function (current best is only replaced by something as good as or better). Given that the random search algorithm samples the problem search space in an unbiased (uniform) manner it may discover areas of interest not considered by conventional wisdom.

The penalty of the algorithms simplicity and lack of memory is its inefficiency. The algorithm does not make use of any problem specific information such as gradient of the response surface. It may perform worse than a complete enumeration of the search space given that there are no mechanisms to bias or prevent the procedure from re-investigating already visited regions of the search space.

Random Search for Continuous Function Optimization
This guide demonstrates the random search algorithm applied to a simple summed squaring function. We start by defining the problem as a class with methods for assessing and comparing candidate solutions. The function is defined as the sum of the squared parameters, where the number of function parameters defines the difficulty or number of dimensions of the problem. Each function parameter is constrained between -5.12 and +5.12.

Candidate solutions are assessed via the evaluate method and are expected as arrays of floating point values. The global solution to the problem is known at 0.0 in each dimension which evaluates to the optimal score of 0.0. In one-dimension the function's response surface can be graphed which looks like the letter 'u' with the optima in the middle of the function. In two-dimensions the response surface looks like a basin. The known optimal scoring is made available in the is_optimal?(scoring) function, useful for an algorithm for accessing whether the optimal solution has been achieved. The problem also defines a solution score comparison, enforcing the minimization constrain of the problem.

class SquaringFunction
  attr_reader :dimensions, :min, :max

  def initialize(dimensions=2)
    @dimensions = dimensions
    @min, @max = -5.12, +5.12
  end

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

  def is_optimal?(scoring)
    scoring == optimal_score
  end

  def optimal_score
    0.0
  end
  
  # true if s1 has a better score than s2
  def is_better?(s1, s2)
    s1 < s2 # minimizing
  end
end

In order to address this problem using the random search algorithm, a candidate solution class and algorithm class are defined. The Solution class is not problem specific, proving a immutable container for solution data in an instance variable which must be set on construction, as well as a score which can be assigned at any time. A default score of NaN (not a number) is assigned defensively to ensure that an error occurs if the solution is not evaluated and is compared to another solution that is evaluated.

class Solution
  attr_reader :data
  attr_accessor :score
  
  def initialize(data)
    @data = data
    @score = 0.0/0.0 # NaN
  end
  
  def to_s
    "[#{@data.inspect}] (#{@score})"
  end    
end

The RandomSearchAlgorithm class requires a maximum number of iterations as parameters on construction which is stored as an instance variable. The core method of the class is search(problem) that executes a random search on the provided problem definition. A single iteration of the algorithm involves the generation of a random candidate solution and its evaluation. The algorithm loops until the stop condition should_stop?(curr_it, problem) is triggered which occurs if the maximum number of iterations have elapsed or if the optimal solution is discovered. The generation of random solutions in the generate_random_solution(problem) method is the only problem-specific logic in the algorithm, creating a random floating point vector within there bounds of the problem space. Finally, the evaluate_candidate_solution(solution, problem) method evaluates a given candidate solution against the problem definition and keeps track of the best solution found.

class RandomSearchAlgorithm
  attr_accessor :max_iterations
  attr_reader :best_solution
  
  def initialize(max_iterations)
    @max_iterations = max_iterations
  end
  
  # execute a random search on the provided problem
  def search(problem)    
    @best_solution = nil
    curr_it = 0
    begin
      candidate = generate_random_solution(problem)
      evaluate_candidate_solution(candidate, problem)
      curr_it += 1
    end until should_stop?(curr_it, problem)
    return @best_solution
  end
  
  def should_stop?(curr_it, problem)
    (curr_it >= @max_iterations) or problem.is_optimal?(best_solution.score)
  end
  
  def generate_random_solution(problem)
    real_vector = Array.new(problem.dimensions) do
      next_bfloat(problem.min, problem.max)
    end
    return Solution.new(real_vector)
  end

  def next_bfloat(min, max)
    min + ((max - min) * rand)
  end
  
  def evaluate_candidate_solution(solution, problem)
    solution.score = problem.evaluate(solution.data)
    # keep track of the best solution found
    if @best_solution.nil? or
      problem.is_better?(solution.score, @best_solution.score)
      @best_solution = solution
      puts " > new best: #{solution.score}"               
    end
  end  
end

Now we can execute the algorithm on the problem. This involves initializing the global random number generator to 1 and initializing the algorithm with the maximum number of 1000 iterations to execute. The problem instance is created with 5 decision variables (dimensions) and the algorithm is executed on the instance.

srand(1) # set the random number seed to 1
algorithm = RandomSearchAlgorithm.new(1000) # limit to 1000 iterations
problem = SquaringFunction.new(5) # create a problem with 5 dimensions
best = algorithm.search(problem) # execute the search
puts "Best Solution: #{best}" # display the best solution

This example provides a demonstration of a standard separation of problem, algorithm, and solution, as well as modularized responsibility within each class. For example, the RandomSearchAlgorithm class can be directly applied to any function optimization problem, or with a replacement of the generate_random_solution(problem) method it can be applied to any problem definition that aligns to the SquaringFunction classes simple interface.

Source Code
Download: RandomSearch.rb

Further Reading
Given the simplicity of the approach there are few resources dedicated to describing it. Instead the following provide some general resources for the broader field of stochastic optimization.

Books