Genetic Algorithm Getting Stuck on Certain Values

Question

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. 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/32^nd of the time. It could change the exponent 7/32^nds of the time, and the mantissa the remaining 3/4^ths 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.

Answer 1

As @Ray mentioned, the solution was to change how I encode the values. I encoded the positions and radius as floating point values initially. I switch from 32-bit IEEE-754 encoding to a 16.16 fixed point representation, since I didn't need more precision than that. I then converted from the fixed point representation to a 32-bit Gray code to store the genes. That allowed the simulations to converge on a solution much more quickly. It also seemed to help the mutations and crossover produce higher quality variations.