Genetic Algorithm Binary Representation

Question

I can't seem to find a good website to explain GA (which I am completely new to), but I was reading a book and it said that:

If we constrain possible values of the intercept to the range [-5, 1.5] and linearly transform the range to the binary range [0, 2^8 - 1], then a value 0.74 would translate into 10011110, and parameter values of [.74, -.11] might be represented by 10011110110010.

Could someone explain to me
1) How the linear transformation of range works, and
2) How is 0.74 represented by 10011110

My rough knowledge of binary would have translated that as

2^8 0 0 2^5 2^4 2^3 2^2 2^1

which is 318.

If you know of any site that might explain this as a good introduction, that would help to. Thanks!

Answer 1

I have written some simple Genetic Algorithms for function optimization in C++. Here is the source code:

https://github.com/mihaioltean/genetic-algorithms

There are 2 implementations: one for real encoding and one for binary representation which also shows how to transform from a binary string to a real interval.

There are many comments in the code, in you need more, please tell me what is not clear and I will add more.

regards, mihai

Answer 2

Linear transforming a range is pretty simple. It's probably easier to work with integers to start with.

Lets say you have range of [0, 10] and you want to translate that into a range [0, 20]. Each value simply gets multiplied by 2, so 0 => 0, 1 => 2, 2 => 4, 3 => 6, etc.

Now let's take another example, you want to translate [1, 10] into [2, 11]. To do that, you simply subtract 1 (for the bottom of the first range) and then add 2 (for the minimum of the second range). So just add 1 to each number, so 1 => 2, 2 => 3, 3 => 4, etc.

Now what happens if you want to combine them. Lets say you want to translate 10,110 into 30,230. First you subtract the minimum of the first number, 10, so the minimum is 0. Then multiply by the scaling factor. In this case 110-10 = 100 and 230-30 = 200, so the scaling factor is 200/100 = 2. Then you add the minimum of the second range, which is 30. So to convert i1 into i2, you have i2 = (i1 - 10) * 2 + 30, which you can then simplify.

If you want to convert [-5, 1.5] range into [0, 255], you subtract -5 (i.e. add 5), multiply by 256, divide by 6.5 (from 1.5 - -5 = 6.5), and then add 0. Then because you're dealing with integer values, you need to round the result to the nearest whole number.

Also, you have a slight error in your binary calculation, the lowest digit is 2^0, not 2^1. So you need to divide 318 by 2 to get the correct answer.