# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.optimization.multivariate.geneticalgorithm

## Class GeneticAlgorithm

• java.lang.Object
• com.numericalmethod.suanshu.optimization.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 are protected so any can be overridden to allow customization.

• 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 and 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 and Description
GeneticAlgorithm(RandomLongGenerator uniform)
Construct an instance of this implementation of genetic algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and 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.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### 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; if uniform 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 pool
children - 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