The Genetic Algorithm Framework – Part 2

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

Introduction

The GAF is a GA framework that makes it easy to create and modify Genetic Algorithms, It was written from first principles in 2013 in order to fully understand the workings of GA systems. The GAF was part of a project run in conjunction with the De Montfort University, Leicester, UK. The GAF brings all of that GA science and functionality to your project in an extremely easy to use form.

click here for further details.

Creating and Testing a GA

In order to create a simple GA and test it, we need a problem to solve. If we are testing the GA, we really need a problem that we already know the answer to. In line with many researchers, the problem we will solve with this example is the Binary F6 function. Details of the Binary F6 function can be found all over the internet, however, for our purposes all we need to understand is that this is a difficult problem to solve using traditional approaches.

Binary F6

Binary F6 3D Plot

A 3D plot of the Binary F6 function is shown here. It can be seen that there are many peaks and troughs within the overall plot. The mission for this example is to identify the values for X and Y that produces the minimum value for f(x,y). If all of this X,Y,Z stuff doesn’t make sense don’t worry it is not that important really.

I can tell you that a value of 0 for X and 0 for Y gives the minimum value for Z. Therefore, this is a problem that we know the answer to, this will allow us to test our GA.

If you are still puzzled as to why this is hard to solve and you are thinking, that you could just test each value for X and Y between the limits of -100 and +100 (as used in this example), i.e. use a ‘brute force’ approach, consider a situation where the range of X and Y lies somewhere between 0 and 23 billion. The non-linear shape of the curve (i.e. its ‘spikeyness’) means that other non-GA approaches struggle to identify the minimum and tend to get stuck in one of the other troughs (minima). Trust me, Binary F6 was made for GAs.

In order to test the GA I will be using three genetic operators. Elitism, Crossover and Mutation. It is worth noting that many systems often combine crossover and mutation into a single operator. The GAF treats them as two completely independent operators. In the next article I will describe these operators in more detail.

When developing GAs the fitness function is probably the single most important thing to get right. In future articles I will describe how to build fitness functions. However, for now at least, we will use the Binary F6 function as it helps us concentrate on developing the algorithm.

To get started, use the NuGet package manager to add the GAF to a project. In this example I used a Console Project.

PM> Install-Package GAF

The code below shows a Console Application that configures a GA to solve the Binary F6 function.

In example, two delegates are used. The first ‘EvaluateFitness’ is passed into the constructor of the GeneticAlgorithm class. The second, ‘TerminateAlgorithm’ is passed as an argument to the Run method. These delegate methods will be called when needed by the GAF.

In order to show the evolving solution, the example below subscribes to the GenerationComplete event. The code in this function displays X, Y and fitness from the best chromosome in each generation.

The results of the run show the final values for X and Y to be -0.00417 and -0.00069 respectively the final fitness value is 0.999982095862215.

The values for X and Y are very close to zero. Near enough is good enough in GA world. Enjoy!

Addendum:

Thanks to those who noticed that the BinaryF6 function as supplied in the original GAF Library is not actually all that good. The version shown in the Evaluation Function below is better.

This code and the supporting project is available from BitBucket.

using System;
using GAF;
using GAF.Operators;

namespace BinaryF6
{
  internal class Program
  {
    private static void Main(string[] args)
    {
      const double crossoverProbability = 0.85;
      const double mutationProbability = 0.08;
      const int elitismPercentage = 5;

      //create a Population of 100 random chromosomes of length 44
      var population = new Population(100, 44, false, false);

      //create the genetic operators 
      var elite = new Elite(elitismPercentage);

      var crossover = new Crossover(crossoverProbability, true)
      {
        CrossoverType = CrossoverType.SinglePoint
      };

      var mutation = new BinaryMutate(mutationProbability, true);

      //create the GA itself 
      var ga = new GeneticAlgorithm(population, EvaluateFitness);

      //subscribe to the GAs Generation Complete event 
      ga.OnGenerationComplete += ga_OnGenerationComplete;

      //add the operators to the ga process pipeline 
      ga.Operators.Add(elite);
      ga.Operators.Add(crossover);
      ga.Operators.Add(mutation);

      //run the GA 
      ga.Run(TerminateAlgorithm);
    }

    public static double EvaluateFitness(Chromosome chromosome) 
    {
      double fitnessValue = -1;
      if (chromosome != null)
      {
        //this is a range constant that is used to keep the x/y range between -100 and +100
        var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);

        //get x and y from the solution
        var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count / 2), 2);
        var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count / 2, chromosome.Count / 2), 2);

        //Adjust range to -100 to +100
        var x = (x1 * rangeConst) - 100;
        var y = (y1 * rangeConst) - 100;

        //using binary F6 for fitness.
        var temp1 = System.Math.Sin(System.Math.Sqrt(x * x + y * y));
        var temp2 = 1 + 0.001 * (x * x + y * y);
        var result = 0.5 + (temp1 * temp1 - 0.5) / (temp2 * temp2);

        fitnessValue = 1 - result;
      }
      else
      {
        //chromosome is null
        throw new ArgumentNullException("chromosome", "The specified Chromosome is null.");
      }

      return fitnessValue;
    }

    public static bool TerminateAlgorithm(Population population, int currentGeneration, long currentEvaluation)
    {
      return currentGeneration > 1000;   
    }

    private static void ga_OnGenerationComplete(object sender, GaEventArgs e)
    {

      //get the best solution 
      var chromosome = e.Population.GetTop(1)[0];

      //decode chromosome

      //get x and y from the solution 
      var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count/2), 2);
      var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count/2, chromosome.Count/2), 2);

      //Adjust range to -100 to +100 
      var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);
      var x = (x1 * rangeConst) - 100;
      var y = (y1*rangeConst) - 100;

      //display the X, Y and fitness of the best chromosome in this generation 
      Console.WriteLine("x:{0} y:{1} Fitness{2}", x, y, e.Population.MaximumFitness);
    }
  }
}

Leave a Reply

Your email address will not be published. Required fields are marked *