jenes
Class GeneticAlgorithm<T extends Chromosome>

java.lang.Object
  jenes.GeneticAlgorithm<T>

Type Parameters:

T - The class of chromosomes to work with.

Direct Known Subclasses:

KnapsackGA, PatternGA, RoyalGA, SimpleGA, TSPGA, TSPGA

public abstract class GeneticAlgorithm<T extends Chromosome>
extends java.lang.Object

This is the main class of JENES, providing the skeleton for implementing genetic algorithms.

A genetic algorithm can be implemented by subclassing GeneticAlgorithm and specifying the method evaluateIndividual(Individual). The genetic algorithm body is made of a sequence of stages. Which stages and in which order to consider is left to the algorithm needs. Generally, the sequence is made of a selection operator, followed by a a crossover operator, and then by a mutation operator. This schema is implemented by SimpleGA.

An example of code is provided below. First, the initial population has to be created.

 BooleanChromosome chrom = new BooleanChromosome(CHROMOSOME_LENGTH);
 Individual<BooleanChromosome> ind = new Individual<BooleanChromosome>(chrom);
 Population<BooleanChromosome> pop = new Population<BooleanChromosome>(ind,
                POPULATION_SIZE);
 

Then, the genetic algorithm is subclassed and instanced.

  GeneticAlgorithm<BooleanChromosome> ga = new GeneticAlgorithm<BooleanChromosome>(pop, GENERATION_LIMIT)
  {
    protected void evaluateIndividual(Individual<BooleanChromosome> individual) {
      BooleanChromosome chrom = individual.getChromosome();
      int count = 0;
      int length=chrom.length();
      for(int i=0; i&ltlength i++)
        if(chrom.getValue(i))
          count++;
 
      individual.setScore(count);
    }
  };
 

In this example, we used an anonymous subclass, but other subclassing methods can be used. After, stages (operators in particular) are added to the algorithm's body.

 AbstractStage<BooleanChromosome> selection = new TournamentSelector<BooleanChromosome>(
                3);
 AbstractStage<BooleanChromosome> crossover = new OnePointCrossover<BooleanChromosome>(
                0.8);
 AbstractStage<BooleanChromosome> mutation = new SimpleMutator<BooleanChromosome>(
                0.2);
 ga.addStage(selection);
 ga.addStage(crossover);
 ga.addStage(mutation);
 

Finally, the algorithm is executed.

 ga.evolve();
 

A genetic algorithm processes a Population of Individuals. At each generation there are an input and output population. The reference to these populations can be respectively obtained by the methods getCurrentPopulation() and getNextPopulation(). Past populations are buffered in the algorithm's history. An history population can be retrieve by the method getHistoryAt(int). The reference to an history population is valid for the history length. After, populations are collected for reuse, so references to them are not anymore valid.

The genetic algorithm execution is invoked by the method evolve(). The algorithm execution passes through the following events:

• Start: the algorithm is just created.
• Init: internal structures, such as the population given as input at generation 0 and history, are initialized.
• Generation: a generation has been just performed.
• Stop: the algorithm terminates its executions.

Each of these events can be captured by AlgorithmEventListeners and GenerationEventListeners. They can also be caputured by the GeneticAlgorithm subclass, by overriding the methods onStart(long), onInit(long), onGeneration(long), and onStop(long). Capturing events is useful to collect statistics and to perform analyses. Evolution terminates when the maximum number of generations is reached. It is possible to terminate the execution on the basis of some condition (e.g. precision level, variance of population, ecc.) by overriding the method end().

GeneticAlgorithm include a support for elitism, that is best individuals at each generation are assured to be at the next generation. The number of elite individuals is set by the method setElitism(int). These individuals are substituted to some individuals to the processed population according to the following strategies:

• GeneticAlgorithm.ElitismStrategy.RANDOM: next population individuals are randomly selected and substituted by elite.
• GeneticAlgorithm.ElitismStrategy.WORST: next population worst individuals are substituted by elite.

The first strategy is more efficient as it does not require to order the population. The drawback is that individuals with a good fitness could be substituted by elite. The second strategy is slower, but assures that only worst individuals are substituted.

The genetic algorithm can be used for both maximizing or minimizing the fitness function. This can be accomplished by setting the body objective through the mehod setBiggerIsBetter(boolean).

GeneticAlgorithm can process populations with a variable number of individuals at each generation.

