Title
Memetic algorithm for sorting unsigned permutations by reversals
Date Issued
16 September 2014
Access level
metadata only access
Resource Type
conference paper
Author(s)
Ayala-Rincón M.
University of Brasilia
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Sorting by reversals unsigned permutations is a problem exhaustively studied in the fields of combinatorics of permutations and bioinformatics with crucial applications in the analysis of evolutionary distance between organisms. This problem was shown to be NP-hard, which gave rise to the development of a series of approximation and heuristic algorithms. Among these approaches, evolutionary algorithms were also proposed, from which to the best of our knowledge a parallel version of the first proposed genetic algorithm computes the highest quality results. These solutions were not optimized for the case when the population reaches a degenerate state, that is when individuals of the population remain very similar, and the procedure still continues consuming computational resources, but without improving the individuals. In this paper, a memetic algorithm is proposed for sorting unsigned permutations by reversals, using the local search as a way to improve the fitness function image of the individuals. Also, the entropy of the population is controlled, such that, when a degenerate state is reached the population is restarted. Several experiments were performed using permutations generated from biological data as well as hundreds of randomly generated permutations of different size, from which some ones were chosen and used as benchmark permutations. Experiments have shown that the proposed memetic algorithm uses more adequately the computational resources and gives competitive results in comparison with the parallel genetic algorithm and outperforms the results of the standard genetic algorithm.
Start page
2770
End page
2777
Language
English
OCDE Knowledge area
Ciencias de la computación
Subjects
Scopus EID
2-s2.0-84908583716
ISBN
9781479914883
ISBN of the container
978-147991488-3
Conference
Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
Sources of information:
Directorio de Producción Científica
Scopus