Keywords

1 Introduction

Global optimization problems (GOPs) always arise in almost all of science research and engineering fields. population-based random optimization algorithms, such as genetic algorithm (GA) [1, 2], ant colony optimization (ACO) [3], particle swarm optimization(PSO) [4] and artificial bee colony algorithm (ABC), have been becoming a popular and promising way to handle these GOPs. ABC was developed by Karaboga [5] firstly, inspired by the collective foraging behavior of honey bee colony. The performance of ABC was demonstrated by comparing ABC with other evolutionary algorithms (EAs). Due to its simple structure, easy implementation and good performances, ABC has successfully attracted numerous researcher’s attention and been applied to solve many practical engineering optimization problems [6,7,8,9].

However, like other EAs, ABC often shows a slow convergence speed [10] since its solution search equation does well in exploration but poorly in exploitation. The search equation is the core operator of ABC, which significantly affects the performance of ABC. Therefore, in order to keep a better balance between exploration and exploitation, many new search equations were proposed. Inspired by PSO, Zhu and Kwong [11] introduced the information of the global best solution into the solution search equation to improve the exploitation ability of ABC (GABC). The experimental results showed that GABC is better than ABC on most benchmark functions. Karaboga and Akay [13] introduced two new parameters i.e., modification rate (MR) and scaling factor (SF), into the solution equation to control frequency and magnitude of perturbation, respectively. In order to combine the advantage of different solution search equations, Kiran et al. [14] proposed a new method, which integrates five search equations to generate candidate solutions by the way of cooperation and competition. Moreover, Wang et al. [12] proposed the MEABC algorithm to improve the local and global search capability of the ABC, in which a pool of three distinct solution search strategies coexists throughout the search process and produces new solutions competitively. Recently, Karabaga et al. [15] proposed a new search equation for onlooker bees (qABC), which uses the valuable information of the best solution among the neighbors to improve the search efficiency of ABC. At the same time there are some improvements that blend with other operations [16, 17], and so on.

According to above considerations, the performance of ABC mainly depends on its solution search equation. Therefore, it is a promising way to improve the performance of ABC by introducing new search equation or integrating multiple search equations. In this paper, we follow this basic idea and propose an improved ABC algorithm, named HGABC. In employed bee phase of HGABC, all employed bees are divided into three groups according to the quality of their food source positions (fitness values), and different groups use different solution search equations. Moreover, to enhance the local exploitation ability in a promising area, in onlooker bee phase of HGABC, the most promising area is firstly recognized based on the quality of all food source positions, and onlooker bees conduct exploitation only around the positions located in the most promising area. The experimental results on 22 benchmark functions show that HGABC performs more competitively and effectively when it is compared with the other ABC variants.

The rest of this paper is organized as follows. Section 2 introduces ABC algorithm briefly. The proposed algorithm is presented detailedly in Sect. 3. Section 4 discusses and analyzes the experimental results. Finally, Sect. 5 concludes this paper.

2 Artificial Bee Colony Algorithm

Inspired by the waggle dance and foraging behaviors of honey bee colony, ABC algorithm has been developed. 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 position corresponds to the quality (fitness value) of the associated solution. The number of the employed bees or the onlooker bees is equal to the number of food sources. The basic ABC algorithm consists of four basic phases, namely initialization phase, employed bee phase, onlooker bee phase and scout bee phase.

2.1 Initialization Phase

In the initialization phase, the necessary parameters, i.e., the number of food source position SN, the termination condition and the parameter limit, should be initialized firstly. Then, the initial food source positions are randomly produced in the whole search space by Eq. (1) as follows,

$$ x_{i,j} = x_{\hbox{min} ,j} + rand\left( {0,1} \right)(x_{\hbox{max} ,j} - x_{\hbox{min} ,j} ) $$
(1)

where \( i = 1,2, \cdots ,SN \), \( j = 1,2, \cdots ,D \), \( SN \) is the population size, and \( x_{i,j} \) is the jth dimension of the ith solution. \( x_{\hbox{min} ,j} \) and \( x_{\hbox{max} ,j} \) are the lower and upper bounds of the jth dimension of the problem, respectively. \( rand\left( {0,1} \right) \) is a random number in the range of [0,1]. The fitness value of the food source positions are calculated as follows,

