búsqueda de cuco

Algoritmo de optimización

En investigación de operaciones , la búsqueda cuco es un algoritmo de optimización desarrollado por Xin-She Yang y Suash Deb en 2009. ^{[1] [2]} Se ha demostrado que es un caso especial de la conocida estrategia de evolución (μ + λ). . ^[3] Se inspiró en el parasitismo de cría obligado de algunas especies de cucos al poner sus huevos en los nidos de aves hospedadoras de otras especies. Algunas aves hospedadoras pueden entrar en conflicto directo con los cucos intrusos. Por ejemplo, si un ave huésped descubre que los huevos no son suyos, los tirará o simplemente abandonará su nido y construirá uno nuevo en otro lugar. Algunas especies de cuco, como Tapera , parásito de cría del Nuevo Mundo, han evolucionado de tal manera que las hembras de cuco parásito suelen estar muy especializadas en la imitación de colores y patrones de los huevos de unas pocas especies hospedadoras elegidas. ^[4] La búsqueda cuco idealizó dicho comportamiento reproductivo y, por lo tanto, puede aplicarse a diversos problemas de optimización.

Metáfora

La búsqueda cuco (CS) utiliza las siguientes representaciones:

Cada huevo en un nido representa una solución y un huevo de cuco representa una nueva solución. El objetivo es utilizar soluciones nuevas y potencialmente mejores (cucos) para sustituir una solución no tan buena en los nidos. En la forma más simple, cada nido tiene un huevo. El algoritmo se puede extender a casos más complicados en los que cada nido tiene múltiples huevos que representan un conjunto de soluciones.

CS se basa en tres reglas idealizadas:

1. Cada cuco pone un huevo a la vez y lo arroja en un nido elegido al azar;
2. Los mejores nidos con huevos de alta calidad pasarán a la siguiente generación;
3. El número de nidos huéspedes disponibles es fijo y el ave huésped descubre el huevo puesto por un cuco con una probabilidad de . En este caso, el ave huésped puede tirar el huevo/abandonar el nido y construir un nido completamente nuevo. ${\displaystyle p_{a}\in (0,1)}$

Además, Yang y Deb descubrieron que la búsqueda de estilo de caminata aleatoria se realiza mejor con vuelos de Lévy que con una simple caminata aleatoria .

Algoritmo

El pseudocódigo se puede resumir como:

Función objetivo:
Generar una población inicial de nidos hospedantes; Mientras (t<MaxGeneration) o (criterio de parada) ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$ ${\displaystyle n}$ Obtener un cuco al azar (digamos, i) y reemplazar su solución realizando vuelos de Lévy; Evaluar su calidad/aptitud [Para maximizar, ]; ${\displaystyle F_{i}}$ ${\displaystyle F_{i}\propto f(\mathbf {x} _{i})}$ Elija un nido entre n (digamos, j) al azar; si ( ), ${\displaystyle F_{i}>F_{j}}$ Reemplace j por la nueva solución; terminar si Una fracción ( ) de los peores nidos se abandona y se construyen otros nuevos; ${\displaystyle p_{a}}$ Mantenga las mejores soluciones/nidos; Clasifique las soluciones/nidos y encuentre las mejores actualmente; Pasar las mejores soluciones actuales a la próxima generación;terminar mientras

Una ventaja importante de este algoritmo es su simplicidad. De hecho, en comparación con otros algoritmos metaheurísticos basados ​​en poblaciones o agentes, como la optimización de enjambre de partículas y la búsqueda de armonía , esencialmente existe un solo parámetro en CS (aparte del tamaño de la población ). Por tanto, es muy fácil de implementar. ${\displaystyle p_{a}}$ ${\displaystyle n}$

Paseos aleatorios y tamaño del paso.

Un tema importante son las aplicaciones de los vuelos de Lévy y los paseos aleatorios en la ecuación genérica para generar nuevas soluciones.

