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