Frente de Pareto

Conjunto de todas las situaciones de eficiencia de Pareto

En la optimización multiobjetivo , el frente de Pareto (también llamado frontera de Pareto o curva de Pareto ) es el conjunto de todas las soluciones eficientes en el sentido de Pareto . ^[1] El concepto se utiliza ampliamente en ingeniería . ^{[2] : 111–148} Permite al diseñador restringir la atención al conjunto de opciones eficientes y hacer concesiones dentro de este conjunto, en lugar de considerar el rango completo de cada parámetro. ^{[3] : 63–65  [4] : 399–412}

Ejemplo de una frontera de Pareto. Los puntos enmarcados representan opciones factibles y se prefieren los valores más pequeños a los más grandes. El punto C no está en la frontera de Pareto porque está dominado tanto por el punto A como por el punto B. Los puntos A y B no están estrictamente dominados por ningún otro y, por lo tanto, se encuentran en la frontera.

Una frontera de posibilidades de producción . La línea roja es un ejemplo de una frontera eficiente en el sentido de Pareto, donde la frontera y el área que se encuentra a su izquierda y por debajo de ella son un conjunto continuo de opciones. Los puntos rojos en la frontera son ejemplos de opciones de producción óptimas en el sentido de Pareto. Los puntos fuera de la frontera, como N y K, no son eficientes en el sentido de Pareto, ya que existen puntos en la frontera que los dominan en el sentido de Pareto.

Definición

La frontera de Pareto, P ( Y ), puede describirse más formalmente de la siguiente manera. Consideremos un sistema con función , donde X es un conjunto compacto de decisiones factibles en el espacio métrico , e Y es el conjunto factible de vectores de criterio en , tal que . ${\displaystyle f:X\rightarrow \mathbb {R} ^{m}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}}$

Suponemos que se conocen las direcciones preferidas de los valores de los criterios. Un punto es preferido a otro punto (domina estrictamente) , escrito como . La frontera de Pareto se escribe así: ${\displaystyle y^{\prime \prime }\in \mathbb {R} ^{m}}$ ${\displaystyle y^{\prime }\in \mathbb {R} ^{m}}$ ${\displaystyle y^{\prime \prime }\succ y^{\prime }}$

${\displaystyle P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.}$

Tasa marginal de sustitución

Un aspecto significativo de la frontera de Pareto en economía es que, en una asignación Pareto-eficiente, la tasa marginal de sustitución es la misma para todos los consumidores. ^[5] Se puede derivar una declaración formal considerando un sistema con m consumidores y n bienes, y una función de utilidad de cada consumidor como donde es el vector de bienes, ambos para todos los i . La restricción de viabilidad es para . Para encontrar la asignación óptima de Pareto, maximizamos el lagrangiano : ${\displaystyle z_{i}=f^{i}(x^{i})}$ ${\displaystyle x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})}$ ${\displaystyle \sum _{i=1}^{m}x_{j}^{i}=b_{j}}$ ${\displaystyle j=1,\ldots ,n}$

${\displaystyle L_{i}((x_{j}^{k})_{k,j},(\lambda _{k})_{k},(\mu _{j})_{j})=f^{i}(x^{i})+\sum _{k=2}^{m}\lambda _{k}(z_{k}-f^{k}(x^{k}))+\sum _{j=1}^{n}\mu _{j}\left(b_{j}-\sum _{k=1}^{m}x_{j}^{k}\right)}$

donde y son los vectores de multiplicadores. Tomando la derivada parcial del lagrangiano con respecto a cada bien para y se obtiene el siguiente sistema de condiciones de primer orden: ${\displaystyle (\lambda _{k})_{k}}$ ${\displaystyle (\mu _{j})_{j}}$ ${\displaystyle x_{j}^{k}}$ ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle k=1,\ldots ,m}$

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ for }}j=1,\ldots ,n,}$

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{k}}}=-\lambda _{k}f_{x_{j}^{k}}^{i}-\mu _{j}=0{\text{ for }}k=2,\ldots ,m{\text{ and }}j=1,\ldots ,n,}$

