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.
Why do my GAs take so long to converge?
genetic algorithms