Hybrid GRASP heuristics for the phylogeny problem combining path-relinking and genetic algorithm as an intensification strategy

A phylogeny is a tree that relates taxonomic units based on their similarity over a set of characteristics. The phylogeny problem under the parsimony criterion consists in finding a phylogeny with a minimum number of evolutionary steps. We propose hybrid heuristic methods - based on GRASP, path-reli...

Full description

Saved in:
Bibliographic Details
Published in:Produção : uma publicação da Associação Brasileira de Engenharia de Produção 2014-09, Vol.24 (3), p.664-674
Main Authors: Vianna, Dalessandro Soares, Vianna, Marcilene de Fátima Dianin
Format: Article
Language:English
Subjects:
ENGINEERING, MANUFACTURING
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A phylogeny is a tree that relates taxonomic units based on their similarity over a set of characteristics. The phylogeny problem under the parsimony criterion consists in finding a phylogeny with a minimum number of evolutionary steps. We propose hybrid heuristic methods - based on GRASP, path-relinking and genetic algorithm methodologies - to build a phylogeny while minimizing parsimony. Computational experiments using benchmark conditions are reported, and the results obtained by the proposed hybrid heuristics are compared with the solutions obtained by a traditional GRASP (without hybridization) heuristic and with previously reported solutions in the literature. The experimental results illustrate that the proposed heuristics are efficient in terms of solution quality and time-to-target-value.
ISSN:0103-6513
1980-5411
1980-5411
DOI:10.1590/S0103-65132013005000050