Genetic Operators

Crossover Operator

The Crossover class has many overloaded constructors, the following constructor represents the most comprehensive. Some of the parameters can be changed using properties of the class.

public Crossover (double crossOverProbability, 
                    bool allowDuplicates, 
                    CrossoverType crossoverType, 
                    ReplacementMethod replacementMethod)

Crossover Probability

The crossover probability is simply a value between 0 and 1 that represents the probability of parents crossing over to produce children. A value of 1 means that all selected parents will crossover and create children. A value of 0.85 means that 85% will be crossed over and the remainder of parents will be pass through untouched to the new generation. When experimenting with crossover probability, a good starting point would be somewhere between 0.65 and 1.

Duplicate Handling

The Crossover Operator can be configured to not allow duplicate solutions within the population. In some rare cases, this can be an advantage, however, this mode of operation is computationally expensive. In addition, a population without duplicates may prevent the GA from converging to an appropriate solution. In most situations the allowDuplicates parameter should be set to true. This is the default value.

Crossover Type

The crossover operator within the GAF can handle one of three types of crossover. Singe or double point crossover.

Single Point

A single random point is selected for each parent chromosome and one part is swapped between them.

Double Point

Two points are selected to determine a centre section in each parent, this is swapped between them.

Double Point Ordered

A single parent is used to create a child however the order of a second parent determines how the chromosome is arranged. This method only works with chromosomes that have a unique set of genes (by Value). For this to be usable custom object based genes required and the Equals method should be overriden within the gene definition to return a value.

Replacement Method

Generational Replacement

New solutions (Children) are created from existing solutions (Parents) and a new population is created.

Delete Last

Children created are used to replace the the weakest solutions in the current population.

The example code below creates a double point crossover operator with a crossover probability of 0.85 that allows duplicates.

var crossover = new Crossover(0.85, 
                                true, 
                                CrossoverType.DoublePoint, 
                                ReplacementMethod.GenerationalReplacement
                              );

Binary Mutate Operator

Although mutation is often closely associated with Crossover, within the GAF, mutation is seen as a first class citizen and is an operator in its own right.

The Binary Mutation Operator, traverses each gene in the population and, based on the probability, swaps a gene from one state to the other. The aim of this operator is to add diversity to the population. This operator cannot be used with genes of type Object.

Diversity is important in order that the best potential solution can be found within the landscape.

The BinaryMutate class constructor is shown below.

public BinaryMutate(double mutationProbability)

Duplicate Solutions

The Binary Mutate Operator can be set to not allow duplicate solutions within the population. If duplicates are not allowed and a mutation would introduce a duplicate solution, the mutation is not implemented.

Elite Operator

public Elite(int elitismPercentage)

Elitism allows a percentage of the best solutions within the population to pass through to the next generation without being modified. A typical value for percentage is 5 - 10%. For example, a percentage of 5% with a population of 100, means that the top 5 individuals form part of the next generation. This means that any future generation is at least as good as the current generation.

This helps protect good individuals. However, it can be shown that as the percentage of Elites is increased, the number of duplicates within the population increases. This is normal behaviour for an approach that does not explicitly handle duplicates and is simply due to the convergence of the algorithm.

The GAF uses a globally unique identifier (GUID) for each gene and each chromosome, the GUID can be used to trace the origin of the chromosome and its gene. This makes it easy to identify whether solutions that have the same value, are actually the same chromosome. This information can help optimise the GA in terms of diversity.

Each solution that is identified as an elite will have its ''IsElite'' property set to true.

This operator does not consider duplicates. To maintain a unique population, ensure that this operator is used before any operators that modify the solutions.

Swap Mutate Operator

public SwapMutate(double mutationProbability)

The Swap Mutate operator, traverses each gene in the population and, based on the specified probability swaps one gene in the chromosome with another. The aim of this operator is to provide mutation without changing any gene values.

Solving the Travelling Salesman Problem provides an example of using this operator.

Random Replace Operator

public RandomReplace(int percentageToReplace, bool allowDuplicates)

This operator will replace the weakest solutions in the new population with the selected amount (by percentage) of randomly generated solutions (Chromosomes) from the current population. Any chromosome marked as Elite will not be replaced. Therefore, 50% of a population of 100 that has 10 'Elites' will replace 45 solutions.

This operator only works with binary Chromosomes as it is simply not possible for this operator to generate custom defined solutions.

Memory Operator

This operator maintains a 'memory' of solutions and ensures that the best solution in that memory is included in the GA population if it is better than the best in the population. The memory is kept up to date with good solutions during the GA run.

