Bees algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Not to be confused with Artificial bee colony algorithm.

In computer science and operations research, the bees algorithm is a population-based search algorithm which was developed 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 topological 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]

Nature-inspired metaheuristics in general have started to attract criticism in the research community for hiding their lack of novelty behind an elaborate metaphor.[5][6][7][8][9] In response, Springer's Journal of Heuristics has updated their editorial policy to state that:[10]

Implementations should be explained by employing standard optimization terminology, where a solution is called a "solution" and not something else related to some obscure metaphor (e.g., harmony, flies, bats, countries, etc.).

Metaphor[edit]

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

Algorithm[edit]

The bees algorithm[2][13] 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,...,nb
             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 nbns 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 nenb solutions (elite sites) recruit nre foragers each, whilst the remaining nb-ne scouts recruit nrbnre 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,[11] 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=nenre+(nb-ne)•nrb+ns (elite sites foragers + remaining best sites foragers + scouts) bees.

See also[edit]

References[edit]

  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. ^ a b c 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. ^ Weyland, Dennis (2010). "A Rigorous Analysis of the Harmony Search Algorithm: How the Research Community can be Misled by a "Novel" Methodology". International Journal of Applied Metaheuristic Computing. 1 (2): 50–60. doi:10.4018/jamc.2010040104. 
  6. ^ Sörensen, Kenneth (2013). "Metaheuristics—the metaphor exposed". International Transactions in Operational Research. 22: 3–18. doi:10.1111/itor.12001. In recent years, the field of combinatorial optimization has witnessed a true tsunami of "novel" metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together – it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. In this paper, we will argue that this line of research is threatening to lead the area of metaheuristics away from scientific rigor. 
  7. ^ Metaheuristics at Scholarpedia, curated by Fred Glover and Kenneth Sörensen. "A large (and increasing) number of publications focuses on the development of (supposedly) new metaheuristic frameworks based on metaphors. The list of natural or man-made processes that has been used as the basis for a metaheuristic framework now includes such diverse processes as bacterial foraging, river formation, biogeography, musicians playing together, electromagnetism, gravity, colonization by an empire, mine blasts, league championships, clouds, and so forth. An important subcategory is found in metaheuristics based on animal behavior. Ants, bees, bats, wolves, cats, fireflies, eagles, vultures, dolphins, frogs, salmon, vultures, termites, flies, and many others, have all been used to inspire a "novel" metaheuristic. [...] As a general rule, publication of papers on metaphor-based metaheuristics has been limited to second-tier journals and conferences, but some recent exceptions to this rule can be found. Sörensen (2013) states that research in this direction is fundamentally flawed. Most importantly, the author contends that the novelty of the underlying metaphor does not automatically render the resulting framework "novel". On the contrary, there is increasing evidence that very few of the metaphor-based methods are new in any interesting sense."
  8. ^ Jerry Swan, Steven Adriaensen, Mohamed Bishr, Edmund K. Burke, John A. Clark, Patrick De Causmaecker, Juanjo Durillo, Kevin Hammond, Emma Hart, Colin G. Johnson, Zoltan A. Kocsis, Ben Kovitz, Krzysztof Krawiec, Simon Martin, J. J. Merelo, Leandro L. Minku, Ender Özcan, Gisele L. Pappa, Erwin Pesch, Pablo Garcáa-Sánchez, Andrea Schaerf, Kevin Sim, Jim E. Smith, Thomas Stützle, Stefan Voß, Stefan Wagner, Xin Yao. "A Research Agenda for Metaheuristic Standardization". "Metaphors often inspire new metaheuristics, but without mathematical rigor, it can be hard to tell if a new metaheuristic is really distinct from a familiar one. For example, mathematically, 'Harmony search' turned out to be a simple variant of 'Evolution Strategies' even though the metaphors that inspired them were quite different. Formally describing state, representation, and operators allows genuine novelty to be distinguished from minor variation."
  9. ^ Alexander Brownlee and John R. Woodward (2015). "Why we fell out of love with algorithms inspired by nature". The Conversation.
  10. ^ Journal of Heuristic Policies on Heuristic Search Research. Springer. "Proposing new paradigms is only acceptable if they contain innovative basic ideas, such as those that are embedded in classical frameworks like genetic algorithms, tabu search, and simulated annealing. The Journal of Heuristics avoids the publication of articles that repackage and embed old ideas in methods that are claimed to be based on metaphors of natural or manmade systems and processes. These so-called "novel" methods employ analogies that range from intelligent water drops, musicians playing jazz, imperialist societies, leapfrogs, kangaroos, all types of swarms and insects and even mine blast processes (Sörensen, 2013). If a researcher uses a metaphor to stimulate his or her own ideas about a new method, the method must nevertheless be translated into metaphor-free language, so that the strategies employed can be clearly understood, and their novelty is made clearly visible. (See items 2 and 3 below.) Metaphors are cheap and easy to come by. Their use to "window dress" a method is not acceptable."
  11. ^ a b c d Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics. Journal of Computing and Information Systems, 9(3), 1-7.
  12. ^ Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.
  13. ^ 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.

External links[edit]