${\displaystyle \mathbf {x} _{t+1}=\mathbf {x} _{t}+sE_{t},}$

donde se extrae de una distribución normal estándar con media cero y desviación estándar unitaria para paseos aleatorios, o se extrae de la distribución de Lévy para vuelos de Lévy . Obviamente, los paseos aleatorios también pueden estar relacionados con la similitud entre el huevo de un cuco y el huevo del huésped, lo que puede ser complicado de implementar. Aquí, el tamaño del paso determina hasta dónde puede llegar un caminante aleatorio durante un número fijo de iteraciones. La generación del tamaño del paso de Lévy es a menudo complicada, y Leccardi ^[6] realizó una comparación de tres algoritmos (incluido el de Mantegna ^[5] ) , quien encontró que una implementación del enfoque de Chambers et al. ^[7] era el más computacionalmente posible. eficiente debido al bajo número de números aleatorios requeridos. ${\displaystyle E_{t}}$ ${\displaystyle s}$

Si s es demasiado grande, entonces la nueva solución generada estará demasiado lejos de la solución anterior (o incluso saltará fuera de los límites). Entonces, es poco probable que se acepte tal medida. Si s es demasiado pequeño, el cambio es demasiado pequeño para ser significativo y, en consecuencia, dicha búsqueda no es eficiente. Por lo tanto, un tamaño de paso adecuado es importante para mantener la búsqueda lo más eficiente posible.

Como ejemplo, para paseos aleatorios isotrópicos simples, sabemos que la distancia promedio recorrida en el espacio de dimensión d es ${\displaystyle r}$

${\displaystyle r^{2}=2dDt,}$

donde es el coeficiente de difusión efectiva. Aquí está el tamaño del paso o la distancia recorrida en cada salto y el tiempo necesario para cada salto. La ecuación anterior implica que ^[8] ${\displaystyle D=s^{2}/2\tau }$ ${\displaystyle s}$ ${\displaystyle \tau }$

${\displaystyle s^{2}={\frac {\tau \;r^{2}}{t\;d}}.}$

Para una escala de longitud típica L de una dimensión de interés, la búsqueda local suele estar limitada a una región de . Para y t=100 a 1000, tenemos para d=1 y para d=10. Por lo tanto, podemos usar s/L=0,001 a 0,01 para la mayoría de los problemas. Aunque la derivación exacta puede requerir un análisis detallado del comportamiento de los vuelos de Lévy. ^[9] ${\displaystyle r=L/10}$ ${\displaystyle \tau =1}$ ${\displaystyle s\approx 0.01L}$ ${\displaystyle s\approx 0.001L}$

El análisis de algoritmos y convergencia será fructífero porque hay muchos problemas abiertos relacionados con las metaheurísticas ^[10]

Análisis teorico

Como esfuerzos importantes, se requieren análisis teóricos para mejorar el rendimiento de los algoritmos basados ​​en CS: ^[11]

1. Análisis teórico sobre la convergencia de algoritmos basados ​​en CS.
2. Proporcionar las condiciones suficientes y necesarias para la configuración de los parámetros de control.
3. Emplear reglas de búsqueda no homogéneas para mejorar el algoritmo CS clásico

Algoritmos de búsqueda de cuco mejorados

La convergencia del algoritmo Cuckoo Search se puede mejorar sustancialmente reemplazando genéticamente los nidos abandonados (en lugar de utilizar los reemplazos aleatorios del método original). ^[12] También se han realizado modificaciones al algoritmo mediante el cruzamiento adicional de los mejores nidos (de alta calidad) ^[13] y este enfoque se ha aplicado con éxito a una variedad de problemas de optimización industrial. ^{[14] [15]}

Referencias

