genetic-algorithmcombinatorics

How can I get my GA to converge?

I'm trying to write a GA to solve the following puzzle...

enter image description here

A binary encoding is (I think) very efficient. Each piece can be:

This means that each piece's orientation and position can be encoded in 9 bits, making a total of 117 bits for the whole puzzle.

The fitness is calculated by placing each piece in the frame, ignoring any parts that lie out of the frame, and then adding up the number of empty squares. When that hits zero, we have a solution.

I have some standard GA methods I've used in other code (which I'll paste in below), but I can't seem to get it to converge. The fitness drops to about 11 (give or take), but never seems to go any lower. I've tried fiddling with the parameters, but can't get it any better.

At the risk of posting too much code, I'll show what I've got (where it seems relevant). If anyone can give me some idea how I could improve, it would be great. This is all in C#, but it should be clear enough to people who use other languages.

After generating an initial population of 1000 chromosomes (code not shown as it's just generating random binary strings of length 117), I enter the main loop, where on each generation, I call the Breed method, passing in the current population and some parameters...

private static List<Chromosome> Breed(List<Chromosome> population, int crossoverGene, 
                  double mutationProbability, double mutationRate) {
  List<Chromosome> nextGeneration = new List<Chromosome>();
  // Cross breed half of the population number
  for (int nChromosome = 0; nChromosome < population.Count / 2; nChromosome++) {
    Chromosome daddy = Roulette(population);
    Chromosome mummy = Roulette(population);
    string babyGenes = daddy.Genes.Substring(0, crossoverGene)
                     + mummy.Genes.Substring(crossoverGene);
    Chromosome baby = new Chromosome(babyGenes);
    baby.Fitness = Fitness(baby);
    nextGeneration.Add(baby);
  }
  // Mutate some chromosomes
  int numberToMutate = (int)(P() * 100 * mutationProbability);
  List<Chromosome> mutatedChromosomes = new List<Chromosome>();
  for (int i = 0; i < numberToMutate; i++) {
    Chromosome c = Roulette(population);
    string mutatedGenes = MutateGenes(c.Genes, mutationRate);
    Chromosome mutatedChromosome = new Chromosome(mutatedGenes);
    mutatedChromosome.Fitness = Fitness(mutatedChromosome);
    mutatedChromosomes.Add(mutatedChromosome);
  }
  // Get the next generation from the fittest chromosomes
  nextGeneration = nextGeneration
    .Union(population)
    .Union(mutatedChromosomes)
    .OrderBy(p => p.Fitness)
    .Take(population.Count)
    .ToList();
  return nextGeneration;
}

MutateGenes just flips bits at random, based on the mutation rate passed in. The main loop continues until we either hit the maximum number of generations, or the fitness drops to zero. I'm currently running for 1000 generations.

Here's the roulette method...

private static Chromosome Roulette(List<Chromosome> population) {
  double totalFitness = population.Sum(c => 1 / c.Fitness);
  double targetProbability = totalFitness * P();
  double cumProbability = 0.0;
  List<Chromosome> orderedPopulation = population.OrderBy(c => c.Fitness).ToList();
  for (int i = 0; i < orderedPopulation.Count; i++) {
    Chromosome c = orderedPopulation[i];
    cumProbability += 1 / c.Fitness;
    if (cumProbability > targetProbability) {
      return c;
    }
  }
  return orderedPopulation.Last();
}

Don't know if you need to see any of the other code. I was a bit wary about posting too much in case it put people off!

Anyone able to make any suggestions as to how I can get this to improve?

Solution

  • Todor Balabanov's answer is very interesting. Probably using relative coordinates and a proper packing function is the keystone.

    Anyway I'd like to expand upon your idea as much as possible. A full discussion is probably too long for Stackoverflow...

    TL;DR

    1. Binary encoding does not give you any advantage.

    2. The chosen alphabet isn't the smallest that permits a natural expression of the problem.

    3. Considering the full range of coordinates ([0;7] x [0;7]) for every piece is excessive (and somewhat misleading for fitness evaluation).

      Points (2) and (3) allow to reduce the search space from 2^117 to 2^95 elements.

    4. A more informative fitness function is a great help.

      • You can use a multi-value fitness score, penalizing configurations that present holes.
      • Squares covered by overlapping pieces shouldn't be counted: an illegal configuration cannot have a fitness greater than a legal one.

    5. ALPS can reduce the problem of premature convergence (reference implementation here).

    I've have elaborated on these points in a GitHub wiki (it's a work in progress).