Evolutionary multi-objective optimization

Use of evolutionary algorithms for optimization problems with multiple objectives From Wikipedia, the free encyclopedia

Evolutionary multi-objective optimization (EMO), also called evolutionary multi-criterion optimization, is the application of evolutionary algorithms to multi-objective optimization problems. Such problems contain two or more objectives that are optimized simultaneously and generally give rise to a set of trade-off solutions rather than a single optimum.^[1]^[2]

Evolutionary methods are particularly suited to generating finite approximations of the Pareto front because a population can contain several candidate solutions representing different trade-offs at the same time. A typical EMO algorithm therefore attempts to improve convergence toward the Pareto front while maintaining diversity among the solutions.^[3]

Most EMO methods follow an a posteriori approach in which an approximation set is generated before a final solution is selected by a decision maker. Preference information can, however, also be incorporated during the evolutionary search.^[1]^[2]

Background

Evolutionary multi-objective optimization developed from the broader field of evolutionary computation. Early evolutionary-computation approaches included evolutionary programming, associated with the work of Fogel et al.,^[4] and genetic algorithms developed from Holland's work on adaptive systems.^[5]

Goldberg's Genetic Algorithms in Search, Optimization, and Machine Learning became an influential general reference on genetic algorithms,^[6] while Bäck's Evolutionary Algorithms in Theory and Practice provided a unified treatment of evolution strategies, evolutionary programming, and genetic algorithms.^[7]

History

Applications of evolutionary computation to multiple objectives preceded the establishment of EMO as a distinct research field.

Schaffer proposed the Vector Evaluated Genetic Algorithm (VEGA) in 1985. VEGA divided selection according to the individual objectives and demonstrated an early population-based approach to multi-objective optimization.^[8]

Kursawe subsequently developed a variant of evolution strategies for vector optimization. The method generated a finite set of efficient solutions and is an early example of an evolutionary method explicitly designed to approximate trade-offs in a multi-objective problem.^[9]

During the early 1990s, several algorithms introduced selection mechanisms based directly on Pareto dominance. Fonseca and Fleming proposed the Multiobjective Genetic Algorithm (MOGA), which assigned fitness according to dominance rank and used niching mechanisms to maintain multiple trade-off solutions.^[10]

Other influential approaches from this period included the original Nondominated Sorting Genetic Algorithm (NSGA) of Srinivas and Deb^[11] and the Niched Pareto Genetic Algorithm (NPGA) of Horn et al.^[12] These Pareto-based approaches helped establish the modern EMO field.^[1]^[2]

Coello Coello and Toscano Pulido later proposed a multi-objective micro-genetic algorithm, using a very small population together with reinitialization, memory, and elitist mechanisms.^[13]

General principles

An EMO algorithm usually maintains either a population of candidate solutions or an external archive containing selected non-dominated solutions. New solutions are generated by evolutionary variation operators such as mutation and recombination, and a selection mechanism determines which solutions survive.

Unlike single-objective evolutionary optimization, fitness assignment in EMO must account for several objectives. The main tasks of the selection mechanism are therefore to guide the population toward the Pareto-optimal set and to maintain a useful distribution of solutions across different trade-offs.^[1]^[3]

Common components include:

Pareto ranking, in which solutions are compared according to Pareto dominance;
diversity preservation, using techniques such as fitness sharing, crowding, clustering, reference directions, or density estimation;
elitism, in which high-quality non-dominated solutions are explicitly retained;
archiving, in which an external set stores selected non-dominated solutions;
quality indicators, which assign fitness according to a scalar measure of approximation-set quality; and
decomposition, in which a multi-objective problem is represented by a collection of scalar subproblems.

Major algorithmic approaches

Pareto-based methods

Pareto-based methods use dominance relations as a primary part of selection or fitness assignment. Early examples include MOGA, NSGA and NPGA.^[10]^[11]^[12]

The Pareto Archived Evolution Strategy (PAES) combines a simple evolution strategy with an archive of non-dominated solutions. Its basic form is a $(1+1)$ evolution strategy, while the archive is used both for dominance comparison and for maintaining diversity.^[14]

NSGA-II, proposed by Deb et al., introduced an elitist selection procedure, an improved non-dominated sorting method, and the crowding-distance measure for diversity preservation.^[15]

