Optimización de
Procesos
Tier I: Métodos Matemáticos de
Click to edit Master title style
Optimización
Sección 4:
Optimización Multi-Objetivo
Click to Introducción
edit Master title style
• La optimización Multi-objetivo (Multiobjective 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 Introducción
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.
ClickEjemplo
to edit Master
Conceptual
title style
• 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.
Soluciones
Click to editOptimas
Master de
titlePareto
style
• 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.
Ejemplo de Soluciones óptimas de
Click to edit Master title style
Pareto
• Supón que en el ejemplo anterior del viaje
en avión encontramos los siguientes
boletos:
Boleto
A
Tiempo de
Vuelo (hrs)
10
Precio del
Boleto ($)
1700
B
9
2000
C
8
1800
D
7.5
2300
E
6
2200
Click
Comparación
to edit Master
de Soluciones
title style
• 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
Comparación
to edit Master
de Soluciones
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.
Click
Gráfica
to editde
Master
Soluciones
title style
Usualmente, las soluciones de este tipo
tienen una forma típica, mostrada en el
gráfico de abajo:
P la n ede
T icBoleto
k e t O p tio
s
Opciones
den Avión
5000
Región Factible
P rice
($)($)
Precio
4000
D B
3000
2000
E
1000
C A
0
0
5
10
15
F lig h
t TVuelo
im e (h rs)
Tiempo
de
(hrs)
20
25
ClickTipos
to edit
deMaster
Soluciones
title style
• 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.
Soluciones
Click to editóptimas
Master de
title
Pareto
style
• 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 toEjemplo
edit Master
Gráfico
title style
Para la siguiente región factible con
objetivos f1 y f2 donde tanto f1 como f2 son
minimizados:
f2
Región
Factible
Frente de Pareto
f1
Encontrando
Click to editel
Master
Frentetitle
de Pareto
style
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:
f2
w1*
w2
w1
f1
Encontrando
Click to editel
Master
Frentetitle
de Pareto
style
Si esto se hace para un intervalo de líneas
de 90°, todos los puntos en el Frente de
Pareto serán encontrados.
f2
f1
Practicidad
de Master
este Procedimiento
Click to edit
title style
• 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
Procedimientos
to edit Master
Realistas
title style
• 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 Optimización
edit Master title style
• 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
Referencias
Master title style
• 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
Descargar

Multi-Objective Optimization