-1
$\begingroup$

Right now I have a binary genetic algorithm. I used a random 0-512 and other random to get the symbol.

Example:

1- 297 and + = 297

2- 486 and - = -486 ...

I used 512 because the binary of it is 10 0000 0000 and its simple to deal with it if I need to check the fitness.

Someone told me that If I used gray code or binary code I can make custom domains like :

00000 as -89.3

11111 as 187.9

But I don't know how to accomplish this. Any insight would be helpful.

Thank you.

$\endgroup$
  • $\begingroup$ Please check our tour and help center pages. I think this question would be more suitable for Computer Science which has a broader scope than this site. $\endgroup$ – Kaveh Nov 14 '13 at 22:43
  • $\begingroup$ @Kaveh I'm sorry, it won't happen again. $\endgroup$ – EinsL Nov 15 '13 at 0:25
  • $\begingroup$ No reason to be sorry. $\endgroup$ – Kaveh Nov 15 '13 at 0:26
1
$\begingroup$

Two different questions.

How to map your decoded values onto a non-power of two range is really just basic arithmetic. Suppose your target range is the half-open interval [10, 20). (That is, 10.0 <= x < 20.0). Suppose further you have an 8-bit encoding. Let's take the string 01001011. In standard binary, this decodes to the integer 128+8+2+1=139. The total range of values you can represent is of course 0-255 inclusive. 139/(255-0)=0.545098. Think of this as the fraction of the way that 139 is to 255. The target range is only 10.0 however (20-10). Multiplying 0.545098 * 10.0 gives 5.45098. So 5.45098 is the same proportion of 10 as 139 is of 255, right? Now all that's left is to add the lower bound back in so that we're mapping between 10 and 20 instead of 0 and 10.

Putting this all together, let X_int = the decoded integer value from your bit string of length L, and let X_min and X_max be your desired range. Then

X = (X_int / 2^L-1) * (X_max - X_min) + X_min

If you want to use a standard binary encoding, that's all you need. However, Gray codes often do work better in search algorithms because of the Hamming cliff problem. If we want to use Gray codes, we need to be able to get X_int out of the Gray coded bit string.

You typically learn Gray codes by learning how to construct one via the binary reflection trick, but there is a bit of a shortcut here. The reflected gray code of a binary string b is just b xor b logically right shifted by one. We can reconstruct b and decoded it all in one pass through the string. In C-ish pseudocode,

int decode_gray(int[] gray_bits, int numbits)
    int[] binary = new int[numbits]
    binary[0] = gray[0]
    int X_int = binary[0]
    for i=1 to numbits                         // note we start at 1, not 0
        binary[i] = !(binary[i] == gray[i-1])  // g xor g shifted by 1
        X_int += X_int + binary[i]             // building up the powers of two
    return X_int

Let's see an example. Take the string 1101. In the reflected binary Gray code, this is 9. So let's decode it and see what happens.

First we create a new bit string for the binary equivalent, and set it's leading bit to the same as the leading bit from the Gray code

gray = 1101
bin  = 1---
Xint = 1

Now we start the loop with i=1. Comparing gray[1] and bin[0], they are equal. But we take the not of that, so we get false, or 0 for bin[1]. And X_int gets updated with this weird += X_int + bin[i] thing.

gray = 1101
bin  = 10--
Xint = Xint + Xint + 0 = 2

Next trip through the loop, gray[2] == bin[1] again, so bin[2] = 0.

gray = 1101
bin  = 100-
Xint = Xint + Xint + 0 = 4

Finally, we have gray[3] != bin[2], so bin[3] = 1.

gray = 1101
bin  = 1001
Xint = Xint + Xint + 1 = 9

So you get both the binary string 1001, which is 9 in binary, and the parameter value 9 out the back end. Why this works is not too hard to figure out if you spend some time working out the properties of gray and binary codes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well explained and easy to follow. This was exactly what I needed. Thank you. $\endgroup$ – EinsL Nov 14 '13 at 18:09

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