A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy

A phylogenetic tree relates taxonomic units using their similarities over a set of characteristics. Given a set of taxonomic units and their characteristics, the phylogeny problem under the parsimony criterion consists in finding a phylogenetic tree with a minimum number of evolutionary steps. We developed a hybrid genetic algorithm for the problem of building a phylogenetic tree minimizing parsimony. The algorithm combines local search with a crossover strategy based on path-relinking, an intensification technique originally used in the context of other metaheuristics such as scatter search and GRASP. Computational experiments on benchmark and randomly generated instances show that the proposed algorithm is very robust and outperforms other heuristics in terms of solution quality and running times.