Implementing a Breeding Algorithm

In the previous post we saw that introducing a mutation operation that naively you would think could improve the final solution found had little impact.  The question is what about an operation that mixes solutions to create a new potential solution?  For the sake of a biological analogy, a breeding operation where two (or more) parents (solutions from a given generation) 'mix' in some way to produce a child solution that becomes part of the population in the next generation.  So I spent some time creating two such operators, very simplistic one, to see how they affect the outcome for the example problem I described in my first post.

Averaging Operator

The first and simplest breeding operator I could think of is one where the value of each gene is an average of the corresponding values in the parents:

Chromosome	Gene 1	Gene 2
Parent 1	3	6.2
Parent 2	5	4.1
Child	4	5.15

One problem with this is that it will instantly violate the simple sum of gene values constraint we imposed.  As such the actual code goes a step further and 'normalises' the genes of the child chromosome to have a sum that matches that of the parents.
This operator is not a true breeding operator in its purest form as it does modify the values of the genes rather than simply create a new chromosome by resequencing genes selected from the parents.  As such it is more of a breeding and mutation operator in one.  The reason behind the decision to do this was that in a continuous variable problem, the best solution may possibly exist in a space 'between' the solutions that have already been explored, so a mutation and a resequencing combined may help to explore the problem space more rapidly.  Remember that in the first post a single point crossover breeding operator was used, this takes part of each parent and concatenates to form a child, the table below showing how the same parents can produce 2 different children by changing the point of crossover

Chromosome	Gene 1	Gene 2	Gene 3	Gene 4
Parent 1	1	2	3	4
Parent 2	9	8	7	6
Child	1	2	7	6
Child	1	8	7	6

and we have the results of this non-mutating breeding operator to compare with those of a hybrid breeder-mutator operation.

Results do show that this operator gives no noticeable advantage over the out of the box pure crossover operation, with R=0.941  and F=0.235  with the SwapMutate operator unmodified from the first post.

the code for this operator is:

 public void Invoke(Population currentPopulation, ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)  
 {  
    Debug.WriteLine("Breeding from pop size of {0} into pop size of {1}", currentPopulation.PopulationSize, newPopulation.PopulationSize);  
    //first check sixe of new population, if its big enough already just return  
    if (newPopulation.PopulationSize >= currentPopulation.PopulationSize)  
      return;  
    //also cannot perform with less than 2 chromosomes  
    if (currentPopulation.PopulationSize < 2)  
      return;  
    while (newPopulation.PopulationSize < currentPopulation.PopulationSize)  
    {  
      //otherwise take 2 chromosomes at random from the current population (include elite ones)  
      var parents = currentPopulation.Solutions.SelectRandomMembers(2);  
      //craete the new chromosome  
      //assumes both parents have the same the sum of gene values  
      var sum = parents.First().Genes.Sum(g => g.RealValue);  
      var newGenes = new List<double>();  
      for (int i = 0; i < parents.First().Genes.Count; i++)  
      {  
         newGenes.Add((parents.First().Genes.ElementAt(i).RealValue + parents.Last().Genes.ElementAt(i).RealValue) / 2);  
      }  
      //now normalise to the same sum  
      var newsum = newGenes.Sum();  
      var m = sum / newsum;  
      var ch = new Chromosome(newGenes.Select(g => g * m));  
      newPopulation.Solutions.Add(ch);  
    }  
 }  

Normalised Sum Operator

A slight variation on the averaging breeder is to instead simply sum the gene values of the parents, then 'normalise' the sum of gene values to meet the constraint.  Again this does not offer any great advantage with R=0.978 and F=0.244

from code

 public void Invoke(Population currentPopulation, ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)  
     {  
       Debug.WriteLine("Breeding from pop size of {0} into pop size of {1}", currentPopulation.PopulationSize, newPopulation.PopulationSize);  
       //first check sixe of new population, if its big enough already just return  
       if (newPopulation.PopulationSize >= currentPopulation.PopulationSize)  
         return;  
       //also cannot perform with less than 2 chromosomes  
       if (currentPopulation.PopulationSize < 2)  
         return;  
       while (newPopulation.PopulationSize < currentPopulation.PopulationSize)  
       {  
         //otherwise take 2 chromosomes at random from the current population (include elite ones)  
         var parents = currentPopulation.Solutions.SelectRandomMembers(2);  
         //craete the new chromosome  
         //assumes both parents have the same the sum of gene values  
         var sum = parents.First().Genes.Sum(g => g.RealValue);  
         var newGenes = new List<double>();  
         for (int i = 0; i < parents.First().Genes.Count; i++)  
         {  
           newGenes.Add(parents.First().Genes.ElementAt(i).RealValue + parents.Last().Genes.ElementAt(i).RealValue);  
         }  
         //now normalise to the same sum  
         var newsum = newGenes.Sum();  
         var m = sum / newsum;  
         var ch = new Chromosome(newGenes.Select(g => g * m));  
         newPopulation.Solutions.Add(ch);  
       }  

Conclusion
Although the operators selected for use in the algorithm obviously do have a factor in the obtaining of a good solution, it appears that they do not have a significant impact on just how good a solution can be found.  It may be a leap of faith at this stage but it is my belief that the fitness calculation will have a far more significant impact, and that is something that I will explore in the next post.
And on that theme, the next post may possibly be delayed as I am currently in hospital and have no access to my PC to do any coding, but hopefully I will get my hands dirty again fairly soon and be able to produce another post.