Artificial bee colony algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 16:26, 31 August 2016

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 Karaboga in 2005.^[1]

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

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.).

Algorithm

In the ABC model, the colony consists of three groups of bees: employed bees, onlookers and scouts. It is assumed that there is only one artificial employed bee for each food source. In other words, the number of employed bees in the colony is equal to the number of food sources around the hive. Employed bees go to their food source and come back to hive and dance on this area. The employed bee whose food source has been abandoned becomes a scout and starts to search for finding a new food source. Onlookers watch the dances of employed bees and choose food sources depending on dances. The main steps of the algorithm are given below.:^[8]

Initial food sources are produced for all employed bees
REPEAT
- Each employed bee goes to a food source in her memory and determines a neighbour source, then evaluates its nectar amount and dances in the hive
- Each onlooker watches the dance of employed bees and chooses one of their sources depending on the dances, and then goes to that source. After choosing a neighbour around that, she evaluates its nectar amount.
- Abandoned food sources are determined and are replaced with the new food sources discovered by scouts.
- The best food source found so far is registered.
UNTIL (requirements are met)

In ABC, a population based algorithm, the position of a food source represents a possible solution to the optimization problem and the nectar amount of a food source corresponds to the quality (fitness) of the associated solution. The number of the employed bees is equal to the number of solutions in the population. At the first step, a randomly distributed initial population (food source positions) is generated. After initialization, the population is subjected to repeat the cycles of the search processes of the employed, onlooker, and scout bees, respectively. An employed bee produces a modification on the source position in her memory and discovers a new food source position. Provided that the nectar amount of the new one is higher than that of the previous source, the bee memorizes the new source position and forgets the old one. Otherwise she keeps the position of the one in her memory. After all employed bees complete the search process, they share the position information of the sources with the onlookers on the dance area. Each onlooker evaluates the nectar information taken from all employed bees and then chooses a food source depending on the nectar amounts of sources. As in the case of the employed bee, she produces a modification on the source position in her memory and checks its nectar amount. Providing that its nectar is higher than that of the previous one, the bee memorizes the new position and forgets the old one. The sources abandoned are determined and new sources are randomly produced to be replaced with the abandoned ones by artificial scouts.

Artificial bee colony algorithm

ABC is a swarm intelligence algorithm proposed by Karaboga in 2005, which is inspired by the behavior of honey bees. Since the development of ABC, it has been applied to solve different kinds of problems. Artificial bee colony (ABC) algorithm is a recently proposed optimization technique which simulates the intelligent foraging behavior of honey bees. A set of honey bees is called swarm which can successfully accomplish tasks through social cooperation. In the ABC algorithm, there are three types of bees: employed bees, onlooker bees, and scout bees. The employed bees search food around the food source in their memory; meanwhile they share the information of these food sources to the onlooker bees. The onlooker bees tend to select good food sources from those found by the employed bees. The food source that has higher quality (fitness) will have a large chance to be selected by the onlooker bees than the one of lower quality. The scout bees are translated from a few employed bees, which abandon their food sources and search new ones.

In the ABC algorithm, the first half of the swarm consists of employed bees, and the second half constitutes the onlooker bees.

The number of employed bees or the onlooker bees is equal to the number of solutions in the swarm. The ABC generates a randomly distributed initial population of SN solutions (food sources), where SN denotes the swarm size.

Let $X_{i}=\{x_{i,1},x_{i,2},\ldots ,x_{i,n}\}$ represent the $i^{th}$ solution in the swarm, Where $n$ is the dimension size. Each employed bee $X_{i}$ generates a new candidate solution $V_{i}$ in the neighborhood of its present position as equation below:

V_{i_{k}}=X_{i_{k}}+\Phi _{i_{k}}\times (X_{i_{k}}-X_{j_{k}})

Where $X_{j}$ is a randomly selected candidate solution ( $i\neq j$ ), $k$ is a random dimension index selected from the set $\{1,2,\ldots ,n\}$ , and $\Phi _{i_{k}}$ is a random number within $[-1,1]$ . Once the new candidate solution $V_{i}$ is generated, a greedy selection is used. If the fitness value of $V_{i}$ is better than that of its parent $X_{i}$ , then update $X_{i}$ with $V_{i}$ ; otherwise keep $X_{i}$ unchanged. After all employed bees complete the search process; they share the information of their food sources with the onlooker bees through waggle dances. An onlooker bee evaluates the nectar information taken from all employed bees and chooses a food source with a probability related to its nectar amount. This probabilistic selection is really a roulette wheel selection mechanism which is described as equation below:

