Artificial bee colony algorithm

Artificial Bee Colony (ABC) algorithm, proposed by Karaboga for optimizing numerical problems in (Karaboga, 2005), simulates the intelligent foraging behavior of honey bee swarms. In ABC algorithm, the colony of artificial bees contains three groups of bees: employed bees, and unemployed bees: onlookers and scouts. In ABC, first half of the colony consists of employed artificial bees and the second half constitutes the artificial onlookers. The employed bee whose food source has been exhausted becomes a scout bee. In ABC 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 food sources, each of which also represents a site, being exploited at the moment or to the number of solutions in the population.

In ABC optimization, the steps given below are repeated until a stopping criteria is satisfied:

Initialize the food source positions

REPEAT 

  Employed Bees Phase

  Onlooker Bees Phase

  Scout Bee Phase

  Memorize the best solution achieved so far

UNTIL(cycle= Maximum Cycle Number (MCN))

Initialization Phase

The population of solutions \(x_{ij}\) are initialized in the range of the parameter \(j\). The following definition might be used for this purpose (<ref>eq3</ref>):

where \(xmin_j \) is the lower bound of the parameter \(j\) and \(xmax_j \) is the upper bound of the parameter \(j\).

Employed Bees Phase

Each employed bee determines a food source (\(\upsilon_{ij}\)), which is also representative of a site, within the neighbourhood of the food source in her memory (\(x_{ij}\)) for example using the formula (<ref>neig</ref>) and evaluates its profitability. Each employed bee shares her food source information with onlookers waiting in the hive and then each onlooker selects a food source site depending on the information taken from employed bees.

  :<math neig> \upsilon_{ij} = x_{ij} + \phi_{ij}(x_{ij} - x_{kj})</math>

\(x_k\) is a randomly selected solution, \(j\) is a randomly chosen parameter, \(\phi_{ij}\) is a random number within the range \([-a,a]\). After producing a new solution (\(\upsilon_i\)), a greedy selection is applied between \(\upsilon_{i}\) and \(x_{i}\)

In order to simulate the information sharing by employed bees in the dance area, probability values \(p_i\) are calculated for the solutions \(x_i\) by means of their fitness values, \(fit_i\). For example, using the following equation (<ref>eq1</ref>).

<math eq1>p_i = \fracTemplate:Fit i{{\sum\limits_{i = 1}^{SN} {fit_i } }} </math>

The fitness values might be calculated using the following definition for minimization problems (<ref>eq2</ref>):

<math eq2>fit_i = \left\{ {\begin{array}{*{20}c} {\frac{1}[[:Template:1 + f i]]} & {} & {if{\rm{ }}f_i \ge 0} \\ {1 + abs(f_i )} & {} & {if{\rm{ }}f_i < 0} \\ \end{array}} \right\}</math>

where \(f_i\) is the cost value of the objective function.

Onlooker Bees Phase

As mentioned before, the nectar amount of a food source corresponds to the quality of the solution represented by that food source position. Onlookers are placed onto the food source sites by using a fitness based selection technique, for example roulette wheel selection method (Goldberg, 1989). New solutions (new positions) \( \upsilon_i\) are produced for the onlookers from the solutions \(x_i\) by (<ref>neig</ref>), selected depending on \(p_i\), and the new solutions are evaluated. As for employed bees, a greedy selection is applied between \(\upsilon_{i}\) and \(x_{i}\).

Scout Bee Phase

Employed bees whose sources have been abandoned become scout and start to search a new food source randomly, for example by . (<ref>eq3</ref>). Every bee colony has scouts that are the colony’s explorers. The explorers do not have any guidance while looking for food. They are primarily concerned with finding any kind of food source. In case of artificial bees, the artificial scouts might have the fast discovery of the group of feasible solutions. In ABC, the artificial employed bee whose food source nectar has been exhausted or the profitability of the food source drops under a certain threshold level is selected and classified as the artificial scout. The classification is controlled by a control parameter that is called ‘‘abandonment criteria” or “limit’’. If a solution representing a food source position is not improved until a predetermined number of trials, then that solution is abandoned by its employed bee and the employed bee becomes a scout. The number of trials for releasing a solution is equal to the value of ‘‘limit’’.

Application: 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, pattern matching and associative memories. Training an artificial neural network is an optimization task since it is desired to find optimal weight set of a neural network in training process. The optimization goal is to minimize the objective function by optimizing the network weights.

Figure 5: An example of Neural Network structure for XOR problem

In the simulations we use a 2-2-1 feed-forward neural network with six connection weights, no biasses (having six parameters, XOR6) and a 2-2-1 feed-forward neural network with 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 parameters (XOR13). Means of Mean Square Errors (MSE) of 30 runs of each configuration are recorded where each run started with a random population with different seeds. The parameter food sources (SN) is chosen 50 and the limit value is set to SN*D, where D is dimension of the weight set.

