Genetic Algorithm Getting Stuck on Certain Values
I'm attempting to teach myself something about genetic algorithms. I found a simple tutorial on it here, and it made enough sense that I was able implement the suggested example of generating a string of single digit numbers and simple arithmetic operators to total 42.
I then attempted the second suggested exercise described at the bottom of the page here. Basically, in a field of randomly placed circles of random size, write a genetic algorithm to find the largest non-overlapping circle you can place in the field.
I have something that seems to work, but I notice that it seems to get hung up on certain values. My "chromosomes" are composed of 3 pieces of data - x position, y position and radius. I'm using crossover and mutation to reproduce in the population. I then rank the results based on how large the resulting circle it is and whether it fits within the field and whether it overlaps other circles or not.
What I'm seeing is that there's a strong tendency for the radius to tend towards values that are just under a power of 2. For example, it will often get stuck bouncing around a radius of 31, 62, 124, etc.
I was trying to determine why this happens. My "genes" are all single precision floating point numbers. Crossover would cause some portion of the bits from one value to replace the corresponding bits of another value. 655
Usually, this will result in the lowest precision bits of one value getting overwritten with those of another value. Occasionally it will cause part of or all of the exponent to get overwritten as well. Once you get a couple generations in, the values are largely of the same magnitude, so this often does very little. Mutation could flip any bit in the float, meaning it could turn a positive to negative 1/32nd of the time. It could change the exponent 7/32nds of the time, and the mantissa the remaining 3/4ths of the time.
Doubling the magnitude (by mutating or crossing over in the exponent, for example) is likely to have a positive effect up to a certain point. But once the generation contains mostly circles that are slightly over 1/2 the maximum value, they'll be less likely to grow by this method. Changes in the mantissa seem to have little effect overall.
My question - is this normal? This seems problematic when trying to generate better generations. I've let my simulation run for millions of generations, and haven't seen it get any better than the next-lowest power-of-2 for the radius. Have I just laid out my data in an unfortunate way, or does this problem come up often in genetic algorithms? Is there a way around it? I tried switching to a 16.16 fixed point representation and it got slightly better. The radiuses would get larger more frequently, but they still seem to hover around powers-of-2. 655