At a glance... |
Syllabus |
Models |
Code |
Lecturer
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.
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....
- np: number of candidates that dominate p (the upstream counter)
- Sp: candidates dominated by p (the downstream set)
- F1: 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
- For everything Q dominated by P
- For P 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 Ip
- Sort candidates by Ip
- 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+
(The following notes come for the excellent website Clever Algorithms.)
SPEA2: 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.
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:
Copyright © 2015 Tim Menzies.
This is free and unencumbered software released into the public domain.
For more details, see the license.