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.

Wiki

GAF / Population