7

I'm currently trying to realize a very simple example of genetic algorithms.

At one point, you have to do a "Cross-Over" (biology) with two numbers (parents) to get a "child".

You can find an explanation of Cross-Over here:

How to "crossover" two strings (1234 & abcd -> 12cd & ab34)

(The second illustration, the easier "one-point" Cross-Over is the one I'm trying to do.)

The chromosomes (parents and child) are numbers but the "Cross-Over" will be a bit operation.

I found a solution for one of the "chromosomes", which is the following :

  • Move the bits X amount to the right (>>> operator )
  • and then move the bits again X positions but this time to the left (<< operator)

So this would keep the end of one of the chromosomes and fill the beginning with 0s.

But I don't really know how to solve the problem of the other chromosome and then also do the Cross-Over.

(Probably a XOR once I kept the beginning / end of the chromosomes and filled the rest with 0s.)

Or should I even approach this problem from another angle?

2
  • Do you always know how large your two inputs are as numbers (e.g., 16-bit integers)?
    – David
    Jul 29, 2012 at 1:01
  • Yes, they are always 16 bit integers. One thing that can be modified is the % of Cross-Over. For example 75% would be keeping the first 4 (25%) bits of parent A and then follow those 4 bits with 12 (75%) bits from parent B.
    – m_vdbeek
    Jul 29, 2012 at 1:05

2 Answers 2

4

If the fraction of the Cross-Over is p (e.g., p = .25), then this should work:

mask1 = ((0xffff >> 16*p) << 16*p)
mask2 = 0xffff ^ mask1
output1 = (input1 & mask1) ^ (input2 & mask2)
output2 = (input1 & mask2) ^ (input2 & mask1)

A couple of notes:

  • This is just pseudocode. You might want some casts in there.
  • This treats p differently than you treat it in your comment above. (Just replace p with 1-p to get to your definition of p.)
2
  • Wow, mind = blown ! It will take me some time to understand this code. ^^ Thank you for your quick answer !
    – m_vdbeek
    Jul 29, 2012 at 1:15
  • Well, shifting the 0xffff pattern right and then left is doing the same thing that you had in your description, so if your p = .5, your mask1 will end up being 0xff after the right shift, and then 0xff00 after the left shift back. XORing this with 0xffff gets you all the bits that aren't turned on in mask2.
    – David
    Jul 29, 2012 at 1:18
1

A naive approach would be to use 4 local variables:

int chromatid1Start;
int chromatid1End;
int chromatid2Start;
int chromatid2End;

Then, assign the incoming chromatid1 to the first two variables and chromatid2 to the last two variables.

chromatid1Start = chromatid1;
chromatid1End = chromatid1;
chromatid2Start = chromatid2;
chromatid2End = chromatid2;

Perform a right-shift on the Start chromatid variables up to the crossover point, then left-shift the exact same amount. On the End chromatid variables, left-shift up to the crossover point, then right-shift the exact same amount.

chromatid1Start = (chromatid1Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid1End = (chromatid1End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);
chromatid2Start = (chromatid2Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid2End = (chromatid2End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);

With that, you can cross the start of one with the end of the other:

int daughterChromatid1 = chromatid1Start + chromatid2End;
int daughterChromatid2 = chromatid2Start + chromatid1End;

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.