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; }
nextGeneration
method implements the following algorithm:
current
generation, using its nextGeneration methodSelectionPolicy
to select a pair of parents
from current
CrossoverPolicy
to parentsMutationPolicy
to each of the offspringHere 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();
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. |
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.