Parallel Genetic Algorithms with Sharing of Individuals for Sorting Unsigned Genomes by Reversals

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.