Scatter search with path relinking for phylogenetic inference

We propose the use of scatter search with path relinking for the inference of phylogenetic trees. Solutions are here represented as trees whose leaves span the set of species under study. These trees are evaluated using a minimum weight criterion under the ultrametric model. The main features of this approach are the utilization of a crossover-based schema for diversification generation, the use of path relinking for solution combination, and the utilization of an improvement method based on internal rotations of subtrees. The resulting algorithm is compared to other approaches such as evolutionary and memetic algorithms, using real data as benchmark. Scatter search provides better results for these instances. (c) 2004 Elsevier B.V. All rights reserved.