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