aima.core.search.local

Class GeneticAlgorithm<A>

java.lang.Object

aima.core.search.local.GeneticAlgorithm<A>

Type Parameters:

A - the type of the alphabet used in the representation of the individuals in the population (this is to provide flexibility in terms of how a problem can be encoded).

Direct Known Subclasses:

GeneticAlgorithmForNumbers

public class GeneticAlgorithm<A>
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.8, page 129.

 function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual
   inputs: population, a set of individuals
           FITNESS-FN, a function that measures the fitness of an individual
           
   repeat
     new_population <- empty set
     for i = 1 to SIZE(population) do
       x <- RANDOM-SELECTION(population, FITNESS-FN)
       y <- RANDOM-SELECTION(population, FITNESS-FN)
       child <- REPRODUCE(x, y)
       if (small random probability) then child <- MUTATE(child)
       add child to new_population
     population <- new_population
   until some individual is fit enough, or enough time has elapsed
   return the best individual in population, according to FITNESS-FN
 --------------------------------------------------------------------------------
 function REPRODUCE(x, y) returns an individual
   inputs: x, y, parent individuals
   
   n <- LENGTH(x); c <- random number from 1 to n
   return APPEND(SUBSTRING(x, 1, c), SUBSTRING(y, c+1, n))
 

Figure 4.8 A genetic algorithm. The algorithm is the same as the one diagrammed in Figure 4.6, with one variation: in this more popular version, each mating of two parents produces only one offspring, not two.

Author:

Ciaran O'Reilly, Mike Stampone, Ruediger Lunde

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	GeneticAlgorithm.ProgressTracer<A> Interface for progress tracers.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.List<A>	finiteAlphabet
protected int	individualLength
protected static java.lang.String	ITERATIONS
protected Metrics	metrics
protected double	mutationProbability
protected static java.lang.String	POPULATION_SIZE
protected java.util.Random	random
protected static java.lang.String	TIME_IN_MILLISECONDS

Constructor Summary

Constructors

Constructor and Description
GeneticAlgorithm(int individualLength, java.util.Collection<A> finiteAlphabet, double mutationProbability)
GeneticAlgorithm(int individualLength, java.util.Collection<A> finiteAlphabet, double mutationProbability, java.util.Random random)

Method Summary

Modifier and Type	Method and Description
void	addProgressTracer(GeneticAlgorithm.ProgressTracer<A> pTracer) Progress tracers can be used to display progress information.
void	clearInstrumentation() Sets the population size and number of iterations to zero.
Individual<A>	geneticAlgorithm(java.util.Collection<Individual<A>> initPopulation, FitnessFunction<A> fitnessFn, GoalTest goalTest, long maxTimeMilliseconds) Template method controlling search.
Individual<A>	geneticAlgorithm(java.util.Collection<Individual<A>> initPopulation, FitnessFunction<A> fitnessFn, int maxIterations) Starts the genetic algorithm and stops after a specified number of iterations.
int	getIterations() Returns the number of iterations of the genetic algorithm.
Metrics	getMetrics() Returns all the metrics of the genetic algorithm.
int	getPopulationSize() Returns the population size.
long	getTimeInMilliseconds()
protected Individual<A>	mutate(Individual<A> child)
protected java.util.List<Individual<A>>	nextGeneration(java.util.List<Individual<A>> population, FitnessFunction<A> fitnessFn) Primitive operation which is responsible for creating the next generation.
protected int	randomOffset(int length)
protected Individual<A>	randomSelection(java.util.List<Individual<A>> population, FitnessFunction<A> fitnessFn)
protected Individual<A>	reproduce(Individual<A> x, Individual<A> y)
Individual<A>	retrieveBestIndividual(java.util.Collection<Individual<A>> population, FitnessFunction<A> fitnessFn)
protected void	updateMetrics(java.util.Collection<Individual<A>> population, int itCount, long time) Updates statistic data collected during search.
protected void	validatePopulation(java.util.Collection<Individual<A>> population)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

