Package org.moeaframework.algorithm

Class SPEA2

java.lang.Object

org.moeaframework.algorithm.AbstractAlgorithm

org.moeaframework.algorithm.AbstractEvolutionaryAlgorithm

org.moeaframework.algorithm.SPEA2

All Implemented Interfaces:

Algorithm, EvolutionaryAlgorithm, Extensible, Configurable, Named, Stateful

public class SPEA2
extends AbstractEvolutionaryAlgorithm

Implementation of the strength-based evolutionary algorithm (SPEA2). SPEA2 uses a novel strength-based measure of fitness for handling multiple objectives.

Note: First, there is a naming difference between this implementation and the original SPEA2 paper. The original SPEA2 paper defines a "population" and an "archive", but the population is really the offspring and the archive is the population. Secondly, the SPEA2 paper defines a parameter k = sqrt(population.size()) for computing a crowding-based niching factor. The SPEA2 C implementation in PISA (written by the same authors as the paper) recommends using k=1 for performance reasons. This implementation makes k a user-specified parameter to support either option. k should be at least 1 and no larger than population.size().

References:

1. Zitzler, E., M. Laumanns, and L. Thiele (2001). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SPEA2.MutableDistanceMap	Mapping of pair-wise distances between points.
class	SPEA2.StrengthFitnessEvaluator	Fitness evaluator for the strength measure with crowding-based niching.

Field Summary

Fields inherited from class org.moeaframework.algorithm.AbstractAlgorithm

initialized, numberOfEvaluations, problem, terminated

Constructor Summary

Constructors

Constructor	Description
SPEA2(Problem problem)	Constructs a new instance of SPEA2 with default settings.
SPEA2(Problem problem, int initialPopulationSize, Initialization initialization, Variation variation, int numberOfOffspring, int k)	Constructs a new instance of SPEA2.

Method Summary

Modifier and Type	Method	Description
protected double[][]	computeDistanceMatrix(Population population)	Computes the distance matrix containing the pair-wise distances between solutions in objective space.
SPEA2.StrengthFitnessEvaluator	getFitnessEvaluator()	Returns the strength-based fitness evaluator.
String	getName()	Returns the name of this algorithm.
int	getNumberOfOffspring()	Returns the number of offspring produced each iteration.
void	initialize()	Performs any initialization that is required by this algorithm.
protected void	iterate()	Performs one iteration of the algorithm.
void	setInitialPopulationSize(int initialPopulationSize)	Sets the initial population size.
void	setNumberOfOffspring(int numberOfOffspring)	Sets the number of offspring produced each iteration.
void	setVariation(Variation variation)	Replaces the variation operator to be used by this algorithm.
protected Population	truncate(Population offspring, int size)	Returns the population of solutions that survive to the next generation.

Methods inherited from class org.moeaframework.algorithm.AbstractEvolutionaryAlgorithm

getArchive, getInitialization, getInitialPopulationSize, getPopulation, getResult, getVariation, loadState, saveState, setArchive, setInitialization, setPopulation

Methods inherited from class org.moeaframework.algorithm.AbstractAlgorithm

assertNotInitialized, evaluate, getExtensions, getNumberOfEvaluations, getProblem, isInitialized, isTerminated, step, terminate

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.moeaframework.algorithm.Algorithm

evaluate, evaluateAll, evaluateAll, getNumberOfEvaluations, getProblem, isInitialized, isTerminated, run, run, step, terminate

Methods inherited from interface org.moeaframework.core.configuration.Configurable

applyConfiguration, getConfiguration

Methods inherited from interface org.moeaframework.algorithm.extension.Extensible

addExtension, getExtensions, removeExtension

Constructor Details

SPEA2

public SPEA2(Problem problem)

Constructs a new instance of SPEA2 with default settings.

Parameters:

problem - the problem

SPEA2

public SPEA2(Problem problem,
 int initialPopulationSize,
 Initialization initialization,
 Variation variation,
 int numberOfOffspring,
 int k)

Constructs a new instance of SPEA2.

Parameters:

problem - the problem

initialPopulationSize - the initial population size

initialization - the initialization procedure

variation - the variation operator

numberOfOffspring - the number of offspring generated each iteration

k - niching parameter specifying that crowding is computed using the k-th nearest neighbor, recommend k=1

Method Details

getName

public String getName()

Description copied from interface: Algorithm

Returns the name of this algorithm. Whenever possible, this name should match the name recognized by AlgorithmFactory.

Returns:

the name of this algorithm

setVariation

public void setVariation(Variation variation)

Description copied from class: AbstractEvolutionaryAlgorithm

Replaces the variation operator to be used by this algorithm.

Overrides:

setVariation in class AbstractEvolutionaryAlgorithm

Parameters:

variation - the variation operator

setInitialPopulationSize

public void setInitialPopulationSize(int initialPopulationSize)

Description copied from class: AbstractEvolutionaryAlgorithm

Sets the initial population size. This value can not be set after initialization.

Overrides:

setInitialPopulationSize in class AbstractEvolutionaryAlgorithm

Parameters:

initialPopulationSize - the initial population size

getNumberOfOffspring

public int getNumberOfOffspring()

Returns the number of offspring produced each iteration.

Returns:

the number of offspring

setNumberOfOffspring

public void setNumberOfOffspring(int numberOfOffspring)

Sets the number of offspring produced each iteration. This is typically set to the same value as the population size.

Parameters:

numberOfOffspring - the number of offspring

getFitnessEvaluator

public SPEA2.StrengthFitnessEvaluator getFitnessEvaluator()

Returns the strength-based fitness evaluator.

Returns:

the strength-based fitness evaluator

initialize

public void initialize()

Description copied from interface: Algorithm

Performs any initialization that is required by this algorithm. This method should only be called once, though the specific implementation may choose to no-op or throw AlgorithmInitializationException if called multiple times.

Implementations should always call super.initialize() to ensure the algorithm is initialized correctly.

Specified by:

initialize in interface Algorithm

Overrides:

initialize in class AbstractEvolutionaryAlgorithm

iterate

protected void iterate()

Description copied from class: AbstractAlgorithm

Performs one iteration of the algorithm. This method should be overridden by implementations to perform each logical iteration of the algorithm.

Specified by:

iterate in class AbstractAlgorithm

truncate

protected Population truncate(Population offspring,
 int size)

Returns the population of solutions that survive to the next generation.

Parameters:

offspring - all offspring solutions

size - the number of solutions to retain

Returns:

the population of solutions that survive to the next generation

computeDistanceMatrix

protected double[][] computeDistanceMatrix(Population population)

Computes the distance matrix containing the pair-wise distances between solutions in objective space. The diagonal will contain all 0's.

Parameters:

population - the population of solutions

Returns:

the distance matrix