The Strength Pareto Evolutionary Algorithm 2 (SPEA2) uses dominance strength together with density information and an external archive.^[16]

Indicator-based methods

Indicator-based evolutionary algorithms use a numerical performance indicator for approximation sets as part of the selection mechanism.

Zitzler and Künzli introduced the general Indicator-Based Evolutionary Algorithm (IBEA), in which fitness assignment can be constructed from a chosen binary quality indicator.^[17]

The SMS-EMOA uses the hypervolume indicator directly in environmental selection. It combines non-dominated sorting with the hypervolume contributions of individual solutions, preferentially retaining a population with large hypervolume.^[18]

HypE is a hypervolume-based evolutionary algorithm developed for many-objective optimization. It estimates hypervolume values and contributions through Monte Carlo sampling when exact hypervolume computation becomes expensive.^[19]

Decomposition and reference-direction methods

Decomposition-based algorithms transform the multi-objective problem into a set of related scalar optimization subproblems.

MOEA/D, introduced by Zhang and Li, decomposes the original problem into scalar subproblems associated with different weight vectors and evolves solutions for neighboring subproblems cooperatively.^[20]

For problems with many objectives, reference-point or reference-direction mechanisms are also used to preserve a useful distribution of solutions. NSGA-III, proposed by Deb and Jain, extends non-dominated sorting with a reference-point-based diversity mechanism intended for many-objective optimization.^[21]

The boundaries between Pareto-based, indicator-based and decomposition-based methods are not always strict. Algorithms may combine dominance, decomposition, indicators, reference directions and preference information in the same selection mechanism.^[3]

Many-objective and many-criteria optimization

Optimization problems involving a relatively large number of objectives are commonly referred to as many-objective or many-criteria optimization problems. The term often refers to problems with more than three objectives, although no universal numerical threshold is required.^[22]

As the number of objectives increases, a progressively larger proportion of candidate solutions may become mutually non-dominated, reducing the selection pressure provided by conventional Pareto dominance. Performance assessment, visualization, diversity preservation and decision making also become increasingly difficult.^[22]

Early work explicitly addressing these difficulties includes Farina and Amato's study of solution concepts for many-criteria optimization problems.^[23] They examined limitations of conventional Pareto optimality and dominance when many criteria are considered and investigated alternative definitions of optimality.

Purshouse and Fleming subsequently investigated the behaviour of evolutionary multi-objective algorithms as the number of conflicting objectives increases. Their 2003 study Evolutionary many-objective optimisation: an exploratory analysis examined deterioration in evolutionary search behaviour with increasing objective-space dimension and discussed phenomena including dominance resistance.^[24]

Purshouse and Fleming later developed this analysis further, examining evolutionary optimization with many conflicting objectives and the loss of selection pressure associated with Pareto dominance.^[25]

Many-objective EMO has motivated methods based on decomposition, reference vectors or reference points, alternative dominance relations, objective reduction, dimensionality reduction, preference articulation, and quality indicators.^[2]^[21]^[22]

The term many-criteria optimization is broader than evolutionary optimization and also encompasses mathematical optimization, decision analysis and techniques for supporting decision makers confronted with many simultaneous criteria. Brockhoff et al. provide an interdisciplinary treatment spanning optimization, performance assessment, visualization, subset selection, machine learning and decision analysis.^[22]

Advantages and limitations

A principal advantage of evolutionary multi-objective optimization is that a population-based search can approximate several parts of a Pareto front in a single optimization run. Evolutionary algorithms also require no general assumptions of differentiability or convexity and can be applied to discrete, continuous, mixed-variable and black-box problems.^[1]^[2]

However, EMO algorithms are generally stochastic and do not guarantee Pareto optimality of the resulting approximation. Their performance depends on the variation and selection mechanisms, population size and stopping conditions. Maintaining convergence and diversity becomes particularly difficult as the number of objectives increases.^[3]^[25]

For computationally expensive objective functions, evolutionary methods may also require a large number of function evaluations. Surrogate-assisted and machine-learning-based variants have therefore been developed to reduce evaluation cost.

Performance assessment

Because EMO algorithms typically return sets of solutions, their performance cannot usually be evaluated through a single objective-function value. Performance indicators are therefore used to compare finite Pareto-front approximations.