donde denota la derivada parcial de con respecto a . Ahora, fije cualquier y . La condición de primer orden anterior implica que ${\displaystyle f_{x_{j}^{i}}}$ ${\displaystyle f}$ ${\displaystyle x_{j}^{i}}$ ${\displaystyle k\neq i}$ ${\displaystyle j,s\in \{1,\ldots ,n\}}$

${\displaystyle {\frac {f_{x_{j}^{i}}^{i}}{f_{x_{s}^{i}}^{i}}}={\frac {\mu _{j}}{\mu _{s}}}={\frac {f_{x_{j}^{k}}^{k}}{f_{x_{s}^{k}}^{k}}}.}$

Por lo tanto, en una asignación óptima de Pareto, la tasa marginal de sustitución debe ser la misma para todos los consumidores. ^{[ cita requerida ]}

Cálculo

Se han estudiado algoritmos para calcular la frontera de Pareto de un conjunto finito de alternativas en informática e ingeniería energética. ^[6] Entre ellos se incluyen:

• "Los máximos de un conjunto de puntos "
• "El problema del vector máximo" o la consulta del horizonte ^{[7] [8] [9]}
• "El algoritmo de escalarización" o el método de sumas ponderadas ^{[10] [11]}
• "El método de las restricciones" ^{[12] [13] [14]} ${\displaystyle \epsilon }$
• Algoritmos evolutivos multiobjetivo ^{[15] [16]}

Aproximaciones

Dado que generar el frente de Pareto completo suele ser difícil desde el punto de vista computacional, existen algoritmos para calcular un frente de Pareto aproximado. Por ejemplo, Legriel et al. ^[17] denominan a un conjunto S una ε -aproximación del frente de Pareto P , si la distancia de Hausdorff dirigida entre S y P es como máximo ε . Observan que una ε -aproximación de cualquier frente de Pareto P en d dimensiones se puede encontrar utilizando (1/ ε ) ^d consultas.

Zitzler, Knowles y Thiele ^[18] comparan varios algoritmos para aproximaciones de conjuntos de Pareto en varios criterios, como la invariancia a la escala, la monotonía y la complejidad computacional.

Referencias

