Class GeneticAlgorithm
- java.lang.Object
-
- dev.nm.solver.multivariate.geneticalgorithm.GeneticAlgorithm
-
- Direct Known Subclasses:
SimpleGridMinimizer.Solution
public abstract class GeneticAlgorithm extends Object
A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. A population of strings (called chromosomes or the genotype of the genome), which encode candidate solutions to an optimization problem, evolves toward better solutions. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached. This implementation is the meta evolutionary algorithm in the reference. It provides a framework for implementing multiple classes of evolutionary algorithms, e.g., Genetic Algorithm, Differential Evolution. All methods areprotected
so any can be overridden to allow customization.- See Also:
- Wikipedia: Differential evolution
- "Kenneth Price, Rainer M. Storn, Jouni A. Lampinen, "Fig. 1.15, Meta-algorithm for evolution strategies (ESs)," Differential Evolution: A Practical Approach to Global Optimization, 2005."
-
-
Field Summary
Fields Modifier and Type Field Description protected boolean
parallel
This indicate if the algorithm is to run in parallel (multi-core).protected List<Chromosome>
population
This is the (current) population pool.protected RandomLongGenerator
uniform
This is a uniform random number generator.
-
Constructor Summary
Constructors Constructor Description GeneticAlgorithm(RandomLongGenerator uniform)
Construct an instance of this implementation of genetic algorithm.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected Chromosome
getBest(int i)
Get the i-th best chromosome.protected Chromosome
getChild(int i)
Produce a child chromosome.protected abstract List<? extends Chromosome>
getFirstGeneration()
Initialize the first population.protected static ArrayList<Chromosome>
getNewPool(int size)
Allocate space for a population pool.protected List<Chromosome>
getNextGeneration(List<Chromosome> parents, List<Chromosome> children)
Populate the next generation using the parent and children chromosome pools.protected Chromosome
getOne()
Pick a chromosome for mutation/crossover.protected abstract boolean
isConverged()
This is the convergence criterion.protected int
nChildren()
Get the number of children before populating the next generation.protected int
nPopulation()
Get the size of the population pool, that is the number of chromosomes.void
run()
Run the genetic algorithm.protected Object
step()
Run a step in genetic algorithm: produce the next generation of chromosome pool.
-
-
-
Field Detail
-
parallel
protected final boolean parallel
This indicate if the algorithm is to run in parallel (multi-core).
-
uniform
protected final RandomLongGenerator uniform
This is a uniform random number generator.
-
population
protected final List<Chromosome> population
This is the (current) population pool. An implementation must guarantee that this is sorted in descending order.
-
-
Constructor Detail
-
GeneticAlgorithm
public GeneticAlgorithm(RandomLongGenerator uniform)
Construct an instance of this implementation of genetic algorithm.- Parameters:
uniform
- a uniform random number generator; ifuniform
is a ThreadIDRNG, the simulations will run in parallel
-
-
Method Detail
-
getFirstGeneration
protected abstract List<? extends Chromosome> getFirstGeneration()
Initialize the first population.- Returns:
- the first population
-
isConverged
protected abstract boolean isConverged()
This is the convergence criterion.- Returns:
true
if the search has converged
-
run
public void run()
Run the genetic algorithm.
-
step
protected Object step()
Run a step in genetic algorithm: produce the next generation of chromosome pool.- Returns:
- true
-
getChild
protected Chromosome getChild(int i)
Produce a child chromosome. This implementation first applies the crossover and then the mutation operators.- Parameters:
i
- an index that ranges from 0 to (population size - 1)- Returns:
- a child chromosome
-
getOne
protected Chromosome getOne()
Pick a chromosome for mutation/crossover. This implementation uniformly and randomly chooses from the population.- Returns:
- a chromosome
-
getNextGeneration
protected List<Chromosome> getNextGeneration(List<Chromosome> parents, List<Chromosome> children)
Populate the next generation using the parent and children chromosome pools. This implementation chooses the best chromosomes among the parents and children.- Parameters:
parents
- the parent chromosome poolchildren
- the children chromosome pool- Returns:
- the next generation population
-
nPopulation
protected int nPopulation()
Get the size of the population pool, that is the number of chromosomes.- Returns:
- the population size
-
nChildren
protected int nChildren()
Get the number of children before populating the next generation. In this implementation, it is the same as the population size (same as the number of parents).- Returns:
- the number of children
-
getBest
protected Chromosome getBest(int i)
Get the i-th best chromosome.- Parameters:
i
- an index- Returns:
- the i-th best chromosome
-
getNewPool
protected static ArrayList<Chromosome> getNewPool(int size)
Allocate space for a population pool.- Parameters:
size
- the population size- Returns:
- a population pool
-
-