Estrategia de evolución

En informática, una estrategia de evolución (ES) es una técnica de optimización basada en ideas de evolución . Pertenece a la clase general de computación evolutiva o metodologías de evolución artificial .

Historia

La técnica de optimización de "estrategia de evolución" fue creada a principios de la década de 1960 y desarrollada aún más en la década de 1970 y posteriormente por Ingo Rechenberg , Hans-Paul Schwefel y sus colaboradores.

Métodos

Las estrategias de evolución utilizan representaciones naturales dependientes del problema, por lo que el espacio de problemas y el espacio de búsqueda son idénticos. Al igual que los algoritmos evolutivos , los operadores se aplican en un bucle. Una iteración del bucle se denomina generación. La secuencia de generaciones continúa hasta que se cumple un criterio de terminación.

La característica especial del ES es la autoadaptación de los tamaños de paso de mutación y la coevolución asociada con ella. El ES se presenta brevemente utilizando la forma estándar, ^{[1] [2] [3]} señalando que hay muchas variantes. ^{[4] [ 5] [6] [7]} El cromosoma de valor real contiene, además de las variables de decisión, tamaños de paso de mutación , donde: . A menudo se utiliza un tamaño de paso de mutación para todas las variables de decisión o cada una tiene su propio tamaño de paso. La selección de pareja para producir descendencia es aleatoria, es decir, independiente de la aptitud. Primero, se generan nuevos tamaños de paso de mutación por apareamiento mediante recombinación intermedia del progenitor con mutación posterior de la siguiente manera: ${\displaystyle n}$ ${\displaystyle n'}$ ${\displaystyle {\sigma }_{j}}$ ${\displaystyle 1\leq j\leq n'\leq n}$ ${\displaystyle \lambda }$ ${\displaystyle {\sigma }_{j}}$

${\displaystyle {\sigma }'_{j}=\sigma _{j}\cdot e^{({\mathcal {N}}(0,1)-{\mathcal {N}}_{j}(0,1))}}$

donde es una variable aleatoria distribuida normalmente con media y desviación estándar . se aplica a todos , mientras que se determina nuevamente para cada . A continuación, la recombinación discreta de las variables de decisión es seguida por una mutación utilizando los nuevos tamaños de paso de mutación como desviaciones estándar de la distribución normal. Las nuevas variables de decisión se calculan de la siguiente manera: ${\displaystyle {\mathcal {N}}(0,1)}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle {\mathcal {N}}(0,1)}$ ${\displaystyle {\sigma }'_{j}}$ ${\displaystyle {\mathcal {N}}_{j}(0,1)}$ ${\displaystyle {\sigma }'_{j}}$ ${\displaystyle x_{j}'}$

${\displaystyle x_{j}'=x_{j}+{\mathcal {N}}_{j}(0,{\sigma }_{j}')}$

Esto da como resultado una búsqueda evolutiva en dos niveles: primero, a nivel del problema en sí y segundo, a nivel del tamaño del paso de mutación. De esta manera, se puede garantizar que el ES busque su objetivo en pasos cada vez más finos. Sin embargo, también existe el peligro de que sea difícil omitir áreas inválidas más grandes en el espacio de búsqueda.

El ES conoce dos variantes de mejor selección para la generación de la siguiente población parental: en el -ES, solo se utilizan los mejores descendientes, mientras que en el -ES elitista, se seleccionan los mejores entre padres e hijos. ${\displaystyle (\mu ,\lambda )}$ ${\displaystyle \mu }$ ${\displaystyle (\mu +\lambda )}$ ${\displaystyle \mu }$

Bäck y Schwefel recomiendan que el valor de sea siete veces el tamaño de la población ^[2] , por lo que no debe elegirse un valor demasiado pequeño debido a la fuerte presión de selección. Los valores adecuados para dependen de la aplicación y deben determinarse experimentalmente. ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$

Los tamaños de paso individuales para cada coordenada, o las correlaciones entre coordenadas, que están definidas esencialmente por una matriz de covarianza subyacente , se controlan en la práctica ya sea por autoadaptación o por adaptación de la matriz de covarianza ( CMA-ES ). ^[6] Cuando el paso de mutación se extrae de una distribución normal multivariante utilizando una matriz de covarianza en evolución , se ha planteado la hipótesis de que esta matriz adaptada se aproxima a la hessiana inversa del paisaje de búsqueda. Esta hipótesis se ha demostrado para un modelo estático que se basa en una aproximación cuadrática. ^[8]

La selección de la siguiente generación en las estrategias de evolución es determinista y se basa únicamente en las clasificaciones de aptitud, no en los valores de aptitud reales. Por lo tanto, el algoritmo resultante es invariante con respecto a las transformaciones monótonas de la función objetivo. La estrategia de evolución más simple opera sobre una población de tamaño dos: el punto actual (padre) y el resultado de su mutación. Solo si la aptitud del mutante es al menos tan buena como la del padre, se convierte en el padre de la siguiente generación. De lo contrario, el mutante se descarta. Este es un -ES . De manera más general, se pueden generar mutantes y competir con el padre, llamado -ES . En -ES, el mejor mutante se convierte en el padre de la siguiente generación, mientras que el padre actual siempre se descarta. Para algunas de estas variantes, se han derivado pruebas de convergencia lineal (en un sentido estocástico ) en funciones objetivo unimodales. ^{[9] [10]} ${\displaystyle {\mathit {(1+1)}}}$ ${\displaystyle \lambda }$ ${\displaystyle {\mathit {(1+\lambda )}}}$ ${\displaystyle (1,\lambda )}$

