algoritmo nvmo para problemas multimodales
TRANSCRIPT
Optimización basada en Malla Variable parafunciones multimodales
Daniel Molina1 Amilkar Puris2 Rafael Bello2 FranciscoHerrera3
1Universidad de Cádiz, 2Universidad de Las Villas, Cuba, 3Universidad de Granada
MAEB 2013, 18 Septiembre 2013
http://sci2s.ugr.es
Presentación
1 Introducción
2 Variable Mesh Optimisation: VMO
3 VMO para optimización multimodal
4 Comparativas y resultados
5 Conclusiones
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo Obtener varios óptimos
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo
x
Fitn
ess
Obtener varios óptimos
x
Fitn
ess
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo
x
Fitn
ess
Obtener varios óptimos
x
Fitn
ess
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo
x
Fitn
ess
Obtener varios óptimos
x
Fitn
ess
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo
x
Fitn
ess
Obtener varios óptimos
x
Fitn
ess
Optimización Multimodal
Problema de optimaciónOptimización x∗ es el optimo sii f (x∗) ≤ f (x) ∀x ∈ Dominio.
Continua Dominio ⊂ <n ⇒ x = [x1, x2, · · · , xn].Multimodal Existen varios óptimos globales, no solo uno.
Obtener el optimo
x
Fitn
ess
Obtener varios óptimos
x
Fitn
ess
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
ρ∗
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
ρ∗
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
ρ∗
Método clearing como técnica de nichos
Métodos de clearingUna técnica clásica para algoritmos de nichos.Evita que se centre demasiado la población en una regiónespecífica.
ComportamientoUtiliza una distancia mínima entre nichos(ρ∗).Borra la solución sol1 si ∃ sol2 dondefitness(sol2) ≤ fitness(sol1) y distance(sol1, sol2) ≤ ρ∗.
Método de clearing y ρ
Influencia de la distancia mínima en el clearingEs demasiado sensible al valor de distancia mínima usado (ρ∗).En algunos benchmarks se sabe la verdadera distancia ρ.
• No es posible en problemas reales.
Cuando ρ∗ < ρ
Se identifican más nichos.El clearing elimina pocassoluciones.
Cuando ρ∗ > ρ
Se identifican pocos nichos.Se eliminan muchassoluciones.
¿Y los óptimos?Depende de la implementación
Método de clearing y ρ
Influencia de la distancia mínima en el clearingEs demasiado sensible al valor de distancia mínima usado (ρ∗).En algunos benchmarks se sabe la verdadera distancia ρ.
• No es posible en problemas reales.
Cuando ρ∗ < ρ
Se identifican más nichos.El clearing elimina pocassoluciones.
Cuando ρ∗ > ρ
Se identifican pocos nichos.Se eliminan muchassoluciones.
¿Y los óptimos?Depende de la implementación
Si distancia mínima es menor que la real ρ, ρ∗ < ρ
Si distancia mínima es menor que la real ρ, ρ∗ < ρ
Si distancia mínima es menor que la real ρ, ρ∗ < ρ
Si distancia mínima es menor que la real ρ, ρ∗ < ρ
Si distancia mínima es menor que la real ρ, ρ∗ < ρ
Mantiene todos los optimos
Si distancia mínima es mayor que la real ρ, ρ∗ > ρ
Si distancia mínima es mayor que la real ρ, ρ∗ > ρ
Si distancia mínima es mayor que la real ρ, ρ∗ > ρ
Si distancia mínima es mayor que la real ρ, ρ∗ > ρ
Si distancia mínima es mayor que la real ρ, ρ∗ > ρ
Se pierde un óptimo
Memoria de óptimos
Memoria de óptimos
Memoria de óptimos
Memoria de óptimos
Ventajas de la memoria externa de óptimos
Podríamos mantener todos los óptimos en la poblaciónSí, pero presenta ventajas adicionales:
Mantener óptimos en poblaciónMenos individuos libres ⇒población estancada.Requiere conocer el númerode óptimos para definir eltamaño de población.Excesiva influencia de losóptimos en la exploración.
Memoria de óptimosPoblación pequeñadestinada a explorar.Se reduce la dependenciaentre el tamaño de lapoblación y los óptimos.No influyen todos losóptimos en la exploración.
Ventajas de la memoria externa de óptimos
Podríamos mantener todos los óptimos en la poblaciónSí, pero presenta ventajas adicionales:
Mantener óptimos en poblaciónMenos individuos libres ⇒población estancada.Requiere conocer el númerode óptimos para definir eltamaño de población.Excesiva influencia de losóptimos en la exploración.
Memoria de óptimosPoblación pequeñadestinada a explorar.Se reduce la dependenciaentre el tamaño de lapoblación y los óptimos.No influyen todos losóptimos en la exploración.
Ventajas de la memoria externa de óptimos
Podríamos mantener todos los óptimos en la poblaciónSí, pero presenta ventajas adicionales:
Mantener óptimos en poblaciónMenos individuos libres ⇒población estancada.Requiere conocer el númerode óptimos para definir eltamaño de población.Excesiva influencia de losóptimos en la exploración.
Memoria de óptimosPoblación pequeñadestinada a explorar.Se reduce la dependenciaentre el tamaño de lapoblación y los óptimos.No influyen todos losóptimos en la exploración.
Ventajas de la memoria externa de óptimos
Podríamos mantener todos los óptimos en la poblaciónSí, pero presenta ventajas adicionales:
Mantener óptimos en poblaciónMenos individuos libres ⇒población estancada.Requiere conocer el númerode óptimos para definir eltamaño de población.Excesiva influencia de losóptimos en la exploración.
Memoria de óptimosPoblación pequeñadestinada a explorar.Se reduce la dependenciaentre el tamaño de lapoblación y los óptimos.No influyen todos losóptimos en la exploración.
Variable Mesh Optimisation
Algoritmo previo para optimización continua.Estudiamos su uso en problemas multimodales.
Principales característicasAlgoritmo población (usa malla de soluciones).Diferentes métodos de combinación.Aplica el clearing al final de cada iteración.
Variable Mesh Optimisation
Algoritmo previo para optimización continua.Estudiamos su uso en problemas multimodales.
Principales característicasAlgoritmo población (usa malla de soluciones).Diferentes métodos de combinación.Aplica el clearing al final de cada iteración.
Variable Mesh Optimisation
Algoritmo previo para optimización continua.Estudiamos su uso en problemas multimodales.
Principales característicasAlgoritmo población (usa malla de soluciones).Diferentes métodos de combinación.Aplica el clearing al final de cada iteración.
Variable Mesh Optimisation
Algoritmo previo para optimización continua.Estudiamos su uso en problemas multimodales.
Principales característicasAlgoritmo población (usa malla de soluciones).Diferentes métodos de combinación.Aplica el clearing al final de cada iteración.
Esquema del VMO
Esquema del VMO
Esquema del VMO
Esquema del VMO
Esquema del VMO
Componentes del VMO
Exploración1 Genera nodos entre cada nodo y su mejor vecino.2 Genera nodos entre cada nodo y el actual óptimo global.3 Genera solución alrededor de los límites de la malla.
Componentes del VMO
Exploración1 Genera nodos entre cada nodo y su mejor vecino.2 Genera nodos entre cada nodo y el actual óptimo global.3 Genera solución alrededor de los límites de la malla.
Componentes del VMO
Exploración1 Genera nodos entre cada nodo y su mejor vecino.2 Genera nodos entre cada nodo y el actual óptimo global.3 Genera solución alrededor de los límites de la malla.
Componentes del VMO
Exploración1 Genera nodos entre cada nodo y su mejor vecino.2 Genera nodos entre cada nodo y el actual óptimo global.3 Genera solución alrededor de los límites de la malla.
Componentes del VMO
Exploración1 Genera nodos entre cada nodo y su mejor vecino.2 Genera nodos entre cada nodo y el actual óptimo global.3 Genera solución alrededor de los límites de la malla.
Clearing con distancia adaptativaValor inicial alto para fomentar la exploración.Se reduce durante la ejecución, para explotar más lassoluciones encontradas.
Inconvenientes del VMO para problemas multimodales
Sólo influye un óptimoLa Fase 2 guía la búsqueda usando únicamente unóptimo.
Distancia de clearing adaptativaLa distancia de clearing se va reduciendo.Podrían perderse óptimos en las etapas iniciales.
Definimos una versión diseñadapara problemas multimodales
Inconvenientes del VMO para problemas multimodales
Sólo influye un óptimoLa Fase 2 guía la búsqueda usando únicamente unóptimo.
Distancia de clearing adaptativaLa distancia de clearing se va reduciendo.Podrían perderse óptimos en las etapas iniciales.
Definimos una versión diseñadapara problemas multimodales
Inconvenientes del VMO para problemas multimodales
Sólo influye un óptimoLa Fase 2 guía la búsqueda usando únicamente unóptimo.
Distancia de clearing adaptativaLa distancia de clearing se va reduciendo.Podrían perderse óptimos en las etapas iniciales.
Definimos una versión diseñadapara problemas multimodales
Niching VMO
Cambios del VMO original1 Nueva Fase 2 que crea soluciones combinando con el óptimo
encontrado más cercano.2 Añadida una Búsqueda Local para mejorar resultados.3 Memoria de óptimos para evitar perder optimos en el clearing.
Memoria de óptimos
Memoria de óptimosSe mantienen los óptimos en la memoria antes de aplicar elclearing.Al final, contiene todos los óptimos obtenidos.
CálculoPara cada solución generada ni :
1 Si fitness(ni) < fitness(ng), M = {ni}, ng = ni .2 Si fitness(ni) ' fitness(ng), M = M ∪ {ni}.
ng es la mejor solución encontrada.f1 ' f2 sii |f1 − f2| ≤ umbral .
Memoria de óptimos
Memoria de óptimos y búsqueda
BúsquedaLa memoria de óptimos no guían la búsqueda.Sólo las soluciones de la población se usan en la búsqueda.
Óptimos encontradosEliminar óptimos de la población favorece la población.Los óptimos alcanzados están en la memoria, no en lapoblación.
Esquema del VMO para nichos
Esquema del VMO para nichos
Esquema del VMO para nichos
Esquema del VMO para nichos
Esquema del VMO para nichos
Esquema del VMO para nichos
Benchmark
Sobre el benchmark12 funciones con diferentes valores de dimensión (1D-20D).20 combinaciones diferentes.Distintos valores de precisión: 10−1, 10−2, 10−3, 10−4, 10−5.
FuncionesTres funciones de dimensión 1 (F1 − F3).Ocho funciones de dimensión 2 (F4 − F11).Cuatro funciones de dimensión 3 (F6,F7,F11,F12).Dos funciones de dimensión 5 (F11,F12).Dos funciones de dimensión 10 (F11,F12).Una función de dimensión 20. (F12).
Benchmark
Sobre el benchmark12 funciones con diferentes valores de dimensión (1D-20D).20 combinaciones diferentes.Distintos valores de precisión: 10−1, 10−2, 10−3, 10−4, 10−5.
FuncionesTres funciones de dimensión 1 (F1 − F3).Ocho funciones de dimensión 2 (F4 − F11).Cuatro funciones de dimensión 3 (F6,F7,F11,F12).Dos funciones de dimensión 5 (F11,F12).Dos funciones de dimensión 10 (F11,F12).Una función de dimensión 20. (F12).
Medidas del benchmark
Prioridades1 Ratio de de soluciones encontradas por cada función y
precisión.2 Número de evaluaciones necesarias para alcanzar los óptimos.
Ratio de óptimos, Peak Ratio (PR)
PR =
∑NRrun=1 NPFi
NKP·NR
Parámetros VMO para nichos
Parámetro Descripción Valor
P Tamaño Población 10+óptimosk Tamaño vecindario 3C Criterio de parada (MaxFEs) benchmarkε Valor umbral 10−6
NLScad Tamaño LScad 12NLS Aplicaciones de LS por iteración 3Istep Evaluaciones de cada BL 150LSfreq Evaluaciones entre llamadas de BL 150
Memoria Distancia mínima Valor precisiónPrecisión entre óptimos
Resultado: Influencia de la precisión (F6D2)
Se usa una memoria de óptimos diferentes para cada valor deprecisión.Sólo se ejecuta una vez para cada valor de precisión.
Comparaciones
Algoritmos de Referencia1 Classic Crowding DE (CDE).2 Modern DE/NRAND/BIN.
Comparando resultados1 PR=1.0 para F1, · · · ,F5.2 Es el mejor algoritmo en: F6(2D), F7(2D y 3D), F11 (10D), y
F12 (3D y 5D).
Análisis de Resultados: Múltiples óptimos
F7(2D) F7(3D)Precisión NVMO DE CDE NVMO DE CDE
1.E-01 1.000 0.347 0.703 1.000 0.097 0.2711.E-02 1.000 0.346 0.724 0.683 0.095 0.2721.E-03 0.945 0.349 0.715 0.399 0.099 0.2741.E-04 0.901 0.337 0.709 0.275 0.095 0.2741.E-05 0.806 0.333 0.716 0.192 0.094 0.270
Obtiene los mejores resultados enfunciones con muchos óptimos
(F7D3 tiene más de 200 óptimos)
Comparando
Comparando resultados en PR
Nivel de precisión NVMO DE/NRAND/BIN CDE
1.0E-01 0.879 0.619 0.7341.0E-02 0.712 0.602 0.6341.0E-03 0.682 0.598 0.5771.0E-04 0.652 0.591 0.4921.0E-05 0.567 0.566 0.435
Media 0.698 0.594 0.575
Análisis1 Mejor algoritmo para cada valor de precisión.2 Alcanza una media del ∼ 70% de óptimos, mientras que el
resto alcanza < 60%.
Sesión Especial del IEEE CEC’2013
N-VMO compitió en una sesión del IEEE Congress onEvolutionary Computation, 2013.Participaron 15 algoritmos con distintas técnicas.Se ejecutaron con el benchmark explicado.El NVMO se mostró altamente competitivo.
Resultados con umbral bajo
El NVMO es el mejor con los mayores valores de umbral.
Resultados, diagramas de PR
El NVMO se muestra muy competitivo.
Resultados por media
Comparando resultados en PR
Posición Algoritmo Media
1 NEA2 0.7940
2 dADE/nrand/1 0.7383
3 CMA-ES 0.7137N-VMO 0.6983
N-VMO como tercera opciónEs estadísticamente equivalente al CMA-ES para nichos.El tiempo de ejecución del N-VMO es mucho mejor que elCMA-ES.
Conclusiones
Propuesto una versión del VMO para nichos: VMO para nichos.
VMO para nichosUtiliza óptimos cercanos para guiar la búsqueda.Aplica un ρ∗ adaptativo para fomentar exploración.El clearing puede eliminar de la población óptimos alcanzados.Una memoria externa de óptimos evita perderlos.Aplica una BL después del clearing.
ResultadosCompetitivo frente algoritmos de referencia.Buenos resultados frente a un gran número de óptimos.Los resultados se están mejorando.
Conclusiones
Propuesto una versión del VMO para nichos: VMO para nichos.
VMO para nichosUtiliza óptimos cercanos para guiar la búsqueda.Aplica un ρ∗ adaptativo para fomentar exploración.El clearing puede eliminar de la población óptimos alcanzados.Una memoria externa de óptimos evita perderlos.Aplica una BL después del clearing.
ResultadosCompetitivo frente algoritmos de referencia.Buenos resultados frente a un gran número de óptimos.Los resultados se están mejorando.
Conclusiones
Propuesto una versión del VMO para nichos: VMO para nichos.
VMO para nichosUtiliza óptimos cercanos para guiar la búsqueda.Aplica un ρ∗ adaptativo para fomentar exploración.El clearing puede eliminar de la población óptimos alcanzados.Una memoria externa de óptimos evita perderlos.Aplica una BL después del clearing.
ResultadosCompetitivo frente algoritmos de referencia.Buenos resultados frente a un gran número de óptimos.Los resultados se están mejorando.
Conclusiones
Propuesto una versión del VMO para nichos: VMO para nichos.
VMO para nichosUtiliza óptimos cercanos para guiar la búsqueda.Aplica un ρ∗ adaptativo para fomentar exploración.El clearing puede eliminar de la población óptimos alcanzados.Una memoria externa de óptimos evita perderlos.Aplica una BL después del clearing.
ResultadosCompetitivo frente algoritmos de referencia.Buenos resultados frente a un gran número de óptimos.Los resultados se están mejorando.
¿Preguntas?
Gracias por su atención.¿Alguna pregunta?