help to write genetic algorithm cross over code

Hello,

I have following parameters---

NP= no. of parent=2

Acually, in each parent, i am joining two (means dr=2) 5*5 matrixs row wise . As N=5, thats why 5*5 matrix is produced.

no. of rows in Parent= N=5

total no. of columns in parent= N*dr= 5*2

So, for cross over , i am exchanging 5*5 matrix between parents.

For example,

i have-----

Parent 1

    *0     2     2     3     2     0     0     2     0     3
     0     0     2     4     3     1     0     1     5     1
     0     0     0     0     0     0     0     0     2     3
     0     4     2     0     3     0     0     0     0     0
     0     3     3     2     0     4     0     2     1     0*

Parent 2

     0     4     2     1     2     0     0     3     1     2
     0     0     2     1     4     1     0     2     3     2
     0     0     0     0     0     3     0     0     0     3
     0     1     2     0     2     0     0     0     0     0
     0     2     3     3     0     2     0     1     4     0

After crossover,

C(1)

     0     2     2     3     2     0   0    3   1    2 
     0     0     2     4     3     1   0    2   3    2
     0     0     0     0     0     3   0    0   0    3
     0     4     2     0     3     0   0    0   0    0 
     0     3     3     2     0     2   0    1   4    0

C (2)

     0     4     2     1     2   0    0    2    0   3  
     0     0     2     1     4   1    0    1    5   1  
     0     0     0     0     0   0    0    0    2   3  
     0     1     2     0     2   0    0    0    0   0  
     0     2     3     3     0   4    0    2    1   0

How to do it one point crossover.

Thank you

Answer 1

[Geoff Hayes]

Reshdev - in your above example, you have chosen a cross-over point at row 1, column 6. You then switched the "halves" of the two matrices (parents). If P1 and P2 are the parents, and C1 and C2 are the children, then the above (as code) would be

 % do a straight copy of the parent "genes" to the children
 C1 = P1;
 C2 = P2;

 % now copy over the data from the other parent that is "crossed over" with the first
 % parent
 xOverPtRowIdx = 1;
 xOverPtColIdx = 6;

 C1(xOverPtRowIdx:end, xOverPtColIdx:end) = P2(xOverPtRowIdx:end, xOverPtColIdx:end);
 C2(xOverPtRowIdx:end, xOverPtColIdx:end) = P1(xOverPtRowIdx:end, xOverPtColIdx:end);

Note how in the above, we replace the two "blocks" in the children with (gene) data from the other parent.

So that part is relatively easy. The question now becomes, how do you choose your cross-over point? Do you wish to allow the exchange of blocks of data given (almost) any row and column pair within the parent matrices? For example, suppose we have two smaller matrices as follows

 P1 = [A B C D E      P2 = [P Q R S T
       F G H I J            U V W $ Y
       K L M N O]           Z # @ 4 2]

I'm just using random symbols for illustration only. Suppose now you pick a cross-over point at the second row and third column. This would mean that the data marked with X would be transferred from parent 1 to child 2, and parent 2 to child 1

P1 = [A B C D E      P2 = [P Q R S T
      F G X X X            U V X X X
      K L X X X]           Z # X X X]

If the above is desirable, then what you can make use of the fact that a pair of row and column indices can be obtained from a linear index using ind2sub . Basically every element in the 5x10 matrix can be represented by either a pair of row and column indices, or by a single linear index. The linear indices range from 1, 2, ..., N, where N is the number of elements in the matrix (in your case, 50).

We can do the following. Randomly choose a linear index in the interval (1,N]. Note how we don't allow 1 to be chosen since that means that there is no change in the two children (all information will be swapped from one child to the other, and there will be no new "genetic" diversity in the population as the children will be identical to the parents).

 [m,n]   = size(P1);
 xOverPt = randi([2 m*n]);

We use the size of P1 (number of rows and columns) to determine the number of elements in the matrices, and generate a random integer between 2 and 50.

Now we convert this linear index to a pair of row and column indices

 [xOverPtRowIdx, xOverPtColIdx] = ind2sub([m n],xOverPt);

And swap the data between the two children using the above swapping code.

Presumably you will do the for each pair of parents, creating two children at a time.

[reshdev]

Actually, each 5*5 matrix in parents represents one gene. So, when we will try to do cross over from between two parents, an array of 5*5 is being exchanged.

Note- each gene(5*5 matrix) is being generated randomly in intialization phase and follow certain constraints.

[reshdev]

right now i am looking to do single point crossover only for simplicity for any number of genes(each 5*5) in parent

[Geoff Hayes]

So how do you plan on doing crossover to ensure that your constraints are still met? Are you just going to swap the two halves?

[reshdev]

if i do it in following way , then i do not need to worry about disturbing constraints because i will not disturbing 'internal matrix elements of genes'.

I am just relocating entire gene(i.e. full gene matrix) from one place to another.

Just to make more clear,

Genes A,B,C,D are 5*5 matrix's each.

Praent 1 = AB

Parent 2= CD

after crossover-

Child 1 =AD

child 2 =CB

[Geoff Hayes]

I guess that you will need a very large population in order to get a lot of genetic diversity. If you ignore everything I said after Note how in the above, we replace the two "blocks" in the children with (gene) data from the other parent., then you should be all set to finish the function.

[reshdev]

Thank you.I got your point.

I have a another small question that is there is any rule that if i have N population size. i should select at least 'this many' parents to go for crossover.

Second question is ---Suppose i have N=100, then if select 10 parents using roulette wheel, how i should decide, which one should do crossover which one?

[Geoff Hayes]

For you first question, you can select as many parents as you want children - so two parents will produce two children. Or you could do something like, two parents produce two children but you only keep one, that which has the better fitness. It is up to you how you want to implement your population replacement scheme.

As for your second question, you can start with one parent and then randomly choose another. Or just take the neighbouring parent (at the next index). You probably want to implement your scheme in such a way that you try not to choose two parents that are identical. Remember, the roulette wheel selection method will allow one member of the population to be chosen multiple times.

You may wish to update this selection so that neighbouring parents "mate" with each other. So if there are 10 parents selected, with labels P1,P2,...,P10, then P1 and P2 produce children C1 and C2, P3 and P4 produce C3 and C4, etc. After the roulette wheel has selected P1, then P2 is chosen as any member of the population that is not P1. This way P1 and P2 are never identical. Then choose P3 (which can be P1 or P2, it doesn't matter), and P4 is chosen as any member of the population that is not P3. Etc. That way all parent pairings are composed of two different parents. The same parent might be in multiple pairings, but P1 never "mates" with itself.

Answer 2

[ANJANA MISHRA]

how to do two point crossover between two different row of a same matrix