Ensure converging to 0, not -1, with binary string

Question

I'm using cooperative coevolution to solve a couple of function optimisation problems, and am having issues.

The functions take N parameters, where each parameter is a number, and all the functions minimise when each and every one of the N parameters is 0.

My representation of the 'individuals' for use in cooperative coevolution is a binary string, so I can perform bit-flip mutations (it's imperative I keep this representation).

Due to the fact that the functions converge when the parameters are zero, of course -1 is pretty close. However, in 32-bit binary representation, -1 is a string of 32 1s, where 0 is a string of 32 0s. I such get stuck in a local optimum, where some of the parameters are -1 and others are 0.

So my question is, how does one go about avoiding/getting out of this? Is it acceptable to probabilistically flip all 32 bits with a probability equal to that of my mutation rate?

Thanks in advance guys

Answer 1

Using machine internal representation is considered harmful because it leads to deceptive solutions in genetic algorithms.

There are many articles about MDP (Minimal Deceptive Problem) in genetic algoritms that cover this topic, for example: http://www.dtic.mil/get-tr-doc/pdf?AD=ADA294072

and great David Goldberg's book which explains deceptive problems and MDP and Building Blocks hypothesis (Genetic Algorithms in Search, Optimization, and Machine Learning, David Goldberg).

Internal representation of signed integer is Two's complement which leads to deceptive chromosome encoding where:

11111111 11111111 11111111 11111111   = -1 
00000000 00000000 00000000 00000000   =  0

If you want to use this Two's complement encoding, then I suggest to mask most left bit to make individual always positive number and then convert to float number with any offset you want.

For example:

int a = ...   // any value from 0 to 0x7fffffff
float x = ( ((float) a) / 0x7fffffff ) * 100 - 50.0;

// now x is in range: -50.0 .. 50.0