Hybrid artificial bee colony algorithm with variable neighborhood search and memory mechanism

FAN Chengli,FU Qiang,LONG Guangzheng,and XING Qinghua

Air and Missile Defense College,Air Force Engineering University,Xi’an 710051,China

1.Introduction

Artificial bee colony(ABC)is a swarm intelligence optimization algorithm,which was developed by Karaboga[1]in 2005 based on the foraging behavior of honeybees.The ABC algorithm has become a research hot spot for the characteristics of simple structure,few control parameters and easy to implement.Numerical comparisons have confirmed that the performance of ABC is superior to the classical evolutionary algorithms[2,3].Accordingly,ABC has been applied to many applications,such as the numerical optimization problem[4],the scheduling problem[5],and the multi-objective optimization problem[6].

In recent years,the improvement of ABC mostly focused on the population structure strategy,the selection strategy and the search strategy.Banharnsakun et al.[7]proposed a modified search equation based on the best-sofar solution.Gao and Liu[8]were inspired by differential evolution(DE)to put forward a new solution search equation and the chaotic initialization strategy.Although the above two ABC variants indeed enhance the exploitationability of ABC, they cannot avoid the algorithm falling into local optimum.Then Yan et al.[9]introduced the crossover operator to ABC,which improved the information exchange ability among artificial bees.Liu et al.[10]presented the improved ABC based on local search.Zhou et al.[11]put forward the neighborhood search mechanism to improve the solution search equation of ABC.They argued that the local search ability of ABC can be enhanced.However,the global search efficiency of the ABC algorithm has not been fundamentally improved.

Therefore,improving the local search ability and the global search efficiency have become the two most significant objectives in ABC study.In order to realize these two objectives,we propose the hybrid ABC(HABC)algorithm which includes two strategies.First,the variable neighborhood search factor is added to the solution search equation,which can enhance the local search ability and increase the population diversity.Then,a memory mechanism is put forward,which imitates the natural behavior of honeybees to fundamentally improve the global search efficiency.

The organization of this paper is as follows.Section 2 briefly introduces the standard ABC algorithm.Section 3 presents the HABC algorithm in details.Section 4 validates the superiority of the HABC algorithm in the numerical experiments. Finally, Section 5 makes the conclusion of this paper.

2.Standard ABC algorithm

The standard ABC algorithm divides the artificial bees into three groups,including employed bees,onlooker bees and scout bees.These three groups can play different roles and spontaneously perform role conversion.The employed bees search for the food source and share the information of the food source to onlooker bees through performing dances.Then onlooker bees select a better food source to exploit in a probability,which accords to the qualities of the food sources.Sometimes,employed bees may convert to scout bees,when the food source is abandoned and they need to search for new ones.

Like the other swarm intelligence optimization algorithms,the standard ABC is an iterative algorithm.The description of standard ABC is described in the following subsections.

2.1 Initialization phase

In the initialization phase,the standard ABC algorithm randomly generates an initial population of food sources.Letrepresent theith food source,and then the position of food sources are produced as

wherei=1,2,...,SNandj=1,2,...,D.SNis the number of food sources,Dis the dimension of the food source,are the lower and upper bounds of the dimensionj.

2.2 Employed bees phase

In this phase,each employed beeXifinds a better food sourcein the neighborhood by using

wherek=1,2,...,SNis a randomly chosen index and different fromi,is a random number in[-1,1].

After producingVi,it will be compared toXiwith the greedy selection mechanism.fitidenotes the fitness value of food sourcei,which is calculated by

wherefiis the objective function value of solutioni.

2.3 Onlooker bees phase

When employed bees select the food source and return to the hive,they will share the information of the food source to onlooker bees through performing dances.Then onlooker bees select the food source depending on this information in a probability.The probability valuepiis calculated by

After the food sources have been selected by onlooker bees based on the probability value,each onlooker bee will search a new food source in its neighboring area following(2).Obviously,this searching procedure is similar to the employed bees.

2.4 Scout bees phase

In the scout bees phase,a food sourceXiis given a control parameter,which records the number of failed trials and denotes as triali.If a food source cannot be improved within triali,Xiwill be abandoned and the employed bees convert to scout bees.Meanwhile,a new food source will be randomly generated by(1).

