Differential Evolution — Optimizador Estocástico Global
- Propuesto por
- Rainer Storn & Kenneth Price
- Año
- 1997
- Tipo
- Population-based stochastic metaheuristic
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
Differential Evolution (DE), introducido por Rainer Storn y Kenneth Price en 1997, es un algoritmo estocástico de optimización basado en población diseñado para espacios de parámetros continuos.
Genera soluciones candidatas combinando diferencias vectoriales entre miembros existentes de la población, lo que lo convierte en una alternativa potente y con pocos parámetros a los Algoritmos Genéticos y la Optimización por Enjambre de Partículas cuando el paisaje de búsqueda no es convexo, es multimodal o no se adapta bien a métodos basados en gradientes.
La intuición detrás del método
Imagine un grupo de exploradores esparcidos por un paisaje desconocido buscando el valle más bajo. En cada paso, cada explorador observa a tres colegas elegidos al azar, se mueve en la dirección sugerida por la diferencia entre dos de ellos escalada por un factor de tamaño de paso, y luego decide si la nueva posición o la antigua es un terreno mejor. A lo largo de muchas rondas, todo el grupo se agrupa gradualmente alrededor del valle más profundo que ha encontrado colectivamente. Differential Evolution funciona exactamente de esta manera: la 'diferencia' entre dos vectores de población actúa como la dirección de búsqueda, y el factor de escala F controla la audacia de cada paso.
Historia
Differential Evolution fue introducido por Rainer Storn y Kenneth Price en su influyente artículo de 1997 en el Journal of Global Optimization. El algoritmo surgió del trabajo anterior de Price sobre temple genético y los experimentos de Storn con cruce de punto flotante. La variante original, ahora llamada DE/best/1/bin, demostró ser competitiva — y a menudo superior — a las estrategias evolutivas y algoritmos genéticos contemporáneos en benchmarks estándar. Una revisión exhaustiva de Das, Mullick y Suganthan (2016) catalogó más de dos décadas de variantes, esquemas adaptativos y aplicaciones, estableciendo a DE como uno de los métodos fundamentales en la literatura de metaheurísticas.
Cuándo usarlo
Differential Evolution es apropiado cuando la función objetivo es continua, posiblemente no diferenciable o multimodal, y los límites de búsqueda para todos los parámetros se conocen de antemano. No requiere información de gradiente ni suposiciones de normalidad, por lo que se adapta al diseño de ingeniería, la optimización de hiperparámetros, la calibración de modelos de simulación y cualquier tarea de optimización de caja negra. Un tamaño de población de aproximadamente 10 veces el número de parámetros es un punto de partida común. DE no debe aplicarse a problemas puramente discretos o combinatorios; también necesita al menos 1 000 iteraciones para converger de manera fiable — si el presupuesto de evaluación de la función es muy ajustado, la optimización bayesiana es una alternativa más eficiente en cuanto a muestras.
Limitaciones y consideraciones
- La convergencia puede ser lenta si el número de iteraciones es insuficiente; menos de 1 000 generaciones a menudo produce un resultado subóptimo.
- El rendimiento es sensible a la elección de F y CR — parámetros mal ajustados pueden llevar a una convergencia prematura o a un progreso excesivamente lento.
- No está diseñado para espacios de búsqueda puramente discretos o combinatorios; existen extensiones discretas pero son menos estándar.
- Cada iteración requiere evaluar la función objetivo NP veces, lo que puede ser costoso cuando cada evaluación es computacionalmente cara.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- No requiere información de gradiente — funciona con cualquier función objetivo de caja negra, incluidas las no diferenciables y ruidosas.
- Muy pocos parámetros de control (F, CR, NP) en relación con su potencia de búsqueda, lo que lo hace comparativamente fácil de configurar.
- Maneja de forma natural paisajes multimodales donde los optimizadores basados en gradientes convergen a óptimos locales.
- Las evaluaciones de la población son independientes y pueden paralelizarse de forma sencilla, reduciendo el tiempo de reloj en sistemas multinúcleo.
- Competitivo con Algoritmos Genéticos y Optimización por Enjambre de Partículas en muchos benchmarks, utilizando una regla de actualización más simple.
Aplicaciones
- Calibración de modelos de simulación y basados en agentes cuyas funciones objetivo no son analíticas.
- Optimización de hiperparámetros para pipelines de aprendizaje automático cuando el espacio de búsqueda es continuo y acotado.
- Problemas de diseño de ingeniería como diseño de antenas, optimización estructural y ajuste de controladores.
- Entrenamiento de redes neuronales y ajuste de modelos no lineales en ingeniería y ciencias naturales.
- Optimización de carteras y estimación de parámetros en modelos de series temporales financieras.
Cómo funciona
Cómo funciona
Se extrae una población de NP vectores de solución candidata de forma uniforme y aleatoria dentro de los límites de búsqueda predefinidos para cada parámetro. Los límites de búsqueda deben ser especificados por el usuario antes de que comience el algoritmo; DE no puede inferirlos del problema. Una buena población inicial cubre todo el espacio factible para que el algoritmo no se pierda regiones prometedoras desde el principio.
Para cada vector objetivo en la población, se seleccionan tres vectores distintos al azar. Se forma un vector mutante añadiendo la diferencia escalada de dos de ellos al tercero: v = x_r1 + F*(x_r2 - x_r3), donde F es el factor de escala (típicamente 0.4–1.0). Este paso basado en diferencias es lo que distingue a DE de otros algoritmos evolutivos y le proporciona información direccional auto-adaptativa sin requerir cálculo de gradientes.
Se construye un vector de prueba mezclando el vector mutante y el vector objetivo original elemento por elemento. Cada elemento se toma del mutante con probabilidad CR (la tasa de cruce, típicamente 0.5–1.0) y del objetivo en caso contrario; al menos un elemento se toma siempre del mutante. Este paso controla el equilibrio entre exploración y explotación: un CR alto favorece al mutante, un CR bajo preserva más de la solución actual.
Se evalúa el vector de prueba en la función objetivo y se compara con el vector objetivo. Si la prueba logra un valor objetivo igual o mejor, reemplaza al objetivo en la siguiente generación; de lo contrario, el objetivo se mantiene sin cambios. Esta selección codiciosa uno a uno evita que la población se deteriore y asegura una mejora monótona de la mejor solución encontrada.
La mutación, el cruce y la selección se repiten durante un número suficiente de generaciones (comúnmente 1 000 o más) hasta que se cumple un criterio de convergencia — por ejemplo, el cambio en el valor objetivo de la mejor solución cae por debajo de un umbral de tolerancia, o se alcanza el número máximo de iteraciones. El mejor vector de la población final es la solución del algoritmo.
Errores comunes
- Ejecutar DE con muy pocas iteraciones (por debajo de ~1 000) es el error más común — el algoritmo no ha tenido suficientes generaciones para converger, y el resultado debe tratarse como preliminar; cambie a optimización bayesiana si el presupuesto de evaluación es ajustado.
- Establecer el factor de escala F demasiado bajo colapsa la diversidad prematuramente; establecerlo demasiado alto impide la convergencia. Comience con F en [0.4, 1.0] y ajuste empíricamente.
- Omitir o especificar incorrectamente los límites de búsqueda es un error crítico — DE utiliza los límites para inicializar la población y producirá resultados sin sentido si los límites son demasiado estrechos o ausentes.
- Tratar DE como una ejecución única es arriesgado en paisajes multimodales — ejecute varios ensayos independientes desde diferentes semillas aleatorias y reporte la mejor solución encontrada entre las ejecuciones.
Preguntas frecuentes
¿Cómo elijo el factor de escala F y la tasa de cruce CR?
Los valores por defecto más citados son F = 0.8 y CR = 0.9 para la estrategia DE/best/1/bin. En la práctica, F controla el tamaño del paso — los valores alrededor de 0.4–1.0 son típicos — y CR controla cuánto reemplaza el mutante al objetivo. Si la población converge demasiado rápido, aumente F o disminuya CR. Las variantes adaptativas de DE (jDE, JADE) ajustan estos parámetros automáticamente durante la ejecución, lo cual es una opción razonable cuando la sintonización manual no es práctica.
¿Cuántas generaciones son necesarias?
Como regla general, se recomiendan al menos 1 000 generaciones. Para problemas de alta dimensionalidad (muchos parámetros) o paisajes complejos, pueden ser necesarias más iteraciones. Observe el valor objetivo de la mejor solución a lo largo de las generaciones: si no ha cambiado durante cientos de iteraciones, es probable que DE haya convergido — o estancado, en cuyo caso es aconsejable volver a ejecutar con una semilla aleatoria fresca.
¿Cómo se compara DE con los Algoritmos Genéticos y la Optimización por Enjambre de Partículas?
Los tres son metaheurísticas basadas en población para optimización continua. DE típicamente utiliza menos parámetros de control que los GA y tiene una regla de actualización más simple y determinista en comparación con PSO. En muchos benchmarks estándar, DE es competitivo o supera a ambos, pero el rendimiento depende del problema. La elección a menudo se reduce a la familiaridad y las implementaciones disponibles en lugar de una clasificación universal.
¿Puede DE manejar parámetros enteros o categóricos?
DE está diseñado para espacios continuos. Los parámetros enteros se pueden acomodar redondeando la solución continua al entero más cercano después de cada actualización, pero esto es una aproximación. Los problemas puramente categóricos o combinatorios — como la planificación o el enrutamiento — se manejan mejor con métodos diseñados para espacios discretos, como la Optimización por Colonia de Hormigas o la Búsqueda Tabú.
Métodos relacionados
Fuentes
Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.
Abrir referencia DOICopiado.Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.
Abrir referencia DOICopiado.