Evolución diferencial

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de marzo de 2016; las comprobaciones requieren 15 ediciones .

Evolución diferencial ( ing. evolución diferencial ) - un método de optimización matemática multidimensional , que pertenece a la clase de algoritmos de optimización estocástica (es decir, funciona con números aleatorios) y utiliza algunas ideas de algoritmos genéticos , pero, a diferencia de ellos, no requiere trabajar con variables en código binario.

Este es un método de optimización directa, es decir, solo requiere la capacidad de calcular los valores de la función objetivo, pero no sus derivadas. El método de evolución diferencial está diseñado para encontrar el mínimo (o máximo) global de funciones no diferenciables, no lineales, multimodales (que posiblemente tengan una gran cantidad de extremos locales) de muchas variables. El método es fácil de implementar y usar (contiene pocos parámetros de control que requieren selección) y se paraleliza fácilmente .

El método de evolución diferencial fue desarrollado por Rainer Storn y Kenneth Price, publicado por primera vez por ellos en 1995 [1] y desarrollado aún más en su trabajo posterior. [2] [3]

Algoritmo

En su forma básica, el algoritmo se puede describir de la siguiente manera. Inicialmente, se genera un conjunto de vectores, llamado generación. Los vectores son puntos del espacio bidimensional en los que se define la función objetivo , que se quiere minimizar. En cada iteración, el algoritmo genera una nueva generación de vectores mediante la combinación aleatoria de vectores de la generación anterior. El número de vectores en cada generación es el mismo y es uno de los parámetros del método. $norte$ $f(x)$

La nueva generación de vectores se genera de la siguiente manera. Para cada vector de la generación anterior , se seleccionan tres vectores aleatorios diferentes entre los vectores de la generación anterior, con la excepción del vector en sí , y el llamado vector mutante se genera mediante la fórmula: $x_{yo}$ $v_{1}$ $v_{2}$ $v_{3}$ $x_{yo}$

v=v_{1}+F\cdot(v_{2}-v_{3}),

donde es uno de los parámetros del método, alguna constante real positiva en el intervalo [0, 2]. $F$

Sobre el vector mutante se realiza una operación de cruce , que consiste en reemplazar algunas de sus coordenadas con las coordenadas correspondientes del vector original (cada coordenada se reemplaza con una cierta probabilidad, que también es uno de los parámetros de este método). El vector obtenido después del cruce se denomina vector de prueba. Si resulta ser mejor que el vector (es decir, el valor de la función objetivo se ha vuelto más pequeño), en la nueva generación, el vector se reemplaza por un vector de prueba; de lo contrario, permanece . $v$ $x_{yo}$ $x_{yo}$ $x_{yo}$ $x_{yo}$

Ejemplos de aplicaciones prácticas

El motor de búsqueda Yandex utiliza el método de evolución diferencial para mejorar sus algoritmos de clasificación. [4] [5]

Notas

↑ Storn, Rainer y Price, Kenneth . Evolución diferencial: un esquema adaptativo simple y eficiente para la optimización global en espacios continuos, archivado el 24 de abril de 2005 en el Informe técnico de Wayback Machine TR -95-012 , ICSI, marzo de 1995.
↑ Storn, Rainer y Price, Kenneth . Evolución diferencial: una heurística simple y eficiente para la optimización global en espacios continuos. Archivado el 6 de enero de 2010 en Wayback Machine (1997)
↑ K. Price, R. Storn, J. Lampinen . Evolución diferencial: un enfoque práctico para la optimización global. Springer, 2005.
↑ Entrevista de A. Sadovsky a la revista IT SPEC, julio de 2007. . Consultado el 3 de octubre de 2009. Archivado desde el original el 13 de mayo de 2013. (indefinido)
↑ A. Gulin y otros Yandex en ROMIP'2009. Optimización de algoritmos de clasificación por métodos de aprendizaje automático. . Consultado el 3 de octubre de 2009. Archivado desde el original el 22 de noviembre de 2009. (indefinido)

Enlaces externos :

Descripción e implementación del método en el sitio de uno de sus autores. Archivado el 1 de diciembre de 2005 en Wayback Machine .
S. Lucas . Fundamentos de Metaheurísticas. Capítulo 3.4.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG