Implementing a mutation algorithm

In the previous post we looked at solving a continuous variable problem with a genetic algorithm, and found that the restriction of the mutation algorithm meant we found a good, but not excellent solution as the value of each gene was set at the time the population is created.  These could be sequenced into many different solutions (chromosomes), but did not actually change value.  With a continuous variable problem we clearly need to tweak the values, so we need to try to create a new mutation algorithm to do this.  There are a number of questions that spring to mind instantly when thinking about how to do this:

1. How do we vary the genes?
2. How many genes in a chromosome should change in a given mutation?
3. What if a mutated chromosome is unviable?

The answer to these and all the other questions that are whizzing round your head vying for attention is simple IT DOESN'T MATTER.

the way we vary the genes is an implementation detail, we could do it in any number of ways, add a small value to it, subtract one, multiply by 1.0001, half it, anything.  And how many we change is again an implementation detail, we change 1 or 2 or all it doesn't matter, any choice made here simply creates a different mutation algorithm, the evolutionary process will still continue.  There may well be a sweet spot for the degree and detail of the mutations for finding a good solution quickly, but that is not the be all and end all for GAs, we just want to explore as much of the problem space as possible.  Finally, if we mutate in such a way as to create an unviable chromosome, it will be culled, and will not have an effect on future generations.  That said, for very specific mutation algorithms we may wish to mutate in such a way that some constraints are not violated.  In the example problem from the last post, where the sum of the gene values must be 1, we may wish to chose to mutate in such a way that this is not violated.  This constraint would always be violated if we simply change the value of a single gene within a chromosome, so a mutation that is aware of the problem may be required to allow some viable mutations to be created.  

In terms of software design this presents a horrible smell.  We are coupling low level code to high level concepts, and specifically creating a single target mutation algorithm, it is not ideal, but the creation of an algorithm that will only create unviable chromosomes would be pointless, so some forethought must be used when formulating a mutation algorithm.

New Mutations

I will look at 2 mutation operators in this post, and detail the results of using each.  The first of these mutation operators simply takes a single gene of a chromosome, modifies its value and adjusts the other genes so that the constraint of the sum of gene values remains a constant.  In practise this operator will select a proportion of the population of solutions not tagged as being elite solutions (elite solutions are earmarked to remain unchanged between generations) and mutate these.  The code I implemented to test this mutation is:

1:   public void Invoke(Population currentPopulation, ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)  
2:      {  
3:        var eliteCount = newPopulation.Solutions.Count(ch => ch.IsElite);  
4:        var numberToMutate = (int)System.Math.Round((newPopulation.PopulationSize - eliteCount) * MutationProbability);  
5:        newPopulation.Solutions  
6:                 .Where(ch => !ch.IsElite) //get the non elite  
7:                 .Take(numberToMutate) // selct the right percentage of these  
8:                 .ToList()  
9:                 .ForEach(ch => DoMutate(ch));  
10:      }  
11:      private void DoMutate(Chromosome ch)  
12:      {  
13:        //need to select a value from the chromosome mutate then ensure the sum is maintained       
14:        var geneIndexToMutate = rand.Next(ch.Genes.Count);  
15:        var gene = ch.Genes.ElementAt(geneIndexToMutate);        
16:        //now change this value, it must have a new value of less than SumOfGenes, so  
17:        var newGene = new Gene(rand.NextDouble() * SumOfGenes);  
18:        //and now modify the others, so find new sum, what do we need to multiply this by to get 1??  
19:        var m = 1d / ch.Genes.Except(new []{gene}).Sum(g => g.RealValue) + newGene.RealValue;  
20:        newGene = new Gene(newGene.RealValue * m);  
21:        //now multiply every gene By this to get mutated chromosome with correct sum  
22:        var AllNewGenes = ch.Genes.Take(geneIndexToMutate)  
23:                      .Select(g => new Gene(g.RealValue * m))  
24:                      .Concat(new[] { newGene })  
25:                      .Concat(ch.Genes.Skip(geneIndexToMutate + 1)  
26:                              .Select(g => new Gene(g.RealValue * m)))  
27:                      .ToList();  
28:        ch.Genes.Clear();  
29:        ch.Genes.AddRange(AllNewGenes);  
30:        //Debug.WriteLine("New Sum {0}", ch.Genes.Sum(g => g.RealValue));  
31:      }  