1. proximedia. «Frente de Pareto». www.cenaero.be . Archivado desde el original el 26 de febrero de 2020. Consultado el 8 de octubre de 2018 .
2. Goodarzi, E., Ziaei, M., y Hosseinipour, EZ, Introducción al análisis de optimización en ingeniería de hidrosistemas ( Berlín / Heidelberg : Springer , 2014), págs. 111–148.
3. Jahan, A., Edwards, KL y Bahraminasab, M., Análisis de decisiones multicriterio , 2.ª ed. ( Ámsterdam : Elsevier , 2013), págs. 63–65.
4. Costa, NR, y Lourenço, JA, "Explorando las fronteras de Pareto en la metodología de superficies de respuesta", en G.-C. Yang, S.-I. Ao, y L. Gelman, eds., Transactions on Engineering Technologies: Congreso Mundial de Ingeniería 2014 (Berlín/Heidelberg: Springer, 2015), págs. 399–412.
5. Just, Richard E. (2004). La economía del bienestar de las políticas públicas: un enfoque práctico para la evaluación de proyectos y políticas. Hueth, Darrell L., Schmitz, Andrew. Cheltenham, Reino Unido: E. Elgar. pp. 18–21. ISBN 1-84542-157-4.OCLC 58538348  .
6. Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudría-Andreu, Antoni; Villafáfila-Robles, Roberto (2013). "Reconfiguración óptima de Pareto de sistemas de distribución de energía mediante un algoritmo genético basado en NSGA-II". Energías . 6 (3): 1439–55. doi : 10.3390/en6031439 . hdl : 2117/18257 .
7. Nielsen, Frank (1996). "Peeling sensible a la salida de capas convexas y máximas". Cartas de procesamiento de información . 59 (5): 255–9. CiteSeerX 10.1.1.259.1042 . doi :10.1016/0020-0190(96)00116-0. 
8. Kung, HT; Luccio, F.; Preparata, FP (1975). "Sobre la búsqueda de los máximos de un conjunto de vectores". Revista de la ACM . 22 (4): 469–76. doi : 10.1145/321906.321910 . S2CID  2698043.
9. Godfrey, P.; Shipley, R.; Gryz, J. (2006). "Algoritmos y análisis para el cálculo vectorial máximo". Revista VLDB . 16 : 5–28. CiteSeerX 10.1.1.73.6344 . doi :10.1007/s00778-006-0029-7. S2CID  7374749. 
10. Kim, IY; de Weck, OL (2005). "Método de suma ponderada adaptativa para optimización multiobjetivo: un nuevo método para la generación del frente de Pareto". Optimización estructural y multidisciplinaria . 31 (2): 105–116. doi :10.1007/s00158-005-0557-6. ISSN  1615-147X. S2CID  18237050.
11. Marler, R. Timothy; Arora, Jasbir S. (2009). "El método de suma ponderada para la optimización multiobjetivo: nuevos conocimientos". Optimización estructural y multidisciplinaria . 41 (6): 853–862. doi :10.1007/s00158-009-0460-7. ISSN  1615-147X. S2CID  122325484.
12. "Sobre una formulación bicriterio de los problemas de identificación de sistemas integrados y optimización de sistemas". IEEE Transactions on Systems, Man, and Cybernetics . SMC-1 (3): 296–297. 1971. doi :10.1109/TSMC.1971.4308298. ISSN  0018-9472.
13. Mavrotas, George (2009). "Implementación efectiva del método de restricción ε en problemas de programación matemática multiobjetivo". Matemáticas Aplicadas y Computación . 213 (2): 455–465. doi :10.1016/j.amc.2009.03.037. ISSN  0096-3003.
14. Carvalho, Iago A.; Coco, Amadeu A. (septiembre de 2023). "Sobre la solución de problemas de árboles de expansión mínimos restringidos con dos objetivos". Journal of Global Optimization . 87 (1): 301–323. doi :10.1007/s10898-023-01295-8.
15. Zhang, Qingfu; Hui, Li (diciembre de 2007). "MOEA/D: Un algoritmo evolutivo multiobjetivo basado en la descomposición". IEEE Transactions on Evolutionary Computation . 11 (6): 712–731. doi :10.1109/TEVC.2007.892759.
16. Carvalho, Iago A.; Ribeiro, Marco A. (noviembre de 2019). "Un sistema inmunológico artificial basado en la filogenia de profundidad de nodos para problemas de diseño de redes multiobjetivo". Swarm and Evolutionary Computation . 50 : 100491. doi :10.1016/j.swevo.2019.01.007.
17. Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). Esparza, Javier; Majumdar, Rupak (eds.). "Aproximación del frente de Pareto de problemas de optimización multicriterio". Herramientas y algoritmos para la construcción y análisis de sistemas . Apuntes de clase en informática. 6015. Berlín, Heidelberg: Springer: 69–83. doi : 10.1007/978-3-642-12002-2_6 . ISBN. 978-3-642-12002-2.
18. Zitzler, Eckart; Knowles, Joshua; Thiele, Lothar (2008), Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.), "Evaluación de la calidad de las aproximaciones de conjuntos de Pareto", Optimización multiobjetivo: enfoques interactivos y evolutivos , Lecture Notes in Computer Science, Berlín, Heidelberg: Springer, págs. 373–404, doi :10.1007/978-3-540-88908-3_14, ISBN 978-3-540-88908-3, consultado el 8 de octubre de 2021