Optimización deProcesos
Click to edit Master title style
Tier I: Métodos Matemáticos de Optimización
Sección 4:
Optimización Multi-Objetivo
Click to edit Master title style
Introducción
• La optimización Multi-objetivo (Multi-objective optimization, MOO) es la optimización de objetivos encontrados.
• Estábamos de hecho haciendo MOO en el capítulo de Introducción cuando optimizamos el espesor del aislamiento – balanceamos dos objetivos opuestos.
• Nos fue posible usar una función objetivo enlazando los dos objetivos con una característica común – costo.
Click to edit Master title style
• En algunos problemas de optimización, no es posible encontrar una manera de enlazar objetivos encontrados.
• A veces las diferencias son cualitativas y la importancia relativa de estos objetivos no puede ser numéricamente cuantificada.
Introducción
Click to edit Master title style
Ejemplo Conceptual
• Supón que necesitas volar un gran trayecto:¿Debes elegir el boleto más barato (más trasbordos) o el menor tiempo de vuelo (más caro)?
• Es imposible dar un valor al tiempo, así que estos dos objetivos no pueden ser ligados.
• También, la importancia relativa variará.– Puede haber un negocio de emergencia que
necesites ir a arreglar rápidamente.– O, tal vez tengas un presupuesto muy apretado.
Click to edit Master title style
Soluciones Optimas de Pareto
• Un problema de MOO con restricciones tendrá muchas soluciones en la región factible.
• Aún cuando es posible que no podamos asignar importancia relativa numéricamente a los objetivos múltiples, podemos clasificar algunas soluciones posibles como mejores que otras.
• Veremos esto en el próximo ejemplo.
Click to edit Master title style
Ejemplo de Soluciones óptimas de Pareto
• Supón que en el ejemplo anterior del viaje en avión encontramos los siguientes boletos:
Boleto Tiempo de Vuelo (hrs)
Precio del Boleto ($)
A 10 1700
B 9 2000
C 8 1800
D 7.5 2300
E 6 2200
Click to edit Master title style
Comparación de Soluciones
• Si comparamos los boletos A y B, no podemos decir que cualquiera es superior sin saber la importancia relativa del Tiempo de Vuelo vs. Precio.
• Sin embargo, la comparación de los boletos B y C muestra que C es mejor que B en ambos objetivos, así que podemos decir que C "domina" a B.
• Así, mientras C es una opción factible, no hay razón para elegir B.
Click to edit Master title style
• Si terminamos las comparaciones, también vemos que D es dominada por E.
• El resto de las opciones (A, C, y E) tienen un trade-off asociado con Tiempo vs. Precio, así ninguno es claramente superior a los otros.
• Llamamos a este el grupo “no dominado” de soluciones porque ninguna de las soluciones está dominada.
Comparación de Soluciones
Click to edit Master title style
Plane Ticket Options
0
1000
2000
3000
4000
5000
0 5 10 15 20 25
Flight Time (hrs)
Pri
ce (
$)
Opciones de Boleto de Avión
Pre
cio
($
)
Tiempo de Vuelo (hrs)
Gráfica de Soluciones
Usualmente, las soluciones de este tipo tienen una forma típica, mostrada en el gráfico de abajo:
Región Factible
AE
D
C
B
Click to edit Master title style
Tipos de Soluciones
• Las soluciones que se encuentran a lo largo de la línea son soluciones no dominadas, mientras que aquellas que yacen dentro de la línea (región factible) son dominadas porque siempre hay otra solución en la línea que tiene cuando menos un objetivo mejor.
Click to edit Master title style
Soluciones óptimas de Pareto
• La línea es llamada el frente de Pareto y las soluciones son llamadas óptimas de Pareto.
• Todas las soluciones óptimas de Pareto son no dominadas.
• Entonces, es importante en MOO encontrar las soluciones más cercanas al Frente de Pareto y mas lejanas a lo largo del mismo como sea posible.
Click to edit Master title style
Ejemplo Gráfico
Para la siguiente región factible con objetivos f1 y f2 donde tanto f1 como f2 son minimizados:
f1
f2
Región Factible
Frente de Pareto
Click to edit Master title style
Encontrando el Frente de Pareto
Una manera de imaginar como encontrar los puntos en el Frente de Pareto es usando una combinación de pesos numéricos para los dos objetivos:
f1
f2
w1
w2
w1*
Click to edit Master title style
Encontrando el Frente de Pareto
Si esto se hace para un intervalo de líneas de 90°, todos los puntos en el Frente de Pareto serán encontrados.
f1
f2
Click to edit Master title style
Practicidad de este Procedimiento
• Realmente, este no es el procedimiento usado en la práctica, pero es una buena ilustración del concepto.
• Este procedimiento requeriría encontrar todos los puntos posibles en la región factible y posteriormente usar muchas combinaciones de pesos.
• Para mas de dos objetivos, la complejidad y el número de combinaciones hacen de este un procedimiento impráctico.
Click to edit Master title style
Procedimientos Realistas
• Existen diferentes métodos usados en la práctica, pero uno es usar un algoritmo genético para enumerar los puntos a lo largo del Frente de Pareto después de varias iteraciones, entonces usa algún método para clasificar la calidad de los trade-offs basado en la aplicación particular a ser modelada.
• Revisa Thibault, J. et al. en las referencias para un ejemplo.
Click to edit Master title style
Optimización
• Se debe recordar que cada punto en el Frente de Pareto se encuentra al resolver un problema de optimización.
• Entonces, como vimos en el Capítulo 3, si el problema es no lineal o muy complejo, el simple paso de obtener solo una solución tal vez no sea trivial.
Click to edit Master title style
Referencias
• Deb, Kalyanmoy; Multi-Objective Optimization using Evolutionary Algorithms
• Thibault, J. et al. “Multicriteria optimization of a high yield pulping process with rough sets” Chemical Engineering Science, 58, (2003)
• Lahanas, Michael; www.mlahanas.de/MOEA/MO_Optimisation.htm