A guide to implementing genetic operators with a full example of a mutation operator can be found at  http://aiframeworks.net/blog/gaf-part-5.

The mutation requires knowledge of the sum of gene values constraint, and this is set on the construction of the operator, this can be seen as a shortcoming of the operator for general use, but for the purposes of investigating the effects of value mutation on chromosomes made up of a set of continuous variables, I have chosen to overlook this.

The results of using this operator are not as impressive as one would possibly expect.  Using the out of the box SwapMutator values of R=0.988 and F=0.247 are found.  Using the new mutation operator, R=0.993 and F=0.248 are found.  A slight improvement in the objective mimisation, with a loss in the constraint.  Now this is a very simplistic mutation of the gene values, with no memory of the previous value retained or used in the mutation.  As such I thought I should try another variation on the operator

17:    var mult = (minMultiplier + this.range * rand.NextDouble());  
18:    var newGene = new Gene( mult * geneValue);  

where minMultiplier +this.range will give a value between 0.5 and 1.5 based on a range value between 0 and 1.  This produces results of R=0.995 and F=0.248 for a range of 0.9; and R=0.990, F=0.247 for a range of 0.2.
So the retention of some of the parent's identity does not seem to help.

Mutate by Pairs

The second mutation I chose to try was the mutation of a chromosome by changing a pair of genes and leaving all others untouched.  By this method the sum of the genes values could be maintained by careful selection of the new values.  The code to perform this mutation is very similar:

1:   public void Invoke(Population currentPopulation, ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)  
2:      {  
3:        var eliteCount = newPopulation.Solutions.Count(ch => ch.IsElite);  
4:        var numberToMutate = (int)System.Math.Round((newPopulation.PopulationSize - eliteCount) * MutationProbability);  
5:        newPopulation.Solutions  
6:                 .Where(ch => !ch.IsElite) //get the non elite  
7:                 .Take(numberToMutate) // selct the right percentage of these  
8:                 .ToList()  
9:                 .ForEach(ch => DoMutate(ch));  
10:      }  
11:      private void DoMutate(Chromosome ch)  
12:      {  
13:        if (ch.Genes.Count <=1) return;  
14:        //need to select a value from the chromosome mutate then ensure the sum is maintained       
15:        var geneIndexToMutate = rand.Next(ch.Genes.Count / 2);  
16:        var geneIndexToMutate2 = geneIndexToMutate;  
17:        while(geneIndexToMutate>=geneIndexToMutate2)  
18:          geneIndexToMutate2 = rand.Next(ch.Genes.Count / 2, ch.Genes.Count);  
19:        //now change this value, it must have a new value of less than SumOfGenes, so    
20:        var newVal1 = -1d;  
21:        var newVal2 = -1d;  
22:        while(newVal1 <=0 || newVal2 <=0)  
23:        {  
24:          newVal1 = rand.NextDouble();  
25:          newVal2 = (ch.Genes.ElementAt(geneIndexToMutate).RealValue+ ch.Genes.ElementAt(geneIndexToMutate2).RealValue) - newVal1;  
26:        }  
27:        //and now modify the others, so find new sum  
28:        var AllNewGenes = ch.Genes.Take(geneIndexToMutate)  
29:                    .Concat(new[] { new Gene(newVal1) })  
30:                    .Concat(ch.Genes.Skip(geneIndexToMutate + 1)  
31:                    .Take(geneIndexToMutate2 - geneIndexToMutate - 1))  
32:                    .Concat(new[]{ new Gene(newVal2) })  
33:                    .Concat(ch.Genes.Skip(geneIndexToMutate2 + 1))  
34:                    .ToList();  
35:        ch.Genes.Clear();  
36:        ch.Genes.AddRange(AllNewGenes);  
37:        //Debug.WriteLine("New Sum {0}", ch.Genes.Sum(g => g.RealValue));  
38:      }  

which gives results of  R=0.989 F = 0.247.

Conclusions

So it appears that the form of the mutation is not the limiting factor in finding a good solution to the problem.  There may well be a better mutation possible, but the quality of the mutation id more likely to impact on the speed of convergence (not strictly a convergence as its a pseudo random exploration of the problem space) rather than the final result.

In coming posts I will explore the use of different breeding operators and finally the effect of the fitness calculation on the final result.