Hitch-hiking: A parallel heuristic search strategy, applied to the phylogeny problem

The article introduces a parallel heuristic search strategy ("Hitch-hiking") which can be used in conjunction with other random-walk heuristic search strategies, It is applied to an artificial phylogeny problem, in which character sequences are evolved using pseudo-random numbers from a hypothetical ancestral sequence. The objective function to be minimized is the minimum number of character-state changes required on a binary tree that could account for the sequences observed at the tips (leaves) of the tree-the Maximum Parsimony criterion. The Hitch-hiking strategy is shown to be useful in that it is robust and that on average the solutions found using the strategy are better than those found without. Also the strategy can dynamically provide information on the characteristics of the landscape of the problem, I argue that Hitch-hiking as a scheme for parallelization of existing heuristic search strategies is of potentially very general use, in many areas of combinatorial optimization.