The standard ABC algorithm utilizes employed bees,onlooker bees and scout bees to iteratively search the solution space until reach the maximum number of iterations,which is denoted asGmax.

2.5 Standard ABC algorithm description

Based on the above description,the pseudo-code of the standard ABC is outlined in Algorithm 1.

3.HABC algorithm

In the ABC standard algorithm,the new food source is randomly selected in the neighboring area according to(2)for each employed bee or onlooker bee searches.It is due to such a random strategy of the search equation that the ABC algorithm is poor at local search ability and its global search efficiency is low. In order to solve these problems,the HABC algorithm is proposed which includes two strategies.First,the variable neighborhood search(VNS)factor,which systematicly changes the neighborhood structure to enhance the local search ability and increase the population diversity,is added to(2).Second,a memory mechanism is put forward.In this memory mechanism,the artificial bees are allowed to simulate the memory ability of real honeybees,which can remember their past successful experiences and improve the global search efficiency.The details of the HABC algorithm is described in the following subsections.

3.1 VNS factor

VNS is a heuristic algorithm,which was developed by Mladenovic’in 1997[20].The core idea of VNS is to define the set of neighborhood structuresNl(x)(l=1,2,...,lmax)that can be used in a systematic way to search the solution space and help the search process escape from local optimum.The core idea of VNS is shown in Fig.1.

Fig.1 Core idea of VNS

In detail,the neighborhoodNl(x)denotes the set of solutions in thelth neighborhood ofx.Thus,the construction ofNl(x)is the significant part of the VNS algorithm.Using thelpmetrics,we can define the neighborhoodsNl(x)in numerical optimization problem as follows:

wherelis the number of neighborhood structures,ρlis the radius ofNl(x)monotonically increasing withl.

The solution search equation which adds the variable neighborhood search factor is described as follows:

wherelbest(i)is the optimal food source in the neighborhood of theXiwhich obtained by the VNS factor.kis a randomly selected neighboring food source,wherekshould be different fromi.is a random value ranging in[-1,1].

The pseudo-code of the VNS factor is described in Algorithm 2

3.2Memory mechanism

The neuroscience has confirmed that the real honeybees have the ability to remember their foraging behavior.As long as we effectively use the memory ability,we can use the past successful experiences to further guide the foraging behavior of employed bees and onlooker bees.However,this memory ability is not taking into account in the standard ABC algorithm as well as its variants.Each time,the choice of new food source is through random search,which greatly limits the search efficiency.Therefore,a memory mechanism is put forward,which assumes the employed bees and onlooker bees can remember their past successful experiences of foraging behavior.Furthermore,these memorized experiences need to be constantly updated and used to guide the subsequent foraging behavior.Obviously,the memory mechanism can fundamentally improve the global search efficiency through imitating the natural behavior of honeybees.

In the HABC algorithm,the memory of food source is denoted by matrixM.

wheredenotes the memory of thejth dimension parameter of the food sourcei(i=1,2,...,SNandj=1,2,...,D),Mis a new control parameter which defines the memory size(m=1,2,...,M).

Initially,Mis set to empty.With the search process of HABC,is constantly updated according to(6).For each,the memorized information includes the following three parts according to:

(i)Optimal neighborhood food source

(ii)Random neighborhood food source

(iii)Random coefficient

In general,if the values ofandcan improve the quality of solution,we consider them as the successful experience and memorize these values.The structure of memory mechanism is illustrated in Table 1.

Table 1 Structure of memory mechanism

3.3 HABC algorithm description

The pseudo-code of the HABC is presented in Algorithm 3.

3.4 Advantages analysis of HABC algorithm

By introducing the variable neighborhood search factor and the memory mechanism,the HABC algorithm includes the following three advantages.

(i)The new solution search equation, that is (6), with thevariable neighborhood search factor has strong local search ability,which can avoid the search process falling into local optimum and make the algorithm fast convergent to the optimal food source.

(ii)The search trajectory of the population is guided by the individual optimal within the neighborhood,and a new food source is generated near the optimal position.This search method based on the elite strategy can effectively improve the exploitation ability and increase the population diversity.