$$ fit\left( {x_{i} } \right) = \left\{ {\begin{array}{*{20}c} {{1 \mathord{\left/ {\vphantom {1 {\left( {1 + f\left( {x_{i} } \right)} \right)}}} \right. \kern-0pt} {\left( {1 + f\left( {x_{i} } \right)} \right)}}} & {\text{if}\left( {f\left( {x_{i} } \right) \ge 0} \right)} \\ {1 + abs\left( {f\left( {x_{i} } \right)} \right)} & {\text{ else}} \\ \end{array} } \right. $$
(2)

where \( f(x_{i} ) \) is the objective function value of the ith food source position, and \( fit(x_{i} ) \) is the fitness value of the ith food source position.

2.2 Employed Bee Phase

In this phase, each employed bee flies to a distinct food source position to search for better food source position, and the candidate food source position is generated as follows,

$$ v_{i,j} = x_{i,j} + \phi_{i,j} \left( {x_{i,j} - x_{k,j} } \right) $$
(3)

where \( i = 1,2, \cdots ,SN \) and \( j = 1,2, \cdots ,D \); \( k \in \left\{ {1,2, \ldots ,SN} \right\} \) and it is different from i; D is the dimension of the problem; \( \phi_{i,j} \) is a random number in the range of [−1,1]. After the generation of the candidate solution \( v_{i} \), if the candidate solution is better than the old one, the old solution will be replaced by the candidate solution. Otherwise, the old solution will be kept.

2.3 Onlooker Bee Phase

After all employed bees complete their search process, they will share the information (quality and position of food source) of their food source position to onlooker bees by assigning each food source position a selection probability, which is calculated as follows,

$$ p_{i} = {{fit(x_{i} )} \mathord{\left/ {\vphantom {{fit(x_{i} )} {\sum\limits_{i = 1}^{SN} {fit(x_{i} )} }}} \right. \kern-0pt} {\sum\limits_{i = 1}^{SN} {fit(x_{i} )} }} $$
(4)

where \( p_{i} \) is the selection probability of the ith food source position, and each onlooker bee selects a food source position to perform search according to the selection probability of each food source position. The same search strategy and greedy selection method are employed by onlooker bees to perform further exploitation.

2.4 Scout Bees Phase

In the scout bee phase, if a certain food source position (solution) fails to be updated during a predetermined cycle (defined as “limit”), the corresponding employed bee becomes a scout bee and the food source position should be replaced by a new one, which is generated randomly according to Eq. (1).

After the initialization, ABC enters a loop of employed bee phase, onlooker phase and scout bee phase until the terminal condition is satisfied.

3 Artificial Bee Colony Algorithm with Hierarchical Groups (HGABC)

In the original ABC or other ABC variants [11], only one search strategy is employed by employed bee and onlooker bee, which may result in that the search ability of these methods are limited. Inspired by the observation in the team work of human being, since each member in the team has different characteristics, such as knowledge, attitude and skill, the whole team usually is divided into multiple groups according to their abilities, and each group takes different responsibilities or tasks. By this way, the work efficiency can be significantly improved. In original ABC, although the colony contains three types of bees, i.e., employed bee, onlooker bee and scout bee, different types of bees are responsible for different search abilities. However, ABC treats all employed bees (or onlooker bee) equally because all employed bees (or onlooker bees) employ the same search strategy. While in real bee colony, each employed bee (or onlooker bee) is a unique individual, and the search ability of them may be different from each other. Therefore, different employed bees (and onlooker bees) may adopt different search strategies in fact.

According to above consideration, in this paper, we propose a novel artificial bee colony algorithm with hierarchical groups, named HGABC. To be specific, in HGABC, the employed bees are divided into three groups based on the quality of their food source positions, and different groups employ different search strategies so as to be responsible for different search abilities. Moreover, in order to pay more attention to the exploitation in the most promising area, all onlooker bees only search around the food source positions which locate in the most promising area. Similarly, three search strategies could be used by onlooker bees in a random manner. The proposed strategies are described in detail as follows.

3.1 Division of Employed Bees and Search Strategies

In ABC, each employed bee occupies a food source position. Since each employed bee has distinct ability and should adopt different search strategy, in order to differentiate employed bees, we firstly divide the employed bees into three group based on the quality of their own food source positions. To be specific, the employed bees firstly sort from best to worst based on the quality of their food source positions. The first \( a \cdot SN \) employed bees, the medium \( b \cdot SN \) employed bees and the last \( c \cdot SN \) employed bees, respectively constitute the high group, medium group and low group, where \( a,b,c \in [0,\;1] \) and \( a + b + c = 1 \).

The high group includes some current good solutions, which may be located in the local optimal areas or the global optimal area. Therefore, its employed bees should learn the beneficial information from the current best solution and conduct exploitation toward the current best solution. The employed bees belonging to the high group adopt the search strategy as follows,

$$ v_{i,j} = x_{k,j} + \varphi_{i,j} (xbest_{j} - x_{k,j} ) $$
(5)

where \( xbest \) is the current best solution; \( x_{k} \) is randomly selected from the population, which is different from \( x_{i} \) and \( xbest \); \( \varphi_{i,j} \) is a random number in the range of [0,1]; j is a randomly selected dimension.

With respect to the medium group, it consists of some neither better nor worse solutions that are not far from or close to the global optimal area. Their employed bees should take the responsibility of obtaining balance between the exploitation and exploration. Therefore, the employed bees in the medium group use the search strategy as follows,

$$ v_{i,j} = x_{k,j} + \phi_{i,j} (x_{k,j} - x_{q,j} ) + \varphi_{i,j} (xbest_{j} - x_{k,j} ) $$
(6)

where \( xbest \) is the current best solution, and \( x_{k} \) and \( x_{q} \) are randomly selected from the population, which are distinct from each other and different from \( x_{i} \) and \( xbest \). \( \varphi_{i,j} \) is a random number in the range of [0,1], and \( \phi_{i,j} \) is a random number in the range of [−1, 1]. j is a randomly selected dimension.

Regarding to the low group, it contains the current bad solutions that may be far from the local optimal areas or the global optimal area with a high probability, and its employed bees should be responsible for exploration by exploiting new areas randomly. Therefore, the third kind of employed bees employ the search strategy as follows,

$$ v_{i,j} = x_{k,j} + \phi_{i.j} (x_{k,j} - x_{q,j} ) $$
(7)

where \( x_{k} \) and \( x_{q} \) are randomly selected from the population, which are distinct from each other and different from \( x_{i} \). \( \phi_{i,j} \) is a random number in the range of [−1, 1]. j is a randomly selected dimension.

Overall, in our proposed algorithm, all employed bees are divided into three groups, namely the high group, the medium group and the low group. The employed bees in different groups adopt different search strategies and undertake different search tasks. More specifically, the high group’s employed bees pay more attention to exploitation, the low group’s employed bees focus on exploration, and the medium group’s employed bees are responsible to balance between exploration and exploitation.

3.2 Search Strategy of Onlooker Bee

In original ABC, after all employed bees complete their search tasks, the onlooker bees start to work depending on the information provided by the employed bees. To be specific, each onlooker bee will select a food source position to conduct exploitation by the roulette wheel method, which is a time-consuming procedure. Moreover, the better the quality of the food source position is, the bigger the selection probability is. In order to pay more attention to the promising area and accelerate the convergence, in this paper, we present a most promising area search strategy for onlooker bee. The details are described as follows.

In order to recognize the most promising area, each food source position denotes an area. To be specific, for the ith food source position, if the Euclidean distance between food source position \( x_{i} \) and \( x_{j} \) (\( j = 1,\;2,\; \cdots ,\;SN \) and \( j \ne i \)) is less than the radius r, the position \( x_{j} \) belongs to the area located by the position \( x_{i} \). Moreover, the radius r is calculated as follows,

$$ r = \frac{{\sum\nolimits_{i = 1}^{SN - 1} {\sum\nolimits_{j = i + 1}^{SN} {d(x_{i} ,x_{j} )} } }}{SN(SN - 1)/2} $$
(8)

where \( d(x_{i} ,x_{j} ) \) is the Euclidean distance between \( x_{i} \) and \( x_{j} \), and SN is the number of the food source positions.

Obviously, there are SN areas in the search space and the best quality area based on the average fitness value of its members is treated as the most promising area. After the most promising area is identified, the onlooker bees only fly to a randomly selected food source position located in the most promising area to search.

Moreover, to make the onlooker bees show different search abilities and keep a better balance between exploration and exploitation, the above three search equations (Eqs. (5), (6) and (7)) are employed by onlooker bees in a random manner based on two control parameters \( s_{1} \) and \( s_{2} \).

According to the proposed modifications, the pseudo-code of onlooker bee phase is shown in Fig. 1 and the completed pseudo-code of the proposed algorithm HGABC is shown in Fig. 2.

Fig. 1.
figure 1

The pseudo-code of onlooker bee phase

Full size image
Fig. 2.
figure 2

The pseudo-code of HGABC

Full size image

4 Experiments

In order to demonstrate the performance of our proposed algorithm HGABC, we compare HGABC with four ABC methods, i.e., the basic ABC [5], GABC [11], qABC [15] and MEABC [12] on 22 benchmark functions with 30D, which are listed in Table 1. To make a fair comparison, for all compared algorithms, SN and limit are set to 50 and \( SN \cdot D \), respectively. Other parameters are set the same as the original papers. For HGABC, a, b and c are respectively set to 0.2, 0.3 and 0.5; \( s_{1} \) and \( s_{2} \) are set to 0.25 and 0.75, respectively. The maximal number of function evaluation (maxFES) is used as the termination condition, which is set to \( 5000 \cdot D \). All algorithms conduct 25 times independent runs on each function. The experimental results are given in Table 2. For the sake of clarity, the best results are marked in boldface. Moreover, the Wilcoxon’s rank sum test at 5% significance level on results gained by two competing algorithms is also conducted to show the significant differences between HGABC and other ABC methods. The results of the test are represented as “+”, “−”, “=”, which mean that the compared algorithm is significantly better than, worse than, equal to HGABC, respectively.

Table 1. Benchmark functions in experiments
Full size table
Table 2. Comparison results on 22 test functions with 30D
Full size table

As shown in Table 2, the metric of mean and std respectively denote the average value and standard deviation of the best objective function value of 25 independent runs. According to these metrics, HGABC successfully gets the best results on all functions except that f 4, f 10 and f 14. To be specific, HGABC is better than ABC, GABC, qABC and MEABC on 18, 12, 18 and 9 functions, respectively. On the contrary, HGABC is only beaten by GABC and MEABC on 1 and 1 function, respectively. Moreover, ABC and qABC is unable to perform better than HGABC on any cases.

In addition, in order to clearly show the convergence speed and robustness of different algorithms, more experimental results about the average FES (AVEN) and success rate (SR) are also given in Table 1. AVEN represents the average FES needed to reach the threshold defined in Table 1. In Table 1, “NAN” denotes that the algorithm cannot get any solutions, whose objective function is smaller than the acceptable value in 25 independent runs. SR represents the ratio of the number of success runs in the 25 independent runs. The success run means that algorithm can find the solution, whose objective function value is less than the acceptable value. Obviously, the search accuracy of HGABC is better than or equal to other algorithms on all functions, excluding f 4, f 10 and f 14. Similarly, the SR of HGABC is 100% on all functions except f 10, on which all algorithms are unable to get a 100% success rate. Overall, HGABC is better than the competitors in terms of solution accuracy, convergence speed and robustness.

To clearly show the advantages of HGABC, the convergence curves of the mean on some representative functions are plotted in Fig. 3. It can be seen from Fig. 3 that HGABC converges faster than ABC, GABC, qABC and MEABC on both unimodal functions and multimodal functions. In conclusion, the experimental results demonstrate that our modifications of employed bee phase and onlooker bee phase can ontain a better balance between exploration and exploitation, and effectively improve the performance of ABC.

Fig. 3.
figure 3

Convergence curve of all ABCs on some representative functions

Full size image

5 Conclusion

This paper presents a new ABC algorithm, called HGABC. In HGABC, in order to differentiate the employed bees, the employed bees are divided into three groups according to the quality of their food source positions. The employed bees belonging to different groups employ different search strategies and are responsible for different search abilities. Moreover, to speed up convergence and pay more attention to the most promising area, the onlooker bees using three search strategies in a random manner only exploit in the most promising area. The comparison results on 22 benchmark functions show that HGABC can significantly improve the performance of ABC and outperform other ABC methods in terms of solution accuracy, convergence speed and robustness. In future, we can apply HGABC to handle real world engineering problems.