GeneticAlgorithm performs by default an initial randomization of the population.

Since:

1.0

Version:

1.2

Author:

Luigi Troiano, Pierpaolo Lombardi, Giuseppe Pascale, Thierry Bodhuin

Nested Class Summary

static class	GeneticAlgorithm.ElitismStrategy The elitism strategy enumeration
static class	GeneticAlgorithm.ResizeStrategy The resize stategy enumeration.
static class	GeneticAlgorithm.Statistics } This class provides some basic statistics regarding the algorithm execution.

Field Summary

protected java.util.List<AlgorithmEventListener<T>>	algorithmListeners The genetic algorithm listeners
protected Sequence<T>	body The main algorithm sequence
static int	DEFAULT_GENERATION_LIMIT The default maximum number of generations
static int	DEFAULT_HISTORY_SIZE The default history size
protected int	elitism The elitism number
protected GeneticAlgorithm.ElitismStrategy	elitismStrategy The elitism strategy used by this genetic algorithm
protected int	generation Current generation count
protected int	generationLimit Maximum number of generations
protected java.util.List<GenerationEventListener<T>>	generationListeners The generation listeners
protected Population<T>	initialPopulation The initial population
static int	MAX_HISTORY_SIZE The maximum history size
static int	MIN_HISTORY_SIZE The minimum history size
protected Random	random The random instance
protected double	randomization Rate of randomization of initial population
protected GeneticAlgorithm.ResizeStrategy	resizeStrategy The resize strategy used by this genetic algorithm
protected GeneticAlgorithm.Statistics	statistics The statistics object responsible for storing statistics about this genetic algorithm.

Constructor Summary

GeneticAlgorithm(Population<T> pop)
Constructs a new genetic algorithm with the specified population and the default generation limit.

GeneticAlgorithm(Population<T> pop, int genlimit)
Constructs a new genetic algorithm with the specified population and the specified generation limit.

Method Summary

void	addAlgorithmEventListener(AlgorithmEventListener ael) Adds a new algorthm event listener
void	addGenerationEventListener(GenerationEventListener gel) Adds a new generation event listener
void	addStage(AbstractStage<T> stage) Adds a new stage at the genetic algorithm's body
protected void	applyElitism() Applies the elitism to the current population, according to the chosen strategy.
protected boolean	end() Provides the algorithm termination condition.
protected abstract void	evaluateIndividual(Individual<T> individual) Evaluates a single individual.
protected void	evaluatePopulation(Population<T> population) Evaluates the population.
void	evolve() Evolves the algorithms by resetting the initial population and restarting the algorithm.
void	evolve(boolean restart) Evolves the algorithm until the termination condition or the generation limit is reached.
Sequence<T>	getBody() Returns the algorithm's body sequence.
Population<T>	getCurrentPopulation() Returns the current population.
int	getElitism() Returns the number of individuals considered for elitism by the genetic algorithm.
GeneticAlgorithm.ElitismStrategy	getElitismStrategy() Returns the elitism strategy used by this genetic algorithm
int	getGeneration() Returns the current generation counter
int	getGenerationLimit() Returns the generation limit
Population<T>	getHistoryAt(int pos) Returns the history population at the specified generation.
int	getHistorySize() Returns the history size that is the number of populations kept by history
Population<T>	getInitialPopulation() Returns the initial population.
Population<T>	getNextPopulation() Returns the genetic algorithm next population.
double	getRandomization() Provides the randomization rate, that is the percentage of individuals being randomized by the algorithm.
GeneticAlgorithm.ResizeStrategy	getResizeStrategy() Returns the resize strategy used by this genetic algorithm.
GeneticAlgorithm.Statistics	getStatistics() Returns algoritm statistics at the moment of invokation.
boolean	isBiggerBetter() Says if the algorithm's body objective is set to maximize or minimize individual fitness.
protected void	onGeneration(long time) Invoked when a generation ga end event occurs.
protected void	onInit(long time) Invoked when an init end ga event occurs.
protected void	onStart(long time) Invoked when a start ga event occurs.
protected void	onStop(long time) Invoked when a stop event occurs.
protected void	randomizeIndividual(Individual<T> individual) Performs an individual randomization.
protected void	randomizePopulation(Population<T> pop) Perform a population randomization, by itering on individuals.
void	removeAlgorithmEventListener(AlgorithmEventListener ael) Removes an algorithm event listener
void	removeGenerationEventListener(GenerationEventListener gel) Removes the generation event listener
void	setBiggerIsBetter(boolean flag) Sets the algorithm's body objective to maximize (true) or minimize (false) the individual fitness.
void	setElitism(int elitism) Sets the number of individuals considered for elitism by the genetic algorithm.
void	setElitismStrategy(GeneticAlgorithm.ElitismStrategy es) Sets the elitism strategy to used by this genetic algorithm.
void	setGenerationLimit(int limit) Sets the generation limit
void	setHistorySize(int hs) Sets the history size, that is the number of populations kept by history.
void	setRandomization(boolean value) Sets the randomization rate to 0 or 1, according to the flag.
void	setRandomization(double rate) Sets the randomization rate.
void	setResizeStrategy(GeneticAlgorithm.ResizeStrategy rs) Sets the resize stragety.
protected void	start(boolean reset) Starts this genetic algorithm.
protected void	stop() Terminates the genetic algorithm, notifying the stop event to listeners.
java.lang.String	toString()
void	updateStatistics(GeneticAlgorithm.Statistics stats) Updates the algoritm statistics at the moment of invokation.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_GENERATION_LIMIT