Common criteria include convergence toward the Pareto front, coverage of different trade-offs, diversity, and the cardinality of the approximation set. The hypervolume indicator combines aspects of convergence and distribution in a single set-quality measure and is strictly Pareto-compliant.^[26]

Quality indicators may be used only for post-hoc performance evaluation or directly within an evolutionary algorithm as part of selection, as in IBEA and SMS-EMOA.^[17]^[18]

Decision making and preferences

The output of an a posteriori EMO method is generally a finite approximation of the Pareto front rather than a single recommended solution. A decision maker must subsequently choose among the resulting trade-offs.

Preference information can instead be incorporated during the evolutionary process. Preference-based EMO methods may focus the search on regions of interest defined by reference points, aspiration levels, weights or other preference models.^[1]^[2]

For many-criteria problems, interaction with the decision maker can become particularly important because presenting or interpreting a high-dimensional Pareto-front approximation becomes difficult.^[22]

Books and surveys

Book-length treatments of evolutionary multi-objective optimization include Deb's Multi-Objective Optimization Using Evolutionary Algorithms^[1] and Coello Coello et al.'s Evolutionary Algorithms for Solving Multi-Objective Problems.^[2]

For many-objective and many-criteria optimization, Brockhoff et al.'s edited volume Many-Criteria Optimization and Decision Analysis: State-of-the-Art, Present Challenges, and Future Perspectives covers optimization, evolutionary computation and decision analysis.^[22]

The broader evolutionary-computation background is covered by Goldberg's Genetic Algorithms in Search, Optimization, and Machine Learning^[6] and Bäck's Evolutionary Algorithms in Theory and Practice.^[7]

EMO conference series

The International Conference on Evolutionary Multi-Criterion Optimization (EMO) is a principal specialist conference series for evolutionary multi-objective and many-objective optimization. The first conference was held in Zürich, Switzerland, from 7 to 9 March 2001.^[27]

The conference series is commonly regarded as the flagship specialist meeting of the EMO research community. It has generally been organized biennially, with proceedings published in Springer's Lecture Notes in Computer Science series. Its scope includes evolutionary and other population-based multi-objective algorithms, theoretical foundations, performance assessment, many-objective optimization, decision making, machine learning and applications.^[28]

The EMO website maintains information about the conference series, previous meetings and the EMO community.^[28]

References

