Algoritmo de abejas

En informática e investigación operativa , el algoritmo de las abejas es un algoritmo de búsqueda poblacional desarrollado por Pham, Ghanbarzadeh et al. en 2005. ^{[ 1 ]} Imita el comportamiento de búsqueda de alimento de las colonias de abejas melíferas. En su versión básica, el algoritmo realiza una búsqueda de vecindario combinada con una búsqueda global, y puede utilizarse tanto para optimización combinatoria como para 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 se han demostrado en varios estudios. ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]}

Una colonia de abejas melíferas puede extenderse a lo largo de grandes distancias (más de 14  km) ^{[ 7 ]} y en múltiples direcciones simultáneamente para recolectar néctar o polen de diversas fuentes de alimento (parches de flores). Una pequeña fracción de la colonia busca constantemente en el entorno nuevos parches de flores. Estas abejas exploradoras se mueven aleatoriamente en el área que rodea la colmena, evaluando la rentabilidad (rendimiento neto de energía) de las fuentes de alimento encontradas. ^{[ 7 ]} Al regresar a la colmena, las exploradoras depositan el alimento recolectado. Aquellos individuos que encuentran una fuente de alimento altamente rentable van a un área en la colmena llamada "pista de baile" y realizan un ritual conocido como la danza de la abeja . ^{[ 8 ]} Mediante la danza de la abeja, una abeja exploradora comunica la ubicación de su descubrimiento a las demás abejas, que se unen a la explotación del parche de flores. Dado que la duración de la danza es proporcional a la calificación de la fuente de alimento por parte de la exploradora, se reclutan más recolectoras para cosechar los parches de flores mejor calificados. Tras bailar, la abeja exploradora regresa a la fuente de alimento que descubrió para recolectar más. Siempre que se consideren rentables, las abejas exploradoras anunciarán las fuentes de alimento abundantes al regresar a la colmena. Las recolectoras reclutadas también pueden realizar la danza de meneo, lo que aumenta el reclutamiento para los parches de flores más rentables. Gracias a este proceso autocatalítico, la colonia de abejas puede cambiar rápidamente el enfoque del esfuerzo de recolección hacia los parches de flores más rentables. ^{[ 7 ]}

El algoritmo de las abejas ^{[ 2 ] [ 9 ]} imita la estrategia de búsqueda de alimento de las abejas melíferas para encontrar 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 explorar el espacio de soluciones. Cada vez que una abeja artificial visita una flor (aterriza sobre una solución), evalúa su rentabilidad (aptitud).

El algoritmo de las abejas consta de un procedimiento de inicialización y un ciclo de búsqueda principal que se repite un número T de veces, o hasta encontrar una solución con una aptitud aceptable. Cada ciclo de búsqueda se compone de cinco procedimientos: reclutamiento, búsqueda local, reducción del vecindario, abandono del sitio y búsqueda global.

Pseudocódigo para el algoritmo estándar de las abejas [ 2 ] 1 para i = 1, ..., ns Yo exploro[i] = Inicializar_scout() ii flower_patch[i] = Initialise_flower_patch(scout[i]) 2. Hacer hasta que la condición de parada sea VERDADERA Reclutamiento() ii para i = 1, ..., na 1 flower_patch[i] = Local_search(flower_patch[i]) 2 flower_patch[i] = Site_abandonment(flower_patch[i]) 3 flower_patch[i] = Neighbourhood_shrinking(flower_patch[i]) iii para i = nb, ..., ns 1 flower_patch[i] = Global_search(flower_patch[i])}

En la rutina de inicialización , las abejas exploradoras se colocan aleatoriamente en el espacio de búsqueda y evalúan la idoneidad de las soluciones en las que aterrizan. Para cada solución, se delimita un vecindario (llamado parche de flores).

