Orbital library

orbital.algorithm.evolutionary
Class GeneticAlgorithm

java.lang.Object
  extended by orbital.algorithm.evolutionary.GeneticAlgorithm
All Implemented Interfaces:
java.io.Serializable, AlgorithmicTemplate, ProbabilisticAlgorithm
Direct Known Subclasses:
IncrementalGeneticAlgorithm, SimpleGeneticAlgorithm, SteadyStateGeneticAlgorithm

public abstract class GeneticAlgorithm
extends java.lang.Object
implements ProbabilisticAlgorithm, AlgorithmicTemplate, java.io.Serializable

A base class for genetic algorithms. Genetic algorithms can be used as an evolutionary search algorithm exploring (with a large population) or exploiting (with a small population) an almost arbitrary search space.

A genetic algorithm provides the following operators:

After implementing the GeneticAlgorithmProblem interface use the evolutionary genetic algorithm like:

 Configuration config =
     new GeneticAlgorithm.Configuration(geneticAlgorithmProblem,
         Selectors.rouletteWheel(),
         maximumRecombination,
         maximumMutation,
         IncrementalGeneticAlgorithm.class);
 Population solution = (Population) config.solve();
 
Or, if you need any additional control of the single steps, use something like:
 ga = new IncrementalGeneticAlgorithm();
 ga.setEvaluation(fitnessEvaluation);
 ga.setSelection(Selectors.rouletteWheel());
 ga.setPopulation(initialPopulation);
 PopulationImpl pop = (PopulationImpl) ga.getPopulation();
 pop.setParentCount(2);
 pop.setChildrenCount(2);
 pop.setMaximumRecombination(maximumRecombination);
 pop.setMaximumMutation(maximumMutation);
 // evolve until stop condition
 while (!isSolution()) {
     ga.evolve();
     System.out.println(ga.getPopulation());
 }
 
With a problem-specific implementation of the stop condition isSolution() which could simply consider the number-of-generations, goodness-of-best-solution or convergence-of-population.

Author:
André Platzer
See Also:
GeneticAlgorithmProblem, HillClimbing, Random, "Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning. .1989.", "Friedberg, R.M. A learning machine: Part I. IBM Journal, 2:2-13, 1958.", "Holland, J. H. Adaption in Natural and Artificial Systems. University of Michigan Press. 1975.", Serialized Form
Invariants:
sub classes must support nullary constructor (for cloning)
Structure:
delegate population:Population, delegate selection:Function

Nested Class Summary
static class GeneticAlgorithm.Configuration
          Algorithmic configuration objects for genetic algorithms.
 
Constructor Summary
protected GeneticAlgorithm()
          Construct a new GeneticAlgorithm.
 
Method Summary
 java.lang.Object clone()
          Returns a deep copy of this exact type of genetic algorithm.
 Function complexity()
          Measure for the asymptotic time complexity of the central solution operation in O-notation.
 boolean equals(java.lang.Object o)
           
abstract  void evolve()
          evolves to the next generation for this population.
 Function getEvaluation()
          Get the evaluation function.
 Population getPopulation()
          Get the Population for this GeneticAlgorithm.
abstract  double getPopulationGrowth()
          Get the population growth factor.
 java.util.Random getRandom()
          Get the random-generator used as probabilistic random source.
 Function getSelection()
          Get the selection scheme to apply while evolving.
 int hashCode()
           
 boolean isCorrect()
          Whether this algorithm is correct.
 void setEvaluation(Function fitnessEvaluation)
          Set the evaluation function.
 void setPopulation(Population pop)
          Set the Population for this GeneticAlgorithm.
 void setRandom(java.util.Random randomGenerator)
          Set the random-generator to use as probabilistic random source.
 void setSelection(Function selector)
          Set the selection scheme to apply while evolving.
 java.lang.Object solve(AlgorithmicProblem gproblem)
          Solve a genetic algorithm problem.
 Function spaceComplexity()
          Measure for the asymptotic space complexity of the central solution operation in O-notation.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

