Artificial Bee Colony (ABC) Optimization

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.

Particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. ABC is based on PSO.

Behaviour Of Real Bees

  • Honey bees live in well-organized colonies and do not require hibernation. 
  • They are best known for their production of honey, which they store in wax combs inside nests. 
  • Honey bees are generally active during spring, when they go in search of plants from which to collect pollen and nectar. From these two ingredients, they create honey, which humans have harvested for hundreds of years.
  • Honey bees are social creatures and live within colonies with a queen, thousands of workers and a few male drones. 
  • Workers make these nests from wax, which they secrete from their abdominal glands. 
  • Honey bees are very adaptable. While honey bees forage for food in groups, a colony can survive without foraging for several years by living on food reserves and huddling in large, compacted masses during winter seasons. 
  • Like some insects, honey bees behave defensively when intruders are near, guarding the entrance to their nests. However, honey bees are able to sting only once. Because stingers contain barbs and are attached to the worker's intestines, they detach from the stinging bee's body after attacking a victim. While a honey bee will die soon after transferring its venom, pheromones secreted during the attack will alarm and stimulate other worker bees to attack, as well.

https://www.orkin.com/pests/stinging-pests/bees/honey-bees/honey-bee-behavior


ABC Algorithm

Working

  • The ABC was first proposed to solve numerical optimization problems by Karaboga.
  • ABC consists of employed and unemployed foragers, and food sources. The ABC consists of three groups of artificial bees: employed foragers, onlookers and scouts. 
  • The employed bees comprise the first half of the colony whereas the second half consists of the onlookers.
  • In the basic ABC, there are 3 kinds of bees: employed, onlooker, and scout bees.
  • The employed bees exploit the food positions, while the onlooker bees are waiting for information from the employed bees about nectar amount of the food positions. 
  • The onlooker bees select food positions using the employed bee information and they exploit the selected food positions. 
  • Finally, the scout bees find new random food positions. 



A bee waiting on the dance area for making decision to choose a food source, is called an onlooker and a bee going to the food source visited by itself previously is named an employed bee. A bee carrying out random search is called a scout. In the ABC algorithm, first half of the colony consists of employed artificial bees and the second half constitutes the onlookers. For every food source, there is only one employed bee. In other words, the number of employed bees is equal to the number of food sources around the hive. The employed bee whose food source is exhausted by the employed and onlooker bees becomes a scout. The main steps of the algorithm are given below: 


• Initialize. 

• REPEAT. 

(a) Place the employed bees on the food sources in the memory; 

(b) Place the onlooker bees on the food sources in the memory; 

(c) Send the scouts to the search area for discovering new food sources. 

• UNTIL (requirements are met).


 At the initialization stage, a set of food source positions are randomly selected by the bees and their nectar amounts are determined. Then, these bees come into the hive and share the nectar information of the sources with the bees waiting on the dance area within the hive. At the second stage, after sharing the information, every employed bee goes to the food source area visited by herself at the previous cycle since that food source exists in her memory, and then chooses a new food source by means of visual information in the neighbourhood of the present one. At the third stage, an onlooker prefers a food source area depending on the nectar information distributed by the employed bees on the dance area. As the nectar amount of a food source increases, the probability with which that food source is chosen by an onlooker increases, too. Hence, the dance of employed bees carrying higher nectar recruits the onlookers for the food source areas with higher nectar amount. After arriving at the selected area, she chooses a new food source in the neighbourhood of the one in the memory depending on visual information. Visual information is based on the comparison of food source positions. When the nectar of a food source is abandoned by the bees, a new food source is randomly determined by a scout bee and replaced with the abandoned one. In our model, at each cycle at most one scout goes outside for searching a new food source and the number of employed and onlooker bees were equal.


In the ABC algorithm, the position of a food source represents a possible solution of 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 or the onlooker bees is equal to the number of solutions in the population.


Phases of ABC

 It generally consist of four phases.

1) Initialization of ABC.

  • Determine the number of artificial bees. 50% are employed bees and 50% are onlooker’s bees.
  • Generate the random initial candidate solutions for employed bees  
  • Determine the limit value.