For example, consider an intelligent radio system where a GA is used to search for and track a radio signal that is jumping around the radio spectrum such as a modern 'channel hopping' system. As the radio signal changes frequency (channel), a GA without the memory operator needs to re-converge on the new channel for each hop of the radio transmitter. Adding the memory operator tries to ensure that if a channel is re-used, the solution representing that channel will be found in memory and added to the population. This will reduce the need for the GA to re-converge on this previously used channel. If the current channel hasn't been used before, the GA will try and converge in the normal manner.

If the GA landscape is constantly changing such that the GA has to re-converge on a new solution, the memory operator could be used to improve its performance. The memory operator is specifically designed for use in cases where where good solutions can appear, disappear and re-appear over time. In these cases the GA has to maintain diversity in order to capture any new solutions that suddenly appear. The memory operator keeps hold of previous good solutions such that if a previous solution 're-appears' it will be found in memory very quickly.

The following code adds the memory operator to the GA, sets the memory capacity to 100 'memories' and specifies that the memory will be updated every 10 generations.

var memory = new Memory(100, 10);
ga.Operators.Add(memory);

Custom Operators

Introduction

There are two methods for producing a custom Genetic Operator for use with the GAF. The recommended option (method 1) is to derive a new Genetic Operator from either an existing one or from one of the operator base classes.

In cases where none of the operator base classes are appropriate, method 2 can be used. This involves creating a C# class that implements the GAF.IGeneticOperator interface.

Method 1 - Deriving a new Genetic Operator

The example Creating an Auto-Mutate Operator demonstrates how a custom genetic operator can easily be built by deriving a new Genetic Operator from an existing one.

Method 2 - Implementing IGeneticOperator

Implementing the IGeneticOperator interface is most flexible way to create a Genetic Operator. The class SimpleOperator in the code shown below shows the simplest example.

IGeneticOperator

public interface IGeneticOperator
{
    void Invoke(Population currentPopulation, 
                ref Population newPopulation, 
                FitnessFunction fitnesFunctionDelegate);

    int GetOperatorInvokedEvaluations();

    bool Enabled { set; get; }
    bool RequiresEvaluatedPopulation { get; set; }
}

SimpleOperator class

using GAF;

namespace Operators
{
    public class SimpleOperator : IGeneticOperator
    {
        public void Invoke(Population currentPopulation, 
                            ref Population newPopulation, 
                            FitnessFunction fitnesFunctionDelegate)
        {
            throw new NotImplementedException();
        }

        public int GetOperatorInvokedEvaluations()
        {
            throw new NotImplementedException();
        }

        public bool Enabled { get; set; }
        public bool RequiresEvaluatedPopulation { get; set; }
    }
}

Once the operator has been created it can be added to the Operators collection in the same way as the other built-in operators e.g.

ga.Operators.Add(simpleOperator)

The Invoke method will be called by the GAF and will present the current generations population (param: population) along with the next generation's population (param: newPopulation). Each operator is responsible for either taking some solutions from the current population and transferring them to the new population. The way in which this is done is left to the implementer of the operator. For example the Crossover Operator takes two solutions from the current population, performs a single or double point crossover, and places the two resulting 'children' into the new population.

The Enabled property should return a value of true (default). The RequiresEvaluatedPopulation property can be used to improve the overall performance of the GA. If the custom operator does not need a fully evaluated population set this to false. The default is true. For example the BinaryMutate and SwapMutate operators do not require the population to be evaluated for them to work, therefore, these operators return a value of false for this property. This helps reduces the number of evaluations undertaken by the GAF.

The GetOperatorInvokedEvaluations method is used by the GAF to determine the number of evaluations an operator invokes. Therefore, the method should return the number of evaluations that the operator undertakes for each invocation.

For example, the built-in Crossover operator evaluates the population to determine which individuals to select. However, the built-in Mutation operator does not perform any evaluations. If an operator performed a single evaluation of each member of a population of say 100 individuals, the GetOperatorInvokedEvaluation method would return 100. For an operator that does not perform any evaluations the GetOperatorInvokedEvaluation method would return 0.

Things to Bear in Mind

Ensure that the new population is not larger than the current population.
Elites passed into the new population by the Elite Operator will be marked with the 'IsElite' property set to true. These should not normally be interfered with by subsequent operators.
If the custom operator changes any existing chromosomes (as apposed to creating new ones), and will not be calling the Evaluate method on that chromosome, ensure that any existing fitness value is reset to zero as the existing value will no longer be valid. This will ensure that even if ReEvaluateAll is set to false, the chromosome will be correctly evaluated before the generation is complete.

References:

Watson, T. (2003) An Investigation into Cooperative Behaviour: Altrurism and Evolutionary Computing. ''Submitted in partial fulfilment of the requirements for the degree of Doctor Of Philosophy DeMontfort University 2003''

Wiki

GAF / Genetic Operators