public static final int DEFAULT_GENERATION_LIMIT

The default maximum number of generations

See Also:

Constant Field Values

DEFAULT_HISTORY_SIZE

public static final int DEFAULT_HISTORY_SIZE

The default history size

See Also:

Constant Field Values

MIN_HISTORY_SIZE

public static final int MIN_HISTORY_SIZE

The minimum history size

See Also:

Constant Field Values

MAX_HISTORY_SIZE

public static final int MAX_HISTORY_SIZE

The maximum history size

See Also:

Constant Field Values

body

protected Sequence<T extends Chromosome> body

The main algorithm sequence

statistics

protected GeneticAlgorithm.Statistics statistics

The statistics object responsible for storing statistics about this genetic algorithm.

generation

protected int generation

Current generation count

randomization

protected double randomization

Rate of randomization of initial population

generationLimit

protected int generationLimit

Maximum number of generations

elitism

protected int elitism

The elitism number

elitismStrategy

protected GeneticAlgorithm.ElitismStrategy elitismStrategy

The elitism strategy used by this genetic algorithm

initialPopulation

protected Population<T extends Chromosome> initialPopulation

The initial population

algorithmListeners

protected java.util.List<AlgorithmEventListener<T extends Chromosome>> algorithmListeners

The genetic algorithm listeners

generationListeners

protected java.util.List<GenerationEventListener<T extends Chromosome>> generationListeners

The generation listeners

resizeStrategy

protected GeneticAlgorithm.ResizeStrategy resizeStrategy

The resize strategy used by this genetic algorithm

random

protected Random random

The random instance

Constructor Detail

GeneticAlgorithm

public GeneticAlgorithm(Population<T> pop)

Constructs a new genetic algorithm with the specified population and the default generation limit.

Parameters:

pop - the sample population

GeneticAlgorithm

public GeneticAlgorithm(Population<T> pop,
                        int genlimit)

Constructs a new genetic algorithm with the specified population and the specified generation limit.

Parameters:

pop - the sample population

genlimit - the generations upper bound

Method Detail

getHistorySize

public final int getHistorySize()

Returns the history size that is the number of populations kept by history

Returns:

the history length

setHistorySize

public final void setHistorySize(int hs)

Sets the history size, that is the number of populations kept by history.

Parameters:

hs - the new number of history populations

getHistoryAt

public final Population<T> getHistoryAt(int pos)

Returns the history population at the specified generation. The pos value can be relative or absolute. If relative, it must be a negative number that specifies how many generations to go back in order to get the population. So that, 0 means the current generation, -1 means one generation back, -2 means two generations back, and so on. If positive, the generation index is absolute. If the population at the specified generation is not available, the method returns null.

Parameters:

pos - the population position

Returns:

the history population, if available. Otherwise it returns null.

getInitialPopulation

public final Population<T> getInitialPopulation()

Returns the initial population. This is the population given as input to the genetic algorithm, thus it is not affected by the initial population randomization.

Returns:

the initial population

getCurrentPopulation

public final Population<T> getCurrentPopulation()

Returns the current population. This is the population given as input to the algorithm's body at the current generation. When the algorithm starts, it is a copy of the initial population, and it is eventually affected by the randomization process.

Returns:

