Download Uso de técnicas para generar soluciones no dominadas y acelerar

Uso de técnicas para generar soluciones no dominadas y
acelerar la convergencia en optimización evolutiva
multiobjetivo
Tesista: Alan Dı́az Manrı́quez.
Asesor: Dr.Gregorio Toscano Pulido
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional
Laboratorio de Tecnologı́as de Información, Tamaulipas, México
14 de Septiembre de 2011
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
1 / 29
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
2 / 29
Introducción, antecedentes y conceptos básicos
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
3 / 29
Introducción, antecedentes y conceptos básicos
Introducción
La mayorı́a de los problemas del mundo real usualmente involucran
dos o más objetivos a ser optimizado simultáneamente.
Cuando un problema requiere de optimizar simultáneamente un
conjunto de funciones objetivo se denomina: problema de
optimización multiobjetivo (MOP).
Los problemas de optimización multiobjetivo yacen en diversas áreas
de investigación.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
4 / 29
Introducción, antecedentes y conceptos básicos
Optimización multiobjetivo
Un problema de optimización multiobjetivo (MOP) puede ser definido
como:
Encontrar el vector ~x ∗ = [x1∗ , x2∗ , ..., xn∗ ]T que satisfaga las m restricciones
de desigualdad:
gi (~x ) ≤ 0
i = 1, 2, ..., m
(1)
j = 1, 2, ..., p
(2)
y p restricciones de igualdad:
hj (~x ) = 0
que optimice la función vectorial:
~f (~x ) = [f1 (~x ), f2 (~x ), ..., fk (~x )]T
(3)
donde ~x = [x1 , x2 , ..., xn ]T es el vector de variables de decisión; ~f es el
conjunto de objetivos a ser minimizados ó maximizados.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
5 / 29
Introducción, antecedentes y conceptos básicos
La comunidad de investigación de operaciones desarrolló una gran
cantidad de trabajos relacionados con la resolución de MOPs, dando
origen a más de 30 técnicas de programación matemática diseñadas
explı́citamente para la resolución de problemas multiobjetivo.
Desventajas
Presuponen que el frente de Pareto es convexo.
Usualmente dependen de un punto inicial de búsqueda.
En funciones multimodales es común que queden estancadas en
regiones donde existen óptimos locales.
Las funciones objetivo deben ser diferenciables.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
6 / 29
Introducción, antecedentes y conceptos básicos
Algoritmos Evolutivos (EAs) hacen referencia a un conjunto algoritmos
inspirados en el Neo-Darwinismo que son especialmente apropiados para
lidiar con este tipo de problemas.
Ventajas
Son técnicas poblacionales que realizan implı́citamente una búsqueda
multidimensional y pueden encontrar más de una solución por
ejecución.
Históricamente han mostrado flexibilidad, adaptabilidad y un buen
desempeño.
Han demostrado ser técnicas útiles para resolver problemas de alta
dimensionalidad, con funciones objetivo que incorporan ruido,
espacios de búsqueda accidentados y de gran tamaño.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
7 / 29
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
En la actualidad se han propuesto diversos algoritmos evolutivos para la
solución de problemas multiobjetivo.
Sin embargo, a pesar de la eficacia de estos algoritmos, cuando la función
aptitud es computacionalmente costosa de evaluar, se necesitan nuevos
esquemas de optimización que permitan disminuir el número de
evaluaciones de la función objetivo pero manteniendo la calidad de las
soluciones (mejorar la eficiencia).
Mejorar eficiencia
Por mejorar la eficiencia se entiende el obtener los mismos resultados que
otros algoritmos (en nuestro caso, un MOEA) usando un número menor de
instrucciones (evaluaciones de la función objetivo).
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
8 / 29
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
Ejemplo
En optimización de diseños aerodinámicos es común evaluar el rendimiento
de una estructura mediante simulaciones de mecánica de fluidos
computacional (CFD). Una simulación CFD es usualmente costosa,
especialmente si se simula en 3 dimensiones (toma aproximadamente 10
horas en una computadora de alto rendimiento).
Si se utilizara un algoritmo que requiriera 1000 evaluaciones de la función
objetivo, tomarı́a aproximadamente un año para completar el proceso de
optimización.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
9 / 29
Mejorar la eficiencia en EAs
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
10 / 29
Mejorar la eficiencia en EAs
Metaheurı́sticas y optimización global
Diversos autores decidieron modificar diferentes EAs y otras
meta-heurı́sticas que habı́an sido exitosamente utilizadas para resolver
problemas de optimización monobjetivo y que tenı́an como caracterı́stica
principal su velocidad de convergencia, habilitándolos para resolver MOPs
con el objetivo de crear enfoques más eficientes (p.ej. evolución diferencial,
recocido simulado, optimización mediante cúmulos de partı́culas, etcétera).
Exitosos
Mucho trabajo al respecto
A la vez existen técnicas que han sido utilizadas exitosamente en
optimización global y algoritmos evolutivos que aun no han sido aplicadas
a problemas de optimización multiobjetivo.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
11 / 29
Mejorar la eficiencia en EAs
Modelos de aproximación
Se han sido utilizados modelos de aproximación en EAs de diversas
maneras:
Migración
Inicialización y para guiar la búsqueda
Reemplazan la función objetivo
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
12 / 29
Mejorar la eficiencia en EAs
Operadores Inteligentes
Recientemente han aparecido operadores de variación que intentan crear
nuevas soluciones de manera más inteligente:
Hacen uso de la información adquirida durante el proceso de búsqueda
Realizan un mejor muestreo del espacio de búsqueda, con la finalidad
de crear soluciones más prometedoras que los operadores tradicionales
Existen trabajos que han sido exitosos (algoritmos culturales)
Trabajo escaso
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
13 / 29
Mejorar la eficiencia en EAs
Algoritmos hı́bridos
Surgieron nuevos desarrollos de algoritmos hı́bridos que hacen referencia a:
Reducir el número de evaluaciones necesarias para resolver el
problema multiobjetivo.
Mejorar la calidad de las soluciones finales.
En estos desarrollos se han combinado EAs que funcionan como motores
de búsqueda de grano grueso y métodos de búsqueda local (p.ej.,
programación matemática, métodos estocásticos de búsqueda local, entre
otros), con la finalidad de combinar adecuadamente la capacidad
explorativa de los EAs con el poder de explotación de la búsqueda local.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
14 / 29
Técnicas para completar el frente de Pareto
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
15 / 29
Técnicas para completar el frente de Pareto
Técnicas para completar el frente de Pareto
Recientemente han surgido técnicas para completar el frente de Pareto a
partir de algunas soluciones que se encuentren sobre el mismo, de tal
manera, que sea posible producir un subconjunto representativo del
verdadero frente de Pareto a partir de algunas cuantas soluciones que
pertenezcan al mismo.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
16 / 29
Técnicas para completar el frente de Pareto
Técnicas para completar el frente de Pareto
Recientemente han surgido técnicas para completar el frente de Pareto a
partir de algunas soluciones que se encuentren sobre el mismo, de tal
manera, que sea posible producir un subconjunto representativo del
verdadero frente de Pareto a partir de algunas cuantas soluciones que
pertenezcan al mismo.
Problema de optimización multiobjetivo
Obtener un conjunto disperso de soluciones que se encuentren lo más
cerca posible al frente de Pareto
⇓
Encontrar únicamente algunas soluciones pertenecientes al frente de
Pareto en una primera fase, y como segunda fase, utilizar estas técnicas
para obtener un subconjunto representativo del frente de Pareto.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
16 / 29
Motivación, objetivo y plan de trabajo
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
17 / 29
Motivación, objetivo y plan de trabajo
Motivación
Motivación
Los enfoques anteriormente descritos han sido utilizados por separado. Sin embargo, los trabajos
que realizan una mezcla de estas técnicas para incrementar la velocidad de convergencia son
escasos. Suponemos que es posible realizar el desarrollo de un algoritmo con énfasis en eficiencia
que incorpore un diseño dividido en dos fases:
Fase 1
Utilizar un EA o alguna técnica de programación matemática para encontrar las áreas más
prometedoras del espacio de búsqueda.
Explorarlas haciendo uso de algún mecanismo que nos permita acelerar la convergencia.
No se tomará en cuenta ni la cantidad de soluciones no dominadas, ni su dispersión
(presuponemos que es más difı́cil converger mientras se mantiene una buena dispersión de
las soluciones).
Fase 2
Utilizar un mecanismo que permita producir un conjunto representativo (con buena
dispersión) de las soluciones no dominadas, a partir de las soluciones obtenidas por la
primera fase.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
18 / 29
Motivación, objetivo y plan de trabajo
Preguntas de Investigación
Preguntas de Investigación
¿Cómo unir exitosamente diversas técnicas para acelerar la
convergencia que permitan mejorar la eficiencia en los algoritmos
evolutivos?
¿Cómo crear soluciones no dominadas a partir de un pequeño
subconjunto de ellas?
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
19 / 29
Motivación, objetivo y plan de trabajo
Hipótesis
Hipótesis
Hipótesis
Es posible que la combinación de diversas técnicas para acelerar
convergencia permitan desarrollar algoritmos evolutivos que puedan
resolver problemas de optimización multiobjetivo con un menor número de
evaluaciones que las necesitadas por aquellos enfoques representativos del
área.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
20 / 29
Motivación, objetivo y plan de trabajo
Objetivos
Objetivo General
El objetivo general de este trabajo es contribuir al conocimiento de los
algoritmos evolutivos multiobjetivo mediante la investigación de:
Técnicas para acelerar la convergencia en algoritmos evolutivos
multiobjetivo
Algoritmos para completar el frente de Pareto
Esta investigación realizará contribuciones tanto a las Ciencias de la
Computación como a la Investigación de Operaciones, en las áreas de
algoritmos evolutivos y optimización multiobjetivo.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
21 / 29
Motivación, objetivo y plan de trabajo
Objetivos
Objetivos particulares
Realizar un estudio comparativo de técnicas para acelerar
convergencia que sirva como base para el desarrollo de nuevos
algoritmos evolutivos multiobjetivo
Contribuir con el estado del arte mediante el desarrollo de al menos
un mecanismo para acelerar la convergencia en algoritmos
evolutivos multiobjetivo.
Contribuir con el estado del arte mediante el desarrollo de al menos
una nueva técnica para completar el frente de Pareto a partir de
algunas soluciones.
Aportar al estado del arte al menos un nuevo algoritmo hı́brido que
utilice las ventajas del mecanismo de aceleración de la velocidad de
convergencia.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
22 / 29
Motivación, objetivo y plan de trabajo
Metodologı́a
Metodologı́a
Etapa 1
Estudiar los mecanismos existentes para acelerar convergencia
(tentativamente los relacionados con la creación de metamodelos)
Diseñar al menos un nuevo mecanismo para acelerar convergencia en
MOEAs (tentativamente se usarán técnicas de aprendizaje máquina
para generar conocimiento nuevo, que a su vez se utilizará el
conocimiento obtenido para crear un operador inteligente que sea
capaz de guiar la búsqueda de manera exitosa).
Validar estadı́sticamente el nuevo mecanismo
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
23 / 29
Motivación, objetivo y plan de trabajo
Metodologı́a
Etapa 2
Estudiar métodos de búsqueda local y otros mecanismos propuestos
para completar el frente de Pareto a partir de algunas soluciones.
Diseñar una nueva técnica para completar el frente de Pareto
Validar estadı́sticamente la técnica propuesta y compararla con
respecto a las representativas del estado del arte.
Etapa 3
Diseñar un nuevo algoritmo que explote las caracterı́sticas de todos
los elementos estudiados durante las dos primeras etapas.
Validar estadı́sticamente el nuevo algoritmo propuesto con respecto a
los MOEAs multiobjetivo representativos del estado del arte utilizando
problemas de prueba y medidas de desempeño estándar, de acuerdo
con la literatura especializada.
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
24 / 29
Motivación, objetivo y plan de trabajo
Metodologı́a
Metodologı́a
METODOLOGIA
Aclerar
Convergencia
AE
- AG
- Surrogados
- Operadores
Inteligentes
- Hibridos
Diseno
MOEA
- PSO
- ED
MOEA
Final
Completado
- Rough Sets
- Busqueda
dispersa
- Metodos de
continuacion
Alan Dı́az Manrı́quez (CINVESTAV)
Diseno
de una nueva
tecnica
Seminario de Investigación
Septiembre, 2011
25 / 29
Motivación, objetivo y plan de trabajo
Metodologı́a
Actividades
Actividad
Estudio literario.
MOEA con aceleración de convergencia (Alg. 1)
Técnica para completar el frente de
Pareto (Alg. 2)
MOEA que combine
(Alg. 1 y Alg. 2)
Cursos
Publicaciones
Examen
predoctoral
Redacción del documento de tesis
Primer Año
P1
P2
P3
X
X
X
X
X
Segundo Año
P1
P2
P3
X
X
X
X
X
X
X
X
Alan Dı́az Manrı́quez (CINVESTAV)
X
X
X
X
X
X
X
Tercer Año
P1
P2
P3
X
X
X
X
X
X
X
X
Cuarto Año
P1
P2
P3
X
X
X
X
X
X
Seminario de Investigación
X
Septiembre, 2011
X
X
26 / 29
Conclusiones
Índice
1
Introducción, antecedentes y conceptos básicos
Optimización evolutiva con múltiples objetivos.
2
Mejorar la eficiencia en EAs
3
Técnicas para completar el frente de Pareto
4
Motivación, objetivo y plan de trabajo
Motivación
Preguntas de Investigación
Hipótesis
Objetivos
Metodologı́a
5
Conclusiones
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
27 / 29
Conclusiones
Conclusiones
Problema multiobjetivo
Programación matemática vs Algoritmos Evolutivos
Funciones costosas de evaluar
Tecnicas para acelerar la convergencia
Hipótesis, objetivos y metodologı́a de la investigación.
Se espera obtener al menos un nuevo algoritmo evolutivo
multiobjetivo que use técnicas para acelerar su convergencia y para
completar el frente de Pareto con el objetivo utilizar un menor
número de evaluaciones de la función objetivo que aquellos algoritmos
más representativos del estado del arte
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
28 / 29
Conclusiones
GRACIAS
Alan Dı́az Manrı́quez (CINVESTAV)
Seminario de Investigación
Septiembre, 2011
29 / 29