Bees algorithm

Last updated

In computer science and operations research, the bees algorithm is a population-based search algorithm which was developed by Pham, Ghanbarzadeh et al. in 2005. [1] 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 and continuous optimization. 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. [2] [3] [4] [5] [6]

Contents

Metaphor

A colony of honey bees can extend itself over long distances (over 14 km) [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. [7] 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. [8] 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. [7]

Algorithm

The bees algorithm [2] [9] 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 [2]     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])}

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, [7] 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, [9] 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), [10] grouped BA (GBA), [5] hybrid modified BA (MBA) [11] and so on. The pseudo-code for the grouped BA (GBA) [5] is as follows.

functionGBA%% Set the problem parametersmaxIteration=..;% number of iterations (e.g. 1000-5000)maxParameters=..;% number of input variablesmin=[..];% 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) parametersR_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 settingsk=3*n/((nGroups+1)^3-1);% GBA's parameter to set the number of scout bees in each groupgroups=zeros(1,nGroups);% An array to keep the number of scout bees for each grouprecruited_bees=zeros(1,nGroups);% An array to keep the number of recruited bees for each groupa=(((max-min)./2)-R_ngh)./(nGroups^2-1);% GBA's parameter for setting neighborhood radiusesb=R_ngh-a;% GBA's parameter for setting neighborhood radiusesfori=1:nGroups% For each groupgroups(i)=floor(k*i^2);% determine the number of scout bees in each groupifgroups(i)==0groups(i)=1;% there has to be at least one scout bee per each groupendrecruited_bees=(nGroups+1-i)^2;% set the number of recruited bees for each groupngh(i)=a*i*i+b;% set the radius patch for each groupendgroup_random=n-sum(groups);% assign the remainder bees (if any) to random searchgroup_random=max(group_random,0);% make sure it is not a negative number%% initialize the population matrixpopulation=zeros(n,maxParameters+1);% A population of n bees including all input variables and their fitnessfori=1:npopulation(i,1:maxParameters)=generate_random_solution(maxParameters,min,max);% random initialization of maxParameters variables between max and minpopulation(i,maxParameters+1)=evalulate_fitness(population(i,:));% fitness evaluation of each solution and saving it at the last index of the population matrixendsorted_population=sortrows(population);% sort the population based on their fitnesses%% Iterations of the grouped bees algorithmfori=1:maxIteration% GBA's main loopbeeIndex=0;% keep track of all bees (i.e, patches)forg=1:nGroups% for each group of scout bees forj=1:groups(g)% exploit each patch within each groupbeeIndex=beeIndex+1;% increase the counter per each patchfori=1:recruited_bees(g)% for each recruited bees of the groupsolution=bee_waggle_dance(sorted_population(beeIndex,1:maxParameters),ngh(g));% search the neighborhood around selected patch/solution within the radius of nghfit=evaluate_fitness(solution);% evaluate the fitness of recently found solutioniffit<sorted_population(beeIndex,maxParameters+1)% A minimization problem: if a better location/patch/solution is found by the recuiter beesorted_population(beeIndex,1:maxParameters+1)=[solution(1:maxParameters),fit];% copy new solution and its fitness to the sorted population matrixendendendendfori=1:group_random% For the remaining random beesbeeIndex=beeIndex+1;solution(beeIndex,1:maxParameters)=generate_random_solution(maxParameters,min,max);% generate a new random solution at the index beeIndexsolution(beeIndex,maxParameters+1)=evaluate_fitness(solution);% evaluate its fitnesssorted_population(beeIndex,:)=[solution(1:maxParameters),fit];% copy the new random solution and its fitness to the sorted population matrixendsorted_population=sortrows(sorted_population);% sort the population based on their fitnessesBest_solution_sofar=sorted_population(1,:);disp('Best:');disp(Best_solution_sofar);% Display the best solution of current iterationend% end of GBA's main loop end% end of main function%% Function Bee Waggle Dancefunctionnew_solution=bee_waggle_dance(solution, ngh, maxParameters)new_solution(1:maxParameters)=(solution-ngh)+(2*ngh.*rand(1,maxParameters));end

See also

Related Research Articles

<span class="mw-page-title-main">Genetic algorithm</span> Competitive algorithm for searching a problem space

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, causal inference, etc.

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Evolutionary computation</span> Trial and error problem solvers with a metaheuristic or stochastic optimization character

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

Fitness proportionate selection, also known as roulette wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination.

<span class="mw-page-title-main">Bee learning and communication</span> Cognitive and sensory processes in bees

Bee learning and communication includes cognitive and sensory processes in all kinds of bees, that is the insects in the seven families making up the clade Anthophila. Some species have been studied more extensively than others, in particular Apis mellifera, or European honey bee. Color learning has also been studied in bumblebees.

<span class="mw-page-title-main">Foraging</span> Searching for wild food resources