2) Employed bee phase

  • For all employed bees Generate new candidate solution.
  • Calculate the fitness value of the new solution.
  • If fitness of new candidate solution is better than the existing solution replace the older solution.
  • Calculate the probability for each individual.

3) Onlooker bee phase.

For all onlooker bees

  • Select an employed bees using roulette wheel.
  • Produce new candidate solution.
  • Compute fitness of individual.
  • If fitness of new candidate solution is better than the existing solution replace the older solution.

4) Scout bee phase

If any food source exhausted then replace it by randomly generated solution by scout memorize the best solution.

Until (stopping criteria is not met).


Two variants of the ABC known as ABCgBest and ABCgBestDist were proposed. In the ABCgBest variant, the global best equation from PSO was incorporated whereas global best and distance based reference selection were incorporated into the ABCgBestDist. The position of the artificial bees in both variations were updated and controlled based on the selection of reference locations

The major advantages which ABC holds over other optimization algorithms include its:

• Simplicity, flexibility and robustness

• Use of fewer control parameters compared to many other search techniques

• Ease of hybridization with other optimization algorithms.

• Ability to handle the objective cost with stochastic nature

• Ease of implementation with basic mathematical and logical operations.


Onlooker bees are the bees which reside in the beehive and search the food sources on the basis of the information collected by the employed bees.

 

Employed Bees Phase

Employed bees search for new food sources (υm) having more nectar within the neighbourhood of the food source (xm) in their memory. They find a neighbour food source and then evaluate its profitability (fitness). For example, they can determine a neighbour food source υmusing the formula given by equation (6):

υmi=xmi+ϕmi(xmixki)(6)


where xkis a randomly selected food source, iis a randomly chosen parameter index and ϕmiis a random number within the range [a,a] .After producing the new food source υm ,its fitness is calculated and a greedy selection is applied between υmandxm .

The fitness value of the solution, fitm(xm) ,might be calculated for minimization problems using the following formula (7)

fitm(xm)=11+fm(xm)1+abs(fm(xm))if  fm(xm)0if  fm(xm)<0(7)


where fm(xm)is the objective function value of solutionxm .

Onlooker Bees Phase

Unemployed bees consist of two groups of bees: onlooker bees and scouts. Employed bees share their food source information with onlooker bees waiting in the hive and then onlooker bees probabilistically choose their food sources depending on this information. In ABC, an onlooker bee chooses a food source depending on the probability values calculated using the fitness values provided by employed bees. For this purpose, a fitness based selection technique can be used, such as the roulette wheel selection method (Goldberg, 1989).

The probability value pmwith which xmis chosen by an onlooker bee can be calculated by using the expression given in equation (8) :

pm=fitm(xm)m=1SNfitm(xm) .(8)


After a food source xmfor an onlooker bee is probabilistically chosen, a neighbourhood source υmis determined by using equation (6), and its fitness value is computed. As in the employed bees phase, a greedy selection is applied between υmand xm .Hence, more onlookers are recruited to richer sources and positive feedback behaviour appears.

Scout Bees Phase

The unemployed bees who choose their food sources randomly are called scouts. Employed bees whose solutions cannot be improved through a predetermined number of trials, specified by the user of the ABC algorithm and called “limit” or “abandonment criteria” herein, become scouts and their solutions are abandoned. Then, the converted scouts start to search for new solutions, randomly. For instance, if solution xmhas been abandoned, the new solution discovered by the scout who was the employed bee of xmcan be defined by (5). Hence those sources which are initially poor or have been made poor by exploitation are abandoned and negative feedback behaviour arises to balance the positive feedback.

 
Explain ABC algorithm and its working? What is the fitness function used so to improve the performance of the algorithm? 

Initialization Phase 
REPEAT
Employed Bees Phase
Onlooker Bees Phase
Scout Bees Phase
Memorize the best solution achieved so far
UNTIL(Cycle=Maximum Cycle Number or a Maximum CPU time)

The procedure of the artificial bee colony (ABC) algorithm. | Download  Scientific DiagramFlow chart of the ABC algorithm. | Download Scientific Diagram

No comments:

Post a Comment

Monk and Inversions

using System; public class Solution { public static void Main () { int T = Convert . ToInt32 ( Console . ReadLine...