hibridación iterativa de de con bl con reinicio para alta dimensionalidad

Hibridación Iterativa de DE con BL conreinicio para alta dimensionalidad

Daniel Molina1 Francisco Herrera2

1Universidad de Cádiz 2Universidad de Granada

11 de Noviembre, CAEPIA’2015

http://sci2s.ugr.es

http://sci2s.ugr.es

Problema de optimización

Optimization problemsOptimización Global f (x∗) ≤ f (x) ∀x ∈ DomainOptimización continua Domain ⊆ <D , x∗ = [x1, x2, · · · , xD ]

Optimización alta dimensionalidad , D ≥ 1000.

Espacio de búsquedaIncrementa exponencialmente.

RequisitoMargen (tiempo, evaluaciones) bajo por dimensión.Requiere mayor eficiencia.

Interés de estas funciones

Problemas realesOptimización de muchos parámetros.

Estudiar separabilidad de variablesEstudiar comportamiento con funciones distinta separabilidad.

Distinta separabilidad de variables

Funciones Totalmente separables

f (x1, x2, ..., xn) =n∑

j=1

gj(xj)

Parcialmente separables

f (x) =|S |∑i=1

wi · gi(xi), S conjunto de variables dijunto.

Con solapamiento

f (x) =|S |∑i=1

wi · gi(xi), S conjunto de variables con

solapamiento.

Estado del arte: MOS

CaracterísticasCombina varios evolutivos y Búsquedas Locales.Aplica cada uno con probabilidad adaptativa.Incluye específicos métodos de BL para altadimensionalidad.

DesventajasComplejo de implementar: 9 componentes.Algunos componentes sólo adecuado pocas funciones.Muchos parámetros: requiere tuning.

ReferenciaAntonio LaTorre, Santiago Muelas, José María Peña:A comprehensive comparison of large scale global

optimizers. Inf. Sci. 316: 517-549 (2015)

Propuesta del CEC’2015

Iterative Hybridation DE with LS: IHDELS.

ReferenciaDaniel Molina, Francisco Herrera: Iterative hybridization of DE with Local Search for the CEC’2015

special session on large scale global optimization. Proceeding on IEEE CEC 2015: 1974-1978 (2015)

Sobre este trabajo

Problemas del algoritmo anterior

Elementos complejos Reinicio no adecuado

En este trabajo abordamos

Simplificar el código Mejorar resultados

Índice

1 Introducción

2 Descripción del modelo original

3 Cambios propuestos

4 Experimentación y conclusiones

Algoritmo propuesto

Algoritmo MeméticoUn Algoritmo Evolutivo (AE) para diversidad.Una Búsqueda Local (BL) para exploración.

Requisitos del AEExplore de forma eficiente.No parámetros oadaptativos.

Requisitos de la BLAdecuado para altadimensionalidad.Robusto.

Elección de los componentes

Diferencial EvolutionEl DE explora muy bíen el espacio de búsqueda.Usamos el Self-Adaptive DE (SaDE).

Método de Búsqueda localUsamos el MTS-LS1, alta dimensionalidad.Combinado con L-BFGS-B para mayor robustez.

Búsquedas Locales complementarias

DiferenciasMTS-LS1 va dimensión a dimensión, rápido.Muy sensible al eje de coordenadas.L-BFGS-B robusto, ya que usa información gradiente(calculada).

Esquema general: IHDELS

CaracterísticasEjecuta alternativamente el DE y la BL.Mantiene la población entre iteraciones.Aplica la BL al mejor.

• Si no mejoró, a una aleatoria.

Selección de la BLElige entre dos métodos de BL en cada caso cuál aplicar.

Esquema general: IHDELS

Componente DE del IHDELS

SaDE: Mutación

Estrategia de mutaciónVarias operadores de mutación.Aplica cada uno con una probabilidad de aplicación.La probabilidad de cada uno se adapta a su ratio de éxito(soluciones que sobreviven).Dicho ratio de éxito se calcula cada LP generaciones.

SaDE: Mutación

Estrategias de mutaciónDE/rand/1:vi = xr1 + F · (xr2 - xr3)DE/rand/2:vi = xr1 + F · (xr2 - xr3) + F · (xr4 - xr5)DE/rand-to-best/1:vi = xi +F · (xbest - xi) + F · (xr1-xr2) + F · (xr3 - xr4)DE/current-to-rand/1:vi = xi + k· (xr2 - xr3) F · (xr4 - xr5)

F ← Normal(0.5, 0.3)

SaDE: Cruce

Cruce

ui =