(iii)The memory mechanism can fundamentally improve the global search efficiency through imitating the natural behavior of honeybees,which remember their past successful experiences and further guide the subsequent foraging behavior.It is different from the other ABC variants.

4.Computational results and discussion

4.1 Benchmark functions and parameter settings

Ten benchmark functions with different features are considered to test the performance of the HABC algorithm which have been widely discussed in the recent ABC literature[3,4,20].The different features of these benchmark functions include unimodal-seperable(US), unimodal-nonseperable (UN),multimodel-seperable(MS)and multimodel-nonseperable(MN).The definition of benchmark functions are shown in Table 2 which includes its formula,feature,interval,optimal solution and dimensionsD.

Table 2 Benchmark functions for test

In order to make a fair comparison,the parameter settings in this paper are the same as that in[4].In detail,the population sizeSNis set to 25,the maximum number of iterationsGmaxis 10 000 and the maximum evaluation number is 500 000.The parameterlimitis calculated with(7).

Moreover,compared with the standard ABC algorithm,the HABC algorithm introduces two new parameters,such as:lmax(the number of neighborhood structures)andM(memory size). Thuswe conduct the experiments to test the influence of the different values oflmaxandMon the performance of the HABC algorithm,wherelmax={1,3,5},M={1,2,3,5,10}.

In each of the following experiments,30 independent runs on 10 benchmark functions are carried out,and the best results are marked as bold.

4.2 Experimental results

4.2.1 Effect of neighborhood structures sizelmax

In the HABC algorithm,a new control parameter is introduced which refers to the number of neighborhood structures,that is,lmax.In this subsection,we design the experiment with different values oflmax(lmax=1,lmax=3,lmax=5)and the influence oflmaxis analyzed in terms of best,worst,mean and standard deviation(SD)benchmark function values.The results of comparison are shown in Table 3.As shown in Table 3,the value oflmaxhas great influence on the performance of HABC.The larger value oflmax,the better algorithm performance.Whenlmax=5,HABC produces the optimal results in terms of best,worst,mean and SD in seven functions(f2,f3,f4,f6,f8,f9,f10),and finds the globally optimal solution in six functions(f1,f3,f4,f5,f9,f10).In addition,whenlmax=1,HABC gives the best SD value in functionf1.

Whenlmax=3,HABC presents the best mean value in functionf5,and the better value in the column “Best”as well as “Worst”of the table on functionf7.It is obvious thatlmax=5 can find the best results for most functions.

Table 3 Performance of HABC algorithm with different lmaxvalues

It can be concluded that the performance of HABC is improved with the increase oflmax.In the theory,the HABC algorithm will find the globally optimal solution whenlmax→+∞,but in fact,too large value oflmaxwill decrease the search efficiency of the algorithm,so we setlmax=5 in the following experiments.

4.2.2 Effect of memory sizeM

In this experiment,the effect of another new parameterMin HABC is tested.As can been seen from the definition of matrixM,the smaller value ofM,the less memory of the artificial bees about successful trails.In contrast,the larger value ofM,the artificial bees can memorize the more successful trails.Therefore, five HABC variants withM={1,2,3,5,10}are checkout.Table 4 presents the experimental results.

Table 4 shows that the HABC algorithm has the similar performances with different values ofM.For allMvalues,we can obtain the optimal results in terms of best,worst and mean values in functionf3,f8,f9andf10.In the other six benchmark functions,M=2 reaches the best mean values in five functions(f2,f4,f5,f6,f7),and finds the best SD values in three functions(f2,f4,f5).In addition,M=1 produces the best mean and SD values in functionf1.M=3 presents the best SD value in functionf7.For most functions,M=1,3 and 5 can produce similar results toM=2.AlthoughM=10 gets the worst results in functionf1andf2,it still produces the competitive solutions in functionf6andf7.

It can be concluded that the final results of HABC are very similar with different values ofM,which means the HABC algorithm is insensitive to parameterM’s setting.Even so,M=2 can achieve the best performance in most functions,so we setM=2 in the following experiment.

4.2.3 Performance test and comparison

