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§
- A simulated annealing solver that uses a
Neighborhood
and anObjective
, aninitial_temperature
(f32
in the magnitute of the objective values), acooling_factor
(f32
between 0 and 1, e.g., 0.9), and anAcceptanceProbabilityFunction
to find a good solution.
Type Aliases§
- Type for the
acceptance_probability_function
. - Type for the acceptance probability.
- Type for the
cooling_factor
, which is a value between 0 and 1 (e.g., 0.9). - Type for the temperature, which should be in the magnitude of the objective values in the beginning.