0

I know GA questions are often almost impossible to answer exactly, but I'm looking for some general advice (although specific advice would be great too!).

I've just written my second GA, which tries to find a phrase (say "i like bananas"), which it does by generating binary strings of 5 times the length of the target string (as I have allowed 32 = 2^5 characters in my strings, the lowercase alphabet, space and five punctuation characters) and breeding and mutating them.

This is all based on an example in Practical Genetic Algorithms by Randy and Sue Ellen Haupt (not sure if I'm allowed to link to Amazon, so I didn't). other sources show similar outlines, so I don't think there is anything specific about that bok, I was just reading it, and so tried their example.

I tried my GA on "colorado" which was the one they used in the book. It found the right answer in around 200-800 generations, which compared to the 1E12 possible combinations of the allowed characters is not bad. However, the authors of the book said that their GA found the answer in just 17 generations, which makes my algorithm look incredibly slow.

If there's had managed it in (say) 100-300, I could have written my poorer performance down to a lack of experience, but 17 is a huge difference from my results. I want to know how to improve my GA to get anywhere near that.

I'll post some code below. This is C#, but anyone familiar with any of the C-family of languages should be able to understand it. I don't really use much C#-specific stuff here. I won't include some of the utility functions, as they have been tested, so I know they work, and this will help keep the amount of code down. If you think I've missed out anything important, please let me know and I'll add it.

First, here's my simple Chromosome class...

public class Chromosome {
  public Chromosome(string genes) {
    Genes = genes;
  }

  public string Genes { get; set; }
  public double Fitness { get; set; }
}

Here is the main routine...

void Main() {
  // We are assuming that each character is mapped to a number between 0 (a) and 25 (z),
  // with space . , ! ? and - taking up the numbers from 26 to 31.
  // Thus, each character can be encoded in a binary string of length 5 (ie "00000"
  // is a, "11001" is z and so on), and so any string can be encoded as a sequence
  // of 1s and 0s, with the encoded length being five times the original string length
  int len = target.Length * 5; // Length of gene string in each chromosome
  int totalChromosomes = 32; // Number of chromosomes in the population
  double crossover = 0.5;
  // The gene number at which crossover will take place
  int crossoverGene = (int)(len * crossover);
  double mutationRate = 0.04;
  // Generate the initial (random) population
  List<Chromosome> population = Initial(totalChromosomes, len);
  int generations = 10000;
  int genNumber = 0;
  Chromosome best;
  do {
    // get the next generation
    population = Breed(population, crossoverGene, mutationRate);
    // Find the best chromosome
    best = population.OrderBy(c => c.Fitness).First();
    genNumber++;
  }
  while (genNumber < generations && best.Fitness > 0);
  Console.WriteLine("Best fitness: " + best.Fitness.ToString("F3") + "\tGenes: " 
                + Decode(best.Genes) + "\t@ generation " + genNumber + "/" + generations);
}

Here is the fitness function, which returns the number of incorrect characters...

private static int Fitness(Chromosome c) {
  int fitness = 0;
  for (int i = 0; i < target.Length; i++) {
    int cTarget = (int)target[i];
    string genes = c.Genes.Substring(i * 5, 5);
    char cChromosome = BinaryToChar(genes);
    if (cTarget != (int)cChromosome) {
      // Add 1 to the fitness for every incorrect character
      fitness++;
    }
  }
  return fitness;
}

The Breed function takes our current population, breeds chromosomes together and returns a new (hopefully better) population. Say we have a population of n chromosomes, we generate n/2 new chromosomes, then add on the best n/2 from the current population.

The Roulette function used here is a straightforward implementation of a roulette wheel selection. I didn't include the code as I tested a lot on the previous GA, and it seems to work fine...

private static List<Chromosome> Breed(List<Chromosome> population, int crossoverGene,
                                               double mutationRate) {
  List<Chromosome> nextGeneration = new List<Chromosome>();
  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);
    string mutatedGenes = "";
    foreach (char gene in babyGenes) {
      // P() returns a random number between 0 and 1
      mutatedGenes += P() < mutationRate ? (gene == '1' ? '0' : '1') : gene;
    }
    Chromosome baby = new Chromosome(mutatedGenes);
    baby.Fitness = Fitness(baby);
    nextGeneration.Add(baby);
  }
  // Add on the best of the previous generation to make up the numbers in the next gen
  nextGeneration = nextGeneration // the new chromosomes we just bread
                    // join with the previous generation, order by fitness,  best first
                    .Union(population.OrderBy(p => p.Fitness) 
                    // Only take the  first n chromosomes, discarding the rest
                    .Take(population.Count() - nextGeneration.Count())).ToList();
  return nextGeneration;
}

I hope that's enough of the code to see what I'm doing. I don't think any of the omitted functions have any significant code.

I have tried this on various strings, varying the population size, crossover and mutation, but other than the fact that it just fails to find an answer on longer strings, nothing seems to have made any noticeable difference.

Anyone able to give me any idea how I can improve my algorithm?

The book authors mentioned that they used a population of 16. I tried varying the population, and found that values around 16 took significantly longer to converge (100 generations or more), whereas once I got up to about 50, it settled at around 200-800.

Edit Following a suggestion by amon, I tried a fitness function that compares the current and target strings on a bit-by-bit basis. I encoded the target string into a binary string, and used the following fitness function...

private static int Fitness(Chromosome c) {
  int fitness = 0;
  for (int i = 0; i < encodedTarget.Length; i++) {
    if (c.Genes[i] != encodedTarget[i]) {
      fitness++;
    }
  }
  return fitness;
}

However, this didn't make any difference. I'm including it here in case anyone can make any suggestions as to how to improve it.

  • Have you tried tweaking your crossover value? – Robert Harvey Jan 1 '17 at 16:06
  • @RobertHarvey Yup, I've tried tweaking everything I could tweak, but it didn't really make much difference. Tried crossovers of 0.1 up to 0.9, but always got a wide range of generations needed, generally somewhere between 200-800. Thanks anyway, any other ideas? – Avrohom Yisroel Jan 1 '17 at 16:10
  • 3
    To debug GAs, dump the population after each generation. Are there notable patterns? My guess is that it takes a long time to find the last character, which is the char containing the crossover boundary. Note that your fitness function operates on runs of 5 bits, but crossover and mutation operate on a bit-by-bit basis. If the fitness function reports the number of wrong bits, you'll see much faster convergence. As it stands, the fitness function cannot guide selection of the last char, and you're effectively waiting for random mutation to guess the correct char. – amon Jan 1 '17 at 17:17
  • 1
    The lesson here is that GAs don't just depend on parameters like crossover rate etc., but very much on how precisely operations like parent selection, mutation, crossover, fitness calculation, … are performed. Experimenting with those as well can have a great effect. – amon Jan 1 '17 at 17:22
  • @amon You're right about the pattern. It finds an almost-perfect match (ie one character wrong), then finds another almost-perfect match, and keeps going like that until it hits the right one. However, the incorrect character isn't always at the crossover point. It sometimes is, but sometimes isn't. I tried picking a random crossover point each generation, but it didn't help. Could you explain more what you mean, as I'm not sure how to change my code. Maybe you could post some modified code for me to see. That way, if it works, I can mark it as an answer. Thanks for the help. – Avrohom Yisroel Jan 1 '17 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.