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

AUTOR(ES)

Vianna, Dalessandro Soares, Vianna, Marcilene de Fátima Dianin

FONTE

Prod.

DATA DE PUBLICAÇÃO

23/08/2013

RESUMO

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.

Documentos Relacionados

• SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM
• Aplicaçaõ das técnicas Path-relinking e Vocabulary buiding na melhoria de performance do algoritmo memético para o problema do caixeiro viajante assimétrico
• HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM
• The metapopulation genetic algorithm: An efficient solution for the problem of large phylogeny estimation
• A GRASP ALGORITHM FOR THE CONTAINER LOADING PROBLEM WITH MULTI-DROP CONSTRAINTS