Frente de Pareto

Conjunto de todas las situaciones eficientes 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 de Pareto . ^[1] El concepto es muy utilizado en ingeniería . ^{[2] : 111–148} Permite al diseñador restringir la atención al conjunto de elecciones 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 frontera de Pareto. Los puntos encuadrados 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 tanto, se encuentran en la frontera.

Una frontera de posibilidades de producción . La línea roja es un ejemplo de una frontera Pareto-eficiente, donde la frontera y el área izquierda y debajo de ella son un conjunto continuo de opciones. Los puntos rojos en la frontera son ejemplos de elecciones de producción óptimas 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. Considere 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 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. Se prefiere un punto a (domina estrictamente) otro punto , escrito como . La frontera de Pareto se escribe entonces como: ${\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 yn bienes, y una función de utilidad de cada consumidor como donde está el vector de bienes, ambos para todo 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 los 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, arregla cualquiera 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 tanto, en una asignación óptima de Pareto, la tasa marginal de sustitución debe ser la misma para todos los consumidores. ^{[ cita necesaria ]}

Cálculo

Los algoritmos para calcular la frontera de Pareto de un conjunto finito de alternativas se han estudiado en informática e ingeniería energética. ^[6] 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 las sumas ponderadas ^{[10] [11]}
• "El método de las restricciones" ^{[12] [13]} ${\displaystyle \epsilon }$
• Algoritmos evolutivos multiobjetivo

Aproximaciones

Dado que generar todo el frente de Pareto suele ser difícil desde el punto de vista computacional, existen algoritmos para calcular un frente de Pareto aproximado. Por ejemplo, Legriel et al. ^[14] llaman 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 se puede encontrar una aproximación ε de cualquier frente de Pareto P en d dimensiones utilizando consultas (1/ ε ) ^{d .}

Zitzler, Knowles y Thiele ^[15] comparan varios algoritmos para aproximaciones de conjuntos de Pareto según diversos criterios, como la invariancia de escala, la monotonicidad y la complejidad computacional.

Referencias

1. proximidad. "Frente de Pareto". www.cenaero.be . 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.
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 superficie de respuesta", en G.-C. Yang, S.-I. Ao y L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlín/Heidelberg: Springer, 2015), págs.
5. Justo, 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. págs. 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 máximas y convexas". 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. Godofredo, P.; Shipley, R.; Gryz, J. (2006). "Algoritmos y análisis para el cálculo de vectores máximos". 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 de frentes de Pareto". Optimización Estructural y Multidisciplinar . 31 (2): 105-116. doi :10.1007/s00158-005-0557-6. ISSN  1615-147X. S2CID  18237050.
11. Marler, R. Timoteo; Arora, Jasbir S. (2009). "El método de suma ponderada para la optimización multiobjetivo: nuevos conocimientos". Optimización Estructural y Multidisciplinar . 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 y optimización de sistemas integrados". Transacciones IEEE sobre sistemas, hombre y cibernética . 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 ε-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. Legriel, Julien; Le Guernic, Colas; Algodón, Scott; Maler, Oded (2010). Esparza, Javier; Majumdar, Rupak (eds.). "Aproximación al frente de Pareto de problemas de optimización multicriterio". Herramientas y Algoritmos para la Construcción y Análisis de Sistemas . Apuntes de conferencias sobre informática. 6015 . Berlín, Heidelberg: Springer: 69–83. doi : 10.1007/978-3-642-12002-2_6 . ISBN 978-3-642-12002-2.
15. Zitzler, Eckart; Knowles, Josué; 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 , Apuntes de conferencias sobre informática, 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