Skip to content

Simulated Annealing

Introduction

Simulated annealing chooses its next possible position similar to hill climbing, but it accepts worse results with a probability that decreases with time. It simulates a temperature that decreases with each iteration, similar to a material cooling down.

Example

from gradient_free_optimizers import SimulatedAnnealingOptimizer

...

opt = SimulatedAnnealingOptimizer(search_space, annealing_rate=0.999)
opt.search(objective_function, n_iter=100)

About the implementation

The simulated annealing algorithm inherits the methods to get new positions from hill-climbing and the methods to accept the new position from stochastic-hill-climbing. Similar to stochastic hill climbing it may accept a worse position with the goal of escaping a local optimum. The start_temp is a factor for the probability of accepting a worse position.

\[ p = \exp^{-\frac{\text{score}_{normalized}}{\text{temp}}} \]

This probability decreases over time, because of the annealing_rate decreasing the start_temp over time.

\[ \text{start_temp} \leftarrow \text{start_temp} * \text{annealing_rate} \]

Parameters

epsilon

The step-size of the hill climbing algorithm. Increasing epsilon also increases the average step-size, because its proportional to the standard-deviation of the distribution of the hill-climbing-based algorithm. If epsilon is too large the newly selected positions will be at the edge of the search space. If its value is very low it might not find new positions.

  • type: float
  • default: 0.03
  • typical range: 0.01 ... 0.3

distribution

The mathematical distribution the algorithm draws samples from. All available distributions are taken from the numpy-package.

  • type: string
  • default: "normal"
  • possible values: "normal", "laplace", "logistic", gumbel"

n_neighbours

The number of positions the algorithm explores from its current postion before setting its current position to the best of those neighbour positions. If the value of n_neighbours is large the hill-climbing-based algorithm will take a lot of time to choose the next position to move to, but the choice will probably be a good one. It might be a prudent approach to increase n_neighbours of the search-space has a lot of dimensions, because there are more possible directions to move to.

  • type: int
  • default: 3
  • typical range: 1 ... 10

start_temp

The start temperatur determines the probability for the algorithm to jump to a worse position.

  • type: float
  • default: 1
  • typical range: 0.5 ... 1.5

annealing_rate

Rate at which the temperatur-value of the algorithm decreases. An annealing rate above 1 increases the temperature over time.

  • type: float
  • default: 0.97
  • typical range: 0.9 ... 0.99