Evolución diferencial

Parte de una serie sobre el
Algoritmo evolutivo
Desarrollo artificial Vida artificial Algoritmo evolutivo celular Algoritmo cultural Evolución diferencial Fitness efectivo Computación evolutiva Estrategia de evolución Adaptación gaussiana Optimización multimodal evolutiva Evolución gramatical Optimización de Enjambre de partículas Algoritmo memético Estrategia de evolución natural Neuroevolución Algoritmo genético basado en promotores Algoritmo de optimización en espiral Código auto modificable Código polimórfico
Algoritmo genético
Cromosoma Algoritmo de selección clonal Transversal Mutación Memoria genética Sistemas genéticos difusos Selección Algoritmo de vuelo
Programación genética
Programación genética cartesiana Programación genética lineal Programación de expresiones múltiples Esquema Eurisko Punto de referencia de paridad
v t mi

Evolución diferencial optimizando la función Ackley 2D.

En el cálculo evolutivo , la evolución diferencial ( DE ) es un método que optimiza un problema al tratar iterativamente de mejorar una solución candidata con respecto a una determinada medida de calidad. Dichos métodos se conocen comúnmente como metaheurísticas, ya que hacen pocas o ninguna suposición sobre el problema que se está optimizando y pueden buscar espacios muy grandes de soluciones candidatas. Sin embargo, metaheurísticas como la DE no garantizan que nunca se encuentre una solución óptima.

DE se usa para funciones multidimensionales de valor real, pero no usa el gradiente del problema que se está optimizando, lo que significa que DE no requiere que el problema de optimización sea diferenciable , como lo requieren los métodos de optimización clásicos como el descenso de gradiente y los métodos de cuasi-newton . Por lo tanto, DE también se puede utilizar en problemas de optimización que ni siquiera son continuos , son ruidosos, cambian con el tiempo, etc. ^[1]

DE optimiza un problema manteniendo una población de soluciones candidatas y creando nuevas soluciones candidatas combinando las existentes de acuerdo con sus fórmulas simples, y luego manteniendo la solución candidata que tenga la mejor puntuación o idoneidad en el problema de optimización en cuestión. De esta manera, el problema de optimización se trata como una caja negra que simplemente proporciona una medida de calidad dada una solución candidata y, por lo tanto, el gradiente no es necesario.

DE fue introducido por Storn y Price en la década de 1990. ^{[2] [3]} Se han publicado libros sobre aspectos teóricos y prácticos del uso de DE en computación paralela , optimización multiobjetivo , optimización restringida , y los libros también contienen encuestas de áreas de aplicación. ^{[4] [5] [6] [7]} Las encuestas sobre los aspectos de investigación multifacéticos de la ED se pueden encontrar en artículos de revistas. ^{[8] [9]}

Algoritmo

Una variante básica del algoritmo DE funciona al tener una población de soluciones candidatas (llamadas agentes). Estos agentes se mueven en el espacio de búsqueda utilizando fórmulas matemáticas simples para combinar las posiciones de los agentes existentes de la población. Si la nueva posición de un agente es una mejora entonces se acepta y forma parte de la población, de lo contrario la nueva posición simplemente se descarta. El proceso se repite y, al hacerlo, se espera, pero no se garantiza, que finalmente se descubra una solución satisfactoria.

Formalmente, sea ​​la función de aptitud la que debe minimizarse (tenga en cuenta que la maximización se puede realizar considerando la función en su lugar). La función toma una solución candidata como argumento en forma de un vector de números reales y produce un número real como salida que indica la idoneidad de la solución candidata dada. Se desconoce el gradiente de . El objetivo es encontrar una solución para todos en el espacio de búsqueda, lo que significa que es el mínimo global.${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle h:=-f}$${\displaystyle f}$${\displaystyle \mathbf {m} }$${\displaystyle f(\mathbf {m} )\leq f(\mathbf {p} )}$${\displaystyle \mathbf {p} }$${\displaystyle \mathbf {m} }$

Designemos una solución candidata (agente) en la población. El algoritmo DE básico se puede describir de la siguiente manera:${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$

• Elija los parámetros , y . es el tamaño de la población, es decir, el número de agentes candidatos o "padres"; un escenario clásico es 10 . El parámetro se llama probabilidad de cruce y el parámetro se llama peso diferencial . Los escenarios clásicos son y . El rendimiento de la optimización puede verse muy afectado por estas opciones; vea abajo.${\displaystyle {\text{CR}}\in [0,1]}$${\displaystyle F\in [0,2]}$${\displaystyle {\text{NP}}\geq 4}$${\displaystyle {\text{NP}}}$${\displaystyle n}$${\displaystyle {\text{CR}}\in [0,1]}$${\displaystyle F\in [0,2]}$${\displaystyle F=0.8}$${\displaystyle CR=0.9}$
• Inicialice todos los agentes con posiciones aleatorias en el espacio de búsqueda.${\displaystyle \mathbf {x} }$
• Hasta que se cumpla un criterio de terminación (por ejemplo, número de iteraciones realizadas o aptitud adecuada alcanzada), repita lo siguiente:
  • Para cada agente de la población:${\displaystyle \mathbf {x} }$
    • Elija tres agentes y, de la población al azar, deben ser distintos entre sí y también del agente . ( se llama vector "base").${\displaystyle \mathbf {a} ,\mathbf {b} }$${\displaystyle \mathbf {c} }$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {a} }$
    • Elija un índice aleatorio en el que se optimice la dimensionalidad del problema.${\displaystyle R\in \{1,\ldots ,n\}}$${\displaystyle n}$
    • Calcule la posición potencialmente nueva del agente de la siguiente manera:${\displaystyle \mathbf {y} =[y_{1},\ldots ,y_{n}]}$
      • Para cada uno , elija un número aleatorio distribuido uniformemente${\displaystyle i\in \{1,\ldots ,n\}}$${\displaystyle r_{i}\sim U(0,1)}$
      • Si o entonces establece lo contrario . (La posición del índice se reemplaza con certeza).${\displaystyle r_{i}<CR}$${\displaystyle i=R}$${\displaystyle y_{i}=a_{i}+F\times (b_{i}-c_{i})}$${\displaystyle y_{i}=x_{i}}$${\displaystyle R}$
    • Si, entonces reemplace el agente en la población con la solución candidata mejorada o igual .${\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {y} }$
