Algoritmo de abelhas - Bees algorithm
Em ciência da computação e pesquisa operacional , o algoritmo de abelhas é um algoritmo de busca baseado em população que foi desenvolvido por Pham, Ghanbarzadeh et al. em 2005. Ele imita o comportamento de forrageamento de alimentos de colônias de abelhas. Em sua versão básica, o algoritmo realiza uma espécie de busca na vizinhança combinado com pesquisa global, e pode ser usado tanto para otimização combinatória e otimização contínua . A única condição para a aplicação do algoritmo das abelhas é que alguma medida de distância entre as soluções seja definida. A eficácia e habilidades específicas do algoritmo das abelhas foram comprovadas em vários estudos.
Metáfora
Uma colônia de abelhas melíferas pode se estender por longas distâncias (mais de 14 km) e em várias direções simultaneamente para colher néctar ou pólen de várias fontes de alimento (canteiros de flores). Uma pequena fração da colônia busca constantemente o ambiente em busca de novos canteiros de flores. Essas abelhas batedoras se movem aleatoriamente na área ao redor da colmeia, avaliando a lucratividade (rendimento líquido de energia) das fontes de alimento encontradas. Ao retornar à colmeia, os batedores depositam os alimentos colhidos. Os indivíduos que encontraram uma fonte de alimento altamente lucrativa vão para uma área da colméia chamada de “pista de dança” e realizam um ritual conhecido como dança do balanço . Por meio da dança do balanço, uma abelha escuteira comunica o local de sua descoberta aos observadores ociosos, que se juntam na exploração do canteiro de flores. Como a duração da dança é proporcional à avaliação do batedor quanto à fonte de alimento, mais forrageadoras são recrutadas para colher os canteiros de flores com melhor avaliação. Depois de dançar, o batedor retorna à fonte de alimento que descobriu para coletar mais alimentos. Contanto que sejam avaliados como lucrativos, as ricas fontes de alimento serão anunciadas pelos batedores quando retornarem à colmeia. As forrageadoras recrutadas também podem balançar a dança, aumentando o recrutamento de canteiros de flores altamente recompensadores. Graças a este processo autocatalítico, a colônia de abelhas é capaz de mudar rapidamente o foco do esforço de forrageamento para os canteiros de flores mais lucrativos.
Algoritmo
O algoritmo das abelhas simula a estratégia de forrageamento das abelhas para buscar a melhor solução para um problema de otimização. Cada solução candidata é considerada uma fonte de alimento (flor) e uma população (colônia) de n agentes (abelhas) é usada para pesquisar o espaço da solução. Cada vez que uma abelha artificial visita uma flor (pousa em uma solução), ela avalia sua lucratividade (aptidão).
O algoritmo das abelhas consiste em um procedimento de inicialização e um ciclo de busca principal que é iterado por um determinado número T de vezes, ou até que uma solução de adequação aceitável seja encontrada. Cada ciclo de pesquisa é composto por cinco procedimentos: recrutamento, pesquisa local, redução de bairro, abandono do site e pesquisa global.
Pseudocode for the standard bees algorithm
1 for i=1,…,ns
i scout[i]=Initialise_scout()
ii flower_patch[i]=Initialise_flower_patch(scout[i])
2 do until stopping_condition=TRUE
i Recruitment()
ii for 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 for i = nb,...,ns
1 flower_patch[i]=Global_search(flower_patch[i])}
Na inicialização rotina ns explorar as abelhas são colocadas aleatoriamente no espaço de busca, e avaliar a adequação das soluções onde eles pousam. Para cada solução, uma vizinhança (chamada de canteiro de flores) é delimitada.
No procedimento de recrutamento, os olheiros que visitaram as soluções mais aptas nb ≤ ns (melhores locais) executam a dança do balanço. Ou seja, eles recrutam forrageadoras para buscar mais nas vizinhanças as soluções mais promissoras. Os batedores que localizaram as melhores soluções ne ≤ nb (locais de elite) recrutam nre forrageadoras cada um, enquanto os nb - ne batedores restantes recrutam nrb ≤ nre forrageadoras cada. Assim, o número de forrageadoras recrutadas depende da lucratividade da fonte de alimento.
No procedimento de busca local, as forrageadoras recrutadas são espalhadas aleatoriamente nos canteiros de flores, incluindo as soluções visitadas pelos olheiros (exploração local). Se qualquer uma das forrageadoras em um canteiro de flores acertar uma solução de maior aptidão do que a solução visitada pelo batedor, essa forrageira se tornará o novo batedor. Se nenhuma forrageira encontrar uma solução de maior aptidão, o tamanho do canteiro de flores é reduzido (procedimento de redução de vizinhança). Normalmente, os canteiros de flores são inicialmente definidos sobre uma grande área e seu tamanho é gradualmente reduzido pelo procedimento de redução de vizinhança. Como resultado, o escopo da exploração local é progressivamente focado na área imediatamente próxima ao melhor fitness local. Se nenhuma melhoria na aptidão for registrada em um determinado canteiro de flores para um número predefinido de ciclos de pesquisa, o máximo local de aptidão é considerado encontrado, o canteiro é abandonado (abandono do local) e um novo olheiro é gerado aleatoriamente.
Como nas colônias de abelhas biológicas, um pequeno número de batedores continua explorando o espaço de solução em busca de novas regiões de alta aptidão (pesquisa global). O procedimento de pesquisa global reinicializa os últimos ns - nb manchas de flores com soluções geradas aleatoriamente.
No final de um ciclo de pesquisa, a população de escuteiros é novamente composta por ns scouts: nr scouts produzidos pelo procedimento de pesquisa local (alguns dos quais podem ter sido reinicializados pelo procedimento de abandono do site), e ns - nb scouts gerados por o procedimento de pesquisa global. O tamanho total da colônia de abelhas artificiais é n = ne • nre + ( nb - ne ) • nrb + ns (forrageadoras de elite + melhores locais para forrageadoras + batedores) abelhas.
Variantes
Além do algoritmo básico das abelhas, há várias versões aprimoradas ou híbridas do BA, cada uma delas focando em algumas deficiências do BA básico. Essas variantes incluem (mas não estão limitadas a) BA difuso ou aprimorado (EBA), BA agrupado (GBA), BA modificado híbrido (MBA) e assim por diante. O pseudocódigo para o BA agrupado (GBA) é o seguinte.
function GBA
%% Set the problem parameters
maxIteration = ..; % number of iterations (e.g. 1000-5000)
maxParameters = ..; % number of input variables
min = [..] ; % an array of the size maxParameters to indicate the minimum value of each input parameter
max = [..] ; % an array of the size maxParameters to indicate the maximum value of each input parameter
%% Set the grouped bees algorithm (GBA) parameters
R_ngh = ..; % patch radius of the neighborhood search for bees in the first group (e.g. 0.001 - 1)
n = ..; % number of scout bees (e.g. 4-30)
nGroups = ..; % number of groups, excluding the random group
%% GBA's automatic parameter settings
k = 3 * n / ((nGroups+1)^3 - 1); % GBA's parameter to set the number of scout bees in each group
groups = zeros(1,nGroups); % An array to keep the number of scout bees for each group
recruited_bees = zeros(1,nGroups); % An array to keep the number of recruited bees for each group
a = (((max - min) ./ 2) - R_ngh) ./ (nGroups^2 - 1); % GBA's parameter for setting neighborhood radiuses
b = R_ngh - a; % GBA's parameter for setting neighborhood radiuses
for i=1:nGroups % For each group
groups(i) = floor(k*i^2); % determine the number of scout bees in each group
if groups(i) == 0
groups(i) = 1; % there has to be at least one scout bee per each group
end
recruited_bees = (nGroups+1-i)^2; % set the number of recruited bees for each group
ngh(i) = a * i*i + b; % set the radius patch for each group
end
group_random = n - sum(groups); % assign the remainder bees (if any) to random search
group_random = max(group_random,0); % make sure it is not a negative number
%% initialize the population matrix
population = zeros(n,maxParameters+1); % A population of n bees including all input variables and their fitness
for i=1:n
population(i,1:maxParameters)= generate_random_solution(maxParameters,min, max); % random initialization of maxParameters variables between max and min
population(i,maxParameters+1) = evalulate_fitness(population(i,:)); % fitness evaluation of each solution and saving it at the last index of the population matrix
end
sorted_population = sortrows(population); % sort the population based on their fitnesses
%% Iterations of the grouped bees algorithm
for i=1:maxIteration % GBA's main loop
beeIndex = 0; % keep track of all bees (i.e, patches)
for g=1:nGroups % for each group of scout bees
for j = 1 : groups(g) % exploit each patch within each group
beeIndex = beeIndex + 1; % increase the counter per each patch
for i = 1 : recruited_bees(g) % for each recruited bees of the group
solution = bee_waggle_dance(sorted_population(beeIndex,1:maxParameters),ngh(g)); % search the neighborhood around selected patch/solution within the radius of ngh
fit = evaluate_fitness(solution); % evaluate the fitness of recently found solution
if fit < sorted_population(beeIndex,maxParameters+1) % A minimization problem: if a better location/patch/solution is found by the recuiter bee
sorted_population(beeIndex,1 : maxParameters+1) = [solution(1 : maxParameters),fit]; % copy new solution and its fitness to the sorted population matrix
end
end
end
end
for i= 1 : group_random % For the remaining random bees
beeIndex = beeIndex + 1;
solution(beeIndex,1:maxParameters)= generate_random_solution(maxParameters,min, max); % generate a new random solution at the index beeIndex
solution(beeIndex,maxParameters+1)= evaluate_fitness(solution); % evaluate its fitness
sorted_population(beeIndex,:) = [solution(1 : maxParameters),fit]; % copy the new random solution and its fitness to the sorted population matrix
end
sorted_population=sortrows(sorted_population); % sort the population based on their fitnesses
Best_solution_sofar=sorted_population(1,:);
disp('Best:');disp(Best_solution_sofar); % Display the best solution of current iteration
end % end of GBA's main loop
end % end of main function
%% Function Bee Waggle Dance
function new_solution=bee_waggle_dance(solution, ngh, maxParameters)
new_solution(1:maxParameters) = (solution-ngh)+(2*ngh.*rand(1, maxParameters));
end
Veja também
- Algoritmos de otimização de colônia de formigas
- Algoritmo de colônia de abelha artificial
- Computação evolucionária
- Hipótese de forrageamento do voo Lévy
- Centro de Engenharia de Manufatura
- Otimização matemática
- Metaheurística
- Otimização de enxame de particulas
- Inteligência de enxame