Artificial Bee Colony

An Optimization Algorithm

Abstract – Artificial Bee Colony (ABC) is a meta-heuristic approach in which a colony of artificial bees cooperates to find high quality solution for numerical optimization problems with a non-leaner time complexity. ABC is widely used for various problems where either the convention algorithms are not able to find suitable solution or the time used by conventional algorithms is not acceptable.  Its application laying from data mining to neuroscience, search engines and clustering.  

  1. Introduction

A short definition for algorithm could be a process or set of rules and regulations to be followed to solve complex operation by computer. Algorithms have different types based on the various ways of approaching toward a better solution as follows:

  1. Divide and conquer approach.

  2. Dynamic programming algorithm.

  3. Greedy algorithm.

  4. Swam intelligence algorithms.

  5. ETC.

The real world problems are classified in to two major types of time complexity such as a linear problem and non-linear problems. When we say complexity of a problem is a function of linear we means the execution time of running an algorithm over the problem takes linear time such as Time =  ax + c where (x flows from 1 to n) while non-linear problems takes exponential time for execution Such as Time=ax+c where (x flows from 1 to n).

Swarm intelligence is the collective behavior of decentralized and self organized systems inspired by nature. SI consists of population which interacts with each other to pass available information to each other and it results to emerge a global intelligence system.

  1. Artificial Bee Colony (ABC)

Artificial bee colony algorithm is based on intelligent foraging behavior of honey bee swarm proposed by Dr. Karaboga in 2005. The algorithm is used to solve non-linear searching problem mimicking the behavior of a honey bee swarm as they search the food source [1]. Artificial Bee 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:

  1. Pseudo code / Structure

  • Initial food sources are produced for all employed bees

  • REPEAT

    • Each employed bee goes to a food source in her memory and determines a neighbor 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 neighbor 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 [2].

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 denotes the swarm size.

Let X_i=\{x_1,1,x_2,2,\ldots,x_n,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 parentX_i, then update X_i withV_i; otherwise keep X_i unchangeable. 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}{fit_j}

Where fit_i is the fitness value of the i^{th}solution in the swarm. As seen, the better the solutioni, 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 andlb,ub, are lower and upper boundaries of the i^{th} dimension, respectively [2].

 

  1. Summary

This paper shortly introduces swarm intelligence and optimization algorithm ‘Artificial Bee Colony’ and also put a glance on different types of algorithm. The paper shortly divides real world problems into two classes based on their time complexity, linear problem and non-linear exponential problems. Swarm intelligence algorithms are used to solve non-linear complex problem. Artificial bee colony (ABC) is one of the swarm intelligence algorithm inspired by nature. ABC is mimicking the forging behavior of honey bee for finding the food source. Each food source is considered as a solution to the problem and the food source with better quality is the best available solution.  

ABC is widely used in search engines, clustering, data mining, neurosciences, robotics and artificial intelligence.  

References

[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]    Basturk B., Karaboga D., an Artificial Bee Colony (ABC) Algorithm for Numeric Function

Optimization, IEEE Swarm Intelligence Symposium 2006, Indianapolis, Indiana, USA,

2006

Category: Papers

About Author

Ramin Sadat

Ramin specializes in Text Analytics, Machine Learning and Meta-Heuristic Optimization Techniques. He holds Master's degrees in Computer Science and Business Administration. Currently, he works as the Microsoft SharePoint Developer at the US Department of State in Afghanistan. Previously, he has held positions at Information Management Specialist at the World Bank, and Senior Solutions Developer with Etisalat Afghanistan.

Published posts  1

Comments