Optimization Online


A genetic algorithm for the phylogeny problem using an optimized crossover strategy based on path-relinking

Celso Ribeiro (celso***at***inf.puc-rio.br)
Dalessandro Vianna (dalessandrosoares***at***yahoo.com.br)

Abstract: A phylogenetic tree relates taxonomic units, based on their similarity over a set of characters. We propose a new genetic algorithm for the problem of building a phylogenetic tree under the parsimony criterion. This genetic algorithm makes use of an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originaly proposed and applied in the context of implementations of other metaheuristics such as tabu search, scatter search, and GRASP. Computational results are reported for benchmark instances from the literature and for randomly generated test problems, illustrating the effectiveness of this genetic algorithm heuristic with respect to other algorithms.

Keywords: Genetic algorithms, phylogeny, pah relinking

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, submitted for publication, 2003.

Download: [Postscript]

Entry Submitted: 10/11/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/11/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