nsga2spea2.md

home | copyright ©2016, tim@menzies.us

overview | syllabus | src | submit | chat

---

NSGA-II, SPEA2, and Others

Problem: How to find cull many solutions, with multiple objectives

History: 1990s: NSGA, NPGA, MOGA

• Sort according how often not dominated (nondominating sort)
• Preserve diversity of solutions.
  • If a crowded part of the space, delete some
  • Elitism (to improve convergence)

All had some high computation times.

NSGA-II (fast, approximate, non-dominating sort)

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. Trans. Evol. Comp 6, 2 (April 2002), 182-197. DOI=http://dx.doi.org/10.1109/4235.996017

Cited by: 15,300+ papers

A standard genetic algorithm (Crossover, mutation) with a state-of-the art selection operator for multi-objectives.

• Divide candidates into frontiers:
• For some small number:
  • Keep the top i-frontiers until we reach that number
  • If you fill up half way through a frontier,
  • Delete some using crowd-pruning

BUt how do you finds the bands? And what is crowd-pruning?

• Patience. First, do you get the general idea?
• Some fast primary ranking method to generate frontier1, frontier2, frontier3...
• Keep frontier1, frontier2, frontier3... till frontieri gives you too many items
• Sort frontieri by secondary ranking method, prune the lower ones

Primary rankings: sort by how many things you dominate:

• Part one: find....
  • n_p: number of candidates that dominate p (the upstream counter)
  • S_p: candidates dominated by p (the downstream set)
  • F₁: frontier 1 (the frontier of things dominated by no one)
• Part two...
  • For P in frontier i
    • For everything Q dominated by P
      • decrease the upstream counter by 1
    • If upstream counter == 0 + then Q belongs in frontier i

Secondary ranking (only applied to the "too much" frontier that cross "over the line").

Find an approximation to the cuboid space around around each candidate:

• For each objective,
  • Sort the candidates on that objective
  • For each candidate p in that "too much" frontier,
    • Find the gap equal to the sum of the space up and down to the next candidate
    • Normalize gap by the max-min in that objective.
    • Add gap to I_p
• Sort candidates by I_p
  • Discard the smaller ones.

Officially faster. Strange to say, no runtimes in the famous NSGA-II paper

BYW, NSGA-II's author has recently released NSGA-II for many objective problems

• multi: 2,3,4
• many: 5+

SPEA2: Improving the Strength Pareto Evolutionary Algorithm

Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization Eckart Zitzler, Marco Laumanns, Lothar Thiele, Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Proceedings of the EUROGEN'2001. Athens. Greece, September 19-21

Cited by 4774.

(The following notes come for the excellent website Clever Algorithms.)

Again, a genetic algorithm (crossover, mutate) with a novel select operator.

• Worried about individuals dominated by the same candidate.
• All individuals scored by the number of other people they dominate.
• If individuals have identical score, resolve via reflection on local density.

Data structures:

• Population: space of current mutants (build, somewhat, from the Archive).
• Archive: a space of good ideas (usually smaller than Population; e.g. size/2).

Functions:

• CalculateRawFitness() number of solutions that a give solution dominate.
• CandidateDensity() estimates the density of local Pareto front
  • Euclidean distance of the objective values to the K nearest neighbors (in objective space)
  • K = sqrt( size(Archive) + size(Population) )
• PopulateWithRemainingBest() fills in Archive with remaining candidate solutions in order of fitness.
• RemoveMostSimilar() truncates Archive, removing members with the smallest difference in their objective scores.
• SelectParents: all pairs comparison, remove dominated ones

Algorithm:

IBEA

Indicator-Based Selection in Multiobjective Search Eckart Zitzler, Simon Künzli, in Parallel Problem Solving from Nature, Volume 3242 of the series Lecture Notes in Computer Science pp 832-842, 2004, http://dx.doi.org/10.1007/978-3-540-30217-9_84"

GA + continuous domination.

After mutation, down select as follows:

1. Remove an individual that losses most
2. If pop still too big, goto step 1.

Works Quite Well

Epsilon Dominance

Kalyanmoy Deb, Manikanth Mohan, and Shikhar Mishra. 2005. Evaluating the ε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions. Evol. Comput. 13, 4 (December 2005), 501-525. DOI=http://dx.doi.org/10.1162/106365605774666895

Simple. Under-used. Some studies say it works better than NSGA-II (which is potentially slower).

Two populations:

• a population of hastily-built, simplistically analyzed candidates
• an archive containing best-in-show.

Main loop

0. Build a population at random, then:
1. Using bdom, build an archive from the nondomnated parts of population
   • For "o" objectives, build an "o" dimensional chessboard where the objectives are divided into steps of size ε (some domain-specfic "near enough is good enough" number, gathered from the users);
   • Precompute and cache what cells dominate the other in dom[i] = [j1,j2,j3..];
   • Mark all archive cells as "undominated".
   • For all "c" in nondominated( population) call fastdom(c).
2. Using two random items p1,p2 from population
   • select the one "p" that bdom dominates (or, if none, either at random)
3. Pick a random item "a" from the archive
4. Create a candidate called "c" from p,a (using crossover and mutation)
5. Add "c" to the population, removing one item p3, selected as follows: - Searching in random order, if "c" bdom's "p3" from population, delete "p3" and goto step6 - If "c" dominates nothing, delete anything at random
6. Add "c" to archive using fastdom(c).
7. If current solutions good enough, then return archive.
8. If evaluation budget exhausted, then return archive,
9. Else, got to step2.

Fastdom(c) (fast way to build Pareto frontier in the archive, my name)

Here, the chessboard has cells and cells have only one member.

Case (a): ff "c" goes into a "dominated" cell then delete "c"

Case (b,d): if "c" goes into an unoccupoed "undominated" cell[i], follow the dom[i] links.

• for all j ε dom[i]
• if cell[j] is "undominated"
• then mark it "dominated" and recurse on dom[j].

Case (c): if "c" goes into an occupied cell, then delete either "c" or the occupant as follows:

• delete "c" f dominated by the occupant (using bdom);
• else delete occupant if "c" dominated occupant (using bdom)
• else delete the one furthest from "heaven" (Euclidean distance to Utopian point)

MOEA/D

Serious cool.

See MOEA/D