Content deleted Content added
Altered template type. Add: arxiv, pmid, doi, pages, issue, volume, date, journal, title, bibcode, authors 1-4. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget |
|||
| (31 intermediate revisions by 20 users not shown) | |||
Line 6:
'''Bicriteria optimization''' denotes the special case in which there are two objective functions.
There is a direct relationship between [[multitask optimization]] and multi-objective optimization.<ref>J. -Y. Li, Z. -H. Zhan, Y. Li and J. Zhang, "Multiple Tasks for Multiple Objectives: A New Multiobjective Optimization Method via Multitask Optimization," in IEEE Transactions on Evolutionary Computation, {{doi|10.1109/TEVC.2023.3294307}}</ref>
== Introduction ==▼
▲== Introduction ==
A multi-objective optimization problem is an [[optimization problem]] that involves multiple objective functions.<ref name="Miettinen1999" /><ref name="HwangMasud1979" /><ref name=hassanzadeh>{{cite journal|last1=Hassanzadeh|first1=Hamidreza|last2=Rouhani|first2=Modjtaba|title=A multi-objective gravitational search algorithm|journal=In Computational Intelligence, Communication Systems and Networks (CICSyN)|date=2010|pages=7–12}}</ref> In mathematical terms, a multi-objective optimization problem can be formulated as▼
{{See also|Pareto order}}
▲A multi-objective optimization problem is an [[optimization problem]] that involves multiple objective functions.<ref name="Miettinen1999" /><ref name="HwangMasud1979" /><ref name=hassanzadeh>{{cite journal |last1=Hassanzadeh |first1=Hamidreza |last2=Rouhani |first2=Modjtaba |title=A multi-objective gravitational search algorithm |journal=In Computational Intelligence, Communication Systems and Networks (CICSyN) |date=2010 |pages=7–12}}</ref> In mathematical terms, a multi-objective optimization problem can be formulated as
: <math>
\min_{x \in X} (f_1(x), f_2(x),\ldots, f_k(x))
Line 23 ⟶ 25:
\end{align}</math>
[[File:Front pareto.svg|thumb|300px|Example of a [[Pareto frontier]] (in red), the set of Pareto optimal solutions (those that are not dominated by any other feasible solutions). The boxed points represent feasible choices, and smaller values are preferred to larger ones. Point ''C'' is not on the Pareto frontier because it is dominated by both point ''A'' and point ''B''. Points ''A'' and ''B'' are not strictly dominated by any other, and hence do lie on the frontier.]]
If some objective function is to be maximized, it is equivalent to minimize its negative or its inverse. We denote <math>Y \subseteq \mathbb R^k</math> the image of <math>X</math>; <math>x^*\in X</math> a [[feasible solution]] or '''feasible decision'''; and <math>z^* = f(x^*) \in \mathbb R^k</math>an '''objective vector''' or an '''outcome'''.
Line 32 ⟶ 33:
A solution <math>x^*\in X</math> (and the corresponding outcome <math>f(x^*)</math>) is called Pareto optimal if there does not exist another solution that dominates it. The set of Pareto optimal outcomes, denoted <math> X^* </math>, is often called the '''[[Pareto front]]''', Pareto frontier, or Pareto boundary.
The Pareto front of a multi-objective optimization problem is bounded by a so-called '''[[nadir]] objective vector''' <math> z^{nadir} </math>and an '''ideal objective vector''' <math> z^{ideal} </math>, if these are finite. The nadir objective vector is defined as
:<math> z^{nadir} = \begin{pmatrix}
\sup_{x^* \in X^*} f_1(x^*) \\
Line 61 ⟶ 62:
===Optimal control===
{{Main
In [[engineering]] and [[economics]], many problems involve multiple objectives which are not describable as the-more-the-better or the-less-the-better; instead, there is an ideal target value for each objective, and the desire is to get as close as possible to the desired value of each objective. For example, energy systems typically have a trade-off between performance and cost<ref>{{Cite journal |last1=Shirazi |first1=Ali |last2=Najafi |first2=Behzad |last3=Aminyavari |first3=Mehdi |last4=Rinaldi |first4=Fabio |last5=Taylor |first5=Robert A. |date=2014-05-01 |title=Thermal–economic–environmental analysis and multi-objective optimization of an ice thermal energy storage system for gas turbine cycle inlet air cooling |journal=Energy |volume=69 |pages=212–226 |doi=10.1016/j.energy.2014.02.071 |hdl=11311/845828 |doi-access=free |bibcode=2014Ene....69..212S |hdl-access=free}}</ref><ref>{{cite journal |last1=Najafi |first1=Behzad |last2=Shirazi |first2=Ali |last3=Aminyavari |first3=Mehdi |last4=Rinaldi |first4=Fabio |last5=Taylor |first5=Robert A. |date=2014-02-03 |title=Exergetic, economic and environmental analyses and multi-objective optimization of an SOFC-gas turbine hybrid cycle coupled with an MSF desalination system |journal=Desalination |volume=334 |issue=1 |pages=46–59 |doi=10.1016/j.desal.2013.11.039 |hdl=11311/764704 |doi-access=free |bibcode=2014Desal.334...46N |hdl-access=free}}</ref> or one might want to adjust a rocket's fuel usage and orientation so that it arrives both at a specified place and at a specified time; or one might want to conduct [[open market operations]] so that both the [[inflation rate]] and the [[unemployment rate]] are as close as possible to their desired values.
Often such problems are subject to linear equality constraints that prevent all objectives from being simultaneously perfectly met, especially when the number of controllable variables is less than the number of objectives and when the presence of random shocks generates uncertainty. Commonly a multi-objective [[quadratic function#Bivariate (two variable) quadratic function|quadratic objective function]] is used, with the cost associated with an objective rising quadratically with the distance of the objective from its ideal value. Since these problems typically involve adjusting the controlled variables at various points in time and/or evaluating the objectives at various points in time, [[intertemporal optimization]] techniques are employed.<ref>{{cite book |doi=10.1109/IECON.2009.5415056 |isbn=978-1-4244-4648-3 |chapter=Chaos rejection and optimal dynamic response for boost converter using SPEA multi-objective optimization approach |title=2009 35th Annual Conference of IEEE Industrial Electronics |pages=3315–3322 |year=2009 |last1=Rafiei |first1=S. M. R. |last2=Amirahmadi |first2=A. |last3=Griva |first3=G. |s2cid=2539380 }}</ref>
===Optimal design===
Line 71 ⟶ 72:
Product and process design can be largely improved using modern modeling, simulation, and optimization techniques.{{citation needed|date=February 2017}} The key question in optimal design is measuring what is good or desirable about a design. Before looking for optimal designs, it is important to identify characteristics that contribute the most to the overall value of the design. A good design typically involves multiple criteria/objectives such as capital cost/investment, operating cost, profit, quality and/or product recovery, efficiency, process safety, operation time, etc. Therefore, in practical applications, the performance of process and product design is often measured with respect to multiple objectives. These objectives are typically conflicting, i.e., achieving the optimal value for one objective requires some compromise on one or more objectives.
For example, when designing a paper mill, one can seek to decrease the amount of capital invested in a paper mill and enhance the quality of paper simultaneously. If the design of a paper mill is defined by large storage volumes and paper quality is defined by quality parameters, then the problem of optimal design of a paper mill can include objectives such as i) minimization of expected variation of those quality parameters from their nominal values, ii) minimization of the expected time of breaks and iii) minimization of the investment cost of storage volumes. Here, the maximum volume of towers is a design variable. This example of optimal design of a paper mill is a simplification of the model used in.<ref name=RoRiPi11>{{Cite journal |
=== {{anchor|MOGA}} Process optimization ===
Line 80 ⟶ 81:
In 2013, Ganesan et al. carried out the multi-objective optimization of the combined carbon dioxide reforming and partial oxidation of methane. The objective functions were methane conversion, carbon monoxide selectivity, and hydrogen to carbon monoxide ratio. Ganesan used the Normal Boundary Intersection (NBI) method in conjunction with two swarm-based techniques (Gravitational Search Algorithm (GSA) and Particle Swarm Optimization (PSO)) to tackle the problem.<ref>{{Cite journal|title = Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production|journal = Applied Energy|date = 2013-03-01|pages = 368–374|volume = 103|doi = 10.1016/j.apenergy.2012.09.059|first1 = T.|last1 = Ganesan|first2 = I.|last2 = Elamvazuthi|first3 = Ku Zilati|last3 = Ku Shaari|first4 = P.|last4 = Vasant| bibcode=2013ApEn..103..368G }}</ref> Applications involving chemical extraction<ref>{{Cite book|publisher = Springer International Publishing|date = 2015-03-23|isbn = 978-3-319-15704-7|pages = 13–21|series = Lecture Notes in Computer Science|doi = 10.1007/978-3-319-15705-4_2|first1 = Timothy|last1 = Ganesan|first2 = Irraivan|last2 = Elamvazuthi|first3 = Pandian|last3 = Vasant|first4 = Ku Zilati Ku|last4 = Shaari| title=Intelligent Information and Database Systems | chapter=Multiobjective Optimization of Bioactive Compound Extraction Process via Evolutionary Strategies | volume=9012 |editor-first = Ngoc Thanh|editor-last = Nguyen|editor-first2 = Bogdan|editor-last2 = Trawiński|editor-first3 = Raymond|editor-last3 = Kosala}}</ref> and bioethanol production processes<ref>{{Cite book|title = Contemporary Advancements in Information Technology Development in Dynamic Environments|url = https://books.google.com/books?id=L6N_BAAAQBAJ|publisher = IGI Global|date = 2014-06-30|isbn = 9781466662537|first = Khosrow-Pour|last = Mehdi}}</ref> have posed similar multi-objective problems.
In 2013, Abakarov et al. proposed an alternative technique to solve multi-objective optimization problems arising in food engineering.<ref>{{Cite journal|title=Multi-criteria optimization and decision-making approach for improving of food engineering processes
In 2018, Pearce et al. formulated task allocation to human and robotic workers as a multi-objective optimization problem, considering production time and the ergonomic impact on the human worker as the two objectives considered in the formulation. Their approach used a [[Linear programming|Mixed-Integer Linear Program]] to solve the optimization problem for a weighted sum of the two objectives to calculate a set of [[Pareto efficiency|Pareto optimal]] solutions. Applying the approach to several manufacturing tasks showed improvements in at least one objective in most tasks and in both objectives in some of the processes.<ref>{{Cite journal |last1=Pearce |first1=Margaret |last2=Mutlu |first2=Bilge |last3=Shah |first3=Julie |last4=Radwin |first4=Robert |date=2018 |title=Optimizing Makespan and Ergonomics in Integrating Collaborative Robots Into Manufacturing Processes |journal=IEEE Transactions on Automation Science and Engineering |volume=15 |issue=4 |language=en-US |pages=1772–1784 |doi=10.1109/tase.2018.2789820 |bibcode=2018ITASE..15.1772P |s2cid=52927442|issn=1545-5955 |doi-access=free}}</ref>
===Radio resource management===
Line 96 ⟶ 97:
=== Inspection of infrastructure ===
Autonomous inspection of infrastructure has the potential to reduce costs, risks and environmental impacts, as well as ensuring better periodic maintenance of inspected assets. Typically, planning such missions has been viewed as a single-objective optimization problem, where one aims to minimize the energy or time spent in inspecting an entire target structure.<ref name="GalceranCarreras2013">{{cite journal|last1=Galceran|first1=Enric|last2=Carreras |first2=Marc|title=A survey on coverage path planning for robotics|journal=Robotics and Autonomous Systems|volume=61 |issue=12|year=2013|pages=1258–1276|issn=0921-8890 |doi=10.1016/j.robot.2013.09.004|citeseerx=10.1.1.716.2556|s2cid=1177069 }}</ref> For complex, real-world structures, however, covering 100% of an inspection target is not feasible, and generating an inspection plan may be better viewed as a multiobjective optimization problem, where one aims to both maximize inspection coverage and minimize time and costs. A recent study has indicated that multiobjective inspection planning indeed has the potential to outperform traditional methods on complex structures<ref name="EllefsenLepikson2017">{{cite journal |last1=Ellefsen |first1=K.O. |last2=Lepikson |first2=H.A. |last3=Albiez |first3=J.C. |title=Multiobjective coverage path planning: Enabling automated inspection of complex, real-world structures |journal=Applied Soft Computing |volume=61 |year=2019 |pages=264–282 |issn=1568-4946 |doi=10.1016/j.asoc.2017.07.051 |url=https://www.researchgate.net/publication/318893583 |hdl=10852/58883 |arxiv=1901.07272
== Solution ==
Line 102 ⟶ 103:
As multiple [[Pareto optimality|Pareto optimal]] solutions for multi-objective optimization problems usually exist, what it means to solve such a problem is not as straightforward as it is for a conventional single-objective optimization problem. Therefore, different researchers have defined the term "solving a multi-objective optimization problem" in various ways. This section summarizes some of them and the contexts in which they are used. Many methods convert the original problem with multiple objectives into a single-objective [[optimization problem]]. This is called a scalarized problem. If the Pareto optimality of the single-objective solutions obtained can be guaranteed, the scalarization is characterized as done neatly.
Solving a multi-objective optimization problem is sometimes understood as approximating or computing all or a representative set of Pareto optimal solutions.<ref name="Ehrgott2005">{{cite book|author=Matthias Ehrgott|title=Multicriteria Optimization |url=https://books.google.com/books?id=yrZw9srrHroC|access-date=29 May 2012|date=1 June 2005|publisher=Birkhäuser|isbn=978-3-540-21398-7}}</ref><ref name="CoelloLamont2007">{{cite book|author1=Carlos A. Coello
When [[Multiple-criteria decision analysis|decision making]] is emphasized, the objective of solving a multi-objective optimization problem is referred to as supporting a decision maker in finding the most preferred Pareto optimal solution according to their subjective preferences.<ref name="Miettinen1999">{{cite book|author=Kaisa Miettinen|title=Nonlinear Multiobjective Optimization|url=https://books.google.com/books?id=ha_zLdNtXSMC|access-date=29 May 2012|year=1999 |publisher=Springer|isbn=978-0-7923-8278-2}}</ref><ref name="BrankeDeb2008">{{cite book|author1=Jürgen Branke|author2=Kalyanmoy Deb|author3=Kaisa Miettinen|author4=Roman Slowinski|title=Multiobjective Optimization: Interactive and Evolutionary Approaches |url=https://books.google.com/books?id=N-1hWMNUa2EC|access-date=1 November 2012|date=21 November 2008 |publisher=Springer |isbn=978-3-540-88907-6}}</ref> The underlying assumption is that one solution to the problem must be identified to be implemented in practice. Here, a human [[decision maker]] (DM) plays an important role. The DM is expected to be an expert in the problem ___domain.
The most preferred results can be found using different philosophies. Multi-objective optimization methods can be divided into four classes.<ref name="HwangMasud1979">{{cite book|author1=Ching-Lai Hwang|author2=Abu Syed Md Masud|title=Multiple objective decision making, methods and applications: a state-of-the-art survey |url=https://archive.org/details/multipleobjectiv0000hwan |url-access=registration|access-date=29 May 2012|year=1979 |publisher=Springer-Verlag|isbn=978-0-387-09111-2}}</ref>
# In so-called '''no-preference methods''', no DM is expected to be available, but a neutral compromise solution is identified without preference information.<ref name="Miettinen1999" /> The other classes are so-called a priori, a posteriori, and interactive methods, and they all involve preference information from the DM in different ways.
Line 139 ⟶ 140:
=== Scalarizing ===
[[File:NonConvex.gif|thumb|Linear scalarization approach is an easy method used to solve multi-objective optimization problem. It consists in aggregating the different optimization functions in a single function. However, this method only allows to find the supported solutions of the problem (i.e. points on the convex hull of the objective set). This animation shows that when the outcome set is not convex, not all efficient solutions can be found.]]
Scalarizing a multi-objective optimization problem is an a priori method, which means formulating a single-objective optimization problem such that optimal solutions to the single-objective optimization problem are Pareto optimal solutions to the multi-objective optimization problem.<ref name="HwangMasud1979" /> In addition, it is often required that every Pareto optimal solution can be reached with some parameters of the scalarization.<ref name="HwangMasud1979" /> With different parameters for the scalarization, different Pareto optimal solutions are produced. A general formulation for a scalarization of a multi-objective optimization problem is
Line 188 ⟶ 190:
:where <math>W_j</math> is individual optima (absolute) for objectives of maximization <math>r</math> and minimization <math>r+1</math> to <math>s</math>.
* '''hypervolume/Chebyshev scalarization'''<ref name="Golovin2021">
::<math>
\min_{x\in X} \max_i \frac{ f_i(x)}{w_i}
</math>
:where the weights of the objectives <math>w_i>0</math> are the parameters of the scalarization. If the parameters/weights are drawn uniformly in the positive orthant, it is shown that this scalarization provably converges to the [[Pareto front]],<ref name="Golovin2021" /> even when the front is non-convex.
=== Smooth Chebyshev (Tchebycheff) scalarization ===
The '''smooth Chebyshev scalarization''';<ref name="Lin2024">{{cite arXiv | last1=Lin | first1=Xi | last2=Zhang | first2=Xiaoyuan | last3=Yang | first3=Zhiyuan | last4=Liu | first4=Fei | last5=Wang | first5=Zhenkun | last6=Zhang | first6=Qingfu | title=Smooth Tchebycheff Scalarization for Multi-Objective Optimization | date=2024 | class=cs.LG | eprint=2402.19078 }}</ref> also called smooth Tchebycheff scalarisation (STCH); replaces the non-differentiable max-operator of the classical Chebyshev scalarization with a smooth logarithmic soft-max, making standard gradient-based optimization applicable. Unlike typical scalarization methods, it guarantees exploration of the entire Pareto front, convex or concave.
;Definition
For a minimization problem with objective functions <math>f_{1},\dots ,f_{k}</math> and the ideal objective vector <math>z^{\mathrm{ideal}}\in\mathbb{R}^{k}</math>, the smooth Chebyshev scalarising function is
<math>
g_{u}^{\mathrm{STCH}}\!\bigl(x\mid\boldsymbol{\lambda}\bigr)=
u\,\ln\!\Bigl(\sum_{i=1}^{k}\exp\!\bigl(\tfrac{\lambda_{i}\,[\,f_{i}(x)-z^{\mathrm{ideal}}_{i}\,]}{u}\bigr)\Bigr),
\qquad
u>0,\;
\boldsymbol{\lambda}\in\Delta_{k-1},
</math>
where <math>u</math> is the ''smoothing parameter'' and <math>\boldsymbol{\lambda}=(\lambda_{1},\dots ,\lambda_{k})</math> is a weight vector on the probability simplex <math>\Delta_{k-1}</math>.
As <math>u\to 0^{+}</math> this converges to the classical (non-smooth) Chebyshev form
<math>
g^{\mathrm{TCH}}\!\bigl(x\mid\boldsymbol{\lambda}\bigr)=
\max_{i}\lambda_{i}\,[\,f_{i}(x)-z^{\mathrm{ideal}}_{i}\,].
</math>
The parameter <math>u</math> controls the trade-off between differentiability and approximation accuracy: smaller values yield a closer match to the classical Chebyshev scalarisation but reduce the [[Lipschitz continuity#Lipschitz constant|Lipschitz constant]] of the gradient, while larger values give a smoother surface at the cost of looser approximation.
[[File:Smooth chebyshev.gif|thumb|STCH covers whole Pareto front; convex or concave; because for every preference vector <math>\boldsymbol{\lambda}\in\Delta</math> the minimiser of <math>g^{\mathrm{STCH}}_{u}(x\mid\boldsymbol{\lambda})</math> lands exactly on a Pareto-optimal point.]]
;Properties
* '''Smoothness and complexity''' — <math>g_{u}^{\mathrm{STCH}}</math> is continuously differentiable with an <math>L</math>-Lipschitz gradient. When every <math>f_{i}</math> is convex the function is convex, and an <math>\varepsilon</math>-optimal point is reachable in <math>\mathcal{O}(1/\varepsilon)</math> first-order iterations; sub-gradient descent on <math>g^{\mathrm{TCH}}</math> needs <math>\mathcal{O}(1/\varepsilon^{2})</math> iterations.<ref name="Lin2024"/>
* '''Pareto optimality''' — For any <math>u>0</math> every minimizer of <math>g_{u}^{\mathrm{STCH}}(\cdot\mid\boldsymbol{\lambda})</math> is weakly Pareto-optimal; if all <math>\lambda_{i}>0</math> (or the minimizer is unique) it is Pareto-optimal.<ref name="Lin2024"/>
* '''Exhaustiveness''' — There exists a threshold <math>u^{*}>0</math> such that, for <math>0<u<u^{*}</math>, every Pareto-optimal point can be obtained as a minimizer of <math>g_{u}^{\mathrm{STCH}}</math> for some weight vector <math>\boldsymbol{\lambda}</math>; when the Pareto front is convex this holds for all <math>u>0</math>.<ref name="Lin2024"/>
For example, [[portfolio optimization]] is often conducted in terms of [[Modern portfolio theory|mean-variance analysis]]. In this context, the efficient set is a subset of the portfolios parametrized by the portfolio mean return <math>\mu_P</math> in the problem of choosing portfolio shares to minimize the portfolio's variance of return <math>\sigma_P</math> subject to a given value of <math>\mu_P</math>; see [[Mutual fund separation theorem#Portfolio separation in mean-variance analysis|Mutual fund separation theorem]] for details. Alternatively, the efficient set can be specified by choosing the portfolio shares to maximize the function <math>\mu_P - b \sigma_P </math>; the set of efficient portfolios consists of the solutions as <math>b</math> ranges from zero to infinity.
Some of the above scalarizations involve invoking the [[minimax]] principle, where always the worst of the different objectives is optimized.<ref>Xu, J., Tao, Z. (2011). Rough Multiple Objective Decision Making. Vereinigtes Königreich: CRC Press., Page 67 https://books.google.com/books?id=zwDSBQAAQBAJ&dq=the%20minimax%20multi%20objective%20-game&pg=PA67</ref>
== A posteriori methods ==
A posteriori methods aim at producing all the Pareto optimal solutions or a representative subset of the Pareto optimal solutions. Most a posteriori methods fall into either one of the following three classes:
* [[Mathematical programming]]-based a posteriori methods where an algorithm is
* [[Evolutionary algorithm]]s where one run of the algorithm produces a set of Pareto optimal solutions;
* [[Deep learning]] methods where a model is first trained on a subset of solutions and then queried to provide other solutions on the Pareto front.
=== Mathematical programming ===
Well-known examples of mathematical programming-based a posteriori methods are the Normal Boundary Intersection (NBI),<ref name="doi10.1137/S1052623496307510">{{Cite journal | last1 = Das | first1 = I. | last2 = Dennis | first2 = J. E. | doi = 10.1137/S1052623496307510 | title = Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems | journal = SIAM Journal on Optimization | volume = 8 | issue = 3 | pages = 631 | year = 1998 | hdl = 1911/101880| s2cid = 207081991 | hdl-access = free }}</ref> Modified Normal Boundary Intersection (NBIm),<ref name="S. Motta">{{cite journal|last=
=== Evolutionary algorithms ===
[[Evolutionary algorithms]] are popular approaches to generating Pareto optimal solutions to a multi-objective optimization problem. Most evolutionary multi-objective optimization (EMO) algorithms apply Pareto-based ranking schemes. Evolutionary algorithms such as the Non-dominated Sorting Genetic Algorithm-II (NSGA-II),<ref name="doi10.1109/4235.996017">{{Cite journal | doi = 10.1109/4235.996017| title = A fast and elitist multiobjective genetic algorithm: NSGA-II| journal = IEEE Transactions on Evolutionary Computation| volume = 6| issue = 2| pages = 182| year = 2002| last1 = Deb | first1 = K.| last2 = Pratap | first2 = A.| last3 = Agarwal | first3 = S.| last4 = Meyarivan | first4 = T.| bibcode = 2002ITEC....6..182D| citeseerx = 10.1.1.17.7771| s2cid = 9914171}}</ref> its extended version NSGA-III,<ref>{{Cite journal |last1=Deb |first1=Kalyanmoy |last2=Jain |first2=Himanshu |date=2014 |title=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints
Another paradigm for multi-objective optimization based on novelty using evolutionary algorithms was recently improved upon.<ref name=vargas2015>
=== Deep learning methods ===
[[Deep learning]] conditional methods are new approaches to generating several Pareto optimal solutions. The idea is to use the generalization capacity of deep neural networks to learn a model of the entire Pareto front from a limited number of example trade-offs along that front, a task called ''Pareto Front Learning''.<ref name=":0">{{Cite journal |last1=Navon |first1=Aviv |last2=Shamsian |first2=Aviv |last3=Chechik |first3=Gal |last4=Fetaya |first4=Ethan |date=2021-04-26 |title=Learning the Pareto Front with Hypernetworks |url=https://openreview.net/pdf?id=NjF772F4ZZR |journal=Proceedings of International Conference on Learning Representations (ICLR)|arxiv=2010.04104 }}</ref> Several approaches address this setup, including using hypernetworks<ref name=":0" /> and using Stein variational gradient descent.<ref>{{Cite journal |last1=Xingchao |first1=Liu |last2=Xin |first2=Tong |last3=Qiang |first3=Liu |date=2021-12-06 |title=Profiling Pareto Front With Multi-Objective Stein Variational Gradient Descent |url=https://proceedings.neurips.cc/paper/2021/hash/7bb16972da003e87724f048d76b7e0e1-Abstract.html |journal=Advances in Neural Information Processing Systems |language=en |volume=34}}</ref>
Line 216 ⟶ 251:
Commonly known a posteriori methods are listed below:
* ε-constraint method<ref name="Mavrotas2009">{{cite journal|last1=Mavrotas|first1=George|title=Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems|journal=Applied Mathematics and Computation|volume=213|issue=2|year=2009|pages=455–465|issn=0096-3003|doi=10.1016/j.amc.2009.03.037}}</ref><ref name="CarvalhoRibeiro2020">{{cite journal|last1=Carvalho|first1=Iago A.|last2=Ribeiro|first2=Marco A.|title=An exact approach for the Minimum-Cost Bounded-Error Calibration Tree problem|journal=Annals of Operations Research|volume=287|issue=1|year=2020|pages=109–126|issn=0254-5330|doi=10.1007/s10479-019-03443-4|s2cid=209959109}}</ref>
* Pareto-Hypernetworks <ref name=":0"/>
* Multi-objective Branch-and-Bound<ref name="MavrotasDiakoulaki2005">{{cite journal|last1=Mavrotas|first1=G.|last2=Diakoulaki|first2=D.|title=Multi-criteria branch and bound: A vector maximization algorithm for Mixed 0-1 Multiple Objective Linear Programming|journal=Applied Mathematics and Computation|volume=171|issue=1|year=2005|pages=53–71|issn=0096-3003|doi=10.1016/j.amc.2005.01.038}}</ref><ref name="VincentSeipp2013">{{cite journal|last1=Vincent|first1=Thomas|last2=Seipp|first2=Florian|last3=Ruzika|first3=Stefan|last4=Przybylski|first4=Anthony|last5=Gandibleux|first5=Xavier|title=Multiple objective branch and bound for mixed 0-1 linear programming: Corrections and improvements for the biobjective case|journal=Computers & Operations Research|volume=40|issue=1|year=2013|pages=498–509|issn=0305-0548|doi=10.1016/j.cor.2012.08.003}}</ref><ref name="PrzybylskiGandibleux2017">{{cite journal|last1=Przybylski|first1=Anthony|last2=Gandibleux|first2=Xavier|title=Multi-objective branch and bound|journal=European Journal of Operational Research|volume=260|issue=3|year=2017|pages=856–872|issn=0377-2217|doi=10.1016/j.ejor.2017.01.032}}</ref>
* Normal Boundary Intersection (NBI)<ref name="doi10.1137/S1052623496307510" />
Line 257 ⟶ 292:
# classification of objective functions.<ref name=Miettinen2008 />
On the other hand, a fourth type of generating a small sample of solutions is included in:<ref name=Luque2011>{{cite journal | last1 = Luque | first1 = M. | last2 = Ruiz | first2 = F. | last3 = Miettinen | first3 = K. | title = Global formulation for interactive multiobjective optimization | doi = 10.1007/s00291-008-0154-3 | journal = OR Spectrum | volume = 33 | pages = 27–48 | year = 2008 | s2cid = 15050545 | url = http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-65364}}</ref><ref name=Ruiz2012>{{Cite journal | last1 = Ruiz | first1 = F. | last2 = Luque | first2 = M. | last3 = Miettinen | first3 = K. | title = Improving the computational efficiency in a global formulation (GLIDE) for interactive multiobjective optimization | doi = 10.1007/s10479-010-0831-x | journal = Annals of Operations Research | volume = 197 | pages = 47–70 | year = 2011 | s2cid = 14947919 | url = http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-63800}}</ref> An example of the interactive method utilizing trade-off information is the [[Zionts-Wallenius method]],<ref name=Zionts1976>{{cite journal | last1 = Zionts | first1 = S. | last2 = Wallenius | first2 = J. | doi = 10.1287/mnsc.22.6.652 | title = An Interactive Programming Method for Solving the Multiple Criteria Problem | journal = Management Science | volume = 22 | issue = 6 | pages = 652 | year = 1976 }}</ref> where the decision maker is shown several objective trade-offs at each iteration, and (s)he is expected to say whether (s)he likes, dislikes, or is indifferent with respect to each trade-off. In reference point-based methods (see e.g.,
| last1 = Nakayama
| first1 = H.
Line 275 ⟶ 310:
== Hybrid methods ==
Different [[hybrid algorithm|hybrid]] methods exist, but here we consider hybridizing MCDM ([[multi-criteria decision-making]]) and EMO (evolutionary multi-objective optimization). A hybrid algorithm in multi-objective optimization combines algorithms/approaches from these two fields (see e.g.,
The roots for hybrid multi-objective optimization can be traced to the first Dagstuhl seminar organized in November 2004 (see [http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=04461 here]). Here, some of the best minds{{Citation needed|date=July 2018}} in EMO (Professor Kalyanmoy Deb, Professor Jürgen Branke, etc.) and MCDM (Professor Kaisa Miettinen, Professor Ralph E. Steuer, etc.) realized the potential in combining ideas and approaches of MCDM and EMO fields to prepare hybrids of them. Subsequently, many more Dagstuhl seminars have been arranged to foster collaboration. Recently, hybrid multi-objective optimization has become an important theme in several international conferences in the area of EMO and MCDM (see e.g.,
== Visualization of the Pareto front ==
Visualization of the Pareto front is one of the a posteriori preference techniques of multi-objective optimization. The a posteriori preference techniques provide an important class of multi-objective optimization techniques.<ref name="Miettinen1999" /> Usually, the a posteriori preference techniques include four steps: (1) computer approximates the Pareto front, i.e., the Pareto optimal set in the objective space; (2) the decision maker studies the Pareto front approximation; (3) the decision maker identifies the preferred point at the Pareto front; (4) computer provides the Pareto optimal decision, whose output coincides with the objective point identified by the decision maker. From the point of view of the decision maker, the second step of the a posteriori preference techniques is the most complicated. There are two main approaches to informing the decision maker. First, a number of points of the Pareto front can be provided in the form of a list (interesting discussion and references are given in<ref name="BensonSayin1997">{{cite journal|last1=Benson|first1=Harold P.|last2=Sayin|first2=Serpil|title=Towards finding global representations of the efficient set in multiple objective mathematical programming|journal=Naval Research Logistics |volume=44 |issue=1|year=1997|pages=47–67|issn=0894-069X|doi=10.1002/(SICI)1520-6750(199702)44:1<47::AID-NAV3>3.0.CO;2-M |hdl=11693/25666 |url=http://repository.bilkent.edu.tr/bitstream/11693/25666/1/Towards%20finding%20global%20representations%20of%20the%20efficient%20set%20in%20multiple%20objective%20mathematical%20programming.pdf}}</ref>) or using heatmaps.<ref name="Pryke, Mostaghim, Nazemi">{{cite book|last=Pryke|first=Andy|author2=Sanaz Mostaghim |author3=Alireza Nazemi |title=Evolutionary Multi-Criterion Optimization |chapter=Heatmap Visualization of Population Based Multi Objective Algorithms |volume=4403|year=2007 |pages=361–375 |doi=10.1007/978-3-540-70928-2_29|series=Lecture Notes in Computer Science|isbn=978-3-540-70927-5|s2cid=2502459
=== Visualization in bi-objective problems: tradeoff curve ===
In the case of bi-objective problems, informing the decision maker concerning the Pareto front is usually carried out by its visualization: the Pareto front, often named the tradeoff curve in this case, can be drawn at the objective plane. The tradeoff curve gives full information on objective values and on objective tradeoffs, which inform how improving one objective is related to deteriorating the second one while moving along the tradeoff curve. The decision maker takes this information into account while specifying the preferred Pareto optimal objective point. The idea to approximate and visualize the Pareto front was introduced for linear bi-objective decision problems by S. Gass and T. Saaty.<ref name="GassSaaty1955">{{cite journal |last1=Gass |first1=Saul|last2=Saaty|first2=Thomas|title=The computational algorithm for the parametric objective function |journal=Naval Research Logistics Quarterly|volume=2|issue=1–2|year=1955|pages=39–45|issn=0028-1441 |doi=10.1002/nav.3800020106}}</ref> This idea was developed and applied in environmental problems by J.L. Cohon.<ref name="Cohon2004">{{cite book|author=Jared L. Cohon |title=Multiobjective Programming and Planning |url=https://books.google.com/books?id=i4Qese2aNooC|access-date=29 May 2012 |date=13 January 2004|publisher=Courier Dover Publications |isbn=978-0-486-43263-2}}</ref> A review of methods for approximating the Pareto front for various decision problems with a small number of objectives (mainly, two) is provided in.<ref name="RuzikaWiecek2005">{{cite journal |last1=Ruzika |first1=S. |last2=Wiecek|first2=M. M.|author2-link=Margaret Wiecek |title=Approximation Methods in Multiobjective Programming |journal=Journal of Optimization Theory and Applications |volume=126|issue=3|year=2005|pages=473–501 |issn=0022-3239 |doi=10.1007/s10957-005-5494-4|s2cid=122221156}}</ref>
=== Visualization in high-order multi-objective optimization problems ===
| |||