Title
Parallel Multi-Island Genetic Algotirth for Sorting Unsigned Genomes by Reversals
Date Issued
28 September 2018
Access level
metadata only access
Resource Type
conference paper
Author(s)
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Sorting unsigned permutations by reversals is an NP-hard optimization problem with applications in computational molecular biology. Several approximation and metaheuristic algorithms were proposed, among them, in a previous work, a competitive genetic algorithm and its parallel version using island models were proposed. In this paper, focusing on improving accuracy, new island models are proposed by diversifying the distribution of genetic material between islands through static and dynamic communication topologies. In static topologies, communication between islands is predefined and maintained during the computation, while in dynamic topologies the communication is continuously modified. The proposed island models use parallelism in a global and a local level, in which respectively, the exchange of individuals between islands and the fitness computation occurs. Results from the experiments performed with randomly generated synthetic permutations show that parallel island models using both dynamic and static communication topologies outperform parallel approaches found in the literature in terms of run-time as well as accuracy.
Language
English
OCDE Knowledge area
Bioinformática
Subjects
Scopus EID
2-s2.0-85056265955
ISBN of the container
978-150906017-7
Conference
2018 IEEE Congress on Evolutionary Computation, CEC 2018 - Proceedings
Sources of information:
Directorio de Producción Científica
Scopus