Class 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.

    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 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