An Improved Genetic Algorithm for Problem of Genome Rearrangement

摘要

In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsigned permutation of length n, pi =(pi_1, ..., pi_n), into a set S(pi) containing 2n signed permutations, so that the reversal distance of pi is equal to the reversal distance of the optimal signed permutation in S(pi). Then analyze the structural features of S(pi) by creating a directedgraph and induce a new computing model of this question. Finally, an improved genetic algorithm for solving the new model is proposed. Experimental results show that the proposed model and algorithm is very efficient in practice.