Evolución diferencial

Método de optimización matemática

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

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

La DE se utiliza para funciones multidimensionales de valor real , pero no utiliza el gradiente del problema que se está optimizando, lo que significa que la 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 cuasi-newton . Por lo tanto, la 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 según sus fórmulas simples, y luego conservando la solución candidata que tenga la mejor puntuación o aptitud para 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.

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 restringida y los libros también contienen encuestas de áreas de aplicación. ^{[5] [6] [7] [8]} Se pueden encontrar encuestas sobre los aspectos de investigación multifacéticos de DE en artículos de revistas. ^{[9] [10]}

Algoritmo

Una variante básica del algoritmo DE funciona con 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 en la población. Si la nueva posición de un agente es una mejora, 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, aunque no se garantiza, que finalmente se descubra una solución satisfactoria.

Formalmente, sea la función de aptitud que debe minimizarse (nótese 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 . Produce un número real como salida que indica la aptitud de la solución candidata dada. El gradiente de no se conoce. El objetivo es encontrar una solución para la cual 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 puede describirse de la siguiente manera: ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$

• Seleccione los parámetros , , y . ${\displaystyle {\text{NP}}\geq 4}$ ${\displaystyle {\text{CR}}\in [0,1]}$ ${\displaystyle F\in [0,2]}$
  • ${\displaystyle {\text{NP}}}$es el tamaño de la población, es decir, el número de agentes candidatos o "padres"; una configuración típica es 10 . ${\displaystyle n}$
  • El parámetro se denomina probabilidad de cruce y el parámetro se denomina ponderación diferencial . Las configuraciones típicas son y . ${\displaystyle {\text{CR}}\in [0,1]}$ ${\displaystyle F\in [0,2]}$ ${\displaystyle CR=0.9}$ ${\displaystyle F=0.8}$
  • El rendimiento de optimización puede verse afectado en gran medida por estas opciones; consulte a continuación.
• Inicializar 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 se alcance la aptitud adecuada), repita lo siguiente:
  • Para cada agente de la población haga lo siguiente: ${\displaystyle \mathbf {x} }$
    • Elija tres agentes de la población al azar; deben ser distintos entre sí y del agente ( se denomina vector "base"). ${\displaystyle \mathbf {a} ,\mathbf {b} }$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {a} }$
    • Elija un índice aleatorio donde es la dimensionalidad del problema que se está optimizando. ${\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 , elija un número aleatorio distribuido uniformemente ${\displaystyle i\in \{1,\ldots ,n\}}$ ${\displaystyle r_{i}\sim U(0,1)}$
      • Si o entonces se establece de otra manera se establece . (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 luego reemplazamos 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} }$
• Seleccione 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 desempeña el DE básico en conjunto en los problemas de referencia Sphere y Rosenbrock al variar los dos parámetros DE y , y mantener fijo = 0,9. ${\displaystyle {\text{NP}}}$ ${\displaystyle {\text{F}}}$ ${\displaystyle {\text{CR}}}$

La elección de los parámetros de DE 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. Storn et al. ^{[4] [5]} y Liu y Lampinen ^[11] idearon reglas generales para la selección de parámetros . Zaharie realizó un análisis de convergencia matemática con respecto a la selección de parámetros. ^[12] ${\displaystyle {\text{NP}}}$ ${\displaystyle {\text{CR}}}$ ${\displaystyle F}$

Manejo de restricciones

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

Sin embargo, este método tiene ciertas desventajas. Un desafío importante es la selección adecuada del coeficiente de penalización . Si se establece demasiado bajo, puede que no aplique las restricciones de manera efectiva. Por el contrario, si es demasiado alto, puede ralentizar en gran medida o incluso detener el proceso de convergencia. A pesar de estos desafíos, este enfoque sigue siendo ampliamente utilizado debido a su simplicidad y porque no requiere alterar el algoritmo de evolución diferencial en sí. ${\displaystyle \rho }$ ${\displaystyle \rho }$

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

Variantes

Se desarrollan continuamente variantes del algoritmo DE en un esfuerzo por mejorar el rendimiento de la optimización. En el algoritmo básico indicado anteriormente, son posibles muchos esquemas diferentes para realizar el cruce y la mutación de agentes; consulte, por ejemplo, ^[4].

Véase también

• 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 al electromagnetismo". Revista IEEE Antennas and Propagation . 53 (1): 38–49. doi :10.1109/MAP.2011.5773566. S2CID  27555808.
2. Storn, Rainer; Price, Kenneth (1995). "Evolución diferencial: un esquema simple y eficiente para la optimización global en espacios continuos" (PDF) . Instituto Internacional de Ciencias de la Computación . TR (95). Berkeley: TR-95-012 . Consultado el 3 de abril de 2024 .
3. Storn, R.; Price, K. (1997). "Evolución diferencial: una heurística simple y eficiente para la optimización global en espacios continuos". Journal of Global Optimization . 11 (4): 341–359. doi :10.1023/A:1008202821328. S2CID  5297867.
4. Storn, R. (1996). "Sobre el uso de la evolución diferencial para la optimización de funciones". Conferencia bienal de la North American Fuzzy Information Processing Society (NAFIPS) . pp. 519–523. doi :10.1109/NAFIPS.1996.534789. S2CID  16576915.
5. Price, K.; Storn, RM; Lampinen, JA (2005). Evolución diferencial: un enfoque práctico para la optimización global. Springer. ISBN 978-3-540-20950-8.
6. Feoktistov, V. (2006). Evolución diferencial: en busca de soluciones. Springer. ISBN 978-0-387-36895-5.
7. GC Onwubolu y BV Babu, Nuevas técnicas de optimización en ingeniería . Consultado el 17 de septiembre de 2016 .
8. Chakraborty, Reino Unido, ed. (2008), Avances en la evolución diferencial, Springer, ISBN 978-3-540-68827-3
9. S. Das y PN Suganthan, "Evolución diferencial: un estudio del estado del arte", IEEE Trans. on Evolutionary Computation, vol. 15, n.º 1, págs. 4-31, febrero de 2011, DOI: 10.1109/TEVC.2010.2059031.
10. S. Das, SS Mullick, PN Suganthan, "Avances recientes en evolución diferencial: un estudio actualizado", Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.
11. Liu, J.; Lampinen, J. (2002). "Sobre la configuración del parámetro de control del método de evolución diferencial". Actas de la 8.ª Conferencia Internacional sobre Soft Computing (MENDEL) . Brno, República Checa. pp. 11–18.
12. Zaharie, D. (2002). "Valores críticos para los parámetros de control de algoritmos de evolución diferencial". Actas de la 8.ª Conferencia Internacional sobre Soft Computing (MENDEL) . Brno, República Checa. pp. 62–67.