Content deleted Content added
→A posteriori methods: Fixed grammar Tags: Mobile edit Mobile app edit Android app edit App section source |
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 |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 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.
Line 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|author1=Abakarov. A. |author2=Sushkov. Yu. |author3=Mascheroni. R.H. |year=2012 |journal=International Journal of Food Studies |volume=2 |pages=1–21 |doi=10.7455/ijfs/2.1.2013.a1
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 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 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.
Line 210 ⟶ 241:
=== 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 ===
| |||