Sorting unsigned permutations by reversals using multi-objective evolutionary algorithms with variable size individuals

Abstract

Sorting by reversals is a simplified version of the genome rearrangement problem that seeks to discover the evolutionary relationship between different genomes, and is one of the many challenging problems in Bioinformatics. Solving the problem optimally has been proved to be NP-Hard and so a selection of approximation algorithms have been developed. In this paper a new mapping order is introduced to solve the problem of sorting unsigned permutations using a specialized multi-objective genetic algorithm. Our modified genetic algorithm uses a population with variable length individuals to maintain a worst time running time complexity of 0(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n), where n is the problem size. The results show that this approach is more effective than the 3/2 heuristic method and previous genetic algorithm approaches.