In order to further validate the effectiveness of the proposed algorithm,the results of HABC are compared with the standard ABC and the quick ABC(qABC)[4].The relevant results are shown in Table 5.It can be observed that,the same optimal results are obtained from ABC,qABC and HABC algorithms in terms of best,worst,median and mean values in four functions(f3,f8,f9,f10).Except for functionf8,the SD values of HABC are not greater than ABC and qABC,which indicates the HABC algorithm has strong robustness.

Table 4 Performance of HABC algorithm with different M values

Table 5 Comparison of the HABC algorithm with ABC and qABC

Continued

In the other six benchmark functions,the best solutions are obtained by HABC.In addition,ABC finds the better mean values than qABC in functionf2,f5,f6andf7.It is worth mentioning that,only HABC finds the globally optimal solutions in functionf1,f4andf5,which means HABC can effectively solve the complex numerical optimization problems.

Fig.2 depicts the convergence curves of these three algorithms.Compared with ABC and HABC,qABC has the faster convergence speed in the early generations in five functions(f1,f4,f6,f9,f10).However,it converges to worse results than HABC as the number of iterations increases.

Fig.2 Convergence curves of three algorithms

Meanwhile,HABC converges to best final solutions with the fast convergence speed in functionf2,f3,f5,f7andf8.

It can be concluded that HABC are superior to ABC and qABC both in final solutions and convergences peed.

The main reason for this is that the HABC algorithm redefines the solution search equation by adding the variable neighborhood search factor which increases the population diversity and enhances the local search ability.Moreover,the memory mechanism indeed improves the global search efficiency.

5.Conclusions and future studies

This paper proposes a novel optimization algorithm called the HABC algorithm.Compared with other ABC variants,HABC contains two innovations.First,the local search ability and the population diversity are improved by adding the variable neighborhood search factor to solution search equation.Second,the global search efficiency is enhanced by memory mechanism which imitates the natural behavior of honeybees,and it is not taken into account in the standard ABC as well as its variants.

In the numerical experiments,we test the two new parameters,and give the best parameter values.Then,the comparison results on 10 benchmark functions demonstrate that the HABC algorithm can obtain better final solutions and faster convergence speed.In the next step,we will focus on applying the HABC algorithm to combinatorial optimization problems, such as the allocation problems and scheduling problems.

[1]KARABOGA D.An idea based on honey bee swarm for numerical optimization.Kayseri,Turkey:Erciyes University,2005.

[2]KARABOGA D,BASTURK B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm.Journal of Global Optimization,2007,39(3):459–471.

[3]KARABOGA D,AKAY B.A comparative study of artificial bee colony algorithm.Applied Mathematics and Computation,2009,214(1):108–132.

[4]KARABOGA D,GORKEMLI B.Aquick artificial bee colony(qABC)algorithm and its performance on optimization problems.Applied Soft Computing,2014,23:227–238.

[5]TAHERI J,LEE Y C,ZOMAYA A Y,et al.A bee colony based optimization approach for simultaneous job scheduling and data replication in grid environment.Computers&Operations Research,2013,40(6):1564–1578.

[6]GUO J S,WANG Z T,ZHENG M F,et al.Uncertain multiobjective redundancy allocation problem of repairable systems based on artificial bee colony algorithm.Chinese Journal of Aeronautics,2014,27(6):1477–1487.

[7]BANHARNSAKUN A,ACHALAKUL T,SIRINAOVAKUL B.The best-so-far selection in artificial bee colony algorithm.Applied Soft Computing,2011,11(2):2888–2901.

[8]GAOWF,LIUSY.Amodified artificial bee colony algorithm.Computers&Operations Research,2012,39(3):687–697.

[9]YAN X H,ZHU Y L,CHEN H N,et al.A novel hybrid artificial bee colony algorithm with crossover operator for numerical optimization.Natural Computing,2015,14(1):169–184.

[10]LIU S Y,ZHANG P,ZHU M M.Artificial bee colony algorithm based on local search.Control and Decision,2014,29(1):123–128.

[11]ZHOU X Y,WU Z J,DENG C S,et al.Neighborhood search based artificial bee colony algorithm.Journal of Central South University,2015,46(2):534–546.

[12]KANG F,LI J J,LI H J.Artificial bee colony algorithm and pattern search hybridized for global optimization.Applied Soft Computing,2013,13(1):1781–1791.