Title
Parallel genetic algorithms with sharing of individuals for sorting unsigned genomes by reversals
Date Issued
05 July 2017
Access level
metadata only access
Resource Type
conference paper
Author(s)
Da Silveira L.
Ayala-Rincón M.
Universidade de Brasília
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Rearrangement by reversals is a suitable global operation when treating genomes with a single chromosome. Sorting unsigned genomes by reversals is an NP-hard optimization problem. Several approximation algorithms were proposed, among them, in previous work, a competitive genetic algorithm and its standard parallel version, that provides a substantial speedup, were introduced. In this paper, two approaches using island models to parallelize such algorithm are presented. The first approach uses the unidirectional ring communication topology to exchange individuals between neighboring islands and, the second uses a complete graph scheme for the distribution of individuals among islands. Both approaches were proposed with the objective of improving precision (that is, for reducing the number of reversals) and decreasing the runtime regarding the sequential GA. Experiments were performed with randomly generated synthetic genomes and the results show that the parallel approach using the ring communication topology outperforms the previously proposed GA and its parallel version in terms of accuracy, providing solutions with less reversals and, that the parallel approach using the complete graph topology does not provide significant improvements. Both the new parallel GA approaches get competitive speedups regarding the speedup achieved by the standard parallel version of the genetic algorithm.
Start page
741
End page
748
Language
English
OCDE Knowledge area
Bioinformática
Scopus EID
2-s2.0-85027872091
ISBN
9781509046010
ISBN of the container
978-150904601-0
Conference
2017 IEEE Congress on Evolutionary Computation, CEC 2017 - Proceedings
Sponsor(s)
ACKNOWLEDGMENT Research funded by grant 9974.56.27437.0604/2016 from the Brazilian District-Federal Research Foundation FAP-DF. The second and third authors are partly funded by a CAPES Ph.D. scholarship and a CNPq research productivity grant, respectively.
Sources of information: Directorio de Producción Científica Scopus