Véase también

• Estrategia de evolución de la adaptación de la matriz de covarianza (CMA-ES)
• Optimización sin derivadas
• Computación evolutiva
• Algoritmo genético
• Estrategia de evolución natural
• Teoría de juegos evolutiva

Referencias

1. Schwefel, Hans-Paul (1995). Evolution and Optimum Seeking. Serie de tecnología informática de sexta generación. Nueva York: Wiley. ISBN 978-0-471-57148-3.
2. Bäck, Thomas; Schwefel, Hans-Paul (1993). "Una visión general de los algoritmos evolutivos para la optimización de parámetros". Computación evolutiva . 1 (1): 1–23. doi :10.1162/evco.1993.1.1.1. ISSN  1063-6560.
3. Schwefel, Hans-Paul; Rudolph, Günter; Bäck, Thomas (1995), Morán, Frederico; Moreno, Alvaro; Merelo, JJ; Chacón, Pablo (eds.), "Estrategias evolutivas contemporáneas", Actas de la Tercera Conferencia Europea sobre Avances en Vida Artificial , Berlín, Heidelberg: Springer, pp. 893–907, doi :10.1007/3-540-59496-5_351, ISBN 978-3-540-59496-3
4. Bäck, Thomas; Hoffmeister, Frank; Schwefel, Hans-Paul (1991), Belew, Richard K.; Booker, Lashon B. (eds.), "Un estudio de las estrategias evolutivas", Actas de la Cuarta Conferencia Internacional sobre Algoritmos Genéticos (ICGA) , San Mateo, California: Morgan Kaufmann, ISBN 978-0-852-2-3 978-1-55860-208-3
5. Coelho, VN; Coelho, IM; Souza, MJF; Oliveira, TA; Cota, LP; Haddad, Minnesota; Mladenovic, N.; Silva, PCR; Guimarães, FG (2016). "Estrategias de evolución híbrida autoadaptativa guiadas por estructuras vecinales para problemas de optimización combinatoria". Computación Evolutiva . 24 (4): 637–666. doi :10.1162/EVCO_a_00187. ISSN  1063-6560.
6. Hansen, Nikolaus; Östermeier, Andreas (2001). "Autoadaptación completamente desaleatorizada en estrategias de evolución". Computación Evolutiva . 9 (2): 159-195. doi :10.1162/106365601750190398. ISSN  1063-6560.
7. Hansen, Nikolaus; Kern, Stefan (2004), Yao, Xin; Burke, Edmund K.; Lozano, José A.; Smith, Jim (eds.), "Evaluación de la estrategia de evolución de CMA en funciones de prueba multimodales", Parallel Problem Solving from Nature - PPSN VIII , vol. 3242, Berlín, Heidelberg: Springer, págs. 282–291, doi :10.1007/978-3-540-30217-9_29, ISBN 978-3-540-23092-2
8. Shir, OM; A. Yehudayoff (2020). "Sobre la relación covarianza-hessiana en las estrategias de evolución". Ciencias de la Computación Teórica . 801 . Elsevier: 157–174. arXiv : 1806.03674 . doi : 10.1016/j.tcs.2019.09.002 .
9. Auger, A. (2005). "Resultados de convergencia para (1,λ)-SA-ES usando la teoría de cadenas de Markov φ-irreducibles". Ciencias de la Computación Teórica . 334 (1–3). Elsevier: 35–69. doi :10.1016/j.tcs.2004.11.017.
10. Jägersküpper, J. (2006). "Cómo el ES (1+1) que utiliza mutaciones isotrópicas minimiza las formas cuadráticas definidas positivas". Ciencias de la Computación Teórica . 361 (1). Elsevier: 38–56. doi : 10.1016/j.tcs.2006.04.004 .

Bibliografía

• Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (tesis doctoral). Reimpreso por Frommann-Holzboog (1973). ISBN 3-7728-1642-8 
• Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (tesis doctoral). Reimpreso por Birkhäuser (1977).
• Hans-Paul Schwefel : Evolución y búsqueda del óptimo . Nueva York: Wiley & Sons 1995. ISBN 0-471-57148-2 
• H.-G. Beyer y H.-P. Schwefel. Estrategias evolutivas: una introducción completa . Journal Natural Computing, 1(1):3–52, 2002.
• Hans-Georg Beyer: La teoría de las estrategias evolutivas . Springer, 27 de abril de 2001. ISBN 3-540-67297-4 
• Ingo Rechenberg: Estrategia de evolución '94 . Stuttgart: Frommann-Holzboog 1994. ISBN 3-7728-1642-8 
• J. Klockgether y HP Schwefel (1970). Two-Phase Nozzle And Hollow Core Jet Experiments. AEG-Forschungsinstitut. MDH Staustrahlrohr Project Group. Berlín, República Federal de Alemania. Actas del 11.º Simposio sobre aspectos de ingeniería de la magnetohidrodinámica, Caltech, Pasadena, California, 24.–26.3.1970.
• M. Emmerich, OM Shir y H. Wang: Estrategias de evolución. En: Handbook of Heuristics, 1-31. Springer International Publishing (2018).

Centros de investigación

• Técnica de biónica y evolución en la Technische Universität Berlin
• Cátedra de Ingeniería de Algoritmos (Ls11) – Universidad TU Dortmund
• Centro de investigación colaborativa 531 – Universidad TU Dortmund