• Elija el agente de la población que tenga la mejor aptitud y devuélvalo como la mejor solución candidata encontrada.

Selección de parámetros

Panorama de rendimiento que muestra cómo se comporta el DE básico en conjunto en los problemas de referencia de Sphere y Rosenbrock al variar los dos parámetros de DE y , y se mantiene fijo = 0,9.${\displaystyle {\text{NP}}}$${\displaystyle {\text{F}}}$${\displaystyle {\text{CR}}}$

La elección de los parámetros DE y puede tener un gran impacto en el rendimiento de la optimización. Por lo tanto, la selección de los parámetros de DE que produzcan un buen rendimiento ha sido objeto de mucha investigación. Reglas de oro para la selección de parámetros fueron ideadas por Storn et al. ^{[3] [4]} y Liu y Lampinen. ^[10] Zaharie realizó el análisis de convergencia matemática con respecto a la selección de parámetros. ^[11]${\displaystyle F,{\text{CR}}}$${\displaystyle {\text{NP}}}$

Variantes

Las variantes del algoritmo DE se desarrollan continuamente en un esfuerzo por mejorar el rendimiento de la optimización. Son posibles muchos esquemas diferentes para realizar cruces y mutaciones de agentes en el algoritmo básico dado anteriormente, ver, por ejemplo, ^[3]

Ver también

• Un algoritmo de optimización de Mayfly ^[12]
• Algoritmo de colonia de abejas artificial
• CMA-ES
• Estrategia de evolución
• Algoritmo genético

Referencias

1. Rocca, P .; Oliveri, G .; Massa, A. (2011). "Evolución diferencial aplicada a electromagnetismo". Revista IEEE Antennas and Propagation . 53 (1): 38–49. doi : 10.1109 / MAP.2011.5773566 . S2CID 27555808 . 
2. Storn, R .; Price, K. (1997). "Evolución diferencial - una heurística simple y eficiente para la optimización global en espacios continuos". Revista de optimización global . 11 (4): 341–359. doi : 10.1023 / A: 1008202821328 . S2CID 5297867 . 
3. Storn, R. (1996). "Sobre el uso de la evolución diferencial para la optimización de funciones". Conferencia Bienal de la Sociedad de Procesamiento de Información Difusa de América del Norte (NAFIPS) . págs. 519–523. doi : 10.1109 / NAFIPS.1996.534789 . S2CID 16576915 . 
4. Precio, K .; Storn, RM; Lampinen, JA (2005). Evolución diferencial: un enfoque práctico para la optimización global . Saltador. ISBN 978-3-540-20950-8.
5. Feoktistov, V. (2006). Evolución diferencial: en busca de soluciones . Saltador. ISBN 978-0-387-36895-5.
6. GC Onwubolu y BV Babu, "Nuevas técnicas de optimización en ingeniería" . Consultado el 17 de septiembre de 2016 .
7. Chakraborty, Reino Unido, ed. (2008), Avances en la evolución diferencial , Springer, ISBN 978-3-540-68827-3
8. S. Das y PN Suganthan, " Evolución diferencial: una revisión del estado de la técnica ", IEEE Trans. sobre Computación Evolutiva, Vol. 15, núm. 1, págs. 4-31, febrero de 2011, DOI: 10.1109 / TEVC.2010.2059031.
9. S. Das, SS Mullick, PN Suganthan, " Avances recientes en la evolución diferencial: una encuesta actualizada ", Swarm and Evolutionary Computation, doi: 10.1016 / j.swevo.2016.01.004, 2016.
10. Liu, J .; Lampinen, J. (2002). "Al establecer el parámetro de control del método de evolución diferencial". Actas de la VIII Conferencia Internacional de Soft Computing (MENDEL) . Brno, República Checa. págs. 11-18.
11. Zaharie, D. (2002). "Valores críticos para los parámetros de control de algoritmos de evolución diferencial". Actas de la VIII Conferencia Internacional de Soft Computing (MENDEL) . Brno, República Checa. págs. 62–67.
12. Zervoudakis, Konstantinos; Tsafarakis, Stelios (2020). "Un algoritmo de optimización de efímeras". Computación e Ingeniería Industrial . antes de la impresión (antes de la impresión): cabeza de impresión. doi : 10.1016 / j.cie.2020.106559 .