the current population.

getNextPopulation

public final Population<T> getNextPopulation()

Returns the genetic algorithm next population. This is the population being processed by the algorithm's body at the current generation. It is the population that will be given as input to the algorithm's body sequence at the following generation.

Returns:

the next population

evolve

public final void evolve()
                  throws AlgorithmException

Evolves the algorithms by resetting the initial population and restarting the algorithm.

Throws:

AlgorithmException

evolve

public final void evolve(boolean restart)
                  throws AlgorithmException

Evolves the algorithm until the termination condition or the generation limit is reached. Depending on the argument, the algorithm restarts or continues from the last population.

Parameters:

restart - if true, the initial population is reset; if false, the algorithm continues from the last population.

Throws:

AlgorithmException

end

protected boolean end()

Provides the algorithm termination condition. By default it returns false as reaching the generation limit is the sole ending criterion Subclasses can override this method in order to provide a problem specific termination condition.

Returns:

true if the ga evolution reached the termination condition, false otherwise

start

protected final void start(boolean reset)

Starts this genetic algorithm. This method performs the algorithm initialization and notifies the start and init events. It is automatically invoked by the method evolve(), thus it should not be explicity invoked.

Parameters:

reset - if true, the algorithm reset the initial population.

stop

protected final void stop()

Terminates the genetic algorithm, notifying the stop event to listeners. It is automatically invoked by the method evolve(), thus it should not be explicity invoked.

onStart

protected void onStart(long time)

Invoked when a start ga event occurs. By default, no action is performed. Override this method to make the GeneticAlgorithm subclass able to be notfied of the start event.

Parameters:

time - the start event time expressed in milliseconds

onInit

protected void onInit(long time)

Invoked when an init end ga event occurs. By default, no action is performed. Override this method to make the GeneticAlgorithm subclass able to be notfied of the init event.

Parameters:

time - the init event time expressed in milliseconds

onStop

protected void onStop(long time)

Invoked when a stop event occurs. By default, no action is performed. Override this method to make the GeneticAlgorithm subclass able to be notfied of the stop event.

Parameters:

time - the stop event time expressed in milliseconds

onGeneration

protected void onGeneration(long time)

Invoked when a generation ga end event occurs. By default, no action is performed. Override this method to make the GeneticAlgorithm subclass able to be notfied of the generation event.

Parameters:

time - the generation event time expressed in milliseconds

evaluatePopulation

protected final void evaluatePopulation(Population<T> population)

Evaluates the population. The method iterates the evaluation on each individual. It is automatically invoked by the method evolve(), thus it should not be explicity invoked.

Parameters:

population - the population to be evaluated

evaluateIndividual

protected abstract void evaluateIndividual(Individual<T> individual)

Evaluates a single individual. This evaluation of individuals is specifically related to the problem to solve, thus it is an abstract method requiring an implementation by the sublass.

Parameters:

individual - the individual to be evaluated

randomizePopulation

protected final void randomizePopulation(Population<T> pop)

Perform a population randomization, by itering on individuals. This process is generally useful to enrich the population diversity, necessary to the genetic algorithm for exploiting the search space, especially the initial population is created by cloning a sample individual.

The percentage of individuals to be randomized can be finely controlled by the randomization rate. This is useful in many problems where a dominant solution should be kept in the population, but still providing a random genetic variety. The randomization rate is controlled by the setRandomization(double) method.

This method is automatically invoked by the start(boolean) method, so no explicit invokation is required.

Parameters:

pop - the population to randomize

randomizeIndividual

protected void randomizeIndividual(Individual<T> individual)

Performs an individual randomization. It is invoked by randomizePopulation(Population). By default randomization is delegated to the individual. In some problems, it would be useful to control the randomization process of individual. This is especially the case of when there are some constraints on genes in order to make the individual valid.

Parameters:

individual - the individual to be randomize

setRandomization

public final void setRandomization(boolean value)

Sets the randomization rate to 0 or 1, according to the flag. By this method is possible to apply the randomization process to the whole population or not at all.

Parameters:

value - if true the rate is set to 1, otherwise to 0.

setRandomization

public final void setRandomization(double rate)

Sets the randomization rate. The randomization rate represents the percentage of individuals that will be randomized. The value should be within [0,1]. However the method automatically trims values outside the unary range, so that negative values are trimmed to 0 and values bigger than 1, are trimmed to 1. Therefore the method is consistent for any value.

