Font Size:

Comparison of cooling schedules in the simulated annealing algorithm applied to the clustering problem

Last modified: 2024-05-14

#### Abstract

The simulated annealing (SA) algorithm was proposed by Kirkpatrick, Gellat, and Vecchi (1983). This algorithm evaluates new solutions based on a cooling rate known as \textit{temperature}, denoted by $T_k$. Two widely accepted models for defining $T_k$ exist. The first is the geometric model: $T_k=\alpha T_{k-1}$, with $0<\alpha<1$, which is most commonly used in practice. %\cite{Kim+Kim+Jang+Chen, Talbi}.The second is the logarithmic model: $T_{k+1}=\tfrac{c}{\log(k+1)}$,where $c$ is a constant, facilitating rigorous convergence tests of the SA algorithm. %\cite{Hajek1988, Geman+Geman}

While these are prevalent, there are other cooling schedules less commonly employed yet utilized in research applying the simulated annealing algorithm. Examples include: $T_{k+1}=T_k\cdot \left\{1+\tfrac{T_k\cdot \ln(1+\delta)}{3\cdot \sigma_k}\right\}^{-1}$, $T_{k+1}=\tfrac{T_k}{1+\beta\cdot T_k}$, $T_{k+1}=\tfrac{T_k}{1+\beta_k\cdot T_k}$ and $T_k=T_0\cdot a^{-\left[\tfrac{k}{f\cdot k_{\text{máx}}}\right]^b}$. In this presentation, we will compare these cooling schedules to assess whether the widespread adoption of the geometric model is truly justified. This comparison will be conducted within the context of an optimization problem associated with partitioning a set of quantitative data.

While these are prevalent, there are other cooling schedules less commonly employed yet utilized in research applying the simulated annealing algorithm. Examples include: $T_{k+1}=T_k\cdot \left\{1+\tfrac{T_k\cdot \ln(1+\delta)}{3\cdot \sigma_k}\right\}^{-1}$, $T_{k+1}=\tfrac{T_k}{1+\beta\cdot T_k}$, $T_{k+1}=\tfrac{T_k}{1+\beta_k\cdot T_k}$ and $T_k=T_0\cdot a^{-\left[\tfrac{k}{f\cdot k_{\text{máx}}}\right]^b}$. In this presentation, we will compare these cooling schedules to assess whether the widespread adoption of the geometric model is truly justified. This comparison will be conducted within the context of an optimization problem associated with partitioning a set of quantitative data.

#### Keywords

Simulated annealing, Cooling schedules, Clustering

#### References

\bibitem{Kirkpatrick+Gelatt+Vecchi83} Kirkpatrick, S., Gellat, C., Vecchi, M.: Optimization by simulated annealing. Science. \textbf{220}, 671--680 (1983)