Great Deluge

joe at removethispart.gs.washington.edu joe at removethispart.gs.washington.edu
Tue Nov 11 13:11:44 EST 2003


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
---



More information about the Mol-evol mailing list