simulated_annealing

Simulated annealing is a stochastic optimisation procedure.

Example: Find value for x so that x^2 - 7x + 10 = 0, with x in range [0,10].

make_instance: 

  procedure make_instance(x)
    if /x then {
      return 10 * ?0 # random number [0.0,10.0)
    } else {
      new_x := x + 0.02 * ?0 - 0.01
      if new_x < 0 then new_x := 0
      if new_x > 10 then new_x := 10
      return new_x
    }
  end

evaluation: 

  procedure evaluation(x)
    y := x * x - 7 * x + 10
    return y * y  # returns positive number, 0 is best result
  end

run: 

  result := simulated_annealing(make_instance, evaluation, 1000)
  write("Final value of x: ", result)

Procedures

metropolis_acceptance_criterion (es, en, temp)

Computes the Metropolis acceptance criterion.

es
current instance evaluation
en
new/candidate instance evaluation
temp
temperature value

simulated_annealing (instance_maker, evaluate_instance, num_iterations, can_stop)

Returns the best instance found after performing simulated-annealing stochastic search.

instance_maker
procedure accepting 0 or 1 arguments, returns a new instance: the neighbour of a given instance, or a random instance.
evaluate_instance
procedure taking an instance and returning a positive number indicating quality of solution, with 0 being perfect.
num_iterations
the number of iterations to perform.
can_stop
an optional procedure taking the current evaluation and iteration number, succeeds if the algorithm should stop.
Home