Evolución diferencial

La evolución diferencial ( ED ) es un algoritmo evolutivo que optimiza un problema mediante la mejora iterativa de una solución candidata con respecto a una medida de calidad dada. Estos métodos se conocen comúnmente como metaheurísticas , ya que hacen pocas o ninguna suposición sobre el problema a optimizar y pueden explorar espacios muy amplios de soluciones candidatas. Sin embargo, las metaheurísticas como la ED no garantizan que se encuentre una solución óptima.

DE se utiliza para funciones multidimensionales de valor real , pero no utiliza el gradiente del problema que se está optimizando, lo que significa que DE no requiere que el problema de optimización sea diferenciable , como sí lo requieren los métodos de optimización clásicos como el descenso de gradiente y los métodos 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 mediante la combinación de las existentes según sus fórmulas sencillas. Posteriormente, conserva la solución candidata con la mejor puntuación o aptitud para el problema de optimización en cuestión. De esta forma, el problema de optimización se trata como una caja negra que simplemente proporciona una medida de calidad para cada solución candidata, por lo que no se necesita el gradiente.

Storn y Price introdujeron la Evolución Diferencial en 1995. ^{[ 2 ] [ 3 ] [ 4 ]} Se han publicado libros sobre aspectos teóricos y prácticos del uso de DE en computación paralela , optimización multiobjetivo , optimización con restricciones , y los libros también contienen estudios de áreas de aplicación. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]} Se pueden encontrar estudios sobre los aspectos de investigación multifacéticos de DE en artículos de revistas. ^{[ 9 ] [ 10 ]}

Una variante básica del algoritmo DE funciona mediante una población de soluciones candidatas (denominadas agentes). Estos agentes se mueven por el espacio de búsqueda utilizando fórmulas matemáticas sencillas que combinan las posiciones de los agentes existentes en la población. Si la nueva posición de un agente supone una mejora, se acepta y pasa a formar parte de la población; de lo contrario, se descarta. El proceso se repite y, al hacerlo, se espera, aunque no se garantiza, que finalmente se encuentre una solución satisfactoria.

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

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

• Seleccione los parámetros${\displaystyle {\text{NP}}\geq 4}$,${\displaystyle {\text{CR}}\in [0,1]}$, y${\displaystyle F\in [0,2]}$.
  • NP  :${\displaystyle {\text{NP}}}$es el tamaño de la población, es decir, el número de agentes candidatos o "padres".
  • CR  : El parámetro${\displaystyle {\text{CR}}\in [0,1]}$se denomina probabilidad de cruce .
  • F  : El parámetro${\displaystyle F\in [0,2]}$se denomina peso diferencial .
  • Los entornos típicos son${\displaystyle NP=10n}$,${\displaystyle CR=0.9}$y${\displaystyle F=0.8}$.
  • El rendimiento de la optimización puede verse muy afectado por estas decisiones; véase más abajo.
• Inicializar todos los agentes${\displaystyle \mathbf {x} }$con posiciones aleatorias en el espacio de búsqueda.
• 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${\displaystyle \mathbf {x} }$en la población hacen:
    • Elige tres agentes${\displaystyle \mathbf {a} ,\mathbf {b} }$, y${\displaystyle \mathbf {c} }$de la población al azar, deben ser distintos entre sí, así como del agente.${\displaystyle \mathbf {x} }$. (${\displaystyle \mathbf {a} }$(Se denomina vector "base").
    • Elige un índice aleatorio${\displaystyle R\in \{1,\ldots ,n\}}$dónde${\displaystyle n}$es la dimensionalidad del problema que se está optimizando.
    • Calcular la nueva posición potencial del agente.${\displaystyle \mathbf {y} =[y_{1},\ldots,y_{n}]}$como sigue:
      • Para cada${\displaystyle i\in \{1,\ldots ,n\}}$, elige un número aleatorio con distribución uniforme${\displaystyle r_{i}\sim U(0,1)}$
      • Si${\displaystyle r_{i}<CR}$o${\displaystyle i=R}$luego establecer${\displaystyle y_{i}=a_{i}+F\times (b_{i}-c_{i})}$de lo contrario establecido${\displaystyle y_{i}=x_{i}}$. (Posición del índice${\displaystyle R}$es reemplazado con certeza.)
    • Si${\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )}$luego reemplace al agente${\displaystyle \mathbf {x} }$en la población con la solución candidata mejorada o igual${\displaystyle \mathbf {y} }$.
• Seleccione el agente de la población que tenga la mejor aptitud y devuélvalo como la mejor solución candidata encontrada.

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

La evolución diferencial también puede utilizarse para la optimización con restricciones. Un método común consiste en modificar la función objetivo para incluir una penalización por cualquier violación de las restricciones, expresada como:${\displaystyle f{\tilde {(}}x)=f(x)+\rho \times \mathrm {CV} (x)}$. Aquí,${\displaystyle \mathrm {CV} (x)}$representa una violación de una restricción (una penalización L1) o el cuadrado de una violación de una restricción (una penalización L2).

Sin embargo, este método presenta ciertos inconvenientes. Un desafío importante es la selección adecuada del coeficiente de penalización.${\displaystyle \rho }$. Si${\displaystyle \rho }$Si se establece un valor demasiado bajo, es posible que no se apliquen las restricciones de manera efectiva. Por el contrario, si es demasiado alto, puede ralentizar considerablemente o incluso detener el proceso de convergencia. A pesar de estos desafíos, este enfoque sigue siendo ampliamente utilizado debido a su simplicidad y a que no requiere modificar el algoritmo de evolución diferencial.

Existen estrategias alternativas, como la proyección sobre un conjunto factible o la reducción de dimensionalidad, que pueden utilizarse en casos con restricciones de caja o lineales. Sin embargo, en el contexto de restricciones no lineales generales, los métodos más fiables suelen implicar funciones de penalización.

Se están desarrollando continuamente variantes del algoritmo DE con el fin de mejorar el rendimiento de la optimización. ^{[ 13 ]} Se pueden esbozar las siguientes direcciones de desarrollo:

• Nuevos esquemas para realizar cruces y mutaciones de agentes ^{[ 4 ]}
• Diversas estrategias para gestionar las restricciones
• Estrategias adaptativas que ajustan dinámicamente el tamaño de la población y los parámetros F y CR.
• Algoritmos especializados para la optimización a gran escala
• Algoritmos multiobjetivo y de muchos objetivos
• Técnicas para el manejo de variables binarias/enteras

• Algoritmo de colonia de abejas artificiales
• CMA-ES
• Estrategia de evolución
• Algoritmo genético