Introduction
Introduction
Genetics4j uses a standard version of Genetic Algorithms. However many steps are highly configurable.
Here is a diagram of the main flow:
This is a standard flow for a genetic algorithm. At each generation, we will select some parents who will then generate some offsprings that will be mutated. And finally, a new generation will be created as defined by the replacement strategy from both offsprings and previous generation. The process will stop as soon as the termination conditions are met.
Concepts
Genotype
An individual, which represent a solution, is called a genotype. A genotype can be composed of multiple chromosomes of different nature. A chromosome can encode data in different ways:
-
Binary representation
-
Integer values
-
Real values
-
Tree
-
Linear sequences (Genetic Programming)
The genotype is defined through the Evolutionary Algorithm Configuration class where one can define the ChromosomeSpecs class
Chromosomes
The core module provides the following types of chromosomes out of the box:
-
Bits based chromosomes. See BitChromosomeSpec
-
Integer based chromosomes. See IntChromosomeSpec
-
Float based chromosomes. See FloatChromosomeSpec
-
Double based chromosomes. See DoubleChromosomeSpec
Fitness
Fitness of an individual establish of good of a solution it is. It can be of any type as long as it extends java.lang.Comparable. Which means one could use a Double for a single measure of the fitness as well as more complex data structures for cases such as Multi-Object Optimizations.
The fitness function is established in the EAConfiguration class
Population Generation
Individuals are generated based on their chromosomes' definitions. Each chromosome ships with a default factory. Chromosome factories are defined as ChromosomeFactory, which are configured in the ChromosomeFactoryProvider, which itself is configured in the method chromosomeFactoryProvider() of EAExecutionContext
One could override the way Individuals are generated through either:
-
Specify a generation method in populationGenerator()
-
Provide their own ChromosomeFactoryProvider in EAExecutionContext
Selection Policy
The goal of a SelectionPolicy is to select a set of individuals. It is an important piece of an Evolutionary Algorithm as it helps apply pressure towards the desired goal.
The current set of available selection policies are:
-
DoubleTournament - It implements a double tournament as specified in the paper Fighting Bloat With Nonparametric Parsimony Pressure [fbwnpp]. It is used in Genetic Programming to control bloat by combining tournaments based on fitness with tournaments based on parsimony.
-
MultiSelections - This is a wrapper for combining multiple selection policies. The set of individuals to select will be equally spread across each selection policy
-
MultiTournaments - This operator enables to chain multiple Tournaments
-
ProportionalTournament - It implements a proportional tournament as specified in the paper Fighting Bloat With Nonparametric Parsimony Pressure [fbwnpp]. It is used in Genetic Programming to control bloat by combining tournaments based on fitness with tournaments based on parsimony.
-
RandomSelection - Randomly select individuals with a uniform distribution
-
RouletteWheel - Also called Fitness Proportionate Selection where the probability of selection of an individual is proportionate to its fitness
-
SelectAll - Pass through and will select whatever individuals it can fit in
-
Tournament - It implements k-tournament selection where k invidivuals are picked from the population and the fittest one is selected. Selection pressure will vary bases on the value of k
Combination Policy
The goal of a CombinationPolicy is to combine two individuals and create zero, one or more offsprings.
The current set of available combination policies are:
-
SinglePointCrossover - A random cut is made, separating each parent in half. Offsprings are created by combining each halves
-
MultiPointCrossover - This is an extension of the Single Point Crossover where n cuts are made and the offsprings are created by combining each sections
-
OrderCrossover (OX) - This operator assumes a path representation in the chromosome and construct an offspring by selecting a subtour in one parent and preserving the relative order of the other parent. This is only available for chromosomes of type IntChromosomeSpec
-
PickFirstParent - The first parent is always chosen as the offspring
-
EdgeRecombinationCrossover (ERX) - This operator assumes a path representation in the chromosome and construct an offspring with the aim of preserving the edges from the parents as much as possible. This is only available for chromosomes of type IntChromosomeSpec
-
MultiCombinations- This is a wrapper for combining multiple combination policies. It will select a combination policy randomly with a uniform distribution
Mutation
The goal of a MutationPolicy is to maintain diversity and allow undirected jumps to slightly different areas of the search space.
The current set of available mutation policies are:
-
RandomMutation - Randomly change a value of the chromosomes. It might be flipping bits in the case of bit chromosomes or changing to a different value for int chromosomes
-
SwapMutation - Randomly change two values of the chromosomes
-
PartialMutation - Apply a MutationPolicy for a very specific chromosome of the genotype
-
MultiMutation - This is a wrapper for combining multiple mutation policies. It will select a mutation policy randomly with a uniform distribution
Termination
Termination responsibility is determine whether or not the evolution process should continue or not. Termination conditions could be based on any criteria, be it computation time, diversity in the population, reaching a specific fitness value or a combination of those.
Terminations is a helper class which provides a few out of the box helpful termination conditions.
Replacement Strategy
The replacement strategy is crucial for driving the process as it specifies how to generate the next generation based on the current population and the offsprings.
The current set of available replacement strategies are:
-
Elitism - The best individuals of respectively, the current generation and the mutated offsprings, are retained for the next generation.
-
GenerationalReplacement - The best individuals of the mutated offsprings are retained for the next generation and the current population is discarded.
-
DeleteNLast - The N weakest invidivuals of the current population are discarded and replaced by the best offsprings.