Clone wiki

GAF / Getting Started

Getting Started

A Basic Genetic Algorithm

A genetic algorithm (GA) is best suited to a problem that doesn't require an exact answer, just a good (or better) answer. In addition, it is important that for a genetic algorithm to work, we need to be able to determine how good an answer is.

In summary, genetic algorithms are best suited to problems that can be summed up by the the terms <em>'near enough is good enough'</em> and <em>'knowing a good answer when you see one'</em>.

Fitness and Termination

Fitness refers to the assessment of a solution provided by the genetic algorithm. For example if the GAF is being used to optimise the shape of a fan blade, the genetic algorithm will constantly present a collection of fan blade parameters to the fitness function for evaluation. If you are a developer using the GAF, the fitness function is where your effort should be focused.

The GAF simply requires that you create a fitness function in the following form. The method name is unimportant, but the signature is. The contents of this function are determined by the developer.

 private double CalculateFitness(Chromosome chromosome)
 {
   //calculate fitness 
   //...

   return fitness;
 }

This function is passed to the GAF as a delegate during initialisation and will be called by the GAF when the GAF needs to evaluate a solution. Solutions in this context are passed to the fitness function using the Chromosome type. The value returned by the fitness function should be set to a real number between 0 and 1, with 1 being the fittest.

Stopping the genetic algorithm, hopefully once it has a suitable solution to the problem, is carried out by the Terminate function. This function is also provided by the developer and passed to the GAF as a delegate. It will be called periodically by the GAF. Returning 'true' from this function will terminate the running genetic algorithm. It should take the following form.

private bool TerminateFunction(Population population, 
    int currentGeneration, 
    long currentEvaluation) 
{ 
  //determine criteria on which to terminate
  //...

  return result; 
}

These two functions, as delegates, will be called by the GAF as needed. but with the parameters populated. For example, the Fitness function will pass a populated Chromosome object to be evaluated. Similarly the terminate function will be populated with the current population, the current generation and the number of evaluations so far. The following example would terminate the algorithm after 40000 evaluations.

private bool TerminateFunction(Population population, 
    int currentGeneration, 
    long currentEvaluation) 
{ 
  //example termination criterion 
  return currentEvaluation >= 40000; 
}

Population

Before the GA can be initialised, a population needs to be defined. Full details of the Population object are shown in the following sections of this documentation. However, in order to show how simple this can be, the code below initialises a random binary population of 100 solutions each with a binary chromosome length of 44 bits.

//randomly generated population 
population = new Population(100, 44);

Once the population has been defined, the genetic algorithm can be initialised.

var ga = new GeneticAlgorithm(population, FitnessFunction);

Subscribing to Generation and Run Events

To monitor progress of the algorithm, several events are available. The two main events are OnGenerationComplete and OnRunComplete.

ga.OnGenerationComplete += ga_OnGenerationComplete;
ga.OnRunComplete += ga_OnRunComplete;

Genetic Operators

Before the GA can be run, Genetic Operators need to be determined and added to the Operators collection. The GAF include many operators, these are detailed in the following sections of this documentation. The code shown below configures and adds three operators to the GA (Elite, Crossover, Binary Mutate) and adds them to the Operators collection..

elite = new Elite(5%);

crossover = new Crossover(0.85)
{ 
   CrossoverType = CrossoverType.DoublePoint
};

mutate = new BinaryMutate(0.04);

ga.Operators.Add(elite); 
ga.Operators.Add(crossover); 
ga.Operators.Add(mutate);

Once all of the components are in place, the GA can be run.

ga.Run(TerminateFunction);

Solving the Binary F6 Function

To see a concrete example of how the GA fits together, please see the example, Solving the Binary F6 Function.

Threading Considerations

Delegates and Events

When using the GAF it is important to note that the Fitness and Terminate delegates and the various events of the GAF are not guaranteed to be called on the main thread. This is particularly the case if the Population is configured to evaluate the Chromosomes in parallel (see Chromosomes and Genes).

Therefore, if updating UI components or accessing widely scoped variables, care needs to be taken. Below is an example of the approach that can be taken to ensure that any updates to a Windows Forms UI are called on the main thread.

private delegate void UpDateUICallback();

public void UpdateUI()
{
  if (this.InvokeRequired)
  {
    var callBack = new UpDateUICallback(UpdateUI);
    this.Invoke(callBack);
  }
  else
  {
    // Update UI here
  }
}

Parameters

All of the GAF parameters, and the parameters of the built-in genetic operators, are thread safe. This allows the GAF to be run on a separate thread to that of the consuming process whilst at the same time allowing modification of the parameters while te GA is running.

See Also
Getting Started Population
Chromosomes and Genes Genetic Operators
Events Fitness and Termination
Examples The GAF Evaluation Server
Evaluating using Docker Swarm

Updated