Performance Comparison of Multi-Objective Local Search Strategies to Infer Phylogenetic Trees

The phylogenetic inference aims to estimate the evolutionary relationships among different species, which are commonly represented as a phylogenetic tree. The phylogenetic inference has been modelled in bioinformatics as an optimisation problem, using different criteria to define the optimal tree between the possible topologies. In order to reduce the bias associated to the dependency of a specific criterion, different multi-objective optimisation strategies have been proposed. Recent approaches which involves indicator-based evolutionary and memetic algorithms have included multi-objective local search strategies. However, the performance of the application of local search strategies over these evolutionary approaches has not been studied. In this work, we evaluate the performance of three different multi-objective local search strategies, adapted to the phylogenetic inference problem by using likelihood and parsimony criteria: (1) Pareto local search, (2) Simulated annealing, and (3) Hypervolume-based local search. We tested their use as individual strategy and also as part of two hybrid evolutionary approaches. Experimental results showed that the use of memetic algorithms which involves low probabilities of the local search application have a better performance according to multi-objective quality metrics compared to the other alternatives of application. These results allow proposing new configurations for the most recent multi-objective algorithms, in order to improve the quality of solutions in terms of dominance. © 2018 IEEE.