genetic algorithm binary encoding negative integers

Question

I am trying to implement genetic algorithm for maximizing a function of n integer variables x1..xn where each variable belongs to the range [-n, n]. I am thinking of using binary encoding for representing chromosome but I am not sure about how to encode negative integers. I have searched for quite some time but I haven't come across a common formula for binary encoding. What is the most common way to encode integers in the range [-n,n] for genetic algorithms? I want crossover and mutation to have less complexity (less condition checking). 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)?

Answer 1

user1765444's answer makes good sense... and I just read sashkello's suggestion (using offset binary would eliminate having to frig about with signed ints inside the GA). Doing the crossover and mutates etc would be easy that way - using a combo of both shashkello's and user1765444's answers. The problem is if your datatype has a larger width than your range, then crossover could yield invalid children.

Let's say an int32 has the width you require. Then int32 array[n]. You know there are 32n bits so you might take a crossover point at random m, where m >=0 and m < 32n. You know bit m occurs in array[m/n], bit position m%n starting at the msb (imagining the array to be just one long binary string).

Then say you have 2 parents int32 parent1[n] and int32 parent2[n]. Something like the following pseudo-ish code? In this crossover the string is just a binary string for the sake of the cross (i.e. sign bit treated as just another bit)...

Disclaimer: Sorry, code below is rough n ready, uncompiled, so may contain errors... just a thought!

int child1[n];
uint32 m = rand_like_func(); // random cross over point, a bit position
                             // in the binary string of length n*32;
uint32 arraySlotForCrossOvr = (uint32)(m / n);
uint32 bitInSlotForCrossOvr = 31 - m % n;
uint32 maskForCrossOvrP2 = (1 << bitInSlotForCrossOvr) - 1;
uint32 maskForCrossOvrP1 = ~maskForCrossOvrP2;

// crossover to create child 1
memcpy(child1, parent1, arraySlotForCrossOvr);
child1[arraySlotForCrossOvr] = 
    (int32)( ((uint32)parent1[arraySlotForCrossOvr] & maskForCrossOverP1) |
             ((uint32)parent2[arraySlotForCrossOvr] & maskForCrossOvrP2) )
memcpy(
    child1, 
    parent2 + arraySlotForCrossOvr + 1, 
    total_num_slots - arraySlotForCrossOvr);

Then you might have to detect children that are out of range, or let out of range children just score zero in the next round. Perhaps you could augment the crossover with some intelligence like capping invalid values to the nearest valid value etc?

Hope that helped?

Also, I found "How to Solve It: Modern Heuristics by Z. Michalewicz and D Fogel" really helpful when trying to understand encoding of problems etc :)