Hydra

Introduction

HYDRA for (HYbrid Distance Recombination Algorithm) is a phylogenetic reconstruction software based on the maximum parsimony criterion under Fitch's parsimony. The core of Hydra relies on a memetic algorithm, i.e. a combination of a Genetic Algorithm (GA) and a Local Search (LS) algorithm.

The main features of Hydra are the introduction of a specific crossover operator for trees called DiBIP [1] used with the GA and the definition of a new neighborhood called progressive neighborhood [2] used for LS. They both rely on the notion of topological distance.

HYDRA is provided with a set of benchmarks from C. C. Ribeiro. The current version 1.1 is more efficient than version 1.0 when compiled on an Intel or AMD processor implementing SSE2 instructions.

Download

Hydra is freely available for non commercial purpose.

Results

best results from random instances of C. C. Ribeiro
Problem Hydra AG+PR TNT
tst01 545 549 547
tst02135413581361
tst03833838840
tst04588592595
tst05789790789
tst06596603601
tst07127012761272
tst08853863866
tst09114511501146
tst10721725721
tst11 543 544 547
tst12 1211 1229 1228
tst13 1515 1526 1522
tst14 1160 1174 1163
tst15 752 765 760
tst16 529 545 540
tst17 2453 2468 2468
tst18 1522 1542 1539
tst19 1013 1028 1025
tst20 661 676 675

Bibliography