3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

  • use ad-hoc operators.

    E.g. with Partially Matched Crossover:

    PMX 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).

$\endgroup$
  • $\begingroup$ Thank you so much for your answer, unfortunately I don't understand how the PMX works at all :( $\endgroup$ – Trevör Oct 11 '16 at 11:31
  • $\begingroup$ @TrevörAnneDenise I've added an example. $\endgroup$ – manlio Oct 11 '16 at 12:23
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you elaborate your answer? $\endgroup$ – Evil Oct 12 '16 at 14:21
  • $\begingroup$ Some believe that crossover doesn't help with genetic algorithms and probably makes performance worse. If you are using crossover, try removing it and see if the performance changes. $\endgroup$ – Ray Oct 13 '16 at 22:23
  • $\begingroup$ Well, I meant to elaborate the answer not comment, give a proper citation, sources or explicitly state it is based on the experience (or easy to check). Have you seen manlio answer? $\endgroup$ – Evil Oct 13 '16 at 22:31
  • $\begingroup$ I stand by my "comment". Give it a try. $\endgroup$ – Ray Oct 14 '16 at 4:30
  • $\begingroup$ "it's not necessary" - how do you know? Where did you read that? $\endgroup$ – Auberon Oct 16 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.