Map improving methods

As a first trial, we can use the local search algorithms. In this example, we will use the ``simulated annealing'' algorithm embodied in the annealing command. The command takes some parameters to specify how the search takes place (and how much cpu-time it will consume). Here we use 100 moves per level (the larger the better the search and the more expensive it is), an initial temperature of 50 (this is automatically reajusted), a final temperature of 0.1 (the smaller, the better the search and the more expensive too) and a cooling factor of $0.8$ (always strictly less than $1$, the closer to $1$, the better the search and the more expensive too). This a very fast search (use other parameters in practice).

CG> annealing 100 50 0.1 0.8

Map -1 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M237 M076 A03...

50.00? :
40.00? :
32.00? :
25.60? :
20.48? :
16.38? :
13.11? :
10.49? :
8.39? :
6.71? :
5.37? :
4.29? :
3.44? :
2.75? :
2.20? :
1.76? :
1.41? :
1.13? :
0.90? :
0.72? :
0.58? :
0.46? :
0.37? :
0.30? :
0.24? :
0.19? :
0.15? :
0.12? :

When the annealing process improves over the best known solution, a ``+'' is printed. In our case, no better map could be found. Now we would like to see the best maps found (which are stored in the heap), ordered by loglikelihood:

CG> heaprint

Map  0 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L010 L029 L078 T035 D022 L001 A059 A079 M030 M232 T018 M076 M237 M03...

Map  1 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 M030 A079 M232 T018 M237 M076 M03...

Map  2 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 M030 A079 M232 T018 M076 M237 M03...

Map 14 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 A079 M030 M232 T018 M076 M237 M03...

Map  3 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 A079 M030 M232 T018 M237 M076 A03...

Map  4 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 A079 M030 M232 T018 M076 M237 A03...

Map  6 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 T035 L078 D022 L001 A059 A079 M030 M232 T018 M237 M076 M03...

Map  7 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 M030 A079 M232 T018 M237 M076 M03...

Map  8 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 M030 A079 M232 T018 M076 M237 A03...

Map 13 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 M030 A079 M232 T018 M076 M237 M03...

Map  5 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 M030 A079 M232 T018 M237 M076 A03...

Map 11 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M076 M237 M03...

Map 10 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M237 M076 M03...

Map  9 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M076 M237 A03...

Map 12 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M237 M076 A03...

The best map is always the last map. We see that on this data set there are several maps with different orders and a close (or equal) likelihood. This is not surprising if you remember that the mrkdouble command detected several ``double'' markers. Usually, swapping 2 ``double markers'' in a map will not change the loglikelihood.

Another local search algorithm is the ``taboo search'' algorithm embodied in the greedy command. The command takes some parameters to specify how the search takes place (and how much cpu-time it will consume). Here we use 3 loops (the larger the better the search and the more expensive it is), an additional number of iterations of 0, the minimum size of the taboo list is 1% of the neighborhood and the maximum size of the list is 15%.

CG> greedy 3 1 1 15 0

Map -1 : log10-likelihood =   -70.86
-------:
 Set : Marker List ...
   1 : L029 L010 L078 T035 D022 L001 A059 A079 M030 M232 T018 M076 M237 A03...
Run number 0
-*---*-*---*-----*----*-----*---*----*---*---*-*----*----Run number 1
----**-----*----*-----*----------*----*----*------*-----*--Run number 2
----*---*----*---**--*---------*-----------*-----------*---

The algorithm prints a '-' when the map could not be improved, a ``+'' when the best map has improved and a ``*'' to say that the serach process has detected that it is stuck in a region it has already explored. In this case, it starts from another random order. Here, again, no improvement was obtained. Note that the map improving commands can be used as map validating commands using the cgrobustness command (see 2.5.19).