A phylogenetic tree relates taxonomic units, based on their similarity over a set of characters. We propose a new genetic algorithm for the problem of building a phylogenetic tree under the parsimony criterion. This genetic algorithm makes use of an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originaly proposed and applied in the context of implementations of other metaheuristics such as tabu search, scatter search, and GRASP. Computational results are reported for benchmark instances from the literature and for randomly generated test problems, illustrating the effectiveness of this genetic algorithm heuristic with respect to other algorithms.
Research report, submitted for publication, 2003.