Foraging is searching for wild food resources. It affects an animal's fitness because it plays an important role in an animal's ability to survive and reproduce. Foraging theory is a branch of behavioral ecology that studies the foraging behavior of animals in response to the environment where the animal lives.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

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 multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

Selection is the stage of a genetic algorithm or more general evolutionary algorithm in which individual genomes are chosen from a population for later breeding. Selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population.

<span class="mw-page-title-main">Mating pool</span>

A mating pool is a concept used in evolutionary computation, which refers to a family of algorithms used to solve optimization and search problems.

<span class="mw-page-title-main">Waggle dance</span> Honey bees particular figure-eight 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 nectar and pollen, to water sources, or to new nest-site locations with other members of the colony.

<span class="mw-page-title-main">Differential evolution</span> Method of mathematical optimization

In evolutionary computation, differential evolution (DE) is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as they make few or no assumptions about the optimized problem and can search very large spaces of candidate solutions. However, metaheuristics such as DE do not guarantee an optimal solution is ever found.

<span class="mw-page-title-main">Palynivore</span> Group of herbivorous animals

In zoology, a palynivore /pəˈlɪnəvɔːɹ/, meaning "pollen eater" is an herbivorous animal which selectively eats the nutrient-rich pollen produced by angiosperms and gymnosperms. Most true palynivores are insects or mites. The category in its strictest application includes most bees, and a few kinds of wasps, as pollen is often the only solid food consumed by all life stages in these insects. However, the category can be extended to include more diverse species. For example, palynivorous mites and thrips typically feed on the liquid content of the pollen grains without actually consuming the exine, or the solid portion of the grain. Additionally, the list is expanded greatly if one takes into consideration species where either the larval or adult stage feeds on pollen, but not both. There are other wasps which are in this category, as well as many beetles, flies, butterflies, and moths. One such example of a bee species that only consumes pollen in its larval stage is the Apis mellifera carnica. There is a vast array of insects that will feed opportunistically on pollen, as will various birds, orb-weaving spiders and other nectarivores.

<span class="mw-page-title-main">Stochastic universal sampling</span> Data sampling technique used in genetic algorithm

Stochastic universal sampling (SUS) is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker.

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 in 2005.

In operations research, cuckoo search is an optimization algorithm developed by Xin-She Yang and Suash Deb in 2009. It has been shown to be a special case of the well-known -evolution strategy. It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of host birds of other species. Some host birds can engage direct conflict with the intruding cuckoos. For example, if a host bird discovers the eggs are not their own, it will either throw these alien eggs away or simply abandon its nest and build a new nest elsewhere. Some cuckoo species such as the New World brood-parasitic Tapera have evolved in such a way that female parasitic cuckoos are often very specialized in the mimicry in colors and pattern of the eggs of a few chosen host species. Cuckoo search idealized such breeding behavior, and thus can be applied for various optimization problems.

Random search (RS) is a family of numerical optimization methods that do not require the gradient of the problem to be optimized, and RS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.

Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) that optimizes a function by stochastically and iteratively improving candidate solutions with regard to a given measure of quality, or fitness function. BBO belongs to the class of metaheuristics since it includes many variations, and since it does not make any assumptions about the problem and can therefore be applied to a wide class of problems.

Fish School Search (FSS), proposed by Bastos Filho and Lima Neto in 2008 is, in its basic version, an unimodal optimization algorithm inspired on the collective behavior of fish schools. The mechanisms of feeding and coordinated movement were used as inspiration to create the search operators. The core idea is to make the fishes “swim” toward the positive gradient in order to “eat” and “gain weight”. Collectively, the heavier fishes have more influence on the search process as a whole, what makes the barycenter of the fish school moves toward better places in the search space over the iterations.

References

  1. ↑ 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.
  2. 1 2 3 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.
  3. ↑ Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms, Soft Computing, 1-33.
  4. ↑ Pham, D.T. and Castellani, M. (2015), A comparative study of the bees algorithm as a tool for function optimisation, Cogent Engineering 2(1), 1091540.
  5. 1 2 3 Nasrinpour, H. R., Massah Bavani, A., Teshnehlab, M., (2017), Grouped Bees Algorithm: A Grouped Version of the Bees Algorithm, Computers 2017, 6(1), 5; ( doi : 10.3390/computers6010005)
  6. ↑ Baronti, Luca & Castellani, Marco & Pham, D.. (2020),An Analysis of the Search Mechanisms of the Bees Algorithm., Swarm and Evolutionary Computation. 59. 100746. 10.1016/j.swevo.2020.100746
  7. 1 2 3 4 Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics Archived 2014-02-01 at the Wayback Machine . Journal of Computing and Information Systems, 9(3), 1-7.
  8. ↑ Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, Massachusetts.
  9. 1 2 Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems [ dead link ], Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454-459, 2006.
  10. ↑ 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)
  11. ↑ 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 ( doi : 10.1177/0959651811422759)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.