Most real design problems have more than one objective. A beam should be light and stiff, a schedule short and cheap, a model accurate and simple. When objectives conflict, there is usually no single best solution, only a set of trade-offs: solutions that cannot be improved in one objective without becoming worse in another. These are the Pareto-optimal solutions, and the image of the set in objective space is the Pareto front. Multi-objective optimization is the problem of finding that front, or a useful approximation of it, so that a decision maker can choose among the trade-offs knowing what each one costs.
Classical methods convert the problem into a sequence of single-objective problems, for example by optimizing a weighted sum of the objectives with different weights, and solve each one separately. Evolutionary algorithms offer a different route. A population can hold many trade-offs at once, so one run can approximate a whole front. This idea was tried in the mid-1980s and became practical in the 1990s, once selection was based on Pareto dominance and populations were kept spread along the front. NSGA-II, published in 2002, combined fast non-dominated sorting, a crowding measure, and elitism, and became one of the most widely used algorithms in the field. Comparing algorithms then raised a problem of its own. A front is a set of points, not a number, and the indicators that reduce it to a number can disagree.
Articles
Concepts
- Pareto dominance and Pareto optimality: decision and objective space, dominance, Pareto-optimal sets and fronts, ideal and nadir points, worked through on a small design problem.
- Weighted sums and the ε-constraint method: classical scalarization, why weighted sums cannot reach the non-convex parts of a front, and the ε-constraint and Tchebycheff alternatives.
Algorithms
- NSGA-II: fast non-dominated sorting, crowding distance, the crowded-comparison operator, and elitist survivor selection, implemented and run on the ZDT test problems.
- Multi-objective evolutionary algorithms: from VEGA and MOGA through SPEA2, MOEA/D, and indicator-based methods to NSGA-III and problems with many objectives.
Measuring results
- Quality indicators for Pareto fronts: hypervolume, generational distance, IGD, spacing, and spread, what each one measures, and how the choice of reference point can reverse a ranking.
- Ranking multi-objective optimizers with Pareto optimality: the paper presented in the course, which ranks algorithms by treating their indicator scores as objectives in their own right.
Related topics
Multi-objective algorithms reuse the encodings, operators, and selection schemes of genetic algorithms, replacing a single fitness value with dominance and diversity measures. Constraints are often handled with the same feasibility rules described in constraint handling. In neuroevolution and quality diversity, keeping a spread of solutions rather than one winner reappears in other forms.
References
- Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons.
- Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
- Eiben, A. E., and Smith, J. E. (2015). Introduction to Evolutionary Computing, 2nd ed. Springer.
- Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Kluwer Academic Publishers.