[1]
Deb, Kalyanmoy (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley-Interscience Series in Systems and Optimization. John Wiley & Sons. ISBN 978-0-471-87339-6.
[2]
Coello Coello, Carlos A.; Lamont, Gary B.; Van Veldhuizen, David A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems. Genetic and Evolutionary Computation (2nd ed.). New York: Springer. doi:10.1007/978-0-387-36797-2. ISBN 978-0-387-33254-3.
[3]
Emmerich, Michael T. M.; Deutz, André H. (2018). "A tutorial on multiobjective optimization: fundamentals and evolutionary methods". Natural Computing. 17 (3): 585–609. doi:10.1007/s11047-018-9685-y. PMC 6105305.
[4]
Fogel, Lawrence J.; Owens, Alvin J.; Walsh, Michael J. (1966). Artificial Intelligence Through Simulated Evolution. New York: John Wiley & Sons.
[5]
Holland, John H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.
[6]
Goldberg, David E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-15767-3.
[7]
Bäck, Thomas (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. New York: Oxford University Press. ISBN 978-0-19-509971-3.
[8]
Schaffer, J. David (1985). "Multiple Objective Optimization with Vector Evaluated Genetic Algorithms". Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates. pp. 93–100.
[9]
Kursawe, Frank (1991). "A Variant of Evolution Strategies for Vector Optimization". Parallel Problem Solving from Nature. Lecture Notes in Computer Science. Vol. 496. Springer. pp. 193–197. doi:10.1007/BFb0029752.
[10]
Fonseca, Carlos M.; Fleming, Peter J. (1993). "Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization". In Forrest, Stephanie (ed.). Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann. pp. 416–423. ISBN 1-55860-299-2.
[11]
Srinivas, Nidamurthy; Deb, Kalyanmoy (1994). "Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms". Evolutionary Computation. 2 (3): 221–248. doi:10.1162/evco.1994.2.3.221.
[12]
Horn, Jeffrey; Nafpliotis, Nicholas; Goldberg, David E. (1994). "A Niched Pareto Genetic Algorithm for Multiobjective Optimization". Proceedings of the First IEEE Conference on Evolutionary Computation. Vol. 1. IEEE. pp. 82–87. doi:10.1109/ICEC.1994.350037.
[13]
Coello Coello, Carlos A.; Toscano Pulido, Gregorio (2001). "A Micro-Genetic Algorithm for Multiobjective Optimization". Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science. Vol. 1993. Springer. pp. 126–140. doi:10.1007/3-540-44719-9_9.
[14]
Knowles, Joshua D.; Corne, David W. (2000). "Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy". Evolutionary Computation. 8 (2): 149–172. doi:10.1162/106365600568167. PMID 10843519.
[15]
Deb, Kalyanmoy; Pratap, Amrit; Agarwal, Sameer; Meyarivan, T. (2002). "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation. 6 (2): 182–197. doi:10.1109/4235.996017.
[16]
Zitzler, Eckart; Laumanns, Marco; Thiele, Lothar (2002). "SPEA2: Improving the Strength Pareto Evolutionary Algorithm". Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems. pp. 95–100.
[17]
Zitzler, Eckart; Künzli, Simon (2004). "Indicator-Based Selection in Multiobjective Search". Parallel Problem Solving from Nature – PPSN VIII. Lecture Notes in Computer Science. Vol. 3242. Springer. pp. 832–842. doi:10.1007/978-3-540-30217-9_84.
[18]
Beume, Nicola; Naujoks, Boris; Emmerich, Michael (2007). "SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume". European Journal of Operational Research. 181 (3): 1653–1669. doi:10.1016/j.ejor.2006.08.008.
[19]
Bader, Johannes; Zitzler, Eckart (2011). "HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization". Evolutionary Computation. 19 (1): 45–76. doi:10.1162/EVCO_a_00009. PMID 20649424.
[20]
Zhang, Qingfu; Li, Hui (2007). "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition". IEEE Transactions on Evolutionary Computation. 11 (6): 712–731. doi:10.1109/TEVC.2007.892759.
[21]
Deb, Kalyanmoy; Jain, Himanshu (2014). "An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints". IEEE Transactions on Evolutionary Computation. 18 (4): 577–601. doi:10.1109/TEVC.2013.2281535.
[22]
Brockhoff, Dimo; Emmerich, Michael; Naujoks, Boris; Purshouse, Robin, eds. (2023). Many-Criteria Optimization and Decision Analysis: State-of-the-Art, Present Challenges, and Future Perspectives. Natural Computing Series. Cham: Springer. doi:10.1007/978-3-031-25263-1. ISBN 978-3-031-25262-4.
[23]
Farina, Marco; Amato, Paolo (2002). "On the Optimal Solution Definition for Many-Criteria Optimization Problems". 2002 Annual Meeting of the North American Fuzzy Information Processing Society Proceedings. IEEE. pp. 233–238. doi:10.1109/NAFIPS.2002.1018061.
[24]
Purshouse, Robin C.; Fleming, Peter J. (2003). "Evolutionary Many-Objective Optimisation: An Exploratory Analysis". Proceedings of the 2003 Congress on Evolutionary Computation. Vol. 3. IEEE. pp. 2066–2073. doi:10.1109/CEC.2003.1299927.
[25]
Purshouse, Robin C.; Fleming, Peter J. (2007). "On the Evolutionary Optimization of Many Conflicting Objectives". IEEE Transactions on Evolutionary Computation. 11 (6): 770–784. doi:10.1109/TEVC.2007.910138.
[26]
Zitzler, Eckart; Thiele, Lothar; Laumanns, Marco; Fonseca, Carlos M.; Grunert da Fonseca, Viviane (2003). "Performance Assessment of Multiobjective Optimizers: An Analysis and Review". IEEE Transactions on Evolutionary Computation. 7 (2): 117–132. doi:10.1109/TEVC.2003.810758.
[27]
Zitzler, Eckart; Thiele, Lothar; Deb, Kalyanmoy; Coello Coello, Carlos A.; Corne, David, eds. (2001). Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 7–9, 2001, Proceedings. Lecture Notes in Computer Science. Vol. 1993. Springer. doi:10.1007/3-540-44719-9. ISBN 978-3-540-41745-3.
[28]
"The EMO Website". EMO Online. Retrieved 28 August 2026.