Simulated annealing

The annealing command simulates the annealing of a metal using an analogy between the energy of the system and the criterion minimized (the opposite of the loglikelihood). Given an initial marker ordering and a current parameter called the ``temperature'' (noted $T$), the map is perturbated and the difference $\delta$ in loglikelihood is computed:

• if the loglikelihood is improved ($\delta \geq 0$), the perturbation is accepted and the perturbated map becomes the new map.
• else, the perturbated is accepted only with probability $e ^{\frac{\delta}{T}}$. This simulated the Boltzman distribution used in statistical physics.

Starting from an initial temperature $T_i$, this process is repeated a given number of times (noted $N$). then the temperature is cooled by a constant ratio $\alpha< 1$. This process is repeated until a final temperature $T_f$ is reached. Naturally, the slower the cooling and the larger the number of trial at constant temperature, the slower the method but also the more powerful it is. Basically, we strongly advise users to play with the parameters $T_i, T_f,\alpha,N$ on their data. CARTHAGENE includes an auto-adjusting methods for $T_i$ which makes the parameter of limited importance. The parameter $\alpha$ should be taken close to $1$ and a value between $0.9$ and $0.995$ is typical. The parameter $N$ should be of the same order as $n^2$ where $n$ is the number of markers selected.

The parameters should be adjusted by trial and error. When the simulated annealing is executed, the software reports its behavior. If a new improved map is found, a '+'' is printed. If such an event occurs not too long before the end of the annealing, the process should be ideally repeated with a slower/longer cooling schedule.