Improving and validating existing maps

Map improving and validating commands all try to find a map whose loglikelihood is improved over an initial map. For all such commands, the initial map used is the best map in the heap. Beyond a possible map improvement, all these commands may affect the contents of the heap: all maps considered by these commands are candidate for insertion.

The first category of commands are simple heuristics command that slightly perturbate the initial map in a systematic manner:

These commands are simple and systematic. CARTHAGENE offers much more powerful commands that use a class of discrete optimization techniques called ``stochastic optimization'' or more precisely ``local search methods''. This class of methods is usually acknowledged as the most efficient class of technique for hard discrete optimisation problems such as the genetic marker ordering2.2

These optimisation methods all follow a similar principle: one or several current orders are stochastically ``perturbated'' and depending on the result of the pertubation and a random choice, the perturbated maps may replace the original maps or not. Three such methods are integrated in CARTHAGENE: simulated annealing [LA84], taboo search [Glo89,Glo90] and genetic algorithm [Gol89]. The three methods use the same perturbation mechanism: a subsection of the map is chosen and flipped 2.3. Simulated annealing and the genetic algorithm may also use more complex perturbation techniques.

Moreover, it is possible to assess the robustness of a given map by looking at the map distribution using Markov Chain Monte Carlo. For that, see the mcmc command. It works only in the comparative mapping approach.

These commands described next can take a long time to improve or not the current solution. The system does not provide a prediction of the time cost of this algorithms. Nevertheless, these methods can be interrupted online, without loss of information (see section 2.6.11).

Thomas Schiex 2009-10-27