En el proceso de reclutamiento, los exploradores que visitaron las nb ≤ ns soluciones más aptas (los mejores sitios) realizan la danza de la cola. Es decir, reclutan recolectores para explorar los alrededores de las soluciones más prometedoras. Los exploradores que localizaron las mejores ne ≤ nb soluciones (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 reclutados se dispersan aleatoriamente dentro de los parches de flores que rodean las soluciones visitadas por los exploradores (explotación local). Si alguno de los recolectores en un parche de flores encuentra una solución con 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 con mayor aptitud, el tamaño del parche de flores se reduce (procedimiento de reducción de vecindario). Por lo general, los parches de flores se definen inicialmente sobre un área grande, y su tamaño se reduce gradualmente mediante el procedimiento de reducción de vecindario. Como resultado, el alcance de la exploración local se centra progresivamente en el área inmediatamente cercana al mejor desempeño local de aptitud. 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 encontró el máximo local de aptitud, el parche se abandona (abandono del sitio) y se genera un nuevo explorador aleatoriamente.

Como en las colonias de abejas biológicas, ^{[ 7 ]} un pequeño número de exploradoras continúa explorando el espacio de soluciones en busca de nuevas regiones de alta aptitud (búsqueda global). El procedimiento de búsqueda global reinicializa los últimos ns - nb parches de flores con soluciones generadas aleatoriamente.

Al final de un ciclo de búsqueda, la población de exploradores vuelve a estar compuesta por ns exploradores: nr exploradores producidos por el procedimiento de búsqueda local (algunos de los cuales pueden haber sido reiniciales 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 (recolectoras de sitios de élite + recolectoras de los mejores sitios restantes + exploradores) abejas.

Además del algoritmo básico de abejas, ^{[ 9 ]} existen varias 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), ^{[ 10 ]} BA agrupado (GBA), ^{[ 5 ]} BA híbrido modificado (MBA) ^{[ 11 ]} y así sucesivamente. El código pseudo-MATLAB para el BA agrupado (GBA) ^{[ 5 ]} es el siguiente.

función GBA %% Establecer los parámetros del problema maxIteration = ..; % número de iteraciones (por ejemplo, 1000-5000) maxParameters = ..; % número de variables de entrada min = [..] ; % un array del tamaño de maxParameters para indicar el valor mínimo de cada parámetro de entrada max = [..] ; % un array del tamaño de 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 = ..; % radio del parche de búsqueda del 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 GBA k = 3 * n / (( nGroups + 1 ) ^ 3 - 1 ); % Parámetro de GBA para establecer el número de abejas exploradoras en cada grupo groups = zeros ( 1 , nGroups ); % Un array para mantener el número de abejas exploradoras para cada grupo recruited_bees = zeros ( 1 , nGroups ); % Un array para mantener el número de abejas reclutadas para cada grupo a = ((( max - min ) ./ 2 ) - R_ngh ) ./ ( nGroups ^ 2 - 1 ); % Parámetro de GBA para establecer radios de vecindario b = R_ngh - a ; % Parámetro de GBA para establecer radios de vecindario for i = 1 : nGroups % Para cada grupo groups ( i ) = floor ( k * i ^ 2 ); % Determinar el número de abejas exploradoras en cada grupo if groups ( i ) == 0 groups ( i ) = 1 ; % Debe haber al menos una abeja exploradora por cada grupo end recruited_bees = ( nGroups + 1 - i ) ^ 2 ; % Establecer el número de abejas reclutadas para cada grupo ngh ( i ) = a * i * i + b ; % Establecer el radio del parche para cada grupo end group_random = n - sum ( groups ); % Asignar las abejas restantes (si las hay) a la búsqueda aleatoria group_random = max ( group_random , 0 ); % Asegurarse de que no sea un número negativo%% Inicializar la matriz de población population = zeros ( n , maxParameters + 1 ); % Una población de n abejas que incluye todas las variables de entrada y su aptitud para i = 1 : n population ( i , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % Inicialización aleatoria de las variables maxParameters entre max y min population ( i , maxParameters + 1 ) = evalulate_fitness ( population ( i ,:)); % Evaluación de la aptitud de cada solución y su almacenamiento en el último índice de la matriz de población endpoblación_ordenada = filas_ordenadas ( población ); % ordena la población en función de su aptitud%% Iteraciones del algoritmo de abejas agrupadas para i = 1 : maxIteration % Bucle principal de GBA beeIndex = 0 ; % mantener un registro de todas las abejas (es decir, parches) para g = 1 : nGroups % para cada grupo de abejas exploradoras para j = 1 : groups ( g ) % explotar cada parche dentro de cada grupo beeIndex = beeIndex + 1 ; % aumentar el contador por cada parche para i = 1 : recruited_bees ( g ) % para cada abeja reclutada del grupo solution = bee_waggle_dance ( sorted_population ( beeIndex , 1 : maxParameters ), ngh ( g )); % buscar el vecindario alrededor del parche/solución seleccionado dentro del radio de ngh fit = evaluate_fitness ( solution ); % evaluar la aptitud de la solución encontrada recientemente si fit < sorted_population ( beeIndex , maxParameters + 1 ) % Un problema de minimización: si la abeja reclutadora encuentra una mejor ubicación/parche/solución sorted_population ( beeIndex , 1 : maxParameters + 1 ) = [ solution ( 1 : maxParameters ), fit ]; % copiar la nueva solución y su aptitud a la matriz de población ordenada end end end endfor i = 1 : group_random % Para las abejas aleatorias restantes beeIndex = beeIndex + 1 ; solution ( beeIndex , 1 : maxParameters )= generate_random_solution ( maxParameters , min , max ); % genera una nueva solución aleatoria en el índice beeIndex solution ( beeIndex , maxParameters + 1 )= evaluate_fitness ( solution ); % evalúa su aptitud sorted_population ( beeIndex ,:) = [ solution ( 1 : maxParameters ), fit ]; % copia la nueva solución aleatoria y su aptitud a la matriz de población ordenada endpoblación_ordenada = sortrows ( población_ordenada ); % ordena la población en función de sus aptitudes Mejor_solución_hasta_el_momento = población_ordenada ( 1 ,:);disp ( 'Mejor:' ); disp ( Mejor_solución_hasta_el_momento ); % Muestra la mejor solución de la iteración actual end % fin del bucle principal de GBA end % fin de la función principal%% Función Bee Waggle Dance function new_solution = bee_waggle_dance ( solution, ngh, maxParameters ) new_solution ( 1 : maxParameters ) = ( solution - ngh ) + ( 2 * ngh .* rand ( 1 , maxParameters )); end

• Algoritmos de optimización por colonia de hormigas
• Algoritmo de colonia de abejas artificiales
• Computación evolutiva
• hipótesis de búsqueda de alimento en vuelo de Lévy
• Centro de Ingeniería de Fabricación
• Optimización matemática
• Metaheurística
• Optimización por enjambre de partículas
• Inteligencia de enjambre

• El sitio web del algoritmo de las abejas
• Científicos ponen a trabajar a abejas bailarinas – BBC News
• El taller de algoritmos de las abejas