1

I'm creating a genetic algorithm and I just encounter a problem, let's take an example. I have a list of numbers : [2, 3, 6, 8, 9, 1, 4] which represent my datas. The best solution to my problem depends on the order of the numbers in the list. So I have two solution : S1 [2, 3, 9, 8, 1, 6, 4] and S2 [1, 6, 4, 3, 9, 2, 8]

If I do a basic cross-over with S1 and S2 I may obtain a solution like this : child [2, 3, 9, 8, 9, 2, 8] and we can see that the solution is bad because I duplicate datas.

The question is how may I realized an evolution (so cross-over) without duplicate thoses datas ?

thanks.

taspai
  • 71
  • 6
  • 3
    Possible duplicate of [Crossover operator for permutations](http://stackoverflow.com/questions/14420411/crossover-operator-for-permutations) – sve Feb 16 '16 at 15:13
  • @svs yes it's the same idea, thanks and sorry, I didn't find this post when I was searching – taspai Feb 16 '16 at 15:25

2 Answers2

2

You will need a crossover operator like Ordered Crossover (OX1) that can perform crossover without duplicate thoses datas:

OX1: A randomly selected portion of one parent is mapped to a portion of the other parent. From the replaced portion on, the rest is filled up by the remaining genes, where already present genes are omitted and the order is preserved.

You should take care with mutation too, because it can change the genes order, in this case you can use a mutation operator like Reverse Sequence Mutation (RSM).

In the reverse sequence mutation operator, we take a sequence S limited by two positions i and j randomly chosen, such that i<j. The gene order in this sequence will be reversed by the same way as what has been covered in the previous operation.

giacomelli
  • 7,287
  • 2
  • 27
  • 31
0

You have Permutation Encoding, look at this explanation: http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php

In general you take the elements of the first parent in order in which they are met in the first parent and you take the rest of the elements in the order in which they are met in the second parent.

Todor Balabanov
  • 376
  • 3
  • 6
  • 17