Clone wiki

GAF / Population

Population

Introduction

The population represents the collection of possible solutions. The class has the following overloaded constructor.

public Population(int populationSize, 
            int chromosomeLength, 
            bool reEvaluateAll,
            bool useLinearlyNormalisedFitness, 
            ParentSelectionMethod selectionMethod,
            evaluateInParallel);

Population Size and Chromosome Length ==

For many genetic algorithm configurations, a binary string is used. These are typically initialised in a random manner. Specifying the population size and chromosome length in the constructor of the Population will generate the specified number of random
solutions (chromosomes) each with a binary string of the specified length.

The GAF is capable of handling chromosomes other than binary strings and it may not always be appropriate to start from a random population. In this case, a more appropriate population (collection of chromosomes) can be generated externally and passed to the Solutions property of the Population object. The example code below creates an empty population, the method ''CreateChromosomes()'' defined by the developer (not shown here) returns a List of Chromosome objects (List<Chromosome>) as the population.

var population = new Population();
var chromosomes = CreateChromosomes();

foreach (var chromosome in chromosomes)
{
  population.Solutions.Add(chromosome);
}

alternatively...

var population = new Population();

population.Solutions = CreateChromosomes();

Re-Evaluate All

Many GA problems are not noisy, that is, the fitness value would not change
if the solution were to be re-evaluated. In situations such as these, the evaluation
process can be optimised not to re-evaluate each solution at each generation.
The GAF handles this type of optimisation internally. However, in noisy environments,
environments where re-evaluating the same solution could produce a different fitness
from the previous evaluation, it is important to re-evaluate all solutions. The re-evaluate
parameter ensure this.

Linear Normalisation

Linear normalisation, as implemented within the GAF, simply orders the
solutions by decreasing evaluation, and creates a fitness based on this ordering.
For example for a population of 100, the fittest would be 1.0 and each subsequent
solution would decrease linearly in value down to the worst solution with a fitness
of 0. The starting point and decrement parameters of this approach are fixed
within the GAF.

Linear normalisation can be invoked by setting the useLinearlyNormalisedFitness
parameter to true in the constructor of the Population object.

Linearly normalising fitness helps maintain natural selection. Natural selection occurs
when the fittest individuals are selected as parents for the next generation, proportionally
to their fitness. However, in some problem domains, where the difference between the fitness
value of the fittest and others within the solution is very small, each has a similar
probability of being selected as a parent. By normalising the fitness of the population
between a minimum and maximum value natural selection can be improved. The GAF normalises
linearly between 0 and 1.0.

Parent Selection Method

At each generation, the population object is responsible for selecting parents when requested.
The method by which this is done can be controlled by the Parent Selection parameter.

Fitness Proportional Selection

This method is often referred to as Roulette Wheel selection The analogy to a roulette wheel
can be envisaged by imagining a roulette wheel
in which each candidate solution represents a section of the wheel. The size of the sections
are proportionate to the probability of selection of the solution. This means that fitter solutions
are more likely to be selected but all solutions have a chance.

Stochastic Universal Sampling

Stochastic Universal Sampling is a development of fitness proportionate selection.
Where FPS chooses several solutions from the population by repeated random sampling,
Stochastic Universal Sampling uses a single random value to sample all of the solutions
by choosing them at evenly spaced intervals. This gives weaker members of the population
a better chance of being chosen.

Tournament Selection

Tournament selection involves executing several "tournaments" using individuals chosen
at random from the population. The winner of each tournament is selected.

Parallel Evaluation

The population object is responsible for calling the user specified fitness function. This function will be called for each solution in the population. In some systems there may be a performance benefit in
using the .Net Parallel Task Library to evaluate the population. Since version 2.2.1, a constructor argument (and/or property) of the
population object can be used to control this behaviour. Where the target framework does not support the Parallel Task Library
e.g. PCL profiles, this argument/property has no effect.

In some cases operators can perform evaluations for example the Memory Operator and Crossover when configured
to use the Delete Last replacement method perform evaluations before adding children to the population. The specific
operator invoked evaluations such as these are not conducted in parallel.

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

Updated