P_{i}={\frac {fit_{i}}{\sum _{j}{fit_{j}}}}

Where $fit_{i}$ is the fitness value of the $i^{th}$ solution in the swarm. As seen, the better the solution $i$ , the higher the probability of the $i^{th}$ food source selected. If a position cannot be improved over a predefined number (called limit) of cycles, then the food source is abandoned. Assume that the abandoned source is $X_{i}$ , and then the scout bee discovers a new food source to be replaced with $i^{th}$ as equation below:

X_{i_{k}}=lb_{j}+rand(0,1)\times (ub_{j}-lb_{j})

Where $rand(0,1)$ is a random number within $[0,1]$ based on a normal distribution and $lb,ub$ , are lower and upper boundaries of the $i^{th}$ dimension, respectively.

References

^ D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005.
^ 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.
^ 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 ﬁeld 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 ﬂow 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 scientiﬁc rigor.
^ Fred Glover and Kenneth Sörensen (ed.). "Metaheuristics". Scholarpedia. "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."
^ 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."
^ Alexander Brownlee and John R. Woodward (2015). "Why we fell out of love with algorithms inspired by nature". The Conversation.
^ 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."
^ Karaboga, Dervis (2005). "An Idea Based on Honey Bee Swarm For Numerical Optimization". {{cite journal}}: Cite journal requires |journal= (help)

External links

Artificial Bee Colony Algorithm

[1] D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005.

[2] 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.

[3] 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 ﬁeld 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 ﬂow 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 scientiﬁc rigor.

[4] Fred Glover and Kenneth Sörensen (ed.). "Metaheuristics". Scholarpedia. "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."

[5] 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."

[6] Alexander Brownlee and John R. Woodward (2015). "Why we fell out of love with algorithms inspired by nature". The Conversation.

[7] 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."

[8] Karaboga, Dervis (2005). "An Idea Based on Honey Bee Swarm For Numerical Optimization". {{cite journal}}: Cite journal requires |journal= (help)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 2: / Line 2: @@
 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 Karaboga in 2005.<ref>D. [[Dervis Karaboga]], An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005.</ref>
+Nature-inspired metaheuristics in general have started to [[List of metaphor-inspired metaheuristics#Criticism of the metaphor methodology|attract criticism in the research community]] for hiding their lack of novelty behind an elaborate metaphor.<ref>{{cite journal|last=Weyland|first=Dennis|title=A Rigorous Analysis of the Harmony Search Algorithm: How the Research Community can be Misled by a "Novel" Methodology|journal=[[International Journal of Applied Metaheuristic Computing]]|volume=1|issue=2|year=2010|pages=50–60|doi=10.4018/jamc.2010040104}}</ref><ref>{{cite journal|first=Kenneth|last=Sörensen|title=Metaheuristics—the metaphor exposed|journal=[[International Transactions in Operational Research]]|doi=10.1111/itor.12001|volume=22|pages=3–18|year=2013|quote=In recent years, the ﬁeld 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 ﬂow 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 scientiﬁc rigor.}}</ref><ref>{{scholarpedia|title=Metaheuristics|urlname=Metaheuristics|curator=[[Fred W. Glover|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."</ref><ref>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. [http://www.cs.nott.ac.uk/~exo/docs/publications/research-agenda-metaheuristic.pdf "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."</ref><ref>Alexander Brownlee and John R. Woodward (2015). [http://theconversation.com/why-we-fell-out-of-love-with-algorithms-inspired-by-nature-42718 "Why we fell out of love with algorithms inspired by nature"]. ''[[The Conversation (website)|The Conversation]]''.</ref> In response, [[Springer Science+Business Media|Springer]]'s ''Journal of Heuristics'' has updated their editorial policy to state that:<ref>[http://www.springer.com/cda/content/document/cda_downloaddocument/Journal+of+Heuristic+Policies+on+Heuristic+Search.pdf?SGWID=0-0-45-1483502-p35487524 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 algorithm]]s, [[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."</ref>
+<blockquote>
+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 search|harmony]], [[firefly algorithm|flies]], [[bat algorithm|bats]], [[Imperialist competitive algorithm|countries]], etc.).
+</blockquote>
 == Algorithm ==
@@ Line 44: / Line 48: @@
 * [[Particle swarm optimization]]
 * [[Swarm intelligence]]
-* [[Bees algorithm]]
 == References ==

Revision as of 16:26, 31 August 2016

Algorithm

Artificial bee colony algorithm

See also

References

External links