En la investigación de operaciones y ciencias de la computación , el algoritmo de abejas es un algoritmo de búsqueda basado en la población que fue desarrollado por Pham, Ghanbarzadeh et al. en 2005. [1] Imita el comportamiento de búsqueda de alimentos de las colonias de abejas melíferas. En su versión básica del algoritmo lleva a cabo una especie de búsqueda local combinado con la búsqueda global, y se puede utilizar tanto para la optimización combinatoria y la optimización continua . La única condición para la aplicación del algoritmo de las abejas es que se defina alguna medida de distancia entre las soluciones. La eficacia y las capacidades específicas del algoritmo de las abejas han sido probadas en varios estudios. [2][3] [4] [5]
Metáfora
Una colonia de abejas melíferas puede extenderse a grandes distancias (más de 14 km) [6] y en múltiples direcciones simultáneamente para recolectar néctar o polen de múltiples fuentes de alimento (parches florales). Una pequeña fracción de la colonia busca constantemente en el medio ambiente en busca de nuevos parches florales. Estas abejas exploradoras se mueven aleatoriamente en el área circundante a la colmena, evaluando la rentabilidad (rendimiento energético neto) de las fuentes de alimento encontradas. [6] Cuando regresan a la colmena, los exploradores depositan la comida recolectada. Aquellos individuos que encontraron una fuente de alimento altamente rentable van a un área de la colmena llamada "pista de baile" y realizan un ritual conocido como baile de meneo . [7] A través del baile de meneo, una abeja exploradora comunica la ubicación de su descubrimiento a los espectadores ociosos, que se unen a la explotación del parche de flores. Dado que la duración del baile es proporcional a la calificación de la fuente de alimento del explorador, se reclutan más recolectores para cosechar los parches de flores mejor calificados. Después de bailar, el explorador regresa a la fuente de alimento que descubrió para recolectar más comida. Siempre que se evalúen como rentables, los exploradores anunciarán fuentes de alimentos ricos cuando regresen a la colmena. Los recolectores de forrajes reclutados también pueden bailar bailando, lo que aumenta el reclutamiento de parches de flores altamente gratificantes. Gracias a este proceso autocatalítico, la colonia de abejas puede cambiar rápidamente el enfoque del esfuerzo de búsqueda de alimento en los parches de flores más rentables. [6]
Algoritmo
El algoritmo de las abejas [2] [8] imita la estrategia de búsqueda de alimento de las abejas melíferas para buscar la mejor solución a un problema de optimización. Cada solución candidata se considera una fuente de alimento (flor) y se utiliza una población (colonia) de n agentes (abejas) para buscar el espacio de la solución. Cada vez que una abeja artificial visita una flor (aterriza en una solución), evalúa su rentabilidad (aptitud).
El algoritmo de las abejas consiste en un procedimiento de inicialización y un ciclo de búsqueda principal que se repite para un número determinado T de veces, o hasta que se encuentra una solución de aptitud aceptable. Cada ciclo de búsqueda se compone de cinco procedimientos: reclutamiento, búsqueda local, reducción de vecindarios, abandono del sitio y búsqueda global.
Pseudocódigo para el algoritmo estándar de abejas [2] 1 para i = 1,…, ns Yo scout [i] = Initialise_scout () ii parche_flor [i] = Initialise_patch_flor (explorador [i]) 2 hacer hasta stop_condition = TRUE i Reclutamiento () ii para i = 1, ..., na 1 parche_de_flor [i] = Búsqueda_local (parche_de_flor [i]) 2 parche_flor [i] = Abandono del sitio (parche_flor [i]) 3 parche_de_flor [i] = encogimiento_de_el_ vecindario (parche_de_flor [i]) iii para i = nb, ..., ns 1 parche_de_flor [i] = Global_search (parche_de_flor [i])}
En la rutina de inicialización, ns abejas exploradoras se colocan aleatoriamente en el espacio de búsqueda y evalúan la idoneidad de las soluciones donde aterrizan. Para cada solución, se delimita un vecindario (llamado parche de flores).
En el procedimiento de reclutamiento, los scouts que visitaron las soluciones nb ≤ ns más aptas (mejores sitios) realizan la danza del meneo. Es decir, reclutan recolectores para buscar más en los barrios de las soluciones más prometedoras. Los exploradores que localizaron las mejores soluciones ne ≤ nb (sitios de élite) reclutan nre recolectores cada uno, mientras que los nb - ne exploradores restantes reclutan nrb ≤ nre recolectores cada uno. Por lo tanto, el número de recolectores reclutados depende de la rentabilidad de la fuente de alimento.
En el procedimiento de búsqueda local, los recolectores recolectados se dispersan aleatoriamente dentro de los parches florales que encierran las soluciones visitadas por los exploradores (explotación local). Si alguno de los recolectores en un parche de flores aterriza en una solución de mayor aptitud que la solución visitada por el explorador, ese recolector se convierte en el nuevo explorador. Si ningún recolector encuentra una solución de mayor aptitud, el tamaño del parche de flores se reduce (procedimiento de encogimiento del vecindario). Por lo general, los parches de flores se definen inicialmente en un área grande y su tamaño se reduce gradualmente mediante el procedimiento de reducción del vecindario. Como resultado, el alcance de la exploración local se enfoca progresivamente en el área inmediatamente cercana al mejor estado físico local. Si no se registra ninguna mejora en la aptitud en un parche de flores dado durante un número preestablecido de ciclos de búsqueda, se considera que se ha encontrado el máximo local de aptitud, se abandona el parche (abandono del sitio) y se genera un nuevo explorador al azar.
Al igual que en las colonias de abejas biológicas, [6] un pequeño número de exploradores sigue explorando el espacio de la solución en busca de nuevas regiones de alta aptitud (búsqueda global). El procedimiento de búsqueda global reinicializa los últimos parches de flores ns - nb con soluciones generadas aleatoriamente.
Al final de un ciclo de búsqueda, la población de exploradores se compone de nuevo de ns exploradores: nr exploradores producidos por el procedimiento de búsqueda local (algunos de los cuales pueden haber sido reiniciados por el procedimiento de abandono del sitio), y ns - nb exploradores generados por el procedimiento de búsqueda global. El tamaño total de la colonia de abejas artificiales es n = ne • nre + ( nb - ne ) • nrb + ns (sitios de élite recolectores + resto de mejores sitios recolectores + exploradores) abejas.
Variantes
Además del algoritmo básico de las abejas, [8] hay una serie de versiones mejoradas o híbridas del BA, cada una de las cuales se centra en algunas deficiencias del BA básico. Estas variantes incluyen (pero no se limitan a) BA difuso o mejorado (EBA), [9] BA agrupado (GBA), [5] BA híbrido modificado (MBA) [10] y así sucesivamente. El pseudocódigo para el BA agrupado (GBA) [5] es el siguiente.
función GBA %% Establecer los parámetros del problemamaxIteration = ..; % número de iteraciones (por ejemplo, 1000-5000) maxParameters = ..; % número de variables de entrada min = [..] ; % una matriz del tamaño maxParameters para indicar el valor mínimo de cada parámetro de entrada max = [..] ; % una matriz del tamaño maxParameters para indicar el valor máximo de cada parámetro de entrada %% Establecer los parámetros del algoritmo de abejas agrupadas (GBA)R_ngh = ..; % del radio de parche de la búsqueda de vecindario para abejas en el primer grupo (por ejemplo, 0.001 - 1) n = ..; % número de abejas exploradoras (por ejemplo, 4-30) nGroups = ..; % número de grupos, excluyendo el grupo aleatorio Configuración automática de parámetros de %% GBAk = 3 * n / (( nGrupos + 1 ) ^ 3 - 1 ); Parámetro de% GBA para establecer el número de abejas exploradoras en cada grupo grupos = ceros ( 1 , nGrupos ); % Una matriz para mantener el número de abejas exploradoras de cada grupo recruited_bees = ceros ( 1 , nGroups ); % Una matriz para mantener el número de abejas reclutadas para cada grupo a = ((( máximo - mínimo ) ./ 2 ) - R_ngh ) ./ ( nGrupos ^ 2 - 1 ); Parámetro de% GBA para establecer radios de vecindad b = R_ngh - a ; Parámetro de% GBA para establecer radios de vecindad para i = 1 : nGroups % Para cada grupo grupos ( i ) = piso ( k * i ^ 2 ); % determina el número de abejas exploradoras en cada grupo si grupos ( i ) == 0 grupos ( i ) = 1 ; % debe haber al menos una abeja exploradora por cada grupo finalrecruited_bees = ( nGroups + 1 - i ) ^ 2 ; % establece el número de abejas reclutadas para cada grupo ngh ( i ) = a * i * i + b ; % establece el parche de radio para cada grupo finalgroup_random = n - sum ( grupos ); % asigna las abejas restantes (si las hay) a una búsqueda aleatoria group_random = max ( group_random , 0 ); % asegúrese de que no sea un número negativo %% inicializar la matriz de poblaciónpoblación = ceros ( n , maxParameters + 1 ); % Una población de n abejas que incluye todas las variables de entrada y su aptitud para i = 1 : n población ( i , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % de inicialización aleatoria de variables maxParameters entre max y min población ( i , maxParameters + 1 ) = evalulate_fitness ( población ( i , :)); % de evaluación de la aptitud de cada solución y guardarla en el último índice de la matriz de población finalsorted_population = sortrows ( población ); % clasifica la población en función de su aptitud %% Iteraciones del algoritmo de abejas agrupadaspara i = 1 : bucle principal de maxIteration % GBA beeIndex = 0 ; % realiza un seguimiento de todas las abejas (es decir, parches) para g = 1 : nGroups % para cada grupo de abejas exploradoras para j = 1 : grupos ( g ) % explotan cada parche dentro de cada grupo beeIndex = beeIndex + 1 ; % de aumento del contador por cada parche para i = 1 : abejas_reclutadas ( g ) % por cada abeja reclutada del grupo solution = bee_waggle_dance ( población_ordenada ( beeIndex , 1 : maxParameters ), ngh ( g )); % busca el vecindario alrededor del parche / solución seleccionado dentro del radio de ngh ajuste = evaluar_ajuste ( solución ); % evalúa la idoneidad de la solución encontrada recientemente if fit < sorted_population ( beeIndex , maxParameters + 1 ) % Un problema de minimización: si el recuiter bee encuentra una mejor ubicación / parche / solución sorted_population ( beeIndex , 1 : maxParameters + 1 ) = [ solución ( 1 : maxParameters ), ajuste ]; % copia nueva solución y su adecuación a la matriz de población ordenada fin finfinalfinalfor i = 1 : group_random % Para las abejas aleatorias restantes beeIndex = beeIndex + 1 ; solución ( beeIndex , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % genera una nueva solución aleatoria en el índice beeIndex solución ( beeIndex , maxParameters + 1 ) = evaluate_fitness ( solución ); % evalúa su aptitud sorted_population ( beeIndex , :) = [ solución ( 1 : maxParameters ), ajuste ]; % copia la nueva solución aleatoria y su adecuación a la matriz de población ordenada finalpoblación_ordenada = sortrows ( población_ ordenada ); % clasifica la población en función de su aptitud Best_solution_sofar = sorted_population ( 1 , :);disp ( 'Mejor:' ); disp ( Best_solution_sofar ); % Muestra la mejor solución de la iteración actual end % end del bucle principal de GBA end % fin de la función principal %% Función Bee Waggle Dancefunción nueva_solución = bee_waggle_dance ( solución, ngh, maxParameters ) new_solution ( 1 : maxParameters ) = ( solución - ngh ) + ( 2 * ngh . * rand ( 1 , maxParameters )); final
Ver también
Referencias
- ^ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S y Zaidi M. El algoritmo de las abejas. Nota técnica, Centro de ingeniería de fabricación, Universidad de Cardiff, Reino Unido, 2005.
- ^ a b c Pham, DT, Castellani, M. (2009), El algoritmo de las abejas: modelado del comportamiento de forrajeo para resolver problemas de optimización continua . Proc. ImechE, Parte C, 223 (12), 2919-2938.
- ^ Pham, DT y Castellani, M. (2013), Benchmarking y comparación de algoritmos de optimización continua basados en la población inspirados en la naturaleza , Soft Computing, 1-33.
- ^ Pham, DT y Castellani, M. (2015), Un estudio comparativo del algoritmo de las abejas como herramienta para la optimización de funciones , Cogent Engineering 2 (1), 1091540.
- ^ a b c Nasrinpour, HR, Massah Bavani, A., Teshnehlab, M., (2017), algoritmo de abejas agrupadas: una versión agrupada del algoritmo de abejas , Computadoras 2017, 6 (1), 5; ( doi : 10.3390 / ordenadores6010005 )
- ^ a b c d Tereshko V., Loengarov A., (2005) Toma de decisiones colectivas en la dinámica de búsqueda de alimento de las abejas . Revista de sistemas informáticos y de información, 9 (3), 1-7.
- ^ Von Frisch, K. (1967) El lenguaje de la danza y la orientación de las abejas. Prensa de la Universidad de Harvard, Cambridge, Massachusetts.
- ^ a b Pham DT, Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimization Problems , Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems ( IPROMS 2006), Oxford: Elsevier, págs. 454-459, 2006.
- ^ Pham DT, Haj Darwish A., (2008), A. Selección difusa de sitios de búsqueda locales en el algoritmo de abejas . Actas de máquinas y sistemas de producción innovadores (IPROMS 2008)
- ^ Pham QT, Pham DT, Castellani M., Un algoritmo de abejas modificado y un método basado en estadísticas para ajustar sus parámetros. Actas de la Institución de Ingenieros Mecánicos (ImechE), Parte I: Revista de Ingeniería de Sistemas y Control, 2011 ( doi : 10.1177 / 0959651811422759 )
enlaces externos
- El sitio web del algoritmo de las abejas
- Los boffins ponen a trabajar a las abejas bailarinas - BBC News