Artificial bee colony algorithm
From Scholarpedia
| This article is undergoing 1 initial review (2 completed); It may contain inaccuracies and unapproved changes made by anonymous reviewers. | ||||||||||||||||||||
Author: Dr. Dervis Karaboga, Erciyes University, Computer Engineering Department, Turkey
Artificial Bee Colony (ABC) algorithm is a population based modern heuristic algorithm and was introduced by Karaboga in 2005 (Karaboga, 2005) for optimizing numerical problems. It was inspired of the intelligent foraging behavior of honey bees. The algorithm is specifically based on the model proposed by Tereshko and Loengarov (2005) for the foraging behaviour of honey bee colonies. The model consists of three essential components: food sources, employed and unemployed foraging bees. Foraging bees search for rich food sources close to their hive. The model also defines two leading modes of behaviour which are neccessary for self-organizing: recruitment of foragers to rich food sources resulting in positive feedback and abandonment of poor sources by foragers causing negative feedback.
In ABC, a colony of artificial forager bees (agents) search rich artificial food sources (good solutions for a given problem). In the application, first, the optimization problem is converted into the problem of finding the best parameter vector which minimizes an objective function. Secondly, artificial bees discover a population of initial solution vectors and then iteratively improve them by employing the strategies: recruitment to good solutions, abandonment of poor solutions; and using a neigbour production mechanism.
Contents |
Global Optimization Problem
A global optimization problem can be defined as finding the parameter vector 
that minimizes an objective function 
(1) subject to bounds (2), inequality (3) and/or equality (4) constraints.
- (1)
where is defined on a search space, 
, which is a 
-dimensional rectangle in 
(
). The variable domains are limited by their lower and upper bounds (2).
- (2)
- (3)
- (4)
This problem is also known as constrained optimization problem. If 
, then it is called unconstrained optimization problem.
The Artificial Bee Colony Metaheuristic
In ABC, the colony of artificial bees contains three groups of bees: employed bees associated with specific food sources, onlooker bees watching the dance of employed bees within the hive to choose a food source and scouts searching for food sources randomly. Onlooker bees and scouts are also called unemployed bees. In ABC, the first half of the colony consists of employed bees while the second half constitutes the onlooker bees. The employed bee whose food source has been exhausted becomes a scout bee. In ABC, the position of a food source represents a possible solution to the 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 food sources (solutions) since each employed bee is associated with only one food source.
The general scheme of the ABC algorithm is as follows:
Initialize the food source positions and set parameters
REPEAT
Employed Bees Phase
Onlooker Bees Phase
Scout Bees Phase
Memorize the best solution achieved so far
UNTIL(Cycle=Maximum Cycle Number or a Maksimum CPU time)
Initialization Phase
The population of food sources 
are initialized 
, 
the population size). Since each food source, 
, is a solution vector to the optimization problem, each vector holds elements 
that correspond to the parameters of an optimization problem and is the number of optimization parameters.
The following definition might be used for initialization purpose (5):
- (5)
where 
and 
are the lower and upper bound of the parameter , respectively.
Employed Bees Phase
Employed bees search for new food sources (
) having more nectar within the neighbourhood of the food source () in their memory. They find a neighbour food source and then evaluate its profitability (fitness). For example, they can determine a neighbour food source using the formula given by the equation (6), and evaluate its fitness using equation (7).
- (6)
where 
is a randomly selected food source, 
is a randomly chosen parameter index and 
is a random number within the range ![[-a,a]](/wiki/images/math/f5e8764ee4926fe7edd53618793aacd6.png)
. After producing new food source (
), its fitness is calculated and a greedy selection is applied between and .
The fitness value might be calculated for minimization problems using the following definition (7)
- (7)
where 
is the cost value of the objective function for the solution 
.
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 for , 
, with that , is choosen by an onlooker bee can be calculated by using the expression given in equation (8) :
- (8)
After a food source for an onlooker bee is probabilistically chosen, a neighbourhood source is determined by using the equation (6), and then its fitness value is computed. As in employed bees phase, a greedy selection is applied between and .
Scout Bees Phase
The unemployed bees who choose their food sources randomly are called scouts. Firstly, in ABC, employed bees whose solutions can not be improved through a predetermined number of trials become scouts and then their solutions are abondoned. Secondly, they start to search for new solutions, randomly. For instance, if the solution has been abandoned, the new solution discovered by the scout who was the employed bee of can be defined by (5). The number of trials for abandoning a solution is an important control parameter called ‘‘limit’’ or “abandonement criterion”
Main features of the ABC algorithm
The ABC algorithm
1) mimics the foraging behaviour of honeybees closely
2) has been originally proposed for numerical optimization
3) can be also used for combinatorial optimization problems
4) can be used for unconstrained and constrained optimization problems
5) has the ability of local and global search
6) is quite simple, flexible and robust
7) employs a few control parameters
Applications of ABC
An Unconstrained Optimization Problem: Neural Network Training for XOR problem
The exclusive-OR (XOR), boolean function is a difficult classification problem mapping two binary inputs to a single binary output as (0 0;0 1;1 0;1 1)›(0;1;1;0). This classical benchmark is also a hard task for the neural networks that are being successfully applied to solving problems in pattern classification, function approximation, optimization, patern matching and associative memories. Training an artificial neural network is an optimization task since it is desired to find the optimal weight set of a neural network in training process. The optimization goal is to minimize the objective function by optimizing the network weights.
In the simulations a 2-2-1 feed-forward neural network having six connection weights and no biases (having six parameters, XOR6), a 2-2-1 feed-forward neural network having six connection weights and three biases (having 9 parameters, XOR9) and a 2-3-1 feed-forward neural network having nine connection weights and four biases totally thirteen weights (XOR13) were used.
In Table 1, means of Mean Square Errors (MSE) of 30 runs of each configuration are recorded for ABC and Particle Swarm Optimization (PSO) algorithms where each run started with a random population with different seeds. The value of SN was chosen as 50 and the limit value was set to SN*n, where n is dimension of the weight set.
| XOR6 | XOR9 | XOR13 | |
|---|---|---|---|
| ABC | 0.007051 | 0.006956 | 0.006079 |
| PSO | 0.097255 | 0.057676 | 0.014549 |
From the results presented in Table 1, it is clear that the ABC algorithm is more successful than standard PSO at training neural networks on the XOR benchmark problem in all cases (Karaboga and Basturk, 2007).
A Constrained Optimization Problem: Welded Beam Design
In order to handle with constraints in the constrained optimization problem addressed, the ABC algorithm employed Deb’s rules. Deb’s rules are used instead of the greedy selection employed between and in ABC proposed for unconstrained optimization problems (Karaboga and Basturk, 2007). Deb’s method uses a tournament selection operator, where two solutions are compared at a time by applying following criteria (Deb, 2000):
- Any feasible solution satisfying all constraints is preferred to any infeasible solution violating any of the constraints,
- Among two feasible solutions, the one having better fitness value is preferred,
- Among two infeasible solutions, the one having smaller constraint violation is preferred.
Welded beam design illustrated in Fig.2 minimizes the cost of the beam subject to constraints on shear stress,
, bending stress in the beam, 
, buckling load on the bar, 
, end deflection of the beam,
, and side constraints. There are four design parameters 
which correspond to 
variables, respectively.
- (9)
From the results presented in Table 2, it is seen that ABC is able to find the optimum solution for the constrained engineering design problem: welded beam. The low mean and standard deviation values show the robustness of the algorithm. When compared to the results produced by (Montes and Coello 2005) (
-ES), the ABC algorithm is more robust.
| Best | Mean | Std. Dev. | Evaluations | |
|---|---|---|---|---|
| ABC | 1.724852 | 1.741913 | 3.1E-02 | 30000 |
| (-ES) Montes and Coello 2005
| 1.724852 | 1.777692 | 8.8E-2 | 30000 |
| x1 | x2 | x3 | x4 | g1 | g2 | g3 | g4 | g5 | g6 | g7 | f(x) |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.20573 | 3.470489 | 9.036624 | 0.20573 | 0 | -2E-06 | 0 | -3.43298 | -0.08073 | -0.23554 | 0 | 1.724852 |
Other Approaches Inspired of Honeybee Foraging Behaviour
Combinatorial Optimization:
Lucic and Teodorovic introduced a Bee System based on foraging behaviour of bee colonies for solving difficult combinatorial optimization problems (Lucic and Teodorovic, 2001).The Bee System was tested through many instances of the Traveling Salesman Problem (Lucic,2002; Lucic and Teodorovic, 2002; Teodorovic, 2003; Lucic and Teodorovic, 2003a). Teodorovic and Dell (2005) proposed a Bee Colony Optimization (BCO) Metaheuristic for the Ride-matching problem in 2005 and (Markovic et al., 2007) applied for the routing and wavelength assignment (RWA) in all-optical networks. Another algorithm simulating foraging behaviour is BeeAdHoc described by Wedde and Farooq (2005c), which is a routing algorithm for energy efficient routing in mobile ad hoc networks. Drias and Yahi (2005) introduced a meta-heuristic named "Bees Swarm Optimization" and its adaptation to the features of the MAX-W-SAT problem was introduced to contribute to its resolution. Chong et al. (2006) described a bee colony optimization algorithm based on foraging and waggle dance and using dance durations to select a new path, and the algorithm was applied to job shop scheduling. Chong et al. (2007) utilized an efficient neighborhood structure to search for feasible solutions and iteratively improve them. The results indicated that the performance of the proposed approach is comparable to other efficient scheduling approaches. In (Quijano and Passino, 2007), a model of honey bee social foraging was introduced for solving a class of optimal resource allocation problems.
Numerical Optimization:
Yang (2005) developed a virtual bee algorithm (VBA) to solve the numerical function optimizations. The algorithm works for the functions with two-parameters. Pham et al. (2005) described the Bees Algorithm which mimics the foraging behaviour of honey bees. In its basic version, the algorithm performs a kind of neighbourhood search combined with random search and can be used for both combinatorial optimization and functional optimization.
Current Trends
The initial applications of ABC were in the area of numerical optimization problems since it was originally proposed for this kind of problems (Karaboga, 2005). The performance of ABC was compared with Genetic Algorithm (GA), Differential Evolution (DE), and PSO algorithms for unconstrained numerical optimization problems (Basturk and Karaboga 2006, Karaboga and Basturk 2007a, Karaboga and Basturk 2008).
An extended version of the ABC was compared on the constrained optimization problems with DE and PSO algorithms in (Karaboga and Basturk 2007b,Domínguez 2009).
The ABC algorithm was applied to train feed-forward neural networks on classification problems: In (Karaboga, Basturk and Ozturk, 2007) XOR, Decoder-Encoder and 3-Bit Parity benchmark problems were chosen to compare the performance of ABC with Genetic Algorithm (GA) and Back-Propagation (BP) Algorithms; In ( Karaboga, Ozturk, Akay, 2008) 3 medical problems (cancer, diabetes, heart) were considered from Proben1 database (Prechelt, 1994) and the classification performance of the ABC algorithm was compared to Back-Propagation (BP), Levenberg-Marquardt (LM) and Genetic Algorithm (GA).
The use of ABC for optimizing hybrid functions, solving integer programming and engineering design problems (Rao et al., 2008,Singh, 2009, Karaboga, 2009), combinatorial type optimization, multi-objective optimization and binary-variable optimization are current hot topics.
Several papers reporting on research related to ABC and its applications can be found in http://mf.erciyes.edu.tr/abc
References
Appendix -- Foraging Behaviour of Honey Bees
An interesting swarm is honey bee colony which performs tasks within and out of the hive in a swarm intelligent manner. Since the availability of the nectar sources around the hive varies in space and time, the colony of bees has to adapt its foraging behaviour to the changes in the environment. For instance, an appropriate division of the worker efforts between exploring new sources and exploiting the available ones is very important via collective intelligence for the maintenance of the colony (Vries and Biesmeijer, 1998).As stated before, the minimal model of forage selection that leads to the emergence of collective intelligence of honey bee swarms consists of three essential components: food sources, employed foragers and unemployed foragers (Tereshko and Loengarov, 2005)..
(i) Food sources: The “profitability” of a food source is related to several factors such as its closeness to the nest, richness of energy and the ease of extracting the energy from the source. In the minimal model, the profitability of a food source is represented with one of the quantities.
(ii) Employed foragers: These foragers are associated with a specific food source they exploit or are employed at. They carry information about the specific source such as its distance, direction from the hive and the profitability of the source and then they share this information with the forager bees waiting in the hive by dancing which is an example of multiple interaction.
(iii) Unemployed foragers seeking a food source to exploit: scouts and onlooker bees . The scouts randomly search the environment surrounding the hive for new food sources and this behaviour is a kind of fluctuations which is vital for self-organization; and the onlooker bees waiting in the hive find a food source by means of the information presented by employed foragers. The mean number of scouts is about 5–10% of the foragers (Tereshko and Loengarov, 2005)
The exchange of information among bees is the most important occurrence in the formation of collective knowledge. While examining the entire hive, it is possible to distinguish some parts that commonly exist in all hives. The most important part of the hive regarding to exchanging information is the dancing area where different types of dances are performed: Waggle dance, Round dance, Tremble dance, and etc. Communication among bees related to the quality of food sources is called waggle dance. Since information about all the current rich sources is available to onlooker bees on the dance floor, they probably could watch numerous dances and choose to employ themselves at profitable sources. Employed foragers share their information with a probability which is proportional to the profitability of their food sources. There is a greater probability of onlooker bees choosing more profitable sources since more information is circulating about the more profitable sources. Hence, the recruitment is proportional to profitability of food sources (Tereshko and Loengarov, 2005).
External Links
http://mf.erciyes.edu.tr/abc http://mf.erciyes.edu.tr/abc]: This is the official web site dedicated to the ABC Algorithm
See also
Algorithm, Swarm intelligence, Ant colony optimization, Flocking and swarming
