rapid_solve::heuristics

Module simulated_annealing

Source
Expand description

This module contains the SimulatedAnnealingSolver implementing the simulated annealing metaheuristic.

  • Starts with an initial solution and iteratively considers neighbors.
  • An improvement is always accepted, but a worse neighbor is also accepted with a certain probability.
  • This probability is based on the difference in objective value and the current temperature.
  • The temperature is reduced whenever a worse neighbor is accepted.
  • The search stops after a certain number of iterations, or after a certain time limit, or if the whole neighborhood is explored without any acceptance.
  • The best solution seen during this process is returned.
  • The acceptance probability usualy depends exponentially on the difference in objective value and the current temperature, i.e., e-∆f/T, where ∆f is the difference in objective value and T is the current temperature.
  • The simulated annealing heuristic is similar to the deterministic threshold accepting heuristic, which performs similar, but does not require computing the acceptance probability.

For an example, see the simulated annealing solver for the TSP.

Structs§

Type Aliases§