POPULATION_SIZE

protected static final java.lang.String POPULATION_SIZE

See Also:

Constant Field Values

ITERATIONS

protected static final java.lang.String ITERATIONS

See Also:

Constant Field Values

TIME_IN_MILLISECONDS

protected static final java.lang.String TIME_IN_MILLISECONDS

See Also:

Constant Field Values

metrics

protected Metrics metrics

individualLength

protected int individualLength

finiteAlphabet

protected java.util.List<A> finiteAlphabet

mutationProbability

protected double mutationProbability

random

protected java.util.Random random

Constructor Detail

GeneticAlgorithm

public GeneticAlgorithm(int individualLength,
                        java.util.Collection<A> finiteAlphabet,
                        double mutationProbability)

GeneticAlgorithm

public GeneticAlgorithm(int individualLength,
                        java.util.Collection<A> finiteAlphabet,
                        double mutationProbability,
                        java.util.Random random)

Method Detail

addProgressTracer

public void addProgressTracer(GeneticAlgorithm.ProgressTracer<A> pTracer)

Progress tracers can be used to display progress information.

geneticAlgorithm

public Individual<A> geneticAlgorithm(java.util.Collection<Individual<A>> initPopulation,
                                      FitnessFunction<A> fitnessFn,
                                      int maxIterations)

Starts the genetic algorithm and stops after a specified number of iterations.

geneticAlgorithm

public Individual<A> geneticAlgorithm(java.util.Collection<Individual<A>> initPopulation,
                                      FitnessFunction<A> fitnessFn,
                                      GoalTest goalTest,
                                      long maxTimeMilliseconds)

Template method controlling search. It returns the best individual in the specified population, according to the specified FITNESS-FN and goal test.

Parameters:

population - a set of individuals

fitnessFn - a function that measures the fitness of an individual

goalTest - test determines whether a given individual is fit enough to return. Can be used in subclasses to implement additional termination criteria, e.g. maximum number of iterations.

maxTimeMilliseconds - the maximum time in milliseconds that the algorithm is to run for (approximate). Only used if > 0L.

Returns:

the best individual in the specified population, according to the specified FITNESS-FN and goal test.

retrieveBestIndividual

public Individual<A> retrieveBestIndividual(java.util.Collection<Individual<A>> population,
                                            FitnessFunction<A> fitnessFn)

clearInstrumentation

public void clearInstrumentation()

Sets the population size and number of iterations to zero.

getMetrics

public Metrics getMetrics()

Returns all the metrics of the genetic algorithm.

Returns:

all the metrics of the genetic algorithm.

getPopulationSize

public int getPopulationSize()

Returns the population size.

Returns:

the population size.

getIterations

public int getIterations()

Returns the number of iterations of the genetic algorithm.

Returns:

the number of iterations of the genetic algorithm.

getTimeInMilliseconds

public long getTimeInMilliseconds()

Returns:

the time in milliseconds that the genetic algorithm took.

updateMetrics

protected void updateMetrics(java.util.Collection<Individual<A>> population,
                             int itCount,
                             long time)

Updates statistic data collected during search.

Parameters:

itCount - the number of iterations.

time - the time in milliseconds that the genetic algorithm took.

nextGeneration

protected java.util.List<Individual<A>> nextGeneration(java.util.List<Individual<A>> population,
                                                       FitnessFunction<A> fitnessFn)

Primitive operation which is responsible for creating the next generation. Override to get progress information!

randomSelection

protected Individual<A> randomSelection(java.util.List<Individual<A>> population,
                                        FitnessFunction<A> fitnessFn)

reproduce

protected Individual<A> reproduce(Individual<A> x,
                                  Individual<A> y)

mutate

protected Individual<A> mutate(Individual<A> child)

randomOffset

protected int randomOffset(int length)

validatePopulation

protected void validatePopulation(java.util.Collection<Individual<A>> population)