Table 1: Experimental Results of ANN training process
	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 ABC algorithm is more successful than PSO at training neural networks on the XOR benchmark problem in three cases.

Artificial Bee Colony Algorithm for Constrained Optimization Problems

Constrained optimization (CO) finds parameter vector \(\vec x\) (<ref>coeq2</ref>) that minimizes an objective function \(f (\vec x )\) subject to inequality (<ref>coeq3</ref>) and/or equality (<ref>coeq4</ref>) constraints.

{\rm minimize~} f(\vec x),~~\vec x = (x_1 , \ldots ,x_n ) \in \mathbb{R}^n </math>

{\rm ~~~~~~~~~~~~~~~~~~~~~~}l_i \leq x_i\leq u_i, ~~~i=1,\ldots,n </math>

{\rm subject~to:~} g_j( \vec{x} ) \leq 0,~for j=1,\ldots,q </math>

{\rm ~~~~~~~~~~~~~~~~~~~~~~} h_j(\vec{x})=0,~for j=q+1,\ldots,m </math>

The objective function f is defined on a search space, \(S\), which is defined as a \(n\)-dimensional rectangle in \(R^n\) (\(S \subseteq R^n\)). Domains of variables are defined by their lower and upper bounds (<ref>coeq2</ref>). A feasible region \(F \subseteq S\) is defined by a set of \(m\) additional constraints (\(m \geq 0\)) (<ref coeq3</ref>,<ref>coeq4></ref>) and \(\vec x in F \in S\). At any point \(\vec x in F\), constraints \(g_k\) that satisfy \(g_k(\vec x)=0\) are called active constraints at \(\vec x\). By extension, equality constraints \(h_j\) are also called active at all points of \(S\) (Michalewicz and Schoenauer, 1995). Constrained optimization problems are hard to optimization algorithms but no single parameter (number of linear, nonlinear, active constraints, the ratio \( \rho=|F|/|S|\), type of the function, number of variables) is proved to be significant as a major measure of difficulty of the problem (Michalewicz et al., 1999).

In order to handle with constraints the ABC algorithm employs Deb’s rules instead of the greedy selection to direct the solutions to feasible region in running process. 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 is preferred to any infeasible solution,
Among two feasible solutions, the one having better objective function value is preferred,
Among two infeasible solutions, the one having smaller constraint violation is preferred.

In order to improve the convergence rate of ABC algorithm, in the version of ABC for constrained optimization, two new control parameters are introduced. One of them is \(MR\) which is used in neighbour solution production (<ref>coeq5</ref>) to control the number of parameters to be changed. In basic ABC, only one randomly chosen parameter of the old solution is changed to produce a new solution.

