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

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

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

protected FitnessComparator	fitnessComparator Compares solutions based on strength.
protected SPEA2.StrengthFitnessEvaluator	fitnessEvaluator Strength-based fitness evaluator.

Fields inherited from class org.moeaframework.algorithm.AbstractEvolutionaryAlgorithm

archive, initialization, population

Fields inherited from class org.moeaframework.algorithm.AbstractAlgorithm

initialized, numberOfEvaluations, problem, terminated

Constructor Summary

SPEA2(Problem problem, Initialization initialization, Variation variation, int numberOfOffspring, int k)
Constructs a new instance of SPEA2.

Method Summary

protected double[][]	computeDistanceMatrix(Population population) Computes the distance matrix containing the pair-wise distances between solutions in objective space.
protected void	initialize() Performs any initialization that is required by this algorithm.
protected void	iterate() Performs one iteration of the 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, getPopulation, getResult, getState, setState

Methods inherited from class org.moeaframework.algorithm.AbstractAlgorithm

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

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.moeaframework.core.Algorithm

evaluate, getNumberOfEvaluations, getProblem, isTerminated, step, terminate

Field Detail

fitnessEvaluator

protected final SPEA2.StrengthFitnessEvaluator fitnessEvaluator

Strength-based fitness evaluator.

fitnessComparator

protected final FitnessComparator fitnessComparator

Compares solutions based on strength.

Constructor Detail

SPEA2

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

Constructs a new instance of SPEA2.

Parameters:

problem - the problem

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 Detail

initialize

protected void initialize()

Description copied from class: AbstractAlgorithm

Performs any initialization that is required by this algorithm. This method is called automatically by the first invocation of AbstractAlgorithm.step(), but may also be called manually prior to any invocations of step. Implementations should always invoke super.initialize() to ensure the hierarchy is initialized correctly.

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