Cooperative Simulated Annealing

Cooperative simulated annealing implements concurrent synchronous runs of multiple SA processes. The concurrent processes are coupled through cooperative transitions, which replace the uniform distribution used to select the neighbors. Essentially, the algorithm manipulates multiple solutions (a population of solutions) at once.

To get a better idea of this, assume we have five solutions. We start with a randomly chosen population:

$${\text{Pop}}_0=[S_1,S_2,S_3,S_4,S_5]$$

The new population is iteratively produced. Any new solution is cooperatively produced by the previous value of that solution, and the previous value of another randomly selected solution.

How do we find $S_{1\text{new}}$ from $S_1$ and $S_4$? We find the neighbors of $S_1$ that are closer to $S_4$ than $S_1$ itself (using some distance measure). These neighbors constitute what is known as the CLOSER set.

The CLOSER set is defined as:

$$\text{CLOSER}=\{s_k\in \mathcal{N}(S_1)|d(s_k,S_4)<d(s_k,S_1)\}$$

If the CLOSER set is not empty, the new solution is randomly selected from it. Otherwise, the new solution is randomly selected from the neighborhood of $S_1$.

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

$$\begin{array}{rl}\Delta E& =E({\text{Pop}}_k)-E({\text{Pop}}_{k-1})\\ T& =\{\begin{array}{ll}T,& \text{if }\Delta E<0\\ \alpha T,& \text{otherwise}\end{array}\end{array}$$