Taboo search

The greedy command uses a taboo search technique. Starting from an initial map, all the possible maps that can be obtained from the initial map by flipping a subsection of the map are built and their maximum loglikelihood computed. The best map among all these maps is chosen as the new map unless this move is ``taboo'' (in CARTHAGENE a move is taboo is it has been used ``recently'' where the definition of recently varies stochastically during search). Actually, if the move is taboo and if the best map is better than the best known map, this best taboo map becomes the new map despite its taboo property. This process is repeated a number of times (precomputed by CARTHAGENE and equal to twice the number of markers) but extra iterations can be specified.

The whole process can be repeated a given number of times, starting each time from a different starting point. As the search proceeds, the user is informed of the status: if a new better solution is found, its loglikelihood is reported. If no better solution is found a ``-'' is printed. If the search detets it is stuck, always moving in the same region, a ``*'' is printed and the search automatically restarted from a new starting point. If many such ``*'' are printed, this is usually a good indication that the best solution has been found and is, repeatedly, found again and again.

The parameters of the search are given by the number of time the serach process must be run, how many extra iterations are allowed and the bounds of variation for the definition of what a taboo move is. These bounds are defined as percentages and should therefore be between $1$ and $99$. Typical values are $5$ and $30$.

Thomas Schiex 2009-10-27