how do i avoid repeated value in crossover?

please help me in order to make a one point crossover

P1 =

7     5     1     3     6    11    10     8    12     9     4     2

P2 =

3     5     4     6     2     7     9    11     8     1    10    12

than i do a coding like this

 P1 = RS %RS is an result that i get from parent selection before
 P2 = RS
CrossoverIndex = 6;  
c1 = [P1(1:CrossoverIndex) P2(CrossoverIndex+1:end)]
c2 = [P2(1:CrossoverIndex) P1(CrossoverIndex+1:end)]

then the result i get from the coding is like this

c1 =

7     5     1     3     6    11     9    11     8     1    10    12

c2 =

3     5     4     6     2     7    10     8    12     9     4     2

the result that i get from the coding is wrong because there are same value repeated in c1 number 11, 1 is reapeted and number 2, 4 is missing and also c2 which is 4, 2 is reapeated and mising 11, 1..

what can i do to make the number is not repeated ?

[madhan ravi]

RS?

[sharifah shuthairah syed abdullah]

RS =
  Columns 1 through 10
           1       30016           7           5           4          11          12           3           1           2
           2       39570           9          10           7           1          12           8           4          11
           3       41260           1           9           3          11           5           2           8           4
           4       41482          12          10           9           5          11           8           7           6
           5       41582          11           3           9          10           5           7           8           4
           6       42118           8           9           5           7           6          12           1          10
           7       43574          10           3           8           5           4          11          12           6
           8       49386          12           6           3           5           1           8           2          10
           9       55566           3          12           8           6          11           2          10           5
          10       62880          11           3          10           8           7           6           1           9
  Columns 11 through 14
           9           8           6          10
           6           3           2           5
           7           6          12          10
           3           2           4           1
           6           2           1          12
           4           2           3          11
           1           9           2           7
          11           4           9           7
           9           4           1           7
          12           5           4           2

i take P1 and P2 from RS

Answer 1

[Walter Roberson]

There is no valid 1 point cross-over between P1 and P2 according to those rules.

You can get a valid 1 point cross-over only if you can identify some point, N > 1, such that P1(1:N-1) is a permutation of P2(1:N-1) and P1(N:end) is a permutation of P2(N:end). You can show that cannot happen with those P1 and P2.

[sharifah shuthairah syed abdullah]

i dont really get what u mean..

is N = crossover point?

P1(1:N-1)=  P2(N:end); 
P2(1:N-1)= P1(N:end);

is this what you mean?

can i avoid the result to get the same value twice ?

[Walter Roberson]

If N were the cross-over point, then

temp = P1(N:end);
P1(N:end) = P2(N:end);
P2(N:end) = temp;

However, this would require that N was a valid cross-over point. In order to prevent the same value from occuring twice, you would have to be starting with the situation where P1(1:N-1) is a permutation of P2(1:N-1) and P1(N:end) is a permutation of P2(N:end) . For example if you happened to have

P1 = [7     5     1     3     6    11    10     8    12     9     4     2]
P2 = [3     6     7    11     8     1    12    10     5     4     2     9]

then it would be valid to cross-over at N = 10:

P1 = [7     5     1     3     6    11    10     8    12  ][   9     4     2]
P2 = [3     6     7    11     8     1    12    10     5  ][   4     2     9]

=>

P1 = [7     5     1     3     6    11    10     8    12  ][   4     2     9]
P2 = [3     6     7    11     8     1    12    10     5  ][   9     4     2]

Notice how the part after the break has only the same values in both arrays, 2, 4, 9.

Examine your original data,

     7     5     1     3     6    11    10     8    12     9     4     2
     3     5     4     6     2     7     9    11     8     1    10    12

In order to figure out where a break could be, start from the end. The first one ends in 2, so the break cannot be anywhere before where 2 appears in the bottom row:

     7     5     1     3     6    11    10     8    12     9     4  |?  2
     to include the 2 on the bottom implies
     3     5     4     6  |? 2     7     9    11     8     1    10     12

and since the split has to be at the same place in top and bottom, implies

     7     5     1     3  |? 6    11    10     8    12     9     4    2
     3     5     4     6  |? 2     7     9    11     8     1    10   12

Follow along on the bottom row. 12 is there on the bottom, and 12 is after the split on the top, so we are okay so far. 10 occurs on the bottom, and 10 is after the split on the top, so we are okay so far. 1 appears on the bottom, but 1 is before the split on the top, so we have to move the split on the top, and adjust the bottom to the same position

     7     5  |? 1     3   6    11    10     8    12     9     4    2
     3     5  |? 4     6   2     7     9    11     8     1    10   12

Continuing along the bottom, 8 is on the bottom, and 8 is after the split on the top so we can continue. 11 is on the bottom, and 11 is after the split on the top, so we can continue. 9 is on the bottom, and 9 is after the split on the top, so we can continue. 7 is on the bottom, but 7 is before the split on the top, so we have to move the split on the top and adjust the position of the split on the top to match:

|? 7     5     1     3   6    11    10     8    12     9     4    2
|? 3     5     4     6   2     7     9    11     8     1    10   12

Proceeding, 2 is on the bottom, and 2 is after the split on the top, so we can continue. 6 is on the bottom, and 6 is after the split on the top, so we can continue. 4 is on the bottom, and 4 is after the split on the top, so we can continue. 5 is on the bottom, and 5 is after the split on the top, so we can continue. 3 is on the bottom, and 3 is after the split on the top, so we can continue. We have now reached the split mark and everything on the bottom that is after the split occurs on the top somewhere after the split, so we have found a valid split point and we can finalize to

[][ 7     5     1     3   6    11    10     8    12     9     4    2]
[][ 3     5     4     6   2     7     9    11     8     1    10   12]

But this is just the original P1 and P2! The only valid crossover is the entire array!

With those P1 and P2, there is nowhere in the middle that you can split that will not result in duplicate values.

[sharifah shuthairah syed abdullah]

thank you for the details..the explanation is very helpful..

i used randperms to get my result so everytime i run i will get different result..

and the coding you gave is to fine C1 and C2 or the crossover point?

temp = P1(N:end);
P1(N:end) = P2(N:end);
P2(N:end) = temp;

if i used 2 point crossover do u think it would be ok?

[Walter Roberson]

The code

temp = P1(N:end);
P1(N:end) = P2(N:end);
P2(N:end) = temp;

does not find the crossover point: it just correctly exchanges the ends after you have found the point.

When you use randperm to construct your two arrays, much of the time there will not be any valid cross-over.

[sharifah shuthairah syed abdullah]

thank you so much... i change the point crossover to cycle crossover and it work.. thank you so much for your explaination :)

[Ibrahim Fares]

how you change the crossover to cycle crossover?