The Genetic Algorithm Framework – Part 3

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Genetic Operators

In the previous post, I presented an example GA that solved the tricky Binary F6 function. In that example, three Genetic Operators were used. In this article, I will look more closely at each of these.

In the previous article, I created an initial population of 100 chromosomes (solutions), this represented the first generation of chromosomes. These were then subjected to three genetic operators in turn, once complete, we were left with a new generation. This process was repeated for many generations until an answer to the problem emerged. The order in which each operator is added to the process pipeline determines the order in which each operator is applied. The order was Elite, Crossover, Binary Mutate.

The initial population was created with the following line of code.

var population = new Population(PopulationSize, ChromosomeLength, false, false);

In the Binary F6 example, the population size was 100 and the chromosome length (number of binary digits or ‘Genes’) was 44. The remaining parameters (set to false in the example) can be ignored for now. They relate to noisy environments and Linear Normalisation. Both of these will be discussed in future articles.

Elite

Elitism allows the best solutions to pass through to the next generation without being modified. The Binary F6 example used a value of 5 percent, which, with a population of 100, means that the top 5 chromosomes form part of the next generation. This means that any future generation is at least as good as the current generation. Elitism 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, thereby reducing the performance of the GA. This is normal behaviour for an approach that does not explicitly handle duplicates, and is simply due to the convergence of the algorithm. If you want to experiment with this value, I would recommend a value somewhere between 5 and 10 percent as a starting point.

To create an Elite operator and add it to the GA, the following code can be used.

var elite = new Elite(elitismPercentage); 
ga.Operators.Add(elite );

The Elite operator takes a single parameter in its constructor, the percentage. Chromosomes identified as elite are marked as such. This means that operators later in the pipeline such as Mutate or any that you create yourself, know not to modify these chromosomes. The IsElite property returns the elite status of a chromosome.

bool eliteStatus = myChromosome.IsElite;

Crossover

The crossover operator within the GAF can handle singe or double point crossover. The example in the previous post crossed parent chromosomes at a single point. In many cases, selecting two points and swapping the center section between parents is more appropriate. Single or double point can be selected via a property as shown below.

var crossover = new Crossover(crossoverProbability, true) 
{ 
    CrossoverType = CrossoverType.SinglePoint;
    ga.Operators.Add(crossover);
}

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. The second parameter relates to duplicate handling and should be set to ‘true’ for now. When experimenting with crossover probability, a good starting point would be somewhere between 0.65 and 1.

Binary Mutate

This operator scans each bit (gene) of each chromosome and, based on a probability factor, will toggle the bit (from 1 to 0 or from 0 to 1). Typically the mutation probability is very low, for example 0.02, which means that mutation only occurs occasionally. The mutation operator is used to ensure there is some diversity in the population. Diversity will be covered later in the article.

var mutation = new BinaryMutate(mutationProbability, true); 
ga.Operators.Add(mutation);

The constructor of this operator accepts two parameters, the first is the mutation probability, the second relates to duplicate handling and should be set to ‘true’ for now.

The Binary Mutate operator will not mutate any chromosomes marked as ‘elite’. This ensures that the best solutions from the previous generation remain, unmodified, in the following generation.

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.

An Example

In an intelligent radio system such as the one described in the research detailed here, a GA is used to search for and track a radio signal that is jumping around the radio spectrum (channel hopping). A GA without the memory operator needs to re-converge on the new frequency for each channel hop of the radio transmitter. Adding the memory operator tries to ensures that if a channel is reused, it will be found in memory and will be added to the population causing the GA to instantly converge on the new frequency. 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 the performance. As with all of these things, experimentation will determine the best usage.

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);

Other Operators

The GAF contains other operators to those described above. These will be discussed in future articles.

Diversity

In order that a GA can find suitable solutions to the Binary F6 function, it has to search amongst all the possible solutions. In order to do this, some level of diversity amongst the population is required.

In our example diversity was primarily maintained through the use of the Binary Mutate operator. By swapping a binary digit (gene) of the chromosome every now and then, the operator has the potential to change the solutions X and Y values significantly. This allows completely different values to be tested. If these turn out to be good, the chromosome will be selected as a parent and more similar solutions will be created for the next generation. Every time a mutation happens, a new part of the search space is searched.

Maintaining a level of diversity is very important for a GAs performance. However, the level of diversity has to be balanced with the need to find suitable solutions through convergence.

Mutation is not the only way to maintain diversity. In later posts, I will discuss other replacement and complimentary options.