Simulated Annealing

Header: fiction/algorithms/optimization/simulated_annealing.hpp

constexpr auto fiction::linear_temperature_schedule(const double t) noexcept

A linearly decreasing temperature schedule. The temperature is altered in decrements of 10.

Parameters:

t – The current temperature.

Returns:

The next temperature, i.e. \(\texttt{t} - 10\).

constexpr auto fiction::geometric_temperature_schedule(const double t) noexcept

A logarithmically decreasing temperature schedule. The temperature is altered by multiplying it with 0.99.

Parameters:

t – The current temperature.

Returns:

The next temperature, i.e. \(\texttt{t} \cdot 0.99\).

template<typename State, typename CostFunc, typename TempFunc, typename NextFunc>
std::pair<State, std::invoke_result_t<CostFunc, State>> fiction::simulated_annealing(const State &init_state, const double init_temp, const double final_temp, const std::size_t cycles, CostFunc &&cost, TempFunc &&schedule, NextFunc &&next) noexcept

Simulated Annealing (SA) is a probabilistic optimization algorithm that is used to find a local minimum of a given function. SA was first proposed in “Optimization by simulated annealing” by S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi in Science 1983. It is a metaheuristic that is inspired by the annealing process in metallurgy. The algorithm starts with a random state and iteratively improves the state by randomly selecting a neighboring state. If the neighboring state is better than the current state, it is accepted. If the neighboring state is worse than the current state, it is accepted with a probability that decreases over time. The algorithm stops when the temperature reaches a certain threshold.

Some pre-defined temperature schedules are provided in this header file.

This implementation is based on: https://codereview.stackexchange.com/questions/70310/simple-simulated-annealing-template-in-c11

Template Parameters:

  • State – The state type.

  • CostFunc – The cost function type (specifies the cost type via its return value).

  • TempFunc – The temperature schedule function type.

  • NextFunc – The next state function type.

Parameters:

  • init_state – The initial state to optimize.

  • init_temp – The initial temperature.

  • final_temp – The final temperature.

  • cycles – The number of cycles for each temperature value.

  • cost – The cost function to minimize.

  • schedule – The temperature schedule.

  • next – The next state function that determines an adjacent state given a current one.

Returns:

A pair of the optimized state and its cost value.

template<typename RandStateFunc, typename CostFunc, typename TempFunc, typename NextFunc>
std::pair<std::invoke_result_t<RandStateFunc>, std::invoke_result_t<CostFunc, std::invoke_result_t<RandStateFunc>>> fiction::multi_simulated_annealing(const double init_temp, const double final_temp, const std::size_t cycles, const std::size_t instances, RandStateFunc &&rand_state, CostFunc &&cost, TempFunc &&schedule, NextFunc &&next) noexcept

This variation of Simulated Annealing (SA) does not start from just one provided initial state, but generates a number of random initial states using a provided random state generator. SA as specified above is then run on all these random initial states where the best result of all generated states is finally returned.

Note

If compiler support for C++17’s execution policies is available, the algorithm is parallelized and/or vectorized using std::execution::par_unseq.

Note

The State type must be default constructible.

Template Parameters:

  • RandStateFunc – The random state generator function type (specifies the State type via its return value).

  • CostFunc – The cost function type (specifies the cost value via its return value).

  • TempFunc – The temperature schedule function type.

  • NextFunc – The next state function type.

Parameters:

  • init_temp – The initial temperature.

  • final_temp – The final temperature.

  • cycles – The number of cycles for each temperature value.

  • instances – The number of random initial states to generate.

  • rand_state – The random state generator function.

  • cost – The cost function to minimize.

  • schedule – The temperature schedule.

  • next – The next state function that determines an adjacent state given a current one.

Returns:

A pair of the overall best optimized state and its cost value.