Estrategia de evolución

La estrategia evolutiva (EE) de la informática es una subclase de algoritmos evolutivos , que sirve como técnica de optimización . ^{[ 1 ]} Utiliza los principales operadores genéticos mutación , recombinación y selección de progenitores . ^{[ 2 ]}

La técnica de optimización de la "estrategia evolutiva" fue creada a principios de la década de 1960 y desarrollada posteriormente en la década de 1970 por Ingo Rechenberg , Hans-Paul Schwefel y sus colaboradores. ^{[ 1 ]}

Las estrategias evolutivas se desarrollaron para la optimización numérica y, por lo tanto, se basan en un vector de variables de decisión continuas . ^{[ 16 ]} Para valores discretos , se pueden utilizar métodos de redondeo adecuados o mutaciones apropiadamente adaptadas para enteros. ^{[ 17 ]} En consecuencia, en muchas aplicaciones de ES, el espacio del problema y el espacio de búsqueda son idénticos. Tal representación directa no es posible, por ejemplo, en muchas aplicaciones combinatorias como la planificación , donde se utilizan variantes apropiadamente modificadas de estrategias evolutivas. ^{[ 18 ]} Al igual que los algoritmos evolutivos , los operadores se aplican en un bucle. Una iteración del bucle se llama 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 los pasos de mutación y la coevolución asociada a ella. El ES se presenta brevemente utilizando la forma estándar, ^{[ 19 ] [ 20 ] [ 21 ]} señalando que hay muchas variantes. ^{[ 18 ] [ 22 ] [ 23 ] [ 24 ]} El cromosoma de valor real contiene, además de${\displaystyle n}$variables de decisión,${\displaystyle n'}$tamaños de paso de mutación${\displaystyle {\sigma }_{j}}$, dónde:${\displaystyle 1\leq j\leq n'\leq n}$A menudo se utiliza un mismo tamaño de paso de mutación para todas las variables de decisión o cada una tiene su propio tamaño de paso. Selección de pareja para producir${\displaystyle \lambda }$La descendencia es aleatoria, es decir, independiente de la aptitud. Primero, se generan nuevos tamaños de pasos de mutación por apareamiento mediante la recombinación intermedia de los progenitores.${\displaystyle {\sigma }_{j}}$con la siguiente mutación:

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

dónde${\displaystyle {\mathcal {N}}(0,1)}$es una variable aleatoria con distribución normal y media${\displaystyle 0}$y desviación estándar${\displaystyle 1}$.${\displaystyle {\mathcal {N}}(0,1)}$Se aplica a todos${\displaystyle {\sigma }'_{j}}$, mientras${\displaystyle {\mathcal {N}}_{j}(0,1)}$se determina de nuevo para cada uno${\displaystyle {\sigma }'_{j}}$A continuación, se realiza una recombinación discreta de las variables de decisión, seguida de 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${\displaystyle x_{j}'}$se calculan de la siguiente manera:

${\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 asegurar que el algoritmo evolutivo busque su objetivo con pasos cada vez más precisos. Sin embargo, también existe el riesgo de que sea difícil omitir áreas inválidas extensas 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 (${\displaystyle \mu }$- número de padres,${\displaystyle \lambda }$- número de descendientes): ^{[ 2 ]}

• ${\displaystyle (\mu,\lambda)}$: El${\displaystyle \mu }$Los mejores descendientes se utilizan para la siguiente generación (generalmente${\displaystyle \mu ={\frac {\lambda }{2}}}$).
• ${\displaystyle (\mu +\lambda)}$: Los mejores son seleccionados de una unión de${\displaystyle \mu }$padres y${\displaystyle \lambda }$descendiente.

Bäck y Schwefel recomiendan que el valor de${\displaystyle \lambda }$debería ser aproximadamente siete veces la${\displaystyle \mu }$, ^{[ 20 ]} por lo cual${\displaystyle \mu }$no debe elegirse demasiado pequeño debido a la fuerte presión de selección. Valores adecuados para${\displaystyle \mu }$Dependen de la aplicación y deben determinarse experimentalmente. La selección de la siguiente generación en las estrategias evolutivas 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 y antigua ^{[ 1 ]}${\displaystyle {\mathit {(1+1)}}}$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 es descartado. En términos más generales,${\displaystyle \lambda }$Se pueden generar mutantes que compiten con el progenitor, llamado${\displaystyle (1+\lambda )}$. En${\displaystyle (1,\lambda )}$El mejor mutante se convierte en el progenitor de la siguiente generación, mientras que el progenitor actual siempre se descarta. Para algunas de estas variantes, se han derivado pruebas de convergencia lineal (en un sentido estocástico ) sobre funciones objetivo unimodales. ^{[ 25 ] [ 26 ]}

Los tamaños de paso individuales para cada coordenada, o correlaciones entre coordenadas, que se definen esencialmente por una matriz de covarianza subyacente , se controlan en la práctica ya sea por auto-adaptación o por adaptación de la matriz de covarianza ( CMA-ES ). ^{[ 23 ]} Cuando el paso de mutación se extrae de una distribución normal multivariada usando una matriz de covarianza evolutiva , se ha planteado la hipótesis de que esta matriz adaptada aproxima la inversa del Hessiano 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. ^{[ 27 ]} En 2025, Chen et al. ^{[ 28 ]} propusieron una estrategia de evolución multiagente para la optimización distribuida basada en consenso, donde se diseña un nuevo método de adaptación de pasos para ayudar a múltiples agentes a controlar el tamaño del paso de forma cooperativa.

• Estrategia de evolución de 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

• 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 de evolución: 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). Experimentos con boquillas bifásicas y chorros de núcleo hueco . AEG-Forschungsinstitut. Grupo de proyecto MDH Staustrahlrohr. 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 de marzo de 1970.
• M. Emmerich, OM Shir y H. Wang: Estrategias de evolución . En: Manual de heurística, 1-31. Springer International Publishing (2018).

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