Simulated Annealing

Simulated Annealing is the simulation of physical annealing used as a search algorithm. The acceptance probability $p$$\large p$ of a given solution is given by:

where $\mathrm{\Delta }c$$\large \Delta c$ is the change in the cost, and $T$$\large T$ is the current temperature.

Annealing Schedule

The annealing schedule is the mapping between temperature $T$$\large T$ and iteration $t$$\large t$.

Linear Annealing Schedule:

Geometric Annealing Schedule:

Asymptotic Annealing Schedule:

Cooperative Simulated Annealing

Cooperative Simulated Annealing consists of $n$$\large n$ solutions being searched simultaneously. Thus, the problem state population $Po{p}_t$$\large Pop_{t}$ at iteration $t$$\large t$ consists of $n$$\large n$ states $S_i$$\large S_i$:

At every iteration, the search algorithm generates a new population $Po{p}_{t+1}$$\large Pop_{t + 1}$:

$S_{inew}$$\large S_{i\:new}$ is selected randomly from the closer set of $S_i$$\large S_i$ and another randomly selected state $S_j$$\large S_j$:

where $N(S_i)$$\large N(S_i)$ is the neighborhood of state $S_i$$\large S_i$. If the closer set $\text{CLOSER}(S_i,S_j)$$\large \text{CLOSER}(S_i, S_j)$ is empty, $S_{inew}$$\large S_{i\:new}$ is randomly selected from $N(S_i)$$\large N(S_i)$.

The temperature is updated based on the different of the mean fitness of the new and old populations: