Evolutionary Operators

This page focuses on details regarding the configuration and usage of Crossover, Mutation, and Selection in Evolutionary Algorithm.

Mutation

Mutation is a phase in the algorithm responsible for introducing new genetic material. In terms of searching the solution space, it facilitates the exploration of new areas. The mutation operator is unary, as it takes one Individual and makes a small modification to it. For example, it might change the value of one parameter to another.

The following configuration parameters for the default Mutation class are available in the engine:

MutationPhaseRate - the probability that the mutation phase will occur in an iteration. This is the first check regarding the mutation - if equal to FALSE then no further actions regarding mutation will be done in the current iteration (epoch) of the algorithm. The default value is 1.0 which means that mutation is enabled.
RandomResolutionTypeForIndividual - the formula of selecting individuals for mutation. Two options are possible: {ITERATE_AND_TEST_P, SELECT_P_OF_N}. The default value is SELECT_P_OF_N.
1. ITERATE_AND_TEST_P - a loop will iterate over individuals and mutate each one with a probability equal to MutationIndividualRate. This method applies a series of independent random tests.
2. SELECT_P_OF_N - the number equal to MutationIndividualRate*PopulationSize clamped to the [0, PopulationSize] interval will be selected for mutation. This ensures that the expected number of individuals will be mutated, regardless of RNG.
MutationIndividualRate - probability that an individual will mutate (provided that the mutation happens in the current iteration). See above how this parameter interferes with RandomResolutionTypeForIndividual. The default value is 0.09. This means that approximately 9% of the population will be mutated provided that the probability of the mutation phase is left as default of 1.0.
MutationGeneRate - probability that a gene (one parameter) of an individual that designated for mutation will change. A vector of genes makes the encoding of an individual. The default value is 0.5. This means that once a given Individual is chosen for mutation, half of its parameters will be mutated.
RandomResolutionTypeForGene - an analogous to RandomResolutionTypeForIndividual but this time for selecting genes from a individual rather than individuals from the population.
MutateBothParentsAndChildren - if TRUE, then both individuals from the previous population and children can be mutated. If FALSE, then only the individuals after crossover can be mutated. The default value is TRUE.

Custom Mutation Implementation

It is recommended to use the ready-to-use default Mutation object. However, if you want to provide your own implementation, then inherit from Mutation and you can choose at which point you want to change the default procedure.

You can override the following virtual methods:

MutateGene(individual, gene) - if you only want to change the procedure of making a random modification to the selected parameter (gene). The default implementation assigns a random value from the parameter’s domain with a uniform probability.
MutateIndividual(individual) - if you want to change how the whole Individual is mutated. If you override this method, then the default MutateGene method will not be called, but you can call it manually on selected parameters.
Perform() - if you want to change the logic of the entire mutation phase. If you override this method, both MutateIndividual and MutateGene will not be called unless you manually do so on selected individuals and genes.

Crossover

Crossover, also known as recombination, is a phase in the algorithm responsible for exploiting the best solutions found so far. The crossover operator takes two individuals and combines their parts to produce offspring. The premise is that combining the fittest individuals is likely to produce even better-fit children. There are many crossover operators. The idea and some of the examples are shown below:

The following configuration parameters for the default Crossover class are available in the engine:

CrossoverPhaseRate - probability that the crossover phase will occur in an iteration. This is the first check regarding the crossover - if equal to FALSE then no children population will be produced. The default value is 1.0 which means that crossover is enabled.
CrossoverSelectionType - the way of choosing individuals for crossover. The default value is PSEUDO_ROULETTE.
1. RANDOM - each individual that undergoes crossover is selected using a uniform random distribution.
2. ROULETTE - individuals that will be recombined together are selected using weighted random distribution proportional to their Fitness values.
3. TOP - only the best fit individuals are chosen for crossover. There is no randomness here.
4. PSEUDO_ROULETTE - PseudoRouletteRandomPortion * PopulationSize of individuals will be chosen at random and the rest according to the roulette wheel selection.
5. CONSECUTIVE_PAIRS - in this method, an i-th individual will be recombined with the (i+1)-th individual according to the current ordering of the population. The ordering is arbitrary, not performed by fitness. Here the CrossoverIndividualRate parameter is ignored, meaning that each individual (if the population size is even) will participate in the crossover. If the population size is odd, then the last individual will not be used in the crossover. This is a rather unusual procedure that sometimes works.
PseudoRouletteRandomPortion - used if CrossoverSelectionType = PSEUDO_ROULETTE. The default value is 0.3. From the individuals that will recombine, this portion will be chosen at random.
CrossoverIndividualRate - the average rate of crossover. If N is the PopulationSize, then the expected number of children is equal to N * CrossoverIndividualRate. The default value is 0.45.

Custom Crossover Implementation

It is recommended to use the ready-to-use default Crossover object and optionally spend some time fine-tuning its hyper-parameters. However, if you want to provide your own implementation, then inherit from Crossover.

When inheritting from Crossover, override the virtual CrossoverIndividuals(individual1, individual2) method.

In this method, implement custom logic of exchanging genetic information between individual1 and individual2. Do not hesitate to modify the individual1 and individual2 instances, as these are clones of the parents and will not affect them.

The default implementation calls a protected CrossoverFunction_Multipoint method that represents the two-point crossover operation (see the picture above). It chooses the two points (the start and the end) for the operation at random. Additionally, there is a CrossoverFunction_Onepoint method you can call in your custom implementation, instead. It also chooses its crossover point at random.

Selection

The goal of the Selection is to choose individuals from one generation to the next one.

The default Selection object ranks all the individuals by the Fitness value. Then it selects the top N most fit ones, where N is the expected population size.

If such a logic is insufficient for your needs, you can derive from the Selection class and implement its only method called Perform(currentPopulation, populationMaxSize).

currentPopulation - the input population before the selection. For your convenience, it will already be sorted by fitness.
populationMaxSize - the maximum size the population is expected to be after the selection.

The default implementation is:

class Selection
{
public:
	virtual ~Selection();
	virtual void Perform(std::vector<std::unique_ptr<Individual>>& currentPopulation, size_t populationMaxSize);
};

void Selection::Perform(std::vector<std::unique_ptr<Individual>>& currentPopulation, size_t populationMaxSize)
{
	if(currentPopulation.size() > populationMaxSize)
	{
		currentPopulation.resize(populationMaxSize);
	}
}

public class Selection
{
	public virtual List<Individual> Perform(List<Individual> currentPopulation, int populationMaxSize)
	{
		var countToRemove = currentPopulation.Count - populationMaxSize;
		if (countToRemove > 0)
		{
			currentPopulation.RemoveRange(0, countToRemove);
		}

		return currentPopulation;
	}
}

For example, if you want to implement a roulette wheel selection, then use the RouletteSampler<T> class available in the grail::evolution (C++) and Grail.Evolution (C#) namespaces, respectively.

If your population is not diverse enough, you might consider clustering the individuals based on their differences and choosing the fittest ones from different clusters.

API Reference

Crossover
Mutation
Selection
RouletteSampler