In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
and
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
, the bees algorithm is a population-based
search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...
which was developed by Pham, Ghanbarzadeh et al. in 2005.
[Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.] It mimics the food foraging behaviour of honey bee colonies. In its basic version the algorithm performs a kind of neighbourhood search combined with global search, and can be used for both
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
and
continuous optimization
Continuous optimization is a branch of optimization in applied mathematics.
As opposed to discrete optimization, the variables used in the objective function are required to be continuous variables—that is, to be chosen from a set of rea ...
. The only condition for the application of the bees algorithm is that some measure of distance between the solutions is defined. The effectiveness and specific abilities of the bees algorithm have been proven in a number of studies.
[Pham, D.T., Castellani, M. (2009)]
The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems
Proc. ImechE, Part C, 223(12), 2919-2938.[Nasrinpour, H. R., Massah Bavani, A., Teshnehlab, M., (2017)]
Grouped Bees Algorithm: A Grouped Version of the Bees Algorithm
Computers 2017, 6(1), 5; ()
Metaphor
A colony of
honey bees
A honey bee (also spelled honeybee) is a eusocial flying insect within the genus ''Apis'' of the bee clade, all native to Afro-Eurasia. After bees spread naturally throughout Africa and Eurasia, humans became responsible for the current cosm ...
can extend itself over long distances (over 14 km)
[Tereshko V., Loengarov A., (2005]
Collective Decision-Making in Honey Bee Foraging Dynamics
Journal of Computing and Information Systems, 9(3), 1-7. and in multiple directions simultaneously to harvest nectar or pollen from multiple food sources (flower patches).
A small fraction of the colony constantly searches the environment looking for new flower patches. These scout bees move randomly in the area surrounding the hive, evaluating the profitability (net energy yield) of the food sources encountered.
When they return to the hive, the scouts deposit the food harvested. Those individuals that found a highly profitable food source go to an area in the hive called the “dance floor”, and perform a ritual known as the
waggle dance
Waggle dance is a term used in beekeeping and ethology for a particular figure-eight dance of the honey bee. By performing this dance, successful foragers can share information about the direction and distance to patches of flowers yielding nect ...
.
[Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, Massachusetts.]
Through the waggle dance a scout bee communicates the location of its discovery to idle onlookers, which join in the exploitation of the flower patch. Since the length of the dance is proportional to the scout’s rating of the food source, more foragers get recruited to harvest the best rated flower patches. After dancing, the scout returns to the food source it discovered to collect more food.
As long as they are evaluated as profitable, rich food sources will be advertised by the scouts when they return to the hive. Recruited foragers may waggle dance as well, increasing the recruitment for highly rewarding flower patches. Thanks to this autocatalytic process, the bee colony is able to quickly switch the focus of the foraging effort on the most profitable flower patches.
Algorithm
The bees algorithm
[Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M.]
The Bees Algorithm, A Novel Tool for Complex Optimisation Problems
Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454-459, 2006. mimics the foraging strategy of honey bees to look for the best solution to an optimisation problem. Each candidate solution is thought of as a food source (flower), and a population (colony) of ''n'' agents (bees) is used to search the solution space. Each time an artificial bee visits a flower (lands on a solution), it evaluates its profitability (fitness).
The bees algorithm consists of an initialisation procedure and a main search cycle which is iterated for a given number ''T'' of times, or until a solution of acceptable fitness is found. Each search cycle is composed of five procedures: recruitment, local search, neighbourhood shrinking, site abandonment, and global search.
Pseudocode for the standard bees algorithm
1 for i=1,…,ns
i scout
Initialise_scout()
ii flower_patch
Initialise_flower_patch(scout
2 do until stopping_condition=TRUE
i Recruitment()
ii for i =1,...,na
1 flower_patch
Local_search(flower_patch
2 flower_patch
Site_abandonment(flower_patch
3 flower_patch
Neighbourhood_shrinking(flower_patch
iii for i = nb,...,ns
1 flower_patch
Global_search(flower_patch
}
In the initialisation routine ''ns'' scout bees are randomly placed in the search space, and evaluate the fitness of the solutions where they land. For each solution, a neighbourhood (called flower patch) is delimited.
In the recruitment procedure, the scouts that visited the ''nb''≤''ns'' fittest solutions (best sites) perform the waggle dance. That is, they recruit foragers to search further the neighbourhoods of the most promising solutions. The scouts that located the very best ''ne''≤''nb'' solutions (elite sites) recruit ''nre'' foragers each, whilst the remaining ''nb''-''ne'' scouts recruit ''nrb''≤''nre'' foragers each. Thus, the number of foragers recruited depends on the profitability of the food source.
In the local search procedure, the recruited foragers are randomly scattered within the flower patches enclosing the solutions visited by the scouts (local exploitation). If any of the foragers in a flower patch lands on a solution of higher fitness than the solution visited by the scout, that forager becomes the new scout. If no forager finds a solution of higher fitness, the size of the flower patch is shrunk (neighbourhood shrinking procedure). Usually, flower patches are initially defined over a large area, and their size is gradually shrunk by the neighbourhood shrinking procedure. As a result, the scope of the local exploration is progressively focused on the area immediately close to the local fitness best. If no improvement in fitness is recorded in a given flower patch for a pre-set number of search cycles, the local maximum of fitness is considered found, the patch is abandoned (site abandonment), and a new scout is randomly generated.
As in biological bee colonies,
a small number of scouts keeps exploring the solution space looking for new regions of high fitness (global search). The global search procedure re-initialises the last ''ns''-''nb'' flower patches with randomly generated solutions.
At the end of one search cycle, the scout population is again composed of ''ns'' scouts: ''nr'' scouts produced by the local search procedure (some of which may have been re-initialised by the site abandonment procedure), and ''ns''-''nb'' scouts generated by the global search procedure. The total artificial bee colony size is ''n''=''ne''•''nre''+(''nb''-''ne'')•''nrb''+''ns'' (elite sites foragers + remaining best sites foragers + scouts) bees.
Variants
In addition to the basic bees algorithm,
there are a number of improved or hybrid versions of the BA, each of which focuses on some shortcomings of the basic BA. These variants include (but are not limited to) fuzzy or enhanced BA (EBA),
[Pham D. T., Haj Darwish A., (2008), A]
Fuzzy Selection of Local Search Sites in the Bees Algorithm
Proceedings of Innovative Production Machines and Systems (IPROMS 2008) grouped BA (GBA),
hybrid modified BA (MBA)
[Pham Q. T., Pham D. T., Castellani M., A modified Bees Algorithm and a statistics-based method for tuning its parameters. Proceedings of the Institution of Mechanical Engineers (ImechE), Part I: Journal of Systems and Control Eng., 2011 ()] and so on.
The pseudo-code for the grouped BA (GBA)
is as follows.
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) = olution(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,:) = olution(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
See also
*
Ant colony optimization algorithms
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for mult ...
*
Artificial bee colony algorithm
In computer science and operations research, the artificial bee colony algorithm (ABC) is an optimization algorithm based on the intelligent foraging behaviour of honey bee swarm, proposed by Derviş Karaboğa (Erciyes University) in 2005.
Alg ...
*
Evolutionary computation
*
Lévy flight foraging hypothesis
*
Manufacturing Engineering Centre
*
Mathematical optimization
*
Metaheuristic
In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
*
Particle swarm optimization
*
Swarm intelligence
References
External links
The bees algorithm website Boffins put dancing bees to work – BBC NewsThe bees algorithm workshop
{{DEFAULTSORT:Bees algorithm
Nature-inspired metaheuristics