The Genetic Algorithm Framework – Part 5

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Introduction

There are two methods for producing a custom Genetic Operator for use with the GAF (Genetic Algorithm Framework for .NET 4.0). The first is the simplest and involves creating a C# class that implements the GAF.IGeneticOperator interface. The second method is to derive a new Genetic Operator from an existing one. This post will take a brief look at the first method before creating an ‘Auto-Mutate’ Genetic Operator using the second method.

Implementing IGeneticOperator

This is the simplest and most flexible way to create a Genetic Operator. The class SimpleOperator in the code shown below shows the simplest example.

Once the operator has been created, it can be added to the Operators collection in the same way as the other built-in operators, e.g.

ga.Operators.Add(simpleOperator)

The Invoke method will be called by the GAF and will present the current generations population (param: population) along with the next generation’s population (param: newPopulation). Each operator is responsible for either taking some solutions from the current population and transferring them to the new population. The way in which this is done is left to the implementer of the operator. For example, the Crossover Operator takes two solutions from the current population, performs a single or double point crossover, and places these ‘children’ into the new population.

The GetOperatorInvokedEvaluations method is used during by the GAF to determine the number of evaluations an operator invokes. Therefore, the method should return the number of evaluations that the operator undertakes for each invocation.

For example, the built-in Crossover operator evaluates the population to determine which individuals to select. However, the built-in Mutation operator does not perform any evaluations. If an operator performed a single evaluation of each member of a population of say 100 individuals, the GetOperatorInvokedEvaluation method would return 100. For an operator that does not perform any evaluations, the GetOperatorInvokedEvaluation method would return 0.

Things to Bear in Mind

• Ensure that the new population is not larger than the current population.
• Elites passed into the new population by the Elite Operator will be marked with the ‘IsElite’ property set to true. These should not normally be interfered with by subsequent operators.

Auto-Mutation

Watson (2003) discussed an approach that used a non-phenotype gene within the chromosome that could be used to increase the mutation probability. This additional gene was treated to the same genetic operations as the other genes, however, it was not used during chromosome decoding process. The gene was simply used to modify the mutation probability.

The class AutoMutate in the code below shows an Auto-Mutate operator that has been built by deriving from the existing BinaryMutate operator of the GAF. This process makes it very simple to create an operator that could increase the mutation probability depending upon the non-phenotype gene’s value.

In this implementation, a value of 1 increases the probability by a factor of 5, 10 or 20 depending upon the configuration. A value of 0 has no effect on the mutation probability. The code for this extended operator is shown below. As the non-phenotype gene is subject itself, to this increased probability, there is a greater probability that the gene will be changed from 1 to 0 than from 0 to 1. The effect therefore, is that as convergence occurs, less and less chromosomes are subject to this increased mutation rate. However, if the landscape changes significantly, other chromosomes not affected by genetic operators come in to play. Those with the non-phenotype gene will increase the mutation probability rate once again, until the GA converges towards the new solution. The process will continue in this manner at every significant change in landscape. This Auto-Mutation process is explained in greater detail in Watsons paper (see References below).

In this example, the last gene is assumed to be the non-phenotype gene. In order to use this operator, simply create a chromosome with an extra gene. Set this gene to a random value and do not use the gene to store information (non-phenotype gene).

Enjoy!

References

Watson, T. (2003) An Investigation into Cooperative Behaviour: Altrurism and Evolutionary Computing. Submitted in partial fulfillment of the requirements for the degree of Doctor Of Philosophy DeMontfort University 2003

This code and the supporting project is available from BitBucket.

using System;
using GAF;

namespace Operators
{
  public class SimpleOperator : IGeneticOperator
  {
    public void Invoke(Population currentPopulation, 
                       ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)
    {
      throw new NotImplementedException();
    }

    public int GetOperatorInvokedEvaluations()
    {
      throw new NotImplementedException();
    }

    public bool Enabled { get; set; }
  }
}

This code and the supporting project is available from BitBucket.

using System.Linq;
using GAF;
using GAF.Operators;

namespace Operators
{
  public class AutoMutate : BinaryMutate
  {
    private AutoMutateFactor _autoMutationFactorS;
    private readonly object _syncLock = new object();
    private int _geneCount;

    public AutoMutate(double mutationProbability, bool allowDuplicates)
      : base(mutationProbability, allowDuplicates)
    {
    }

    public override void Invoke(Population currentPopulation, ref Population newPopulation,
      FitnessFunction fitnesFunctionDelegate)
    {
      _geneCount = newPopulation.ChromosomeLength;
      base.Invoke(currentPopulation, ref newPopulation, fitnesFunctionDelegate);
    }

    protected override void Mutate(Chromosome chromosome, double mutationProbability)
    {
      //adjust and scale for AutoMutate Factor based on the value of the last gene
      var newMutationProbability = 0.0;
      var nonPhenotypeGene = chromosome.Genes.ElementAt(_geneCount - 1);

      if (nonPhenotypeGene.BinaryValue == 1)
      {
        newMutationProbability = mutationProbability * (int)AutoMutationFactor;
      }
      else
      {
        newMutationProbability = mutationProbability;
      }
      base.Mutate(chromosome, newMutationProbability);
    }

    public AutoMutateFactor AutoMutationFactor
    {
      get
      {
        lock (_syncLock)
        {
          return _autoMutationFactorS;
        }
      }
      set
      {
        lock (_syncLock)
        {
          _autoMutationFactorS = value;
        }
      }
    }
  }
}

This code and the supporting project is available from BitBucket.

namespace Operators
{
  public enum AutoMutateFactor
  {
    None = 1,
    Factor5 = 5,
    Factor10 = 10,
    Factor20 = 20,
    Factor50 = 50
  }
}