Based on my previous post on how to implement a simple genetic algorithm, I got some great comments pointing out that the algorithm might not be the most pure form of a genetic algorithm. I won’t disagree, though I will point out that evolution also does occur due to mutation alone, so genetic algorithms may come in different forms.
Making it more “genetic”
The basic point is that I was only mutating my chromosomes, I wasn’t actually pairing them up and reproducing via a crossover function.
I’ve changed my GeneticAlgorithm class slightly to give more control to the subclasses of how reproduction works, whether it be by mutation and/or crossover. What I’ve done is to change the Mutate method into a Reproduce method, taking in the complete survivor enumeration of IChromosome’s instead. That way, the implementing subclass has full control over the selection and breeding of the survivors.
/// <summary> /// Creates an arbitrary number of mutated chromosomes, based on the input chromosome. /// </summary> protected abstract IEnumerable<IChromosome<T>> Reproduce(IEnumerable<IChromosome<T>> survivors);
The PerformEvolution method has been changed as well. Instead of selecting the survivor to mutate here, we let it be up to the subclass. Thus, we just loop until we’ve reached our ChromosomePopulationSize, while passing the survivors into the Reproduce method.
/// <summary> /// Performs an evolution by picking up the generation survivors and mutating them. /// </summary> public void PerformEvolution() { IList<IChromosome<T>> newGeneration = new List<IChromosome<T>>(); // Get the survivors of the last generation IEnumerable<IChromosome<T>> survivors = GetGenerationSurvivors(); // Add the survivors of the previous generation foreach (var survivor in survivors) newGeneration.Add(survivor); // Until the population is full, add a new mutation of any two survivors, selected by weighted random based on their fitness. Random rnd = new Random(); while (newGeneration.Count < ChromosomePopulationSize) foreach (var offspring in Reproduce(survivors)) { newGeneration.Add(offspring); if (newGeneration.Count == ChromosomePopulationSize) break; } // Overwrite current population ChromosomePopulation = newGeneration; // Increment the current generation CurrentGenerationNumber++; }
Instead of overriding Mutate() in the RgbGuesser class, we’re now overriding Reproduce. Given that we have three basic genes in each of our chromosomes (R, G & B), we can produce 2^3 different combinations, including the original two combinations AAA and BBB. Each time Reproduce is called, we’ll create all eight different combinations and mutate them slightly, before returning them to the GeneticAlgorithm. This way we’re producing eight children of each parent pair of chromosomes, and thus, as Matt^2 pointed out, allowing the chromosomes of developing partial solutions themselves more efficiently.
protected override IEnumerable<IChromosome<Rgb>> Reproduce(IEnumerable<IChromosome<Rgb>> survivors) { // Get two random chromosomes from the survivors var chromA = survivors .OrderBy(c => random.NextDouble() * c.Fitness) .First(); var chromB = survivors .OrderBy(c => random.NextDouble() * c.Fitness) .Where(c => c != chromA) .First(); // Now generate and return each different combination based on the two parents, with slight mutation var aaa = new RgbChromosome(chromA.ChromosomeValue.R, chromA.ChromosomeValue.G, chromA.ChromosomeValue.B); mutateChromosome(aaa); yield return aaa; var aab = new RgbChromosome(chromA.ChromosomeValue.R, chromA.ChromosomeValue.G, chromB.ChromosomeValue.B); mutateChromosome(aab); yield return aab; var abb = new RgbChromosome(chromA.ChromosomeValue.R, chromB.ChromosomeValue.G, chromB.ChromosomeValue.B); mutateChromosome(abb); yield return abb; var aba = new RgbChromosome(chromA.ChromosomeValue.R, chromB.ChromosomeValue.G, chromA.ChromosomeValue.B); mutateChromosome(aba); yield return aba; var baa = new RgbChromosome(chromB.ChromosomeValue.R, chromA.ChromosomeValue.G, chromA.ChromosomeValue.B); mutateChromosome(baa); yield return baa; var bba = new RgbChromosome(chromB.ChromosomeValue.R, chromB.ChromosomeValue.G, chromA.ChromosomeValue.B); mutateChromosome(bba); yield return bba; var bab = new RgbChromosome(chromB.ChromosomeValue.R, chromA.ChromosomeValue.G, chromB.ChromosomeValue.B); mutateChromosome(bab); yield return bab; var bbb = new RgbChromosome(chromB.ChromosomeValue.R, chromB.ChromosomeValue.G, chromB.ChromosomeValue.B); mutateChromosome(bbb); yield return bbb; } private void mutateChromosome(IChromosome<Rgb> chromosome) { chromosome.ChromosomeValue.R = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.R + random.Next(-5, 6))); chromosome.ChromosomeValue.G = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.G + random.Next(-5, 6))); chromosome.ChromosomeValue.B = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.B + random.Next(-5, 6))); }
Reducing the chance of mutation
As weenie points out in the comments, reducing the chance of mutation will actually improve results. By changing the mutateChromosome slightly, we only mutate it for every 1/3 reproductions.
At this point we’ve got several variables to tune – population size, survivor count, mutation probability & mutation severeness. This sounds like an optimal problem for an evolutionary algorithm :)
private void mutateChromosome(IChromosome<Rgb> chromosome) { if (random.Next(1, 4) == 1) { chromosome.ChromosomeValue.R = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.R + random.Next(-5, 6))); chromosome.ChromosomeValue.G = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.G + random.Next(-5, 6))); chromosome.ChromosomeValue.B = Math.Min(255, Math.Max(0, chromosome.ChromosomeValue.B + random.Next(-5, 6))); } }
Downloads
GeneticTesting2.zip – Sample code
-
To be honest, I think that the crossover operator you added changed almost nothing. The number of generations needed to find a valid solution varies from 30 to 200 with an average about 70-80. With a slight modification of the code provided i was able to reduce it to about 10-40 with an average about 20. The main problem in here is that you mutate every single chromosome you produce. All you have to do is decrease the mutation probability from 100% to about 10% and you’ll see quite an improvement.
-
@weenie
Thanks for the comment. That’s what I love about blogging – you live to learn :)
I’ve added an updated section to the entry, reducing the chance of mutation. And you’re right, this does bring the average down to about 20 generations.
-
Since this is a simple problem, creating a child for each possible combination of the parents gene’s is a quick and easy solution, but when problems get larger (such that the number of combinations make this type of reproduction infeasible) and computation time becomes an issue (such that you don’t want to be continuously re-evaluating individuals with the same genetic pattern), the crossover operation will work better if it only produces a small number of unique children (using a pivot point or a random selection of chromosomes). There are a number of different types of crossover operations you can use to avoid simply creating every possible child (including duplicates).
But of course, the beauty of these problems is that you get to tune the algorithm to best solve the problem at hand. That is half the fun – there are so many ways to solve it, and always new things to try.