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 areprotectedso 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 booleanparallelThis indicate if the algorithm is to run in parallel (multi-core).protected List<Chromosome>populationThis is the (current) population pool.protected RandomLongGeneratoruniformThis 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 ChromosomegetBest(int i)Get the i-th best chromosome.protected ChromosomegetChild(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 ChromosomegetOne()Pick a chromosome for mutation/crossover.protected abstract booleanisConverged()This is the convergence criterion.protected intnChildren()Get the number of children before populating the next generation.protected intnPopulation()Get the size of the population pool, that is the number of chromosomes.voidrun()Run the genetic algorithm.protected Objectstep()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; ifuniformis 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:
trueif 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
-
-