Het artikel legt het concept van de Pareto-front uit binnen meervoudige optimalisatie, waarbij de focus ligt op het vinden van oplossingen die optimaal zijn gezien de trade-offs tussen verschillende doelstellingen. Centraal staat het principe van Pareto-dominantie, ondersteund door wiskundige definities en economische toepassingen zoals de marginale substitutiegraad. Daarnaast worden computationele methoden voor het berekenen van de front besproken, evenals benaderingsalgoritmen die worden ingezet wanneer volledige berekeningen te rekenintensief zijn.
Pareto-front
Het overtreffen van een oplossing wordt Pareto-dominantie genoemd: een oplossing A domineert (overtreft) B als A in elk doel niet slechter is dan B, en in ten minste één doel beter is dan B. Dit concept wordt veelvuldig gebruikt in de techniek; het stelt de ontwerper in staat om de aandacht te beperken tot de set efficiënte keuzes en binnen deze set afwegingen te maken, in plaats van het volledige bereik van elke parameter te moeten overwegen.
Voorbeelden
- Puntenverzameling: Stel dat er een set haalbare keuzes is waarbij kleinere waarden worden verkozen boven grotere waarden. Als punt C wordt gedomineerd door zowel punt A als punt B, dan ligt punt C niet op de Pareto-front. Punten A en B worden door geen enkele andere optie strikt gedomineerd en liggen daarom wel op de front.
- Productiekanscurve: Een rode lijn kan een voorbeeld zijn van een Pareto-efficiënte grens, waarbij de grens en het gebied links en eronder een continue set keuzes vormen. De rode punten op de grens zijn voorbeelden van Pareto-optimale productiekeuzes. Punten buiten de grens (zoals N en K) zijn niet Pareto-efficiënt, aangezien er punten op de grens bestaan die hen Pareto-domineren.
Definitie
De Pareto-front, $P(Y)$, kan formeler als volgt worden beschreven. Beschouw een systeem met functie: $f : X \rightarrow \mathbb{R}^m$
waarbij $X$ een compacte verzameling is van haalbare beslissingen in de metrieke ruimte $\mathbb{R}^n$, en $Y$ de haalbare verzameling is van criteriumvectoren in $\mathbb{R}^m$, zodanig dat: $Y = \{y \in \mathbb{R}^m : y = f(x), x \in X\}$
Er wordt aangenomen dat de voorkeursrichtingen van de criteriumwaarden bekend zijn. Een punt $y'' \in \mathbb{R}^m$ heeft de voorkeur boven (domineert strikt) een ander punt $y' \in \mathbb{R}^m$, geschreven als: $y'' \succ y'$
De Pareto-front wordt derhalve genoteerd als: $P(Y) = \{y' \in Y : \{y'' \in Y : y'' \succ y', y' \neq y''\} = \emptyset\}$
Marginale substitutiegraad
Een significant aspect van de Pareto-front in de economie is dat bij een Pareto-efficiënte allocatie de marginale substitutiegraad gelijk is voor alle consumenten. Een formele stelling kan worden afgeleid door een systeem te beschouwen met $m$ consumenten en $n$ goederen, waarbij de nutsfunctie van elke consument wordt weergegeven als: $z_i = f^i(x^i)$
waarbij $x^i = (x{1}^{i}, x{2}^{i}, \ldots, x{n}^{i})$ de vector van goederen is voor alle $i$. De haalbaarheidsbeperking is: $\sum{i=1}^{m} x{j}^{i} = bj$ voor $j = 1, \ldots, n$.
Om de Pareto-optimale allocatie te vinden, maximaliseren we de Lagrange-functie: $Li((x{j}^{k}){k,j}, (\lambdak)k, (\muj)j) = f^i(x^i) + \sum{k=2}^{m} \lambdak (zk - f^k(x^k)) + \sum{j=1}^{n} \muj (bj - \sum{k=1}^{m} x_{j}^{k})$
waarbij $(\lambdak)k$ and $(\muj)j$ de vectoren van multipliers zijn. Het nemen van de partiële afgeleide van de Lagrange-functie ten opzichte van elk goed $x_{j}^{k}$ voor $j = 1, \ldots, n$ en $k = 1, \ldots, m$ geeft het volgende systeem van eerste-orde voorwaarden:
$\frac{\partial Li}{\partial x{j}^{i}} = f{x{j}^{i}}^{1} - \muj = 0$ voor $j = 1, \ldots, n$, $\frac{\partial Li}{\partial x{j}^{k}} = -\lambdak f{x{j}^{k}}^{i} - \mu_j = 0$ voor $k = 2, \ldots, m$ en $j = 1, \ldots, n$,
waarbij $f{x{j}^{i}}$ de partiële afgeleide van $f$ is ten opzichte van $x_{j}^{i}$. Wanneer we nu elke $k \neq i$ en $j, s \in \{1, \ldots, n\}$ vastzetten, impliceren de bovenstaande eerste-orde voorwaarden dat:
$\frac{f{x{j}^{i}}^{i}}{f{x{s}^{i}}^{i}} = \frac{\muj}{\mus} = \frac{f{x{j}^{k}}^{k}}{f{x{s}^{k}}^{k}}$
Bijgevolg moet in een Pareto-optimale allocatie de marginale substitutiegraad voor alle consumenten gelijk zijn.
Computationele berekening
Algoritmen voor het berekenen van de Pareto-front van een eindige set alternatieven zijn bestudeerd in de informatica en energietechniek. Deze omvatten onder andere:
- "The maxima of a point set"
- "The maximum vector problem" of de skyline query
- "The scalarization algorithm" of de methode van gewogen sommen
- De "$\epsilon$-constraints method"
- Multi-objective Evolutionary Algorithms (meervoudige evolutionaire algoritmen)
Benaderingen
Omdat het genereren van de volledige Pareto-front vaak computationeel zwaar is, bestaan er algoritmen voor het berekenen van een benaderde Pareto-front. Zo noemen Legriel et al. een set $S$ een $\epsilon$-benadering van de Pareto-front $P$, als de gerichte Hausdorff-afstand tussen $S$ en $P$ maximaal $\epsilon$ is. Zij stellen vast dat een $\epsilon$-benadering van elke Pareto-front $P$ in $d$ dimensies gevonden kan worden met behulp van $(1/\epsilon)^d$ queries.
Zitzler, Knowles en Thiele vergelijken verschillende algoritmen voor Pareto-set benaderingen op basis van diverse criteria, zoals invariantie voor schaling, monotoniciteit en computationele complexiteit.
Bronverwijzingen
- proximedia. "Pareto Front". www.cenaero.be.
- Kang, Shida; Li, Kaiwen; Wang, Rui (2025-06-01). "A survey on pareto front learning for multi-objective optimization". Journal of Membrane Computing. 7 (2): 128–134. doi:10.1007/s41965-024-00170-z.
- Goodarzi, E., Ziaei, M., & Hosseinipour, E. Z., Introduction to Optimization Analysis in Hydrosystem Engineering (Berlin/Heidelberg: Springer, 2014), pp. 111–148.
- Jahan, A., Edwards, K. L., & Bahraminasab, M., Multi-criteria Decision Analysis, 2nd ed. (Amsterdam: Elsevier, 2013), pp. 63–65.
- Costa, N. R., & Lourenço, J. A., "Exploring Pareto Frontiers in the Response Surface Methodology", in G.-C. Yang, S.-I. Ao, & L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlin/Heidelberg: Springer, 2015), pp. 399–412.
- Just, Richard E. (2004). The welfare economics of public policy : a practical approach to project and policy evaluation. Hueth, Darrell L., Schmitz, Andrew. Cheltenham, UK: E. Elgar. pp. 18–21. ISBN 1-84542-157-4.
- Just, Richard E.; Hueth, Darrell L.; Schmitz, Andrew (2005-01-01). The Welfare Economics of Public Policy: A Practical Approach to Project and Policy Evaluation. Edward Elgar Publishing. ISBN 978-1-84542-157-1.
- Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto (2013). "Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II". Energies. 6 (3): 1439–55. doi:10.3390/en6031439.
- Nielsen, Frank (1996). "Output-sensitive peeling of convex and maximal layers". Information Processing Letters. 59 (5): 255–9. doi:10.1016/0020-0190(96)00116-0.
- Kung, H. T.; Luccio, F.; Preparata, F.P. (1975). "On finding the maxima of a set of vectors". Journal of the ACM. 22 (4): 469–76. doi:10.1145/321906.321910.
- Godfrey, P.; Shipley, R.; Gryz, J. (2006). "Algorithms and Analyses for Maximal Vector Computation". VLDB Journal. 16: 5–28. doi:10.1007/s00778-006-0029-7.
- Kim, I. Y.; de Weck, O. L. (2005). "Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation". Structural and Multidisciplinary Optimization. 31 (2): 105–116. doi:10.1007/s00158-005-0557-6.
- Marler, R. Timothy; Arora, Jasbir S. (2009). "The weighted sum method for multi-objective optimization: new insights". Structural and Multidisciplinary Optimization. 41 (6): 853–862. doi:10.1007/s00158-009-0460-7.
- "On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization". IEEE Transactions on Systems, Man, and Cybernetics. SMC-1 (3): 296–297. 1971. doi:10.1109/TSMC.1971.4308298.
- Mavrotas, George (2009). "Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems". Applied Mathematics and Computation. 213 (2): 455–465. doi:10.1016/j.amc.2009.03.037.
- Carvalho, Iago A.; Coco, Amadeu A. (September 2023). "On solving bi-objective constrained minimum spanning tree problems". Journal of Global Optimization. 87 (1): 301–323. doi:10.1007/s10898-023-01295-8.
- Zhang, Qingfu; Hui, Li (December 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.
- Carvalho, Iago A.; Ribeiro, Marco A. (November 2019). "A node-depth phylogenetic-based artificial immune system for multi-objective Network Design Problems". Swarm and Evolutionary Computation. 50 100491. doi:10.1016/j.swevo.2019.01.007.
- Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). "Approximating the Pareto Front of Multi-criteria Optimization Problems". In Esparza, Javier; Majumdar, Rupak (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Vol. 6015. Berlin, Heidelberg: Springer. pp. 69–83. doi:10.1007/978-3-642-12002-2_6.
- Zitzler, Eckart; Knowles, Joshua; Thiele, Lothar (2008), "Quality Assessment of Pareto Set Approximations", in Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.), Multiobjective Optimization: Interactive and Evolutionary Approaches, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 373–404, doi:10.1007/978-3-540-88908-3_14.
Pareto-front
Het overtreffen van een oplossing wordt Pareto-dominantie genoemd: een oplossing A domineert (overtreft) B als A in elk doel niet slechter is dan B, en in ten minste één doel beter is dan B. Dit concept wordt veelvuldig gebruikt in de techniek; het stelt de ontwerper in staat om de aandacht te beperken tot de set efficiënte keuzes en binnen deze set afwegingen te maken, in plaats van het volledige bereik van elke parameter te moeten overwegen.
Voorbeelden
- Puntenverzameling: Stel dat er een set haalbare keuzes is waarbij kleinere waarden worden verkozen boven grotere waarden. Als punt C wordt gedomineerd door zowel punt A als punt B, dan ligt punt C niet op de Pareto-front. Punten A en B worden door geen enkele andere optie strikt gedomineerd en liggen daarom wel op de front.
- Productiekanscurve: Een rode lijn kan een voorbeeld zijn van een Pareto-efficiënte grens, waarbij de grens en het gebied links en eronder een continue set keuzes vormen. De rode punten op de grens zijn voorbeelden van Pareto-optimale productiekeuzes. Punten buiten de grens (zoals N en K) zijn niet Pareto-efficiënt, aangezien er punten op de grens bestaan die hen Pareto-domineren.
Definitie
De Pareto-front, $P(Y)$, kan formeler als volgt worden beschreven. Beschouw een systeem met functie: $f : X \rightarrow \mathbb{R}^m$
waarbij $X$ een compacte verzameling is van haalbare beslissingen in de metrieke ruimte $\mathbb{R}^n$, en $Y$ de haalbare verzameling is van criteriumvectoren in $\mathbb{R}^m$, zodanig dat: $Y = \{y \in \mathbb{R}^m : y = f(x), x \in X\}$
Er wordt aangenomen dat de voorkeursrichtingen van de criteriumwaarden bekend zijn. Een punt $y'' \in \mathbb{R}^m$ heeft de voorkeur boven (domineert strikt) een ander punt $y' \in \mathbb{R}^m$, geschreven als: $y'' \succ y'$
De Pareto-front wordt derhalve genoteerd als: $P(Y) = \{y' \in Y : \{y'' \in Y : y'' \succ y', y' \neq y''\} = \emptyset\}$
Marginale substitutiegraad
Een significant aspect van de Pareto-front in de economie is dat bij een Pareto-efficiënte allocatie de marginale substitutiegraad gelijk is voor alle consumenten. Een formele stelling kan worden afgeleid door een systeem te beschouwen met $m$ consumenten en $n$ goederen, waarbij de nutsfunctie van elke consument wordt weergegeven als: $z_i = f^i(x^i)$
waarbij $x^i = (x{1}^{i}, x{2}^{i}, \ldots, x{n}^{i})$ de vector van goederen is voor alle $i$. De haalbaarheidsbeperking is: $\sum{i=1}^{m} x{j}^{i} = bj$ voor $j = 1, \ldots, n$.
Om de Pareto-optimale allocatie te vinden, maximaliseren we de Lagrange-functie: $Li((x{j}^{k}){k,j}, (\lambdak)k, (\muj)j) = f^i(x^i) + \sum{k=2}^{m} \lambdak (zk - f^k(x^k)) + \sum{j=1}^{n} \muj (bj - \sum{k=1}^{m} x_{j}^{k})$
waarbij $(\lambdak)k$ and $(\muj)j$ de vectoren van multipliers zijn. Het nemen van de partiële afgeleide van de Lagrange-functie ten opzichte van elk goed $x_{j}^{k}$ voor $j = 1, \ldots, n$ en $k = 1, \ldots, m$ geeft het volgende systeem van eerste-orde voorwaarden:
$\frac{\partial Li}{\partial x{j}^{i}} = f{x{j}^{i}}^{1} - \muj = 0$ voor $j = 1, \ldots, n$, $\frac{\partial Li}{\partial x{j}^{k}} = -\lambdak f{x{j}^{k}}^{i} - \mu_j = 0$ voor $k = 2, \ldots, m$ en $j = 1, \ldots, n$,
waarbij $f{x{j}^{i}}$ de partiële afgeleide van $f$ is ten opzichte van $x_{j}^{i}$. Wanneer we nu elke $k \neq i$ en $j, s \in \{1, \ldots, n\}$ vastzetten, impliceren de bovenstaande eerste-orde voorwaarden dat:
$\frac{f{x{j}^{i}}^{i}}{f{x{s}^{i}}^{i}} = \frac{\muj}{\mus} = \frac{f{x{j}^{k}}^{k}}{f{x{s}^{k}}^{k}}$
Bijgevolg moet in een Pareto-optimale allocatie de marginale substitutiegraad voor alle consumenten gelijk zijn.
Computationele berekening
Algoritmen voor het berekenen van de Pareto-front van een eindige set alternatieven zijn bestudeerd in de informatica en energietechniek. Deze omvatten onder andere:
- "The maxima of a point set"
- "The maximum vector problem" of de skyline query
- "The scalarization algorithm" of de methode van gewogen sommen
- De "$\epsilon$-constraints method"
- Multi-objective Evolutionary Algorithms (meervoudige evolutionaire algoritmen)
Benaderingen
Omdat het genereren van de volledige Pareto-front vaak computationeel zwaar is, bestaan er algoritmen voor het berekenen van een benaderde Pareto-front. Zo noemen Legriel et al. een set $S$ een $\epsilon$-benadering van de Pareto-front $P$, als de gerichte Hausdorff-afstand tussen $S$ en $P$ maximaal $\epsilon$ is. Zij stellen vast dat een $\epsilon$-benadering van elke Pareto-front $P$ in $d$ dimensies gevonden kan worden met behulp van $(1/\epsilon)^d$ queries.
Zitzler, Knowles en Thiele vergelijken verschillende algoritmen voor Pareto-set benaderingen op basis van diverse criteria, zoals invariantie voor schaling, monotoniciteit en computationele complexiteit.
Bronverwijzingen
- proximedia. "Pareto Front". www.cenaero.be.
- Kang, Shida; Li, Kaiwen; Wang, Rui (2025-06-01). "A survey on pareto front learning for multi-objective optimization". Journal of Membrane Computing. 7 (2): 128–134. doi:10.1007/s41965-024-00170-z.
- Goodarzi, E., Ziaei, M., & Hosseinipour, E. Z., Introduction to Optimization Analysis in Hydrosystem Engineering (Berlin/Heidelberg: Springer, 2014), pp. 111–148.
- Jahan, A., Edwards, K. L., & Bahraminasab, M., Multi-criteria Decision Analysis, 2nd ed. (Amsterdam: Elsevier, 2013), pp. 63–65.
- Costa, N. R., & Lourenço, J. A., "Exploring Pareto Frontiers in the Response Surface Methodology", in G.-C. Yang, S.-I. Ao, & L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlin/Heidelberg: Springer, 2015), pp. 399–412.
- Just, Richard E. (2004). The welfare economics of public policy : a practical approach to project and policy evaluation. Hueth, Darrell L., Schmitz, Andrew. Cheltenham, UK: E. Elgar. pp. 18–21. ISBN 1-84542-157-4.
- Just, Richard E.; Hueth, Darrell L.; Schmitz, Andrew (2005-01-01). The Welfare Economics of Public Policy: A Practical Approach to Project and Policy Evaluation. Edward Elgar Publishing. ISBN 978-1-84542-157-1.
- Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto (2013). "Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II". Energies. 6 (3): 1439–55. doi:10.3390/en6031439.
- Nielsen, Frank (1996). "Output-sensitive peeling of convex and maximal layers". Information Processing Letters. 59 (5): 255–9. doi:10.1016/0020-0190(96)00116-0.
- Kung, H. T.; Luccio, F.; Preparata, F.P. (1975). "On finding the maxima of a set of vectors". Journal of the ACM. 22 (4): 469–76. doi:10.1145/321906.321910.
- Godfrey, P.; Shipley, R.; Gryz, J. (2006). "Algorithms and Analyses for Maximal Vector Computation". VLDB Journal. 16: 5–28. doi:10.1007/s00778-006-0029-7.
- Kim, I. Y.; de Weck, O. L. (2005). "Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation". Structural and Multidisciplinary Optimization. 31 (2): 105–116. doi:10.1007/s00158-005-0557-6.
- Marler, R. Timothy; Arora, Jasbir S. (2009). "The weighted sum method for multi-objective optimization: new insights". Structural and Multidisciplinary Optimization. 41 (6): 853–862. doi:10.1007/s00158-009-0460-7.
- "On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization". IEEE Transactions on Systems, Man, and Cybernetics. SMC-1 (3): 296–297. 1971. doi:10.1109/TSMC.1971.4308298.
- Mavrotas, George (2009). "Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems". Applied Mathematics and Computation. 213 (2): 455–465. doi:10.1016/j.amc.2009.03.037.
- Carvalho, Iago A.; Coco, Amadeu A. (September 2023). "On solving bi-objective constrained minimum spanning tree problems". Journal of Global Optimization. 87 (1): 301–323. doi:10.1007/s10898-023-01295-8.
- Zhang, Qingfu; Hui, Li (December 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.
- Carvalho, Iago A.; Ribeiro, Marco A. (November 2019). "A node-depth phylogenetic-based artificial immune system for multi-objective Network Design Problems". Swarm and Evolutionary Computation. 50 100491. doi:10.1016/j.swevo.2019.01.007.
- Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). "Approximating the Pareto Front of Multi-criteria Optimization Problems". In Esparza, Javier; Majumdar, Rupak (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Vol. 6015. Berlin, Heidelberg: Springer. pp. 69–83. doi:10.1007/978-3-642-12002-2_6.
- Zitzler, Eckart; Knowles, Joshua; Thiele, Lothar (2008), "Quality Assessment of Pareto Set Approximations", in Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.), Multiobjective Optimization: Interactive and Evolutionary Approaches, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 373–404, doi:10.1007/978-3-540-88908-3_14.
Groetjes,