Crossover operator for permutations

Question

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?

Saraisaraiya

Cause I want to solve this problem with genetics. – Saraisaraiya

Every genetic algorithm has a fitness test, where you define a set of rules to decide which children will survive and which will die. That was what I wanted to know. – Expiation

Wow, didn't know that : ] I chose parents that they're "the best" - I just wanted to have efficient way to compute children with no repeated elements right now. – Saraisaraiya

How would that be different from running a simple permutation on either Parent1, or Parent2? – Expiation

Answer 1

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.

Amplitude

Seems like the TSP example link is dead. – Disharoon

Answer 2

The choice of crossover depends on whether the order or the absolute position of the integers is important to the fitness. In HeuristicLab (C#) we have implemented several popular ones found in the literature which include: OrderCrossover (2 variants), OrderBasedCrossover, PartiallyMatchedCrossover, CyclicCrossover (2 variants), EdgeRecombinationCrossover (ERX), MaximalPreservativeCrossover, PositionBasedCrossover and UniformLikeCrossover. Their implementation can be found together with reference to a scientific source in the HeuristicLab.Encodings.PermutationEncoding plugin. The ERX makes sense only for the TSP or TSP-like problems. The CX is position-based, the PMX is partly position partly order based, but more towards position. The OX is solely order based.

Beware that our implementations assume a continous numbered permutation with integers from 0 to N-1. You have to map them to this range first.

Disaffection

Answer 3

According to my research and implementations of genetic operators. Many types of crossover operators exist for the order coding (i.e. repetition of genes not allowed, like in TSP). In general, I like to think that there are two main families:

The ERX-family

A list of neighborhood is used to store the neighbors of each node in both parents. Then, The child is generated using only the list. ERX is known to be more respectful and alleles transmitting, which basically means that the links between genes are not likely to be broken.

Examples of ERX-like operators include: Edge Recombination (ERX), Edge-2, Edge-3, Edge-4, and Generalized Partition Crossover (GPX).

OX-like crossovers

Two crossover points are chosen. Then, the genes between the points are swapped between the two parents. Since repetitions are not allowed, each crossover proposes a technique to avoid/eliminate repetitions. These crossover operators are more disruptive than ERX.

Example of OX-like crossovers: Order crossover (OX), Maximal Preservative Crossover (MPX), and Partial-Mapped Crossover (PMX).

The first family (ERX) performs better in plain genetic algorithms. While the second family is more suited in a hybrid genetic algorithm or memetic algorithm (use of local search). This paper explains it in details.

Eckert

"Maximal Preservative Crossover (CX) ", did u mean MPX instead of CX, as far as i get into topic CX stands for Cycle Crossover – Frazee

Answer 4

In Traveling Salesrep Problem (TSP), you want the order to visit a list of cities, and you want to visit each city exactly once. If you encode the cities directly in the genome, then a naive crossover or mutation will often generate an invalid itinerary.

I once came up with a novel approach to solving this problem: Instead of encoding the solution directly in the genome, I instead encoded a transformation that would re-order a canonical list of values.

Given the genome [1, 2, 4, 3, 2, 4, 1, 3], you'd start with the list of cities in some arbitrary order, say alphabetical:

1. Atlanta
2. Boston
3. Chicago
4. Denver

You'd then you'd take each pair of values from the genome and swap the cities in those positions. So, for the genome above, you'd swap those in 1 and 2, and then those in 4 and 3, and then those in 2 and 4, and finally those in 1 and 3. You'd end up with:

1. Denver
2. Chicago
3. Boston
4. Atlanta

With this technique, you can use any type of crossover or mutation operation and still always get a valid tour. If the genome is long enough, then entire solution space can be explored.

I've used this for TSP and other optimization problems with lots of success.

Mawkin