Subsections
greedy
Tries to optimize the maximum multipoint loglikelihood using a
dedicated taboo search algorithm.
The greedy command is invoked either as:
- greedy Options
- greedy NbLoop Fuel TabooMin TabooMax Anytime
The greedy command tries to improve the loglikelihood of the
best known order for the current list of active loci (the best map in
the heap) using a dedicated taboo search algorithm. This iterative
algorithm will automatically compute a minimum number of iterations
but additional iterations can be requested by setting the parameter
Fuel to perform additional iterations. The TabooMin TabooMax indicates the minimum and maximum length of the taboo list
which varies stochastically during search. These two parameters are
%ages (between 0 and 100). Finally, the search is repeated NbLoop times if requested. The Anytime ratio controls the tradeoff
between search speed and solution quality. It may vary from 0 to 100.
During the search, the algorithm gives some feedback by printing either:
- the ``-'' character: iterations have been performed
without improving the best known map.
- the ``*'' character: the algorithm has detected it is
exploring orders it has already considered before on several
occasions and decides to start a new search from a new order.
- ``[number]'': a new improved map has been found.
- Options : -u to obtain the synopsys of the normal
use, -h to print a one line description, -H to
print a short help.
- NbLoop: the number of times the taboo search is repeated.
- Fuel: the extra number of iterations requested. By
default, an heuristically determined number of iterations is
computed. If the Fuel is positive, an extra number of iterations are
performed. If the Fuel is negative then the number of iterations
performed will be exactly equal to the absolute value of the
Fuel. For instance, the following command tests all submap reversals: greedy 1 -1 5 30 0.
- TabooMin TabooMax: the minimum and maximum size of
the taboo list in %age (between 0 and 100).
- Anytime: the %age (between 0 and 100) of the neighborhood
explored at each move. A value 100% means all the possible swaps
(i.e. reversing the order of a consecutive sublist of markers) are
examined. A smaller strictly positive value will speed up the
search, improving solution quality faster at the beginning of the
search. But solution quality may be altered at the end. A typical
value may be 25%. A value of 0 corresponds to the original
Carthagene release 0.5 taboo search algorithm.
nothing. All the map explored by the algorithm are candidate for the
heap.
CG> dsload Data/rh.cg
{1 haploid RH 53 118 /homes/thomas/carthagene/test/Data/rh.cg}
CG> group 0.3 3
...
CG> mrkselset [groupget 10]
CG> sem
Map -1 : log10-likelihood = -161.87
-------:
Set : Marker List ...
1 : G5 G18 G17 G14 G16 G13 G12 G6 G7
CG> greedy 1 0 5 25 0
Map -1 : log10-likelihood = -161.87
-------:
Set : Marker List ...
1 : G5 G18 G17 G14 G16 G13 G12 G6 G7
Run number 0
[-153.81]
[-148.65]
[-145.59]
[-145.08]-
[-143.70]
[-141.81]-------------****---********---*-
CG> flips 9 0 0
Single Flip(window size : 9, threshold : 0.00).
Map -1 : log10-likelihood = -141.81
-------:
Set : Marker List ...
1 : G7 G12 G13 G16 G6 G5 G17 G18 G14
2 2 2 3 2 1 3 3 2 log10
1 6 7 0 0 9 1 2 8 -141.81
Thomas Schiex
2009-10-27
