A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure
Celso Ribeiro (celsoinf.puc-rio.br)
Abstract: A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A GRASP heuristic based on this neighborhood structure and using VND for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time-to-target-value.
Keywords: GRASP, VND, phylogeny, metaheuristics
Category 1: Applications -- Science and Engineering (Biomedical Applications )
Category 2: Combinatorial Optimization (Meta Heuristics )
Citation: Research report, submitted for publication, 2003.
Entry Submitted: 10/12/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|