GeneticAlgorithm

protected GeneticAlgorithm()
Construct a new GeneticAlgorithm.

Method Detail

clone

public java.lang.Object clone()
Returns a deep copy of this exact type of genetic algorithm.

Overrides:
clone in class java.lang.Object

equals

public boolean equals(java.lang.Object o)
Overrides:
equals in class java.lang.Object

hashCode

public int hashCode()
Overrides:
hashCode in class java.lang.Object

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

getPopulationGrowth

public abstract double getPopulationGrowth()
Get the population growth factor.

Returns:
the factor by which the population size increases with each generation (or decreases if < 1).

getSelection

public Function getSelection()
Get the selection scheme to apply while evolving.


setSelection

public void setSelection(Function selector)
Set the selection scheme to apply while evolving.

Parameters:
selector - the selection function Population→Genome for selecting parents.
See Also:
Selectors

getPopulation

public Population getPopulation()
Get the Population for this GeneticAlgorithm.


setPopulation

public void setPopulation(Population pop)
Set the Population for this GeneticAlgorithm.


getEvaluation

public Function getEvaluation()
Get the evaluation function.

Returns:
the evaluation function that specifies the algorithm for evaluation of a Genome's fitness. It is concrete problem-specific.

setEvaluation

public void setEvaluation(Function fitnessEvaluation)
Set the evaluation function.

Parameters:
fitnessEvaluation - the evaluation function that specifies the algorithm for evaluation of a Genome's fitness. It must be set before use and is concrete problem-specific.

getRandom

public java.util.Random getRandom()
Description copied from interface: ProbabilisticAlgorithm
Get the random-generator used as probabilistic random source.

Specified by:
getRandom in interface ProbabilisticAlgorithm
Returns:
the random generator used for producing probabilistic effects.

setRandom

public void setRandom(java.util.Random randomGenerator)
Description copied from interface: ProbabilisticAlgorithm
Set the random-generator to use as probabilistic random source.

Especially called to change the random source to a previous, more secure, or more realistic generator.

Specified by:
setRandom in interface ProbabilisticAlgorithm

isCorrect

public boolean isCorrect()
Description copied from interface: ProbabilisticAlgorithm
Whether this algorithm is correct.

Specified by:
isCorrect in interface ProbabilisticAlgorithm
Returns:
whether all solutions found by this algorithms are correct despite the approximative nature of this algorithm. Monte Carlo algorithms are not correct, while Las Vegas algorithms usually are.

complexity

public Function complexity()
Description copied from interface: AlgorithmicTemplate
Measure for the asymptotic time complexity of the central solution operation in O-notation.

Specified by:
complexity in interface AlgorithmicTemplate
Returns:
the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).
See Also:
AlgorithmicTemplate.solve(AlgorithmicProblem)

spaceComplexity

public Function spaceComplexity()
Description copied from interface: AlgorithmicTemplate
Measure for the asymptotic space complexity of the central solution operation in O-notation.

Specified by:
spaceComplexity in interface AlgorithmicTemplate
Returns:
the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).
See Also:
AlgorithmicTemplate.solve(AlgorithmicProblem)

solve

public java.lang.Object solve(AlgorithmicProblem gproblem)
Solve a genetic algorithm problem. Assuming that the selector has already been set.

Specified by:
solve in interface AlgorithmicTemplate
Parameters:
gproblem - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.
Returns:
the population with the solution that was accepted by isSolution.
See Also:
setEvaluation(Function), GeneticAlgorithmProblem.getEvaluation(), setPopulation(Population), GeneticAlgorithmProblem.getPopulation(), evolve()
Preconditions:
getSelection() != null

evolve

public abstract void evolve()
evolves to the next generation for this population. Parents are selected and will recombine and mutate to produce children genomes who will replace some genomes in this population. This operation is sometimes called breeding.

See Also:
selection, Genome.recombine(Gene[],int,double), PopulationImpl.getMaximumRecombination(), PopulationImpl.getMaximumMutation()

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.