Module simulated_annealing

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

SimulatedAnnealingSolver

A simulated annealing solver that uses a Neighborhood and an Objective, an initial_temperature (f32 in the magnitute of the objective values), a cooling_factor (f32between 0 and 1, e.g., 0.9), and an AcceptanceProbabilityFunction to find a good solution.

Type Aliases

AcceptanceProbabilityFunction

Type for the acceptance_probability_function.

Probability

Type for the acceptance probability.

ScalingFactor

Type for the cooling_factor, which is a value between 0 and 1 (e.g., 0.9).

Temperature

Type for the temperature, which should be in the magnitude of the objective values in the beginning.