Premium
A hybrid genetic algorithm for the phylogeny problem using path‐relinking as a progressive crossover strategy
Author(s) -
Ribeiro Celso C.,
Vianna Dalessandro S.
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00699.x
Subject(s) - crossover , phylogenetic tree , benchmark (surveying) , tree rearrangement , heuristics , tree (set theory) , mathematics , genetic algorithm , path (computing) , algorithm , set (abstract data type) , heuristic , context (archaeology) , mathematical optimization , grasp , evolutionary algorithm , computer science , artificial intelligence , combinatorics , biology , gene , programming language , geography , paleontology , biochemistry , chemistry , geodesy
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.