algorithmgenetic-algorithmcrossover

Crossover operator for permutations

i'm trying to solve the problem of crossover in genetic algorithm on my permutations. Let's say I have two permutations of 20 integers. I want to crossover them to get two children. Parents have the same integers inside, but the order is different.

Example: 

Parent1: 
 5 12 60 50 42 21 530 999 112 234 15 152 601 750 442 221 30 969 113 134
Parent2: 
 12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969  134 21

Let it be that way - how can I get children of these two?

Solution

  • What you are looking for is ordered crossover. There is an explanation for the Travelling Salesman Problem here.

    Here is some Java code that implements the partially mapped crossover (PMX) variant.