In article <bopjnd$ci$1 at mercury.hgmp.mrc.ac.uk>,
Chris Creevey <chris.creevey at may.ie> wrote:
> I was wondering if anyone could describe the great deluge heuristic
>search of tree space please?
This is not a reference to the biblical Flood, but to a search method
introduced by Gunter Dueck:
Dueck, G. 1991. New optimization heuristics: The great deluge algorithm and
record-to-record travel. Technical report 89.06.011, IBM Heidelberg Scientific
Centre, IBM, Heidelberg, Germany.
Dueck, G. 1993. New Optimization Heuristics: the Great-Deluge Algorithm and
the Record-to-Record Travel. Journal of Computational Physics 104: 86-92.
The general idea is that you are searching to maximize something on a space
(in this case tree space -- if you are instead miminizing a quantity X, just
consider it as maximizing its negative, -X). You wander randomly on the
space, but there is a "water level" below which you don't go. If this is W,
you accept any tree that has X > W. As time goes on, W rises slowly.
Finally you are forced up onto a peak (and then, presumably, the rain stops,
or you drown. As far as I know there is no step analogous to sending out
a dove to search for the best location ... )
David Penny has argued that this was an effective method, and Mike Charleston
mentions it in a paper:
Charleston, M. A. 2001. Hitch-Hiking: A Parallel Heuristic Search Strategy,
Applied to the Phylogeny Problem. Journal of Computational Biology
8: 79-91.
and in a conference talk available on the web:
http://taxonomy.zoology.gla.ac.uk/~mac/hitchhiking/hh.html
--
Joe Felsenstein joe at removethispart.gs.washington.edu
Department of Genome Sciences, University of Washington,
Box 357730, Seattle, WA 98195-7730 USA
---
