Evolución diferencial

Método de optimización matemática.

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

En computación evolutiva , la evolución diferencial ( DE ) es un método que optimiza un problema al intentar mejorar de forma iterativa una solución candidata con respecto a una medida de calidad determinada. Estos 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, metaheurísticas como DE no garantizan que alguna vez 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 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 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, no es necesario 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 restringida , y los libros también contienen estudios de áreas de aplicación. ^{[5] [6] [7] [8]} En artículos de revistas se pueden encontrar encuestas sobre los aspectos de investigación multifacéticos de la ED. ^{[9] [10]}

Algoritmo

Una variante básica del algoritmo DE funciona teniendo una población de soluciones candidatas (llamadas agentes). Estos agentes se mueven en el espacio de búsqueda mediante el uso de 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, en caso 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 (tenga en cuenta que la maximización se puede realizar considerando la función ). La función toma como argumento una solución candidata en forma de vector de números reales . Produce un número real como resultado 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 . ${\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 llama probabilidad de cruce y el parámetro se llama peso 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 la optimización puede verse muy afectado por estas opciones; vea abajo.
• 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 donde esté 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 uno , 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 lo contrario, se establece . (La posición del índice se reemplaza con seguridad). ${\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 se reemplaza 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 solución candidata mejor 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 de Sphere y Rosenbrock cuando se varían los dos parámetros de DE y se mantienen fijos = 0,9. ${\displaystyle {\text{NP}}}$ ${\displaystyle {\text{F}}}$ ${\displaystyle {\text{CR}}}$

La elección de los parámetros DE 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. idearon reglas generales para la selección de parámetros. ^{[4] [5]} y Liu y Lampinen. ^[11] Zaharie realizó el 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 restricción (una penalización L1) o el cuadrado de una violación de restricción (una penalización L2). ${\displaystyle f{\tilde {}}(x)=f(x)+\rho \times \mathrm {CV} (x)}$ ${\displaystyle \mathrm {CV} (x)}$

Este método, sin embargo, tiene ciertos inconvenientes. Un desafío importante es la selección adecuada del coeficiente de penalización . Si se establece demasiado bajo, es posible que no aplique 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 porque no requiere alterar el algoritmo de evolución diferencial en sí. ${\displaystyle \rho }$ ${\displaystyle \rho }$

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

Variantes

Continuamente se desarrollan 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]

Ver también

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

Referencias

1. Rocca, P.; Oliveri, G.; Massa, A. (2011). "Evolución diferencial aplicada al electromagnético". Revista IEEE Antenas y Propagación . 53 (1): 38–49. doi :10.1109/MAP.2011.5773566. S2CID  27555808.
2. Destrozado, Rainer; Precio, 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: Instituto Internacional de Ciencias de la Computación: TR-95-012 . Consultado el 3 de abril de 2024 .
3. Storn, R.; Precio, 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.
4. Storn, R. (1996). "Sobre el uso de la evolución diferencial para la optimización de funciones". Conferencia Bienal de la Sociedad Norteamericana de Procesamiento de Información Difusa (NAFIPS) . págs. 519–523. doi :10.1109/NAFIPS.1996.534789. S2CID  16576915.
5. 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.
6. Feoktistov, V. (2006). Evolución diferencial: en busca de soluciones. Saltador. 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. sobre Computación Evolutiva, 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 la evolución diferencial: una encuesta actualizada", Computación enjambre y evolutiva, 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 Computación Suave (MENDEL) . Brno, República Checa. págs. 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 Computación Suave (MENDEL) . Brno, República Checa. págs. 62–67.