\upsilon_{ij}  = \left\{ {\begin{array}{*{20}c}
   {x_{ij}  + \phi _{ij} (x_{ij}  - x_{kj} )} & ,  & {if~~R_j < MR}   \\
   {x_{ij} }  & {\rm ,} & [[:Template:\rm otherwise]]   \\
\end{array}} \right.

</math>

where \(k \in \left\{ {1,2, \ldots SN} \right\}\) is randomly chosen index that has to be different from \(i\), \(R_j\) is uniformly distributed random real number in the range [0,1] and \(j=1,2,\ldots,D\).

The other introduced parameter is employed in the scout production. In the ABC algorithm for constrained optimization problems, artificial scouts are produced at a predetermined period of cycles for discovering new food sources randomly. This period is another control parameter of the modified algorithm called scout production period (\(SPP\)). At each \(SPP\) cycle, it is controlled if there is an abandoned food source, exceeding limit or not. If there is, a scout production process is carried out.

Application: A Constrained Engineering Problem, Welded Beam Design

Welded beam design illustrated in Fig.2 minimizes the cost of the beam subject to constraints on shear stress, \(\tau\), bending stress in the beam, \(\sigma\), buckling load on the bar, \(P_c\) , end deflection of the beam,\(\delta\), and side constraints. There are four design parameters \( x_1, x_2, x_3, x_4\) correspond to \( h, l, t, b\) variables, respectively, shown in Figure <ref>F2</ref>.

Figure 6: The Welded Beam Problem

min f(X) = 1.1047x_1^2x_2 + 0.004811x_3x_4(14.0 + x_2) </math>

\( {\rm{ }}\begin{array}{*{20}l} {subject{\rm{ }}to} & {g_1 (X):{\rm{ }}\tau (x) - \tau _{\max } {\rm{ }} \le 0} \\ {} & {g_2 (X):{\rm{ }}\sigma (x) - \sigma _{\max } \le 0} \\ {} & {g_3 (X):{\rm{ }}x_1 - x_4 \le 0} \\ {} & {g_4 (X):{\rm{ }}0.10471x_1^2 + 0.04811x_3 x_4 (14.0 + x_2 ) - 5.0 \le 0} \\ {} & {g_5 (X):{\rm{ }}0.125 - x_1 \le 0} \\ {} & {g_6 (X):{\rm{ }}\delta (x) - \delta _{\max } \le 0} \\ {} & {g_7 (X):{\rm{ }}P - P_c (x) \le 0} \\ \end{array} \)

where \(\tau (X) = \sqrt {(\tau ')^2 + 2\tau '\tau ''\frac[[:Template:X2]][[:Template:2R]] + (\tau '')^2 } \),

\(\tau ' = \frac{P}[[:Template:\sqrt 2 x 1 x 2]]\),

\(\tau '' = \frac[[:Template:MR]]{J}\), \\

\(M = P(L + \frac[[:Template:X 2]]{2})\),

\( R = \sqrt {\frac[[:Template:X 2^2]]{4} +\left( {\frac[[:Template:X 1 + x 3]]{2}} \right)^2 }, J = 2\left\{ {\frac[[:Template:X 1 x 2]][[:Template:\sqrt 2]]\left[ {\frac[[:Template:X 2^2]][[:Template:12]] + \left( {\frac[[:Template:X 1 + x 3]]{2}} \right)^2 } \right]} \right\}\),

\(\sigma(X) = \frac[[:Template:6PL]][[:Template:X 4 x 3^2]]\),

\(\delta (X) = \frac[[:Template:4PL^3]][[:Template:Ex 3^3 x 4]]\),

\(P_c = \frac{{4.013E\sqrt {\frac[[:Template:X 3^2 x 4^6]][[:Template:36]]} }}[[:Template:L^2]]\left( {1 - \frac[[:Template:X 3]][[:Template:2L]]\sqrt {\frac{E}[[:Template:4G]]} } \right)\)

P=6000 lb., L=14 in, \(\delta_{\max } = 0.25{\rm{ in}}\),

\({\rm{E = 30x10}}^{\rm{6}} {\rm{ psi}}\),

\({\rm{G = 12x10}}^{\rm{6}} {\rm{ psi}}\),

\(\tau _{\max }{\rm{ = 13600psi}}\),

\(\sigma _{\max } = {\rm{30000 psi}}\),

\(X = (x_1,x_2 ,x_3 ,x_4 )^{\rm{T}} \),

\(0.1 \le x_1 ,x_4 \le 2.0\),

\(0.1 \le x_2 ,x_3 \le 10\).

From the results, ABC algorithm can find the optimum solution of a constrained engineering design problem: welded beam design. The low value of mean and the standard deviation calculated from the results show the robustness of the algorithm. As compared to \(\mu+\lambda\)-ES), ABC algorithm is more robust.

Table 2: Statistics of the Results obtained by the ABC algorithm for Welded Beam Problem
	Best	Mean	Std. Dev.	Evaluations
ABC	1.724852	1.741913	3.1E-02	30000
(\(\mu+\lambda\)-ES) Montes and Coello 2005	1.724852	1.777692	8.8E-2	30000

Table 3: Parameter and Constraint values of the best solution obtained by the ABC algorithm for Welded Beam Problem
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 Applications

The first application of ABC algorithm was optimizing numerical problems (Karaboga, 2005).The performance of ABC algorithm is tested on unconstrained numerical optimization problems by GA, DE, and PSO algorithms (Basturk and Karaboga 2006, Karaboga and Basturk 2007a, Karaboga and Basturk 2008). Moreover, in (Karaboga and Basturk 2008a) the performance of ABC algorithm is studied under the change of control parameter values and in (Karaboga and Basturk 2008b), the effect of region scaling on the performance of algorithm is investigated. The extended version of the ABC algorithm is compared on the constrained optimization problems with the algorithms DE and PSO in (Karaboga and Basturk 2007b). ABC algorithm is 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 are chosen and the performance of ABC algorithm is compared with Genetic Algorithm (GA) and Back-Propagation (BP) Algorithm; In ( Karaboga, Ozturk, Akay, 2008) 3 medical problems (cancer, diabetes, heart) are taken from Proben1 database (Prechelt, 1994) and the classification performance of ABC algorithm is tested by the algorithms: back-propagation (BP), Levenberg-Marquardt (LM) and Genetic Algorithm (GA). Nowadays, the performance of ABC algorithm is being studied on hybrid functions, integer programming and engineering design problems in numerical optimization and classification and clustering of data mining techniques. The ABC algorithm is applied to several problems in different areas (Rao et al., 2008,Singh, 2009, Karaboga, 2009).