En informática e investigación de operaciones , el algoritmo de las 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, el algoritmo realiza un tipo de búsqueda de vecindad combinada con una búsqueda global, y se puede utilizar tanto para la optimización combinatoria como para 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 se han demostrado en varios estudios. [2] [3] [4] [5] [6]
Una colonia de abejas melíferas puede extenderse a grandes distancias (más de 14 km) [7] y en múltiples direcciones simultáneamente para cosechar néctar o polen de múltiples fuentes de alimento (parches de flores). Una pequeña fracción de la colonia busca constantemente en el entorno nuevas parcelas de flores. Estas abejas exploradoras se mueven aleatoriamente en el área que rodea la colmena, evaluando la rentabilidad (rendimiento energético neto) de las fuentes de alimento encontradas. [7] Cuando regresan a la colmena, las exploradoras depositan el alimento cosechado. Aquellos individuos que encontraron una fuente de alimento altamente rentable van a un área en la colmena llamada la "pista de baile", y realizan un ritual conocido como la danza del meneo . [8] A través de la danza del 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 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. Después de bailar, la exploradora regresa a la fuente de alimento que descubrió para recolectar más alimento. Mientras se las evalúe como fuentes de alimento rentables, las exploradoras anunciarán que son ricas en alimento cuando regresen a la colmena. Las abejas recolectoras reclutadas también pueden bailar con el cuerpo en movimiento, lo que aumenta el reclutamiento para las parcelas de flores altamente gratificantes. Gracias a este proceso autocatalítico, la colonia de abejas puede cambiar rápidamente el foco del esfuerzo de recolección de alimentos hacia las parcelas 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 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 en el espacio de soluciones. Cada vez que una abeja artificial visita una flor (aterriza en una solución), evalúa su rentabilidad (idoneidad).
El algoritmo de las abejas consta de un procedimiento de inicialización y un ciclo de búsqueda principal que se repite una cantidad determinada 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 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 i scout[i]=Inicializar_scout() ii flower_patch[i]=Inicializar_flower_patch(scout[i]) 2 hacer hasta que la condición de detención sea VERDADERA i Reclutamiento() ii para i = 1,...,na 1 parche_de_flor[i]=Búsqueda_local(parche_de_flor[i]) 2 flower_patch[i]=Abandono del sitio(flower_patch[i]) 3 flower_patch[i]=Vecindario encogido(flower_patch[i]) iii para i = nb,...,ns 1 flower_patch[i]=Búsqueda global(flower_patch[i])}
En la rutina de inicialización, las abejas exploradoras ns 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 soluciones más aptas nb ≤ ns (mejores sitios) realizan la danza del meneo. Es decir, reclutan cazadores-recolectores para que sigan buscando en los alrededores de las soluciones más prometedoras. Los exploradores que localizaron las mejores soluciones ne ≤ nb (sitios de élite) reclutan cazadores-recolectores nre cada uno, mientras que los exploradores nb - ne restantes reclutan cazadores -recolectores nrb ≤ nre cada uno. Por lo tanto, el número de cazadores-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 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 reducción de vecindad). 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 vecindad. Como resultado, el alcance de la exploración local se centra progresivamente en el área inmediatamente cercana al mejor ajuste local. Si no se registra ninguna mejora en el ajuste 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, se abandona el parche (abandono del sitio) y se genera un nuevo explorador aleatoriamente.
Al igual que en las colonias biológicas de abejas, [7] un pequeño número de exploradores 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 abejas exploradoras se compone nuevamente de ns abejas exploradoras: nr abejas exploradoras producidas por el procedimiento de búsqueda local (algunas de las cuales pueden haber sido reiniciadas por el procedimiento de abandono del sitio) y ns - nb abejas exploradoras generadas 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 (abejas recolectoras de sitios de élite + abejas recolectoras de los mejores sitios restantes + abejas exploradoras).
Además del algoritmo básico de las abejas, [9] existen varias versiones mejoradas o híbridas del algoritmo de abejas, cada una de las cuales se centra en algunas deficiencias del algoritmo de abejas básico. Estas variantes incluyen (pero no se limitan a) algoritmo de abejas difuso o mejorado (EBA), [10] algoritmo de abejas agrupado (GBA), [5] algoritmo de abejas híbrido modificado (MBA) [11] , etc. El pseudocódigo para el algoritmo de abejas agrupado (GBA) [5] es el siguiente.
función GBA %% Establece los parámetros del problema maxIteration = ..; % 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 %% Establezca los parámetros del algoritmo de abejas agrupadas (GBA) R_ngh = ..; % del radio del parche de búsqueda de vecindad para las abejas en el primer grupo (por ejemplo, 0,001 - 1) n = ..; % del número de abejas exploradoras (por ejemplo, 4-30) nGroups = ..; % del 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 ); % Una matriz para mantener el número de abejas exploradoras para cada grupo recruited_bees = zeros ( 1 , nGroups ); % Una matriz 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 vecindad b = R_ngh - a ; % Parámetro de GBA para establecer radios de vecindad para i = 1 : nGroups % Para cada grupo groups ( i ) = floor ( k * i ^ 2 ); % determina el número de abejas exploradoras en cada grupo si grupos ( i ) == 0 grupos ( i ) = 1 ; % tiene que haber al menos una abeja exploradora por cada grupo end recruited_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 end group_random = n - sum ( groups ); % asigna las abejas restantes (si las hay) a la búsqueda aleatoria group_random = max ( group_random , 0 ); % se asegura de que no sea un número negativo %% inicializa la matriz de población població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 ); % inicialización aleatoria de las variables maxParameters entre max y min población ( i , maxParameters + 1 ) = evalulate_fitness ( población ( i ,:)); % evaluación de la aptitud de cada solución y guardado en el último índice de la matriz de población fin sorted_population = sortrows ( población ); % ordena la población según su aptitud %% Iteraciones del algoritmo de abejas agrupadas para i = 1 : maxIteration % Bucle principal de 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 : groups ( g ) % explota cada parche dentro de cada grupo beeIndex = beeIndex + 1 ; % aumenta 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 )); % busca el vecindario alrededor del parche/solución seleccionado dentro del radio de ngh fit = evaluating_fitness ( solution ); % evalúa la aptitud de la solución encontrada recientemente si fit < sorted_population ( beeIndex , maxParameters + 1 ) % Un problema de minimización: si el reclutador encuentra una mejor ubicación/parche/solución bee sorted_population ( beeIndex , 1 : maxParameters + 1 ) = [ solution ( 1 : maxParameters ), fit ]; % copia la nueva solución y su aptitud a la matriz de población ordenada end end end end para 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 )= evaluation_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 end sorted_population = sortrows ( sorted_population ); % ordena la población según su aptitud Best_solution_sofar = sorted_population ( 1 ,:); disp ( 'Best:' ); disp ( Best_solution_sofar ); % Muestra la mejor solución de la iteración actual fin % fin del bucle principal de GBA fin % fin de la función principal %% Función Bee Waggle Dance función nueva_solución = bee_waggle_dance ( solución, ngh, parámetros_máximos ) nueva_solución ( 1 : parámetros_máximos ) = ( solución - ngh ) + ( 2 * ngh .* rand ( 1 , parámetros_máximos )); fin