1. X.-S. Yang; S. Deb (diciembre de 2009). Búsqueda de cuco a través de vuelos de Lévy . Congreso Mundial sobre Computación de Inspiración Biológica y la Naturaleza (NaBIC 2009). Publicaciones IEEE. págs. 210-214. arXiv : 1003.1594v1 .
2. Inderciencia (27 de mayo de 2010). "Primavera de diseños de cuco". Alphagalileo.org. Archivado desde el original el 29 de junio de 2010 . Consultado el 27 de mayo de 2010 .
3. Camacho Villalón, CL; Stützle, T.; Dorigo, M. (marzo de 2021). "Búsqueda de cuco ≡ (μ + λ) –Estrategia de evolución" (PDF) . Consultado el 2 de julio de 2021 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
4. RB Payne, MD Sorenson y K. Klitz, The Cuckoos, Oxford University Press, (2005).
5. RN Mantegna, Algoritmo rápido y preciso para la simulación numérica de procesos estocásticos estables de Lévy ^{[ enlace muerto ]} , Physical Review E, Vol.49, 4677-4683 (1994).
6. M. Leccardi, Comparación de tres algoritmos para la generación de ruido de Levy, Actas de la quinta conferencia de dinámica no lineal EUROMECH (2005).
7. Cámaras, JM; Malvas, CL; Atascado, BW (1976). "Un método para simular variables aleatorias estables". Revista de la Asociación Estadounidense de Estadística . 71 (354): 340–344. doi :10.1080/01621459.1976.10480344.
8. X.-S. Yang, Algoritmos metaheurísticos inspirados en la naturaleza, segunda edición, Luniver Press, (2010).
9. M. Gutowski, Vuelos de Lévy como mecanismo subyacente para algoritmos de optimización global, ArXiv Mathematical Physics e-Prints, junio de (2001).
10. XS Yang, Optimización metaheurística: análisis de algoritmos y problemas abiertos, en: Algoritmos experimentales (SEA2011), Eds (PM Pardalos y S. Rebennack), LNCS 6630, págs.21-32 (2011).
11. Cheung, Nueva Jersey; Ding, X.; Shen, H. (21 de enero de 2016). "Un algoritmo de búsqueda de cuco no homogéneo basado en un mecanismo cuántico para la optimización de parámetros reales". Transacciones IEEE sobre cibernética . 47 (2): 391–402. doi :10.1109/TCYB.2016.2517140. PMID  26812745. S2CID  7706150.
12. de Oliveira, Victoria YM; de Oliveira, Rodrigo MS; Alfonso, Carolina M. (31 de julio de 2018). "Enfoque de búsqueda de cuco mejorado con reemplazo genético de nidos abandonados aplicado a la asignación óptima de unidades de generación distribuida". Generación, Transmisión y Distribución IET . 12 (13): 3353–3362. doi : 10.1049/iet-gtd.2017.1992 . ISSN  1751-8687.
13. Walton, S.; Hassan, O.; Morgan, K.; Marrón, señor (1 de septiembre de 2011). "Búsqueda de cuco modificada: un nuevo algoritmo de optimización sin gradiente". Caos, solitones y fractales . 44 (9): 710–718. Código Bib : 2011CSF....44..710W. doi :10.1016/j.caos.2011.06.004. ISSN  0960-0779.
14. Naumann, DS; Evans, B.; Walton, S.; Hassan, O. (1 de abril de 2016). "Una implementación novedosa de optimización computacional de la forma aerodinámica mediante la búsqueda de cuco modificada". Modelado Matemático Aplicado . 40 (7–8): 4543–4559. doi : 10.1016/j.apm.2015.11.023 . ISSN  0307-904X.
15. Zhao, J.; Liu, S.; Zhou, M.; Guo, X.; Qi, L. (julio de 2018). "Algoritmo de búsqueda de cuco modificado para resolver problemas de optimización del despacho de energía económica". Revista IEEE/CAA de Automatica Sinica . 5 (4): 794–806. doi :10.1109/JAS.2018.7511138. ISSN  2329-9274. S2CID  46935795.