You should check "Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation" by Gokturk Ucoluk. It gives an overview of the special crossover operators for permutations and proposes a clever representation of permutations that works well with standard crossover (i.e. crossing over two permutations always produces two permutations).
The key insight is to represent the permutation as its inversion sequence, i.e. for each element i
, store in a[i]
how many elements larger than i
are to the left of i
in the permutation. Unlike the direct representation, the only constraint on a[i]
is local, i.e. a[i]
cannot be larger than N - i
. This means that simple crossover of two valid inversion sequences always produces two valid inversion sequences - no need for special handling of repeating elements.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…