source: branches/OKBJavaConnector/ECJClient/src/ec/multiobjective/spea2/README @ 8614

This package contains is an implementation of the Strength Pareto 
Evolutionary Algorithm 2 (SPEA2).

Details of this approach can be found in the following paper:

E. Zitzler, M. Laumanns, and L. Thiele.SPEA2: Improving the Performance
of the Strength Pareto Evolutionary Algorithm. Technical Report 103,
Computer Engineering and Communication Networks Lab (TIK), Swiss Federal
Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich,
May 2001. 

ftp://ftp.tik.ee.ethz.ch/pub/people/zitzler/ZLT2001a.ps (Postscript),
ftp://ftp.tik.ee.ethz.ch/pub/people/zitzler/ZLT2001a.pdf (PDF)


ABSTRACT 

The Strength Pareto Evolutionary Algorithm (SPEA) (Zitzler and Thiele
1999) is a relatively recent technique for finding or approximating the
Pareto-optimal set for multiobjective optimization problems. In
different studies (Zitzler and Thiele 1999; Zitzler, Deb, and Thiele
2000) SPEA has shown very good performance in comparison to other
multiobjective evolutionary algorithms, and therefore it has been a
point of reference in various recent investigations, e.g., (Corne,
Knowles, and Oates 2000). Furthermore, it has been used in different
applications, e.g., (La-hanas, Milickovic, Baltas, and Zamboglou 2001).
In this paper, an improved ver-sion, namely SPEA2, is proposed, which
incorporates in contrast to its predecessor a fine-grained fitness
assignment strategy, a density estimation technique, and an enhanced
archive truncation method. The comparison of SPEA2 with SPEA and two
other modern elitist methods, PESA and NSGA-II, on different test
problems yields promising results.

This package has a significant history.  The early versions of the
package were donated by Robert Hubley at the Institute for Systems
Biology.  Major later modifications were made by Sean Luke, Gabriel Balan,
and Keith Sullivan.  Then the SPEA2 package was almost entirely rewritten
in 2010 by Faisal Abidi and Sean Luke.


EXAMPLES
--------

The ec.app.moosuite package contains test cases against which to test SPEA2.


How ECJ implements SPEA2
------------------------

SPEA2 is an elitist archive method which in some sense extends mu+lambda. 
That is, SPEA2 maintains a pool (the "archive") of some N high quality
individuals which more or less holds the present known pareto front of
the population.  That archive is carried over from generation to generation.

SPEA2 has an elaborate fitness setting procedure which involves the 
computation of several measures of domination (known as "strength") and
sparsity.  This computation is performed by a revised SimpleEvaluator subclass:

  ec.multiobjective.spea2.SPEA2Evaluator

New children are then bred and an archive is formed by loading the pareto
front, trimmed by sparsity plus various other "highly fit" children (if there
is space).  The breeding procedure is handled by a revised version of 
SimpleBreeder:

  ec.multiobjective.spea2.SPEA2Breeder

Because it uses auxiliary fitness measures to perform breeding, SPEA2 requires
a subclass of MultiObjectiveFitness which stores these auxiliary measures:

  ec.multiobjective.spea2.SPEA2MultiObjectiveFitness

When SPEA2 needs to do breeding, it does so solely from the archive, not from
the full population.  This means that the selection operator 
(TournamentSelection, which SPEA uses) needs to be modified to only 
consider the archive when selecting an individual.  Our modified version is:

  ec.multiobjecive.spea2.SPEA2TournamentSelection


SPEA2 and NSGA-II have different approaches to building archives which impacts
on how you need to set your population sizes in order to achieve the same number
of evaluations.  In ECJ, NSGA-II does not include the archive as part of the basic
population size.  Rather, it builds the archive separately, then builds the
population by breeding from the archive, then gloms the two together.  On the
other hand, SPEA2 uses a (tunable) portion of its population as the archive, and
breeds individuals into the remainder of the population.  This means that to have
a "population size" for SPEA2 that's the same as NSGA-II, you need to increase
SPEA2's population size to NSGA-II's population size plus SPEA2's archive (elites)
size.  For example, if you have an NSGA-II population size of 100, and SPEA2 is using
an archive size of 50, to be fair you should make SPEA2's population size be 150.

If you set things so that SPEA2 and NSGA-II must reevaluate the fitness of 
their archives (which is rare), things are different.  Now you should set SPEA2
so that its archive size and population size is equal to twice NSGA-II's population
size (because NSGA-II's archive size is the size of its population).