En la investigación de operaciones , la búsqueda del cuco es un algoritmo de optimización desarrollado por Xin-she Yang y Suash Deb en 2009. [1] [2] Se inspiró en el parasitismo obligado de la cría de algunas especies de cucos al poner sus huevos en los nidos de otros huéspedes. aves (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 de su propiedad, los arrojará a la basura o simplemente abandonará su nido y construirá un nuevo nido en otro lugar. Algunas especies de cucos como el Tapera parásito de la cría del Nuevo Mundohan evolucionado de tal manera que las hembras de cucos parásitos suelen estar muy especializadas en el mimetismo de colores y patrones de los huevos de unas pocas especies hospedadoras elegidas. [3] La búsqueda del cuco idealizó tal comportamiento reproductivo y, por lo tanto, se puede aplicar para varios problemas de optimización.
Metáfora
La búsqueda del 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 las nuevas y potencialmente mejores soluciones (cucos) para reemplazar 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 varios huevos que representan un conjunto de soluciones.
CS se basa en tres reglas idealizadas:
- Cada cuco pone un huevo a la vez y arroja su huevo en un nido elegido al azar;
- Los mejores nidos con huevos de alta calidad se transferirán a la próxima generación;
- El número de nidos de hospedadores disponibles es fijo, y el ave hospedante descubre el huevo puesto por un cuco con una probabilidad . En este caso, el ave huésped puede tirar el huevo / abandonar el nido y construir un nido completamente nuevo.
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 objetiva: Genere una población inicial de nidos de acogida; Mientras (t)> Obtenga un cuco al azar (digamos, i) y reemplace su solución realizando vuelos de Lévy; Evaluar su calidad / aptitud [Para maximizar, ]; Elija un nido entre n (digamos, j) al azar; Si ( ), Reemplace j por la nueva solución; terminara si Una fracción ( ) de los peores nidos se abandonan y se construyen otros nuevos; Mantenga las mejores soluciones / nidos; Clasifique las soluciones / nidos y encuentre la mejor actual; Pase 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 agentes o poblaciones , como la optimización del enjambre de partículas y la búsqueda de armonía , existe esencialmente un único parámetro. en CS (aparte del tamaño de la población ). Por tanto, es muy fácil de implementar.
Paseos aleatorios y el tamaño del paso.
Un tema importante son las aplicaciones de los vuelos y paseos aleatorios de Lévy en la ecuación genérica para generar nuevas soluciones.
dónde 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, las caminatas aleatorias también pueden estar relacionadas con la similitud entre el huevo de un cuco y el huevo del anfitrión, lo que puede ser complicado en la implementación. Aquí el tamaño del pasodetermina qué tan lejos puede llegar un caminante aleatorio durante un número fijo de iteraciones. La generación del tamaño de paso de Lévy es a menudo complicada, y Leccardi [5] realizó una comparación de tres algoritmos (incluido el de Mantegna [4] ) , quien encontró que una implementación del enfoque de Chambers et al. [6] era la más computacionalmente eficiente debido al bajo número de números aleatorios requeridos.
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 movimiento. 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 caminatas aleatorias isotrópicas simples, sabemos que la distancia promedio viajado en el espacio de la dimensión d es
dónde es el coeficiente de difusión efectivo. Aquí es el tamaño del paso o la distancia recorrida en cada salto, y es el tiempo necesario para cada salto. La ecuación anterior implica que [7]
Para una escala de longitud típica L de una dimensión de interés, la búsqueda local está típicamente limitada en 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. [8]
El análisis de algoritmos y convergencia será fructífero, porque hay muchos problemas abiertos relacionados con las metaheurísticas [9].
Análisis teorico
Como esfuerzos importantes, se requieren análisis teóricos para mejorar el rendimiento de los algoritmos basados en CS: [10]
- Análisis teórico sobre la convergencia de algoritmos basados en CS
- Proporcionar las condiciones suficientes y necesarias para la configuración de los parámetros de control.
- Emplear reglas de búsqueda no homogéneas para mejorar el algoritmo CS clásico
Algoritmos de búsqueda de cuco mejorados
El algoritmo de convergencia de búsqueda de cuco se puede mejorar sustancialmente reemplazando genéticamente los nidos abandonados (en lugar de usar los reemplazos aleatorios del método original). [11] También se han realizado modificaciones al algoritmo mediante el cruzamiento adicional de los mejores nidos (de alta calidad) [12] y este enfoque se ha aplicado con éxito a una serie de problemas de optimización industrial. [13] [14]
Referencias
- ^ X.-S. Yang; S. Deb (diciembre de 2009). Búsqueda de cuco a través de vuelos Lévy . Congreso Mundial sobre la Naturaleza y la Computación de Inspiración Biológica (NaBIC 2009). Publicaciones IEEE. págs. 210-214. arXiv : 1003.1594v1 .
- ^ Inderscience (27 de mayo de 2010). "Diseños de cuco primaverales" . Alphagalileo.org . Consultado el 27 de mayo de 2010 .
- ^ RB Payne, MD Sorenson y K. Klitz, The Cuckoos, Oxford University Press, (2005).
- ^ RN Mantegna, algoritmo rápido y preciso para la simulación numérica de procesos estocásticos estables de Lévy , Physical Review E, Vol.49, 4677-4683 (1994).
- ^ M. Leccardi, Comparación de tres algoritmos para la generación de ruido Levy , Actas de la quinta conferencia de dinámica no lineal EUROMECH (2005).
- ^ Chambers, JM; Mallows, 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 .
- ^ X.-S. Yang, Algoritmos metaheurísticos inspirados en la naturaleza , 2da edición, Luniver Press, (2010).
- ^ M. Gutowski, vuelos de Lévy como mecanismo subyacente para los algoritmos de optimización global , ArXiv Mathematical Physics e-Prints, junio (2001).
- ^ XS Yang, Optimización metaheurística: análisis de algoritmos y problemas abiertos , en: Experimental Algorithms (SEA2011), Eds (PM Pardalos y S. Rebennack), LNCS 6630, pp.21-32 (2011).
- ^ Cheung, Nueva Jersey; Ding, X .; Shen, H. (21 de enero de 2016). "Un algoritmo de búsqueda de cuco no homogéneo basado en el 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 .
- ^ de Oliveira, Victoria YM; de Oliveira, Rodrigo MS; Affonso, 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 distribuidas" . Generación, Transmisión y Distribución IET . 12 (13): 3353–3362. doi : 10.1049 / iet-gtd.2017.1992 . ISSN 1751-8687 .
- ^ Walton, S .; Hassan, O .; Morgan, K .; Brown, MR (1 de septiembre de 2011). "Búsqueda de cuco modificada: un nuevo algoritmo de optimización libre de gradientes" . Caos, solitones y fractales . 44 (9): 710–718. doi : 10.1016 / j.chaos.2011.06.004 . ISSN 0960-0779 .
- ^ Naumann, DS; Evans, B .; Walton, S .; Hassan, O. (1 de abril de 2016). "Una implementación novedosa de optimización de forma aerodinámica computacional usando 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 .
- ^ 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 de 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 .