# GA puzzle solver stuck at local maximum

I have a jigsaw type problem with 192 pieces which I am trying to find solutions to. I have written a GA which starts from a random allocation then 'crosses' by taking rectangular blocks from one solution then filling in from another then 'mutates' by switching pieces at random. Through a complex procedure I can evaluate a solution and calculate a score.

I have a population size of 1000 and take 40% of the first parent in the cross and mutate up to 4% of the pieces in each solution generation. I select the parents with a weighted selection and do not allow any exact duplicates in my population.

The problem I am having is that the algorithm gets stuck at about 70% score, with (I assume) a population full of near identical solutions.

1. What can I do to improve the performance of the algorithm, am I making any glaring mistakes?
2. Should I be mutating more, or directing the mutation more towards poor scoring pieces?
3. Should I have a larger population, or run several populations in parallel and share high scoring solutions between them?

Update

I have replaced my roulette with a tournament selection (with 4 solutions picked at random and the best selected) and implemented mutations up to 4 times on each new child in the generation. I rearranged the process so that I cull half the population, then add some new random results then repopulate with crossovers.

Unfortunately, I seem to get a marginal performance increase, but I still seem to be converging at around 70% score.

Does anyone have any other ideas of things I can tweak to try and break through this barrier?

• When it gets stuck randomly remove 250 genes from the population with new randomly generated 250 genes. Just suggesting a hack and want to know if it works. Oct 20, 2011 at 10:14
• When it's possible to compute a solution to a problem deterministically (which you can with a jigsaw), some people use GAs to find a "reasonably good" solution and then let a deterministic algorithm solve the rest of the problem. This might be easier/more suitable than trying to tweak your GA for better performance. Nov 17, 2011 at 11:29

1000 individuals is typically a fairly large population, so lacking further information, you're probably fine there.

You don't say how quickly your algorithm is converging or exactly you calculate the weights for weighted selection, but if you're doing the typical roulette-wheel or fitness-proportionate selection, it's known that that method produces a large amount of selection pressure, particularly early in the run. What happens is that most early solutions are terrible, so the first mediocre thing it finds gets a much higher proportion of the total fitness than it really deserves and quickly swamps the population. The easiest way to avoid that is to use something with a more controllable selection pressure, like binary tournament selection or rank-biased selection.

For mutation, the general rule of thumb has always been to mutate each allele independently with probability 1/n. Like any heuristic, that's only a starting point, and you should let experiment guide you in making any adjustments, but if I'm understanding you correctly, you have 192 alleles, so a 4% mutation rate gives an expectation of about 8 mutations per individual, which I would guess is too high.

Or do you mean you make a single mutation to 4% of the generated offspring? If that's the case, it's probably too low. I'd start with a method that mutates every single individual by a randomly selected amount, with the expected amount being one flip. Some individuals will get two or three flips, others will not be altered at all.

The third idea, having multiple populations and sharing between them goes by the name of "island model" GAs, and has been known to work pretty well for some problems. However, I think in your case there are some issues with the way the underlying algorithm is working that need to be addressed before moving to a parallel model that will only make it more difficult to tease out the dynamics of what's going on.

Without more details about exactly how you're encoding your solutions, how your crossover and mutation operators work, etc., we're kind of limited to general statements such as those I just made. Feel free to post any clarifications though and I'll take another run at helping understand what might be going on.

• Thanks, my algorithm converges in about 500 generations, I am using a roulette-wheel selection. I will try out the other selection methods you mention as that sounds like the problem I am facing. Your first understanding of my mutation system is correct, so maybe I should reduce it down from 4% and see if that helps. Oct 20, 2011 at 10:13