orbital.algorithm.evolutionary
Class GeneticAlgorithm

java.lang.Object
  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:

• evolve that will simulate the evolutionary search. (Decoupled into sub class)
• select one of the Genomes. (Decoupled into selection function.)

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