{xi + vi si rand[0,1] < CRxi en caso contrario

Adaptación del parámetro CRCR ← Normal(CRmin, 0.1).CRmin se auto-adapta según las últimas solucionesexitosas.

SaDE: Reemplazo

Reemplazo

x t+1i =

{ui si ui mejora a x t

i

x ti en caso contrario

Componente de la BL

Métodos de BL

MTS-LS1Define un grupo de variables aleatorio a mejorar C.Define SR = 10% ratio de búsqueda local.Actualiza solución x durante Istr evaluaciones, ∀i ∈ C .

1 xi’ ← xi + SR.2 si fitness(x ′) ≤ fitness(x) x ← x ′, ir al paso 1.3 en caso contrario x’i ← xi - 0.5 · SR.4 si fitness(x ′) ≤ fitness(x) x ← x ′, ir al paso 1.5 Disminuye SR (SR ← SR/2), si x no mejoró.

L-BFGS-BMétodo matemático muy conocido.Requiere derivada: se aproxima en cada punto.

Índice

1 Introducción




Cambios del algoritmo

Primer cambio: Selección BL

Selección de la BL

El modelo anterior aplicaba probabilidad adaptativa.

Probabilidad inicial

PBLM =1|BL|

∀M ∈ BL

Actualización (tras FreqBL evaluaciones)

PBLM =IBLM∑

m∈BL IBLm

IBLM =

FreqBL∑i=1

Mejora de la BLM

Selección de la Búsqueda Local

ProblemasLaborioso de calcular.Rápidamente se polariza.

Nuevo modelo1 Aplicar la primera vez cada BL de forma alternada, y

devuelve el mejor.2 Guarda para cada BL el ratio de su última ejecución:

RatioBLM =Fitnessanterior − Fitnessnuevo

Fitnessanterior

3 En cada iteración aplica la BL con mayor Ratio.

Ejemplo de nuevo criterio

Ejemplo1 Aplica MTS-LS1 ⇒ RatioMTS=0.9.2 Aplica L-BFGS-B ⇒ Ratiobfgs=0.8.3 Aplica MTS-LS1 ⇒ RatioMTS=0.85.4 Aplica MTS-LS1 ⇒ RatioMTS=0.78.5 Aplica L-BFGS-B ⇒ Ratiobfgs=. . .6 . . .

Tras la modificación

Reinicio del algoritmo

Modelo AnteriorReiniciaba cuando no mejoraba nada en una iteración.Se comprobó que no se aplicaba apenas, y nunca mejoró.

Nuevo modeloReinicia cuando en varias iteraciones (3) la mejora esinferior al 1%.Reinicios parciales tras cada iteración:

• Si la BL no mejora nada, reinicia sus parámetros (SR).• Si el DE no mejora nada, reinicia la población.

Índice

1 Introducción




Benchmark

Sobre el benchmarks15 funciones de dimensión 1000.Diferentes grupos de variables:

• Completamente separables: F1-F3.• Parcialmente separables: F4-F11.• Funciones con solapamiento: F12-F14.• No-separables: F15.

Se ejecuta durante 3 · 106 evaluaciones.Se miden los resultados con distinto número deevaluaciones: 1.25 · 105, 6 · 105, 3 · 106.

IHDELS Parameters

ParámetrosTamaño de la población DE 100.Evaluaciones de cada iteración del DE 50000.Evaluaciones de cada iteración de la BL 50000.

Parámetros del originalFrecuencia de actualización de ProbBL 10.

Parámetros del nuevoMínimo mejora para reinicio 1%Número de iteraciones consecutivas sin mejora 3.

Comparando con el original

Grupo de Funciones Función Original Propuesta

F1 4.80e-29 4.53e-24Separables F2 1.27e+03 1.26e+03

F3 2.00e+01 2.01e+01

F4 3.09e+08 2.55e+08Parcialmente F5 9.68e+06 1.18e+07Separables F6 1.03e+06 1.03e+06

F7 3.18e+04 5.83e+02

F8 1.36e+12 2.19e+12Parcialmente F9 7.12e+08 5.14e+08Separables II F10 9.19e+07 9.16e+07

F11 9.87e+06 2.77e+06

F12 5.16e+02 1.32e+02Con solapamiento F13 4.02e+06 6.29e+05

F14 1.48e+07 1.01e+07

No separable F15 3.13e+06 1.35e+06

ResultadosMejora en 10 de las 15 funciones.Mejora en los problemas más difíciles.

Visualmente

1 Se ordenan los algoritmos por función.2 A cada algoritmo se asignan puntos por su posición.

• Criterio de la Fórmula 1.

3 Para cada algoritmo se suman sus puntos.4 Se muestran la suma de puntos por categoría y totales.

Visualmente

Comparando con MOS

Grupo de Funciones Función Propuesta MOS

F1 4.53e-24 0.00e+00Separables F2 1.26e+03 8.36e+02

F3 2.01e+01 9.10e-13

F4 2.55e+08 1.56e+08Parcialmente F5 1.18e+07 6.79e+06Separables F6 1.03e+06 1.39e+05

F7 5.83e+02 1.62e+04

F8 2.19e+12 8.08e+12Parcialmente F9 5.14e+08 3.87e+08Separables II F10 9.16e+07 1.18e+06

F11 2.77e+06 4.48e+07

F12 1.32e+02 2.46e+02Con solapamiento F13 6.29e+05 3.30e+06

F14 1.01e+07 2.42e+07

No separable F15 1.35e+06 2.38e+06

AnálisisMejora a MOS en las funciones más complejas, aunque noglobalmente.

Gráfica de convergencia

Análisis de gráficasNo sólo obtiene buenos resultados.Podría seguir mejorando con más evaluaciones.

Visualmente

Conclusiones

Hemos presentado un nuevo algoritmo para altadimensionalidad.Se basa en un trabajo previo que modifica:

• Simplificando el mecanismo de elección de la BL.• Mejorando el mecanismo de reinicio.

ResultadosMejora claramente al algoritmo anterior.Mejora al estado del arte (MOS) en los problemas máscomplejos.

Trabajo futuro

Trabajo futuroProbar otros modelos de DEMejorar resultados en funciones separables

[email protected]

hibridación iterativa de de con bl con reinicio para alta dimensionalidad

Presentations & Public Speaking