Parameters:

rate - the randomization rate to use during the randomization phase

getRandomization

public final double getRandomization()

Provides the randomization rate, that is the percentage of individuals being randomized by the algorithm.

Returns:

the randomization rate.

getGeneration

public final int getGeneration()

Returns the current generation counter

Returns:

the current generation counter

getGenerationLimit

public final int getGenerationLimit()

Returns the generation limit

Returns:

the maximum number of generations

setGenerationLimit

public final void setGenerationLimit(int limit)

Sets the generation limit

Parameters:

limit - the new generation limit

addStage

public final void addStage(AbstractStage<T> stage)

Adds a new stage at the genetic algorithm's body

Parameters:

stage - the stage to be add

isBiggerBetter

public final boolean isBiggerBetter()

Says if the algorithm's body objective is set to maximize or minimize individual fitness.

Returns:

true is the body objective is to maximize the fitness false otherwise

setBiggerIsBetter

public final void setBiggerIsBetter(boolean flag)

Sets the algorithm's body objective to maximize (true) or minimize (false) the individual fitness. All stages belonging to the body sequence are recursevely set according to the flag.

Parameters:

flag - true to set the body to maximize the fitness, false to minimize

applyElitism

protected final void applyElitism()

Applies the elitism to the current population, according to the chosen strategy. This method is authomatically invoked by evolve(), and should not be explicitaly invoked.

getElitism

public final int getElitism()

Returns the number of individuals considered for elitism by the genetic algorithm.

Returns:

the elitism parameter

setElitism

public final void setElitism(int elitism)

Sets the number of individuals considered for elitism by the genetic algorithm. If it is 0, elitism has no place in this algorithm.

Parameters:

elitism - the new elitism parameter

getElitismStrategy

public final GeneticAlgorithm.ElitismStrategy getElitismStrategy()

Returns the elitism strategy used by this genetic algorithm

Returns:

the elitism strategy

setElitismStrategy

public final void setElitismStrategy(GeneticAlgorithm.ElitismStrategy es)

Sets the elitism strategy to used by this genetic algorithm. This stratehy can be RANDOM or WORST: in the first case the random individuals will be replaced by the elite individuals; in the latter the algorithm will replace the worst individuals.

Parameters:

es - the elitism strategy

setResizeStrategy

public final void setResizeStrategy(GeneticAlgorithm.ResizeStrategy rs)

Sets the resize stragety. This is for advanced use. The genetic algorithm should have a need to resize an existing population, in particular to expand it. Expanding the population would eventually require to create new Individual. The resize strategy specifies the way to perform such a task. Possible strategies are:

• GeneticAlgorithm.ResizeStrategy.AUTO: entails the creation of new individuals, generally by cloning.
• GeneticAlgorithm.ResizeStrategy.EMPTY: expands the population, without creating new individuals.
• GeneticAlgorithm.ResizeStrategy.NONE: disables the automatic resize of populations.

Parameters:

rs - the new resize strategy

getResizeStrategy

public final GeneticAlgorithm.ResizeStrategy getResizeStrategy()

Returns the resize strategy used by this genetic algorithm.

Returns:

the resize strategy

getBody

public final Sequence<T> getBody()

Returns the algorithm's body sequence.

Returns:

the body stage sequence

addAlgorithmEventListener

public final void addAlgorithmEventListener(AlgorithmEventListener ael)

Adds a new algorthm event listener

Parameters:

ael - the listener to add

removeAlgorithmEventListener

public final void removeAlgorithmEventListener(AlgorithmEventListener ael)

Removes an algorithm event listener

Parameters:

ael - the listener to remove

addGenerationEventListener

public final void addGenerationEventListener(GenerationEventListener gel)

Adds a new generation event listener

Parameters:

gel - the generation listener to add

removeGenerationEventListener

public final void removeGenerationEventListener(GenerationEventListener gel)

Removes the generation event listener

Parameters:

gel - the listener to remove

getStatistics

public final GeneticAlgorithm.Statistics getStatistics()

Returns algoritm statistics at the moment of invokation.

Returns:

an object containing the algorithm statistics

updateStatistics

public final void updateStatistics(GeneticAlgorithm.Statistics stats)

Updates the algoritm statistics at the moment of invokation.

Parameters:

stats - the statistics object to be updated

toString

public final java.lang.String toString()

Overrides:

toString in class java.lang.Object