UNA BREVE INTRODUCCIÓN A LA
OPTIMIZACIÓN MULTIOBJECTIVO
José M. Lanza-Gutiérrez
Universidad de Extremadura (España)
Departamento de tecnología de los
Amsterdam,
The Netherlands
Computadores
y las Comunicaciones
JulyCáceres
06-10, 2013
Escuela Politécnica,
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
1. Presentación: ¿quién soy? ¿a que me dedico? (I)
Estudiante de doctorado de último año/investigador en la Universidad de
Extremadura (España)
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
1. Presentación: ¿quién soy? ¿a que me dedico? (I)
Investigo en la utilización de técnicas de soft-computing multiobjetivo para la
resolución de problemas complejos. Más concretamente al despliegue
eficiente de redes de sensores.
Un ejemplo, supongamos que tenemos una zona de cultivo de grandes
dimensiones. Nos interesa obtener información sobre la humedad, existencia
de plagas, calidad del terreno, nutrientes…para poder adecuarnos a las
necesidades de nuestro cultivo y maximizar la productividad.
El objetivo del proceso de optimización es obtener una red de sensores que
nos proporcione toda esa información pero atendiendo a una serie de
criterios como el coste, comportamiento de la red, seguridad…
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
2. Problemas de optimización: número de objetivos (I)
Podemos clasificar los problemas de optimización en torno al número de
objetivos que consideran:
Problemas de optimización monoobjetivo: Consideran un único objectivo.
Ejemplo: supongamos que deseamos optimizar el proceso de fabricación de
un determinado producto: un mueble.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
2. Problemas de optimización: número de objetivos (II)
El proceso de fabricación de dicho mueble depende de múltiples factores:
Tiempo total dedicado
por cada operario
Calidad de los
materiales empleados
Tipo de materiales
empleados
Empaquetado del
producto
El objetivo del problema de optimización monoobjetivo es el de ajustar los
diversos parámetros del problema para:
Minimizar el coste de fabricación del producto.
¿Algún otro ejemplo de problema monoobjetivo?
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
2. Problemas de optimización: número de objetivos (III)
Problemas de optimización multioobjetivo: Consideran dos o mas objetivos
contrapuestos, es decir la optimización de un objetivo no debe ir
acompañada de la optimización de otro (en tal caso, dicho objetivo no seria
necesario)
Ejemplo: Supongamos que deseamos optimizar el mismo problema
presentado anteriormente, pero ahora atendiendo a varios objetivos
Minimizar el coste de fabricación del producto
Maximizar la calidad de los acabados
Minimizar los costes de transporte
...
Pensemos…¿algún otro ejemplo de problema multiobjetivo?
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
3. Relevancia de la optimización multiobjetivo(I)
¿Qué pensáis? ¿qué tipo de optimización es más habitual? ¿cuál tiene más
potencial? ¿Monoobjetivo o multiobjetivo?
Sin lugar a dudas la optimización multiobjetivo es ampliamente investigada
hoy en día en las principales universidades a nivel mundial.
Podemos encontrar publicaciones sobre multiobjetivo en foros de primer
nivel en Europa, Índia, China, Japón, Estados Unidos…
https://scholar.google.cl/
EL MOTIVO….EL MUNDO REAL ES INHERENTEMENTE
MULTIOBJETIVO.
Es decir, los problemas del mundo real suelen contemplar varios objetivos.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
3. Relevancia de la optimización multiobjetivo(II)
Algunos ejemplos de problemas de optimización multiobjetivo presentes en
la literatura actual:
Telecomunicaciones:
Despliegue de redes de sensores (es mi caso….)
Despliegue de antenas de telefonía óptima
Configuración de las transmisiones en fibra óptica
Biología:
Recombinación de proteínas
Identificación de patrones en cadenas de ADN
Análisis de descendencia entre diversas especies
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (I)
En un problema monoobjetivo, el comparar dos soluciones es muy sencillo.
Supongamos que tenemos un problema a minimizar. Entonces, aquella
solución que proporcione un valor de fitness menor será la mejor de las dos.
(Nota: la función de fitness es la ecuación matemática que nos proporciona
el valor del objetivo que deseamos optimizar para una solución dada. Por
ejemplo, una ecuación que nos proporcione el coste total del producto).
Solución 1: coste de 110$
Solución 2: coste de 130$
min(coste), max(calidad)
Conclusión: la solución 1 es mejor, puesto que minimiza el coste.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (II)
En un problema multiobjectivo la comparación de soluciones no es tan
sencillo. (Recordad que los objetivos están contrapuestos)
¿Que significa realmente que los objetivos están contrapuestos? Implica que
todos los objetivos no pueden optimizarse al mismo tiempo. Supongamos
que tenemos un problema de optimización con dos objetivos a minimizar. El
minimizar uno de ellos implica maximizar el otro y viceversa.
Volvamos al ejemplo anterior. Tenemos un problema con objetivos coste de
fabricación y calidad (valor entre 0 y 10). Dadas dos soluciones, ¿cuál de ellas
es mejor?
Solución 1: coste 110$, calidad 5
Solución 2: coste 130$, calidad 6
29/08/2015
José M. Lanza-Gutiérrez
min(coste), max(calidad)
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (III)
¿Cómo podemos comparar dos soluciones en multiobjetivo? Mediante la
dominancia de Pareto.
Supongamos el mismo problema a minimizar y dos soluciones a y b. ¿Cuándo
a es mejor que b? o mejor ¿cuándo a domina a b? cuando se cumplan las
siguientes condiciones:
•
Al menos el valor de fitness de uno de los objetivos es diferente en ambas
soluciones (Comprobamos que a y b no son la misma solución).
Solución 1: coste 110$, calidad 5 min(coste), max(calidad)
Solución 2: coste 130$, calidad 6
•
29/08/2015
Para cada función de fitness de a, comprobar si el valor proporcionado por
a es mejor o igual que el proporcionado por b. Es decir, si el coste de a es
inferior al de b y si la calidad de a es superior a la de b.
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (IV)
Solución 1: coste 110$, calidad 5
Solución 2: coste 130$, calidad 6
min(coste), max(calidad)
¿Son diferentes?
SI
¿Solución 1 domina a Solución 2?
NO. Solución 1 aporta un menor coste, pero la calidad es inferior.
¿Solución 2 domina a Solución 1?
Evidentemente NO.
Entonces… solución 1 y solución 2 son indiferentes (son igual de buenas o de
malas). No tenemos ningún criterio inicial para decantarnos por una o por
otra.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (V)
Solución 1: coste 110$, calidad 5
Solución 3: coste 140$, calidad 3
min(coste), max(calidad)
¿Cuál es mejor?
La solución 1 domina (es mejor) a la 3, proporciona un menor coste con una
mayor calidad.
Solución 1: coste 110$, calidad 5
Solución 4: coste 110$, calidad 3
min(coste), max(calidad)
¿Cuál es mejor?
La solución 1 domina (es mejor) a la 4, proporciona el mismo coste pero con
una mayor calidad.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (VII)
Supongamos que tenemos una población (piscina) de soluciones a la que
aplicamos el concepto de dominancia entre cada par de dos y las
representamos en un eje de coordenadas
Frente de Pareto
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo(VIII)
El objetivo del proceso de optimización es el de obtener el mejor frente de
Pareto posible (el frente de Pareto óptimo, ¿existe?) y hacerlo de forma
eficiente (rápida) y con convergencia y diversidad:
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Conceptos básicos sobre optimización mutiobjetivo (IX)
En resumen:
Objetivo de un problema de optimización monoobjetivo: obtener una única
solución que optimice la función de fitness.
Objetivo de un problema de optimización multiobjetivo: obtener un
conjunto de soluciones non dominadas que optimice las funciones de fitness.
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Set Covering: una visión multiobjetivo (I)
Dado un conjunto de elementos E y una colección de subconjuntos de E. El
objetivo del set covering es el de encontrar una subcolección de conjuntos de
S que cubra todos los elementos de E minimizando el coste.
Habitualmente se utiliza la función de fitness:

   =
 
=1
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
4. Set Covering: una visión multiobjetivo (I)
En esta versión multiobjetivo tan solo añadimos una nueva matriz de coste.
De esta forma, el problema de optimización quedaría definido como:

1 
 1  =
=1

2 
 2  =
=1
29/08/2015
José M. Lanza-Gutiérrez
Valparaiso (Chile)
Descargar

Problemas de optimización monoobjetivo