# What crossover operator should I use for arranging students in classrooms?

I am building a genetic algorithm to solve a "classroom map" problem. The goal is to place correctly students depending on several factors (shortsighted students, turbulent students...).
Here, the genomes is the classroom layout, each classroom has a fixed blackboard and tables positions, what varies is the position of the students.
Now, if I want to cross two classrooms genomes, I can't simply mix both together, otherwise, say that on genome A student "Bob" is on table #3, and that on genome B the same student "Bob" is on table #15, and that the "child genome" gets table #3 from genome A and table #15 from genome B, then, "Bob" would be on two tables at the same time... no really great.

How can I solve this issue ?

Thank you.

What you're (probably) doing:

0 = Bob
1 = Mary
2 = John
3 = Susan

parents
[2 | 1 | 0 | 3] => John takes first seat, ..., Susan takes fourth seat.
[3 | 2 | 1 | 0] => Susan takes first seat, ..., Bob takes fourth seat.
^
one point crossover
[3 | 2 | 0 | 3]   Where is Susan? (and Mary?)
[2 | 1 | 1 | 0]


What you can do:

• allow the generation of an invalid chromosome / individual assigning a very low fitness value. Such individual will be penalized (ignored) during evolution.

This is very time consuming and not effective

• repair an invalid chromosome. It's time consuming but it could work

E.g. with Partially Matched Crossover:

(from Genetic Algorithm)

PMX builds an offspring by choosing a subsequence from one parent preserving as many positions as possible from the other parent.

1. A subsequence is delimited by two cut points. After this, the segments between the cut points are swapped (the positions in yellow). We have the map: 1↔8, 9↔5, 8↔7 and 6↔3.
2. Fill the positions for which there is no conflict. In the example shown, the positions 4 and 2 in both chromosomes (the positions in blue).
3. Use the map to fill the remaining positions (the positions in green). Note that using the mapping 1↔8 in the o1 vector a conflict occurs again so one must apply the mapping 8↔7 to obtain a number not repeated.

Other operators are listed in Crossover for ordered chromosomes but pay attention to the fact that some operators tend to preserve the relative positions more than the absolute positions.

• change point of view / representation.

E.g. [2 | 1 | 0 | 3] or [3 | 2 | 1 | 0] are permutations. Standard GA crossover operators produce offspring which aren't permutations. A clever representation of permutations could avoid the problem.

You can represent a permutation as its inversion sequence: for each element i, store in a[i] how many elements larger than i are to the left of i in the permutation.

The only constraint on a[i] is that it cannot be larger than N - i (N is the number of genes).

Now standard crossover of two valid inversion sequences always produces two valid inversion sequences: no need for special handling of repeating elements.

This idea is described in Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation (Göktürk Üçoluk).

• Thank you so much for your answer, unfortunately I don't understand how the PMX works at all :( Commented Oct 11, 2016 at 11:31
• @TrevörAnneDenise I've added an example. Commented Oct 11, 2016 at 12:23

Simple. Don't do the Crossover;it's not necessary. Just use mutation.