Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to write a program for maximizing a function using a genetic algorithm. The function has $n$ integer variables $x_1 \dots x_n$, such that each variable is in the range [-n,n].

What is the most common way to binary-encode integers in the range [-n, n]?

Will it work if, for the initial population, instead of generating numbers between -n and n, I generate numbers from 0 to 2n and encode them in binary and then, while decoding, I subtract n every time for every subsequent generation ?

share|improve this question
    
@Renan: I am sorry i forgot to mention that I want to use binary encoding. So I am wondering about a good way to binary-encode integers in the range [-n,n]. I have modified the question. –  vjain27 Apr 23 '13 at 1:58
    
Deleted my comment since it's not relevant, then. –  Renan Apr 23 '13 at 1:58
add comment

2 Answers

The most common way is called two's compliment ("http://en.wikipedia.org/wiki/Two's_complement"), which is essentially the bitwise not of the original number expressed in binary plus one, where the first bit represents the negativity of the number. Alternatively, you could just add another bit to the binary representation which signals whether the number is positive or negative.

share|improve this answer
    
I guess these would make crossover more problematic. Especially the sign-bit representation. For e.g. if during crossover a sign-bit position is selected as the crossover point. –  vjain27 Apr 23 '13 at 2:08
    
I think that the GA should converge to giving low fitness values to elements with the wrong sign bit. As you suggested, the problem is somewhat less with two's compliment, as flipping a bit leads to a change of at most $2^{n-1}$ (n is the number of bits), whereas using the sign bit would allow the value to change by $2^n$ if the sign bit was flipped. –  deftfyodor Apr 23 '13 at 2:12
add comment

The most common binary representation that I have seen in GA's is grey codes (http://en.wikipedia.org/wiki/Gray_code). In this case, you would represent the numbers as $[0,2n]$, and you would probably have an extra bit in there if $n$ was a power of 2. No matter what, there's no method of binary representation that can span $[-n,n]$ without having some unused representations.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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