Optimization Online


A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

Celso Ribeiro (celso***at***inf.puc-rio.br)
Dalessandro Vianna (dalessandrosoares***at***yahoo.com.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.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society