Clone wiki

GAF / Solving the Binary F6 Function

Solving the Binary F6 Function

In order to create a simple GA and test it, a problem is required to be solved, in particular a problem that where the answer is already known. In line with many researchers, the problem selected for 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 that is required is to understand and accept that this is a difficult problem to solve using traditional approaches.

F63dplot1_550x323.jpg

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 aim of the GA produced in this example is to identify the values for X and Y that produces the minimum value for f(x,y).

In this example three genetic operators will be used. [[Genetic Operators#Elite Operator|Elite Operator]], [[Genetic Operators#Crossover Operator|Crossover Operator]]. and [[Genetic Operators#Binary Mutate Operator|Binary Mutate Operator]]. 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.

When developing GAs the fitness function is probably the single most important thing to get right. For this example the the Binary F6 function will be used to see how close the GAs values for X and Y get to the minimum value (i.e. 0).

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

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

This code and the compiled assembly is available via Docker and 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);
        }
    }
}

Updated