14 Genetic Algorithms

14.1 Overview

The genetics package provides a framework and implementations for genetic algorithms.

14.2 GA Framework

org.apache.commons.math.genetic.GeneticAlgorithm provides an execution framework for Genetic Algorithms (GA). Populations, consisting of Chromosomes are evolved by the GeneticAlgorithm until a StoppingCondition is reached. Evolution is determined by SelectionPolicies, MutationPolicies and Fitness.

The GA itself is implemented by the evolve method of the GeneticAlgorithm class, which looks like this: 

public Population evolve(Population initial, StoppingCondition condition) {
    Population current = initial;
    while (!condition.isSatisfied(current)) {
        current = nextGeneration(current);
    }
    return current;
}
The nextGeneration method implements the following algorithm:
  1. Get nextGeneration population to fill from current generation, using its nextGeneration method
  2. Loop until new generation is filled:
    • Apply configured SelectionPolicy to select a pair of parents from current
    • With probability = getCrossoverRate(), apply configured CrossoverPolicy to parents
    • With probability = getMutationRate(), apply configured MutationPolicy to each of the offspring
    • Add offspring individually to nextGeneration, space permitting
  3. Return nextGeneration

14.3 Implementation

Here is an example GA execution: 

// initialize a new genetic algorithm
GeneticAlgorithm ga = new GeneticAlgorithm(
    new OnePointCrossover<Integer>(),
    1,
    new RandomKeyMutation(),
    0.10,
    new TournamentSelection(TOURNAMENT_ARITY)
);
        
// initial population
Population initial = getInitialPopulation();
        
// stopping condition
StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
        
// run the algorithm
Population finalPopulation = ga.evolve(initial, stopCond);
        
// best chromosome from the final population
Chromosome bestFinal = finalPopulation.getFittestChromosome();
The arguments to the GeneticAlgorithm constructor above are:
Parameter value in example meaning
crossoverPolicy OnePointCrossover A random crossover point is selected and the first part from each parent is copied to the corresponding child, and the second parts are copied crosswise.
crossoverRate 1 Always apply crossover
mutationPolicy RandomKeyMutation Changes a randomly chosen element of the array representation to a random value uniformly distributed in [0,1].
mutationRate .1 Apply mutation with probability 0.1 - that is, 10% of the time.
selectionPolicy TournamentSelection Each of the two selected chromosomes is selected based on an n-ary tournament -- this is done by drawing n random chromosomes without replacement from the population, and then selecting the fittest chromosome among them.

The algorithm starts with an initial population of Chromosomes. and executes until the specified StoppingCondition is reached. In the example above, a FixedGenerationCount stopping condition is used, which means the algorithm proceeds through a fixed number of generations.