Neural Comput & Applic DOI 10.1007/s00521-015-1851-x
ORIGINAL ARTICLE
A hybrid approach to artificial bee colony algorithm Lianbo Ma • Yunlong Zhu • Dingyi Zhang Ben Niu
•
Received: 16 August 2014 / Accepted: 11 February 2015 The Natural Computing Applications Forum 2015
Abstract In this paper, we put forward a hybrid approach based on the life cycle for the artificial bee colony algorithm to generate dynamical varying population as well as ensure appropriate balance between exploration and exploitation. The bee life-cycle model is firstly constructed, which means that each individual can reproduce or die dynamically throughout the searching process and population size can dynamically vary during execution. With the comprehensive learning, the bees incorporate the information of global best solution into the search equation for exploration, while the Powell’s search enables the bees deeply to exploit around the promising area. Finally, we instantiate a hybrid artificial bee colony (HABC) optimizer based on the proposed model, namely HABC. Comprehensive test experiments based on the well-known CEC 2014 benchmarks have been carried out to compare the performance of HABC against other bio-mimetic algorithms. Our numerical results prove the effectiveness of the L. Ma (&) Y. Zhu D. Zhang Laboratory of Information Service and Intelligent Control, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China e-mail:
[email protected] Y. Zhu e-mail:
[email protected] D. Zhang e-mail:
[email protected] L. Ma Key Laboratory of Networked Control System CAS, Shenyang 110016, China B. Niu College of Management, Shenzhen University, Shenzhen 518060, China e-mail:
[email protected]
proposed hybridization scheme and demonstrate the performance superiority of the proposed algorithm. Keywords Artificial bee colony algorithm Varying population Life cycle Comprehensive learning
1 Introduction Swarm intelligence (SI) has become a significant research subfield of artificial intelligence inspired by natural behavior of the swarm individuals [1–7]. The artificial bee colony (ABC) algorithm is a popular SI-based algorithm by simulating waggle dance and foraging behaviors of real honeybee colonies [8]. Due to the simple concept, easy implementation and fast convergence, ABC has attracted much attention and wide applications in numerical optimization domain [9, 10] and engineering applications [11– 14]. However, there are still some issues or limitations associated with this algorithm. For example, ABC becomes computationally inefficient after being easily trapped in the local optima. In addition, due to the random selection of the neighbor bee and dimension in the search equation of ABC, the information exchange between individuals is restricted in a random dimension, resulting in that the exploration is deemed not ‘‘global’’ enough. In other words, the quick exploration of the search space and the elaborate exploitation of potentially good solutions have become the two meaningful but contrary goals in ABC research. A number of significant modifications for ABC have been proposed to further improve its performance. For instance, the PSO-based search equation has been introduced to enhance the powerful global search in the early stage of ABC [15]. It integrates the information of the global best
123
Neural Comput & Applic
solution (gbest). Similarly, Banharnsakun et al. [16] has proposed an interesting improvement scheme; that is, the enhanced information share is achieved by incorporating the best-so-far solutions found among the entire population on the onlooker bee phase. Gao et al. [17] develop a hybrid ABC variant using the modified search equation and orthogonal learning strategies, which demonstrated its high effectiveness and efficiency. Several hybrid approaches to ABC also have been developed [18–21]. For example, the Rosenbrock ABC algorithm proposed by Kang et al. [20] utilizes a novel exploitation scheme using the Rosenbrock’s rotational direction method. In [22], the search equation of Gaussian artificial bee colony (GABC) algorithm was modified by adding a control parameter for appropriately balancing the Gaussian and the uniform distribution. However, the existing ABC variants are all built on the population-based modeling approach, in which all individual bees are identical as employed bees or onlooker bees and follow the same rules. Unfortunately, this will cause the loss of population diversity. Recent honeybee biological studies have revealed that the life-cycle mechanism serving as one of the essential evolution processes for honeybee survival, can significantly affect the individual behaviors and population dynamics of honeybees. Many simulation studies have been presented to model such population dynamics [23, 24]. Hence, this paper proposes a novel optimization scheme, namely hybrid artificial bee colony (HABC) algorithm, which synergizes the idea of the bee life-cycle model with a pool of optimal searching strategies including Powell’s search and comprehensive learning. The proposed HABC model is inherently different from others in the following aspects: (a)
(b)
(c)
To redefine the individual behaviors within the bee colony. This new life-cycle framework contains several states of forage, reproduction and death that shift periodically, which enables population size to dynamically vary according to the nutrient (nectar) dynamic change. This mechanism has a significant merit of reducing the computational complexity of the optimization process. To redefine the local search behaviors when a bee finds promising area. The Powell’s search is incorporated to emphasize the exploitation process. To redefine the bee-to-bee communication mechanism. The underlying idea behind comprehensive learning is to facilitate more information shared among bee colony as opposed to classical ABC that engaged in searching just the single individual.
The structure of the paper is as follows. Section 2 describes the canonical ABC algorithm in detail. In Sect. 3, the bee life-cycle model (BLCM) is presented and the proposed
123
HABC algorithm based on BLCM is given in Sect. 4. Section 5 presents the experimental studies of the proposed HABC and the other algorithms with descriptions of the involved benchmark functions, parameters settings and experimental results. Section 6 outlines the conclusions.
2 Canonical ABC algorithm In the canonical ABC algorithm, three kinds of ‘‘bees’’ are employed [7]: employed bees that explore specific nectar (food) sources and passing food information via dancing, onlooker bees that keep watch on the employed bees and scout bees searching for nectar sources randomly. Typically, each food source corresponds to only one employed bee, which means the population size of employed bees is equal to the number of food sources [7–9]. At the initial stage, the employed bees associated with specific food sources share food information with others. Afterward, the onlooker bees are responsible for selecting the locations of good food sources, and it is worth noting that the locations with relatively higher quality food sources are more likely to be chosen by the onlooker bees for exploitation. And then they further exploit the food near their selected food sources. If a food source found by employed bee is exhausted, it will be replaced with a new one by a newly produced scout. The fundamental mathematic representations are listed as follows. Step 1
Initialization phase.
In initialization phase, a group of food sources representing possible solutions are generated randomly by the following equation: xi;j ¼ xmin þ randð0; 1Þ xmax xmin ð1Þ j j j where i = 1, 2,…, SN, j = 1, 2,…, D. SN is the population size (the number of solutions). D denotes the number of and xmax represent variables, i.e., problem dimension. xmin j j the lower upper and upper bounds of the jth variable, respectively. Step 2
Employed bees’ phase.
In the employed bees’ phase, the neighbor food source (candidate solution) can be generated from the old food source of each employed bee in its memory using the following expression: vi;j ¼ xi;j þ u xi;j xk;j ð2Þ where k is a randomly chosen index representing a neighbor bee and should be different from current bee i; j is another randomly chosen index denoting a random variable; / denotes a number randomly falling into [-1, 1].
Neural Comput & Applic
Step 3
Onlooker bees’ phase.
In the onlooker bees’ phase, an onlooker bee selects a food source lying on the probability value linked with that corresponding food source; Pi can be defined as following expression: fitnessi Pi ¼ PSN j¼1 fitnessj
ð3Þ
where fitnessi denotes the fitness (quality) value of jth solution. Step 4
Scout bees’ phase.
In the scout bees’ phase, once a food source (potential solution) cannot be ameliorated further during a predetermined cycle (defined as ‘‘limit’’ in ABC), the food source should be replaced with a new one, while the employed bee associated with it subsequently becomes a scout. The new food source is generated randomly according to Eq. (1). Those procedures from steps 2 to 4 will be carried out repetitively until the termination condition is met.
3 The bees’ life-cycle model 3.1 Individual polyethism in honeybee colony In the biological science, the natural honeybee colony appears to maintain an appropriate dynamically balanced population, where each individual should undergo various phases identified by the individual polyethism [25, 26]. The termed polyethism is an intrinsic characteristic of the social Hymenoptera such as ants, bees, and wasps [27, 28], where worker’s age is according to the tasks it performs. Recent studies have revealed that an adult bee spends roughly its first 15 days performing tasks inside the hive, including brood care, and then switches to outside tasks, mainly foraging [29, 30]. Such polyethism is flexible and adaptively responsive to the social environment in a colony, which means that there are different behavioral stages associated with the natural or experimental changes in resource supply [31]. Furthermore, the honeybees with rich pollen supply demonstrate apparent proliferation; meantime, they will be eliminated from the colony if they live under a poor environment for a long time. This phenomenon indicates that the honeybee population should dynamically vary according to the different conditions to survive. Based on above empirical findings, our BLCM is constructed by three underlying elements as shown in Fig. 1: artificial bees that take on various attributes and behavioral features, the environment with gradient information where
artificial bees undertake different states and the interaction rules between artificial bees and environment. These elements operate together to construct an artificial biological ecology system. 3.2 Complex environment in BLCM The artificial environmental construction is an important factor in BLCM model, which can reflect the graduated complexity such as food distribution, nutrition gradient and boundary. In the natural ecology, honeybees can sense various environmental information through millions of years of evolution, which optimizes the honeybees foraging strategy that enables honeybees consider both the food amount in current position (i.e., fitness) and potential distributed tendency of the food source (i.e., nutrition gradient). To accomplish this modeling, two kinds of environmental information should be elaborately designed: objective function fitness that denotes the food amount and the gradient of function fitness that represents the gradient direction information of the selected food source. Let fi(t) represents the normalized objective function value of ith bee Xi at time t for a minimum problem, Ni(t) is the normalized gradient of function fitness obtained by the ith bee Xi at time t. The food information Fi by combining fit() and Ni(t) is used to evaluate the bee’s performance, which can be described as following. fit Xit fittworst fi ðtÞ ¼ t ð4Þ fitbest fittworst where fit(Xti) is the fitness of the ith bee Xi at time t and fitworst and fitbest are the maximum and minimum of the current position, respectively. Ni ðtÞ ¼
Nutritioni ðtÞ Nutritionworst Nutritionbest Nutritionworst
ð5Þ
where Nutrioni(t) is the gradient of function fitness obtained by the ith bee Xi at time t, which can be calculated as: Nutritioni ðtÞ þ 1 if fi ðt þ 1Þ [ fi ðtÞ Nutritioni ðt þ 1Þ ¼ Nutritioni ðtÞ 1 if fi ðt þ 1Þ\ fi ðtÞ ð6Þ For each Xi at onlooker bee phase, if fitness of the new position is better than older one, it can be viewed that distributed food tendency of the current environment is improved and the Nutritioni is added by one. Otherwise, the nutrient gradient of the ambient environment of Xi is getting worse and its Nutritioni is reduced by one. Then, the food information Fti deciding to reproduce or die for each bee Xi at time t is computed as:
123
Neural Comput & Applic
Artificial bees
Egg brood
Behaviors
Reproduction
Rules
Pupation & eclosion
Hive bees
Transition to foraging
Upgrowth
Forager bees Foraging
Social inhibition
Food availability affects transition rate to foraging
Consumption
Food collection by foragers
Death
Environment Food source
Nutrition gradient
Environmental boundary
Fig. 1 Population dynamic model of a honeybee colony
Hi ðtÞ Ni ðtÞ Fit ¼ g PSt þ ð1 gÞ PSt ; j¼1 Hj ðtÞ j¼1 Nj ðtÞ
g ½0; 1
ð7Þ
where St is the population size and g is a uniform random coefficient varying from 0 to 1. It is worthy noted that the gradient of function fitness used in the artificial environment is regarded as a way of escaping ‘‘optimization valleys.’’ Since an individual may get stuck around local optima, it is possible for the diversity of BLCM to change either gradually or suddenly to eliminate the accidents of being trapped into the local optima. In BLCM, according to Eq. (7), the Ni(t) helps the foraging bees move toward the position with higher fitness gradient, which means it is perhaps a potential area. 3.3 Artificial bee and its behavior in BLCM In our model, the termed artificial bees are classified into two groups: hive bees that are responsible for raising brood within the hive and foraging bees that gather food outside the hive [32, 33]. Note that the foraging bees consist of the employed bees and the onlooker bees with intelligent foraging behaviors derived from the ABC model. As shown in Fig. 1, a new individual at the brood stage enters the colony to be a hive bee through pupation and eclosion. Similarly, the hive bee can be transformed to a foraging bee according to the food availability [24]. The balance between forager and hive bees is assumed in our model to be maintained through social inhibition. The transmission of bees and the death rates of various stages depend strongly on colony conditions (e.g., pollen and nectar supply). To model such artificial honeybee evolution process, some assumptions should be made: Criterion 1 The life-cycle process of the honeybee colony can be divided into three stages: reproduction in which brood emerges as hive bee according to the food condition,
123
upgrowth in which hive bees become foragers and death in which an individual is eliminated from the population. Criterion 2 The termed population in the optimization algorithm can be initialized as foraging bees for searching global optima. If the colony faces better condition, the reproduction and upgrowth are enabled, in which one new hive bee can be created from brood stage as well as a new foraging bee is transmitted from a hive bee. Criterion 3 Once one honeybee has adopted the foraging role, it usually maintains that function until it die. The death stage is activated with the environmental nutrition exhausted, making the population decrease. According to Criterion 2, we assume that the transition from hive bee to forager is determined by food information Fti and a critical threshold of transition judgment is suggested, which if exceeded by Fti searched by the bee Xi would activate the reproduction and upgrowth stages. These can be calculated by the following equations. ðSt SÞ Fit [ max Freproduce ; Freproduce þ ð8Þ Fadapt where S is the initial population size, St is the current colony size and Freproduce and Fadapt are used to adjust the bee reproduction and upgrowth criterions. The new foraging bee transformed from a hive bee can be generated by utilizing a new search equation with best-so-far solution information among the employed and onlooker bees colony based on the works of [15, 16]: xnew; i;j ¼ xi;j þ uðxbest;j xi;j Þ
ð9Þ
where xnew is the new foraging bee, xi is the ith bee, xbest is best individual of current colony, and j is a randomly chosen indexes; / is a uniform random coefficient varying from 0 to 1.
Neural Comput & Applic
According to Criterion 3, if the bee Xi enters the bad environment and its Fti drops to a certain threshold as: ðSt SÞ t Fi \min 0; ð10Þ Fadapt The death stage is activated, and the bee should be discarded from the population. Here Fadapt is used to adjust the death criterions. It is worthy noted that the upgrowth stage activated with a new foraging bee transformed will enable the population size increase by one, and the death stage takes an opposite function. This will lead to that the population size dynamically varies in the foraging process [34, 35]. At the initial stage of the foraging process, the bee will reproduce when its food information rate is larger than Freproduce. In the course of bee foraging, in order to avoid the non-equilibrium condition with the termed population size too large or too small, the reproduction and death criterion, namely Eqs. (8) and (10), are delicately designed: If St exceeds S, the reproduce threshold value will increase by some amount; if St is smaller than S, the death threshold value will decrease. This strategy is more in accordance with the natural evolution processes: The competition among the entire population becomes dominant if there are too crowded individuals in the population, which is more inclined to the death process; oppositely, there will be apparent individual proliferation due to that the population is small with larger chances of surviving and reproducing in the distributed food environment.
4 Hybrid artificial bee colony algorithm based on BLCM Based on the BLCM, we also incorporate two optimal searching strategies to improve algorithm’s ability of balancing exploration and exploitation trade-off: a widely used local searching strategy called Powell’s method and the comprehensive learning based on a new search equation. 4.1 Powell’s pattern search Powell’s method, strictly Powell’s conjugate gradient descent method, is an effective algorithm proposed by Powell [36] for searching a local minimum of an objective function. This method pursues the minimum of the function by a bidirectional search along each search vector in turn. The new position can be then expressed as a linear combination of the search vectors. The new displacement vector becomes a new search vector and is added to the end of the search vector list. Coincidently, the search vector,
which contributed most to the new direction, is deleted from the search vector list. The algorithm iterates an arbitrary number of times until no significant improvement is made. The steps of the algorithm are given as follows.
4.2 Comprehensive learning In canonical ABC, the search equation of Eq. (2) for generating the positional change is much like a blind mutation operator by moving the old solution toward (or away from) another solution selected randomly from the population, which means that the probability that the randomly selected solution is a good solution is the same as that the randomly selected solution is a bad one, so the new candidate solution is not promising to be a solution better than the previous one. To address this concerning issue, inspired by the social learning in PSO model [4], a new search equation is employed in the employed and onlooker phases. To benefit from information of the best source foraged by the excellent bees, we assume that all bees can memory the best position they have reached and share the information to other bees. In the employed or onlooker phase, the bee’s choice of a new solution should not be governed by a probability distribution, while be dominated by the information combination of itself and its population members. Based on that assumption, the new search equation is defined as: xnew;i;j ¼ xi;j þ u1 xgbest;j xi;j þ u2 xpbest;j xi;j ð11Þ where xgbest is the global best of the population found so far and x, pbest is the ith bee’s personal historical best. According to Eq. (11), the gbest term can drive the new candidate solution toward the global best solution, as well as the pbest term can guide bee learn from its personal best experience. Hence, the modified solution search equation described by Eq. (11) can increase the global search ability of the algorithm.
123
Neural Comput & Applic
4.3 The proposed algorithm By integrating above three strategies, this work enriches the artificial bee foraging behaviors and extends the classical ABC framework to self-adaptive, cooperative and varying-population fashion that are capable of balance exploration and exploitation, as the following processes.
Algorithm 2: The proposed HABC algorithm Step 1: Initialization Step 1.1: Randomly generate SN food sources in the search space to form an initial population by Eq. (1)
Table 1 Parameters of the HABC HABC = (S,D, Freproduce, Fadapt, Tp, g) S D Freproduce Fadapt Tp g
Population size Dimensions of optimization problem Reproduction and death criterion Control parameter to adjust reproduction and death criterion Parameter to activate Powell’s search Inertia coefficient
In summary, in order to facilitate the below presentation and test formulation, we define a unified parameters for HABC model in Table 1 and the flowchart of HABC algorithm is summarized in Fig. 2.
Step 1.2: Evaluate the fitness of each bee Step 1.3: Set maximum cycles (LimitC) Step 2: Iteration = 0 Step. 3: Reproduction and death operations based on life-cycle model Step 3.1: Calculate the information rate of each bee in the population by Eq. (7) Step 3.2: If the criterion of reproduction determined by Eq. (8) is met, produce a new solution by Eq. (9), the population size increase by one Step 3.3: If the criterion of death determined by Eq. (10) is met, the population size reduce by one Step. 4: Employ bee phase: Loop over each food source
5 Benchmark test 5.1 Benchmark test suit Instead of the easy benchmarks, a set of 15 shifted and rotated benchmarks from CEC 2014 competitions (f1–f15) on real parameter optimization are employed [37–40], which are defined as follows. The dimensions, initialization ranges, global optimum of each function are listed in Table 2. Table 2 Parameters of CEC 2014 test functions
Step 4.1: Generate a candidate solution Vi by Eq. (11) and evaluate f(Vi)
F
Dimensions
Initial range
x
f ðx Þ
Step 4.2: Calculate the nutrient values Ni(t) by Eqs. (5) and (6)
f1
20/50
[-100, 100]D
O1
100
f2
20/50
[-100, 100]D
O2
200
Step 4.3: Greedy selection and memorize the better solution
f3
20/50
[-100, 100]D
O4
400
f4
20/50
[-100, 100]D
O5
500
f5
20/50
[-100, 100]
D
O6
600
f6
20/50
[-100, 100]D
O7
700
f7
20/50
[-100, 100]D
O8
800
f8
20/50
[-100, 100]D
O17
1700
f9
20/50
[-100, 100]D
O18
1800
f10
20/50
[-100, 100]
D
O19
1900
f11 f12
20/50 20/50
[-100, 100]D [-100, 100]D
O20 O23
2000 2300
f13
20/50
[-100, 100]D
O24
2400
f14
20/50
[-100, 100]D
O25
2500
f15
20/50
[-100, 100]D
O26
2600
Step. 5: Calculate the probability value pi by Eq. (3) Step. 6: Onlooker bee phase: Step 6.1: Generate a candidate solution Vi by Eq. (11) and evaluate f(Vi) Step 6.2: Calculate the nutrient values Ni(t) by Eq. (4) Step 6.3: Greedy selection and memorize the better solution Step. 7: Powell’s search phase If mode (Iteration, Tp) ==0, randomly choose m [ {1,…,SN} that has to be different from the best one, Xbest, generate a new solution Vs by Eq. (11). Use the Vs as a starting point and generate a new solution Vm by Powell’s method as illustrated in Algorithm 1 Step. 8: Iteration = Iteration ? 1 Step. 9: If the iteration is greater than LimitC, stop the procedure; otherwise, go to step 3 Step. 10: Output the best solution achieved
123
x* is the optimal solution; f(x*) is the best values of function; Oi is the shifted global optimum defined in ‘‘shift_data_x.txt,’’ which is randomly distributed in [-80, 80]D
Neural Comput & Applic Fig. 2 Flowchart of the HABC algorithm
Start Initialise: D -dim position X of the bee colony and evluate fitness of each bee
t =1
Determine whether reproduce or die according to F by Eq.(8) ,Eq.(10)
Life-cycle phase N
If the criterion of
N
If the criterion of
reproduction is met?
death is met?
Y
Y Remove current individual
Produce a new individual by Eq.(9)
Employed bee and onlooker bee operation: Update position by Eq.(11) and calculate nutrient by Eq.(5)
Mod (t , Tp ) == 0? Powell's search phase Set Xi as the starting point X 1 , di = ei, the tolerance for stop Set f (1) = f ( X 1 ), X c = X 1 , k = 1, i = 1
N
k ≥ 2?
i > D?
ε
Y
N
Y
X i +1 = X i + λi di , i = i + 1, λ is determined by Minim zing f (X i +1 )
di = di +1
d i +1 = ∑ 1 λi* d i = X D +1 − X D , X c (k + 1) = X D + 1 + λk di + 1, D
f (k + 1) = f ( X c (k + 1)), k = k + 1, X 1 = X c (k ), Δf = f (k ) − f (k − 1)
t = t +1 Y
t < LimitC ?
5.1.1 Some definitions for CEC 2014 All test functions are minimization problems defined as following: Min f(x) = [x1,x2,…,xD]T, where D is dimensions. There are several definitions used in the CEC 2014 functions as follows. Oi = [Oi1, Oi2,…,OiD]T: the shifted global optimum (defined in ‘‘shift_data_x.txt’’), which is randomly distributed in [-80, 80]D. Different from CEC 2013,
Δf < ε
N
N
End
each function has a shift data for CEC’14. All test functions are shifted to O and scalable. For convenience, the same search ranges are defined for all test functions (i.e., [-100, 100]D). Mi: rotation matrix. In CEC 2014, different rotation matrixes are assigned to each function and each basic function. Considering that in the real-world problems, it is seldom that there exist linkages among all variables. Meantime, the variables are divided into subcomponents
123
Neural Comput & Applic
randomly. The rotation matrix for each subcomponent is generated from standard normally distributed entries by Gram–Schmidt ortho-normalization with condition number c that is equal to 1 or 2.
where a ¼ 0:5; b ¼ 3; kmax ¼ 20: Griewank’s Function f70 ðxÞ ¼
D D Y X x2i xi cos pffi þ 1 4000 i¼1 i i¼1
5.1.2 Definitions of the basic functions for CEC 2014
Rastrigin’s Function
High Conditioned Elliptic Function
f80 ðxÞ ¼
f10 ðxÞ ¼
D X
ð106 Þ
i1 D1
x2i
ð12Þ
Bent Cigar Function ¼
x21
þ 10
6
x2i 10 cosð2pxi Þ þ 10
ð19Þ
i¼1
i¼1
f20 ðxÞ
D X
ð18Þ
D X
Modified Schwefel’s Function f90 ðxÞ ¼ 418:9829 D
D X
gðzi Þ;
i¼1
x2i
ð13Þ
ð20Þ
zi ¼ xi þ 4:209687462275036e þ 002
i¼2
8 > zi sinðjzi j1=2 Þ > > > < pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðzi 500Þ2 gðzi Þ ¼ ð500 modðzi ; 500ÞÞ sin j500 modðzi ; 500Þj 10000D > > 2 > pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi > : ðmodðjzi j; 500Þ 500Þ sin j mod ðjzi j; 500Þ 500j ðzi þ 500Þ 10000D
if
jzi j 500
if
ðzi Þ [ 500
if
ðzi Þ\ 500
ð21Þ
Discus Function f30 ðxÞ ¼ 106 x21 þ
D X
x2i
ð14Þ
i¼2
Rosenbrock’s Function f40 ðxÞ ¼
D1 X 100ðx2i xiþ1 Þ2 þ ðxi 1Þ2
ð15Þ
i¼1
Ackley’s Function 0
i¼1
vffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi1 u D u1 X 0 @ f5 ðxÞ ¼ 20 exp 0:2t x2 A D i¼1 i ! D 1X exp cosð2pxi Þ þ 20 þ e D i¼1
¼
kmax D X X
i¼1
k
k
a cosð2pb ðxi þ 0:5ÞÞ
k¼0
i¼1
0 ðxÞ ¼ f7 ðf4 ðx1 ; x2 ÞÞ þ f7 ðf4 ðx2 ; x3 ÞÞ f11 þ þ f7 ðf4 ðxD1 ; xD ÞÞ þ f7 ðf4 ðxD ; x1 ÞÞ
ð16Þ
ð23Þ
Expanded Scaffer’s F6 Function Scaffer’s F6 Function : pffiffiffiffiffiffiffiffiffiffiffiffiffiffi sin2 ð x2 þ y2 0:5Þ gðx; yÞ ¼ 0:5 þ ð1 þ 0:001ðx2 þ y2 ÞÞ2
!
k¼0
kmax X
k D a cosð2pbk xi 0:5Þ
123
ð22Þ
Expanded Griewank’s plus Rosenbrock’s Function
Weierstrass Function f60 ðxÞ
HGBat Function !2 !2 1=2 X D D X 0 f10 ðxÞ ¼ x2i xi i¼1 i¼1 ! D D X X þ 0:5 x2i þ xi =D þ 0:5
0 f12 ðxÞ ¼ gðx1 ; x2 Þ þ gðx2 ; x3 Þ þ þ gðxD1 ; xD Þ þ gðxD ; x1 Þ
ð17Þ
ð24Þ
Neural Comput & Applic
5.1.3 Definitions of the CEC’14 test suite
Hybrid Function 1
Unimodal functions
f8 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 1700 ð32Þ
Rotated High Conditioned Elliptic Function f1 ðxÞ ¼ f10 ðMðx o1 ÞÞ þ 100
ð25Þ
Rotated Bent Cigar Function f2 ðxÞ ¼ f20 ðMðx o1 ÞÞ þ 200
ð26Þ
where N = 3; p = [0.3,0.3,0.4]; g1: Modified Schwefel’s Function f90 ; g2: Rastrigin’s Function f80 ; g3: High Conditioned Elliptic Function f10 . Hybrid Function 2 f9 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 1800 ð33Þ
Multimodal functions Shifted and Rotated Rosenbrock’s Function 2:048ðx o4 Þ þ 1 þ 400 f3 ðxÞ ¼ f40 M 100
ð27Þ
Shifted and Rotated Weierstrass Function 0:5ðx o6 Þ 0 f5 ðxÞ ¼ f6 M þ 600 100 Shifted and Rotated Griewank’s Function 600ðx o7 Þ 0 f6 ðxÞ ¼ f7 M þ 700 100
ð28Þ
ð34Þ
ð29Þ
where N = 4; p = [0.2, 0.2, 0.3, 0.3]; g1: Griewank’s Function f70 ; g2: Weierstrass Function f60 ; g3: Rosenbrock’s Function f40 ; g4: Scaffer’s F6 Function: f120 . Hybrid Function 4 f11 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 2000
where N = 4; p = [0.2, 0.2, 0.3, 0.3]; g1: HGBat Function f100 ; g2: Discus Function f30 ; g3: Expanded Griewank’s plus Rosenbrock’s Function f110 ; g4: Rastrigin’s Function f80 . ð31Þ
Hybrid functions In this set of hybrid functions, the variables are randomly divided into some subcomponents and then different basic functions are used for different subcomponents. f ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ F ðxÞ where f(x) is hybrid function; gi(x) denote ith basic function used to construct the hybrid function; N is number of basic functions; z = [z1, z2,…, zN]. z1 ¼ ½yS1 ; yS2 ; . . .; ySn1 ; z2 ¼ ½ySn2 þ1 ; ySn2 þ2 ; . . .; ySn2 þn1 ; zN ¼ ½ySPN1 i¼1
n1þ1
; ySPN1 i¼1
n2þ1
ð35Þ
ð30Þ
Shifted Rastrigin’s Function 5:12ðx o8 Þ f7 ðxÞ ¼ f80 M þ 800 100
Hybrid Function 3 f10 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 1900
Shifted and Rotated Ackley’s Function f4 ðxÞ ¼ f50 ðMðx o1 ÞÞ þ 500
where N = 3; p = [0.3, 0.3, 0.4]; g1: Bent Cigar Function f20 ; g2: HGBat Function f100 ; g3: Rastrigin’s Function f80 .
Composition Function 1 f12 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 2300 ð36Þ where N = 5; r = [10, 20, 30, 40, 50]; k = [1, 1e-6, 1e26, 1e-6, 1e-6]; bias = [0, 100, 200, 300, 400]; g1: Rotated Rosenbrock’s Function f40 ; g2: High Conditioned Elliptic Function f10 ; g3: Rotated Bent Cigar Function f20 ; g4: Rotated Discus Function f30 ; g5: High Conditioned Elliptic Function f10 . Composition Function 2 f13 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 2400 ð37Þ
; . . .; ySD
y = x - oi, S = randperm(1: D). pi: used to control the percentage of gi(x). P ni: dimension for each basic function Ni¼1 ni ¼ D: n1 = [p1D], n2 = [p2D],…, NN-1 = [pN-1D], nN ¼ P D N1 i¼1 ni .
where N = 3; r = [20]; k = [1]; bias = [0, 100, 200]; g1: Schwefel’s Function f100 ; g2: Rotated Rastrigin’s Function f90 ; g3: Rotated HGBat Function f140 . Composition Function 3 f14 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 2500 ð38Þ
123
Neural Comput & Applic
where N = 3; r = [10, 30, 50]; k = [0.25, 1, 1e-7]; bias = [0, 100, 200]; g1: Rotated Schwefel’s Function f110 ; g2: Rotated Rastrigin’s Function f90 ; g3: Rotated High Conditioned Elliptic Function f10 . Composition Function 4 f15 ðxÞ ¼ g1 ðM1 z1 Þ þ g2 ðM2 z2 Þ þ þ gN ðMN zN Þ þ 2600 ð39Þ where N = 5; r = [10]; k = [0.25, 1, 1e-7, 2.5, 10]; bias = [0, 100, 200, 300, 400]; g1: Rotated Schwefel’s Function f110 ; g2: Rotated HappyCat Function f130 ; g3: Rotated High Conditioned Elliptic Function f10 ; g4: Rotated Weierstrass Function f60 ; g5: Rotated Griewank’s Function f70 . 5.2 Parameters settings In order to fully measure the performance of the proposed algorithm, six successful population-based algorithms are employed for comparison with HABC. • • • • • • •
Canonical particle swarm optimization with constriction factor (PSO) [4]; Classical artificial bee colony algorithm (ABC) [8]; Artificial bee colony algorithm with Powell’s method (PABC) [18]. Adaptive bacterial foraging optimization algorithm with life cycle and social learning (BFOLS) [41]. Genetic algorithm with elitism (EGA) [5]. Covariance matrix adaptation-evolution strategy (CMA-ES) [6]. Increasing-population covariance matrix adaptationevolution strategy (IPOP-CMA-ES) [42].
• •
Multi-swarm PSO (MPSO) [43]. Cooperative coevolutionary algorithm (CCEA) [44].
PSO and ABC are classical population-based paradigms simulating foraging behavior of social animals [4, 8]. PABC uses the similar local search strategy with HABC— Powell’s method to improve the exploitation ability [18]. BFOLS is an enhanced BFO variant using similar lifecycle strategy with HABC [41]. EGA is the classical genetic algorithm with elitist selection scheme [5]. CMA-ES is a successful ES variant using the covariance matrix of the mutation distribution guided by the useful information about search steps [6]. BIPOP-CMA-ES [42] is a multistart strategy using the original CMA-ES algorithm (with slightly modified parameter values) as the basic local search engine. MPSO [43] is a cooperative PSO model, cooperatively coevolving multiple PSO subpopulations. CCEA [44] is the earliest cooperative coevolutionary algorithm which applied the divide-and-conquer approach by Potter and Jone. To facilitate fair comparisons among population-based algorithms, all involved algorithms are tested by the following same parameters: the initial population size for each algorithm is 50; the maximum number of function evaluations is 100,000. For the other specific parameters for involved algorithms, we can follow parameters settings of the original literatures of ABC [8], PABC [18], BFOLC [41], PSO [5], EGA [5], CMA-ES [6], BIPOP-CMA-ES [42], MPSO [43] and CCEA [44], as summarized in Table 3. For the proposed HABC, corresponding parameters can be set as following: The inertia coefficient g = 0.6. The control parameters Tp, Freproduce and Fadapt should be tuned in detail in next section.
Table 3 Parameters setting for all algorithms Type
HABC
PABC
ABC
PSO
CMA-ES
BCOLS
EGA
BIPOP-CMAES
MPSO
CCEA
S
50
50
50
50
50
50
50
50
10
10
N
NA
NA
NA
NA
NA
NA
NA
NA
5
5
g
0.6
NA
NA
NA
NA
NA
NA
NA
NA
NA
Factor
NA
NA
NA
NA
NA
NA
NA
2
NA
NA
Tp
90
30
NA
NA
NA
NA
NA
NA
NA
NA
Freproduce/Fadapt
5/50
NA
NA
NA
NA
30/5
NA
NA
NA
NA
v/c1/c2
NA
NA
NA
0.729/ 2/2
NA
NA
NA
NA
0.729/ 2/2
NA
l/cr/dr/cc/ccov
NA
NA
NA
NA
12/0.1/20/0.12/ 0.08
NA
NA
12/0.1/20/0.12/ 0.08
NA
NA
Crossover/mutation rate
NA
NA
NA
NA
NA
NA
0.8/ 0.01
NA
NA
0.6/ 0.02
Cs/Ce
NA
NA
NA
NA
NA
0.1/0.0001 (Ub– Lb)
0.01
NA
NA
NA
Lb, the lower bound of variables; Ub, the upper bound of variables
123
Neural Comput & Applic Table 4 HABC’s results on nine test functions with different Tp
Func. (dimension)
20
40
60
80
100
Mean
1.87e?03
1.69e?03
1.41e103
2.18e?03
2.33e?03
SD
3.22e-20
2.92e-20
2.43e220
3.75e-20
4.02e-20
Mean
2.65e?02
2.00e102
2.40e?02
2.00e102
3.31e?02
SD
2.32e-15
0
2.04e-20
0
3.01e-15
Mean
6.19e?02
4.03e?02
4.01e102
5.31e?02
6.63e?02
SD
2.2565
1.7532
1.4623
1.9332
2.4212
Mean
6.88e?02
8.60e?02
5.20e102
8.02e?02
6.24e?02
SD
3.94e-01
4.93e-01
2.98e201
4.60e-01
3.58e-01
8.47e?02
6.40e102
6.40e102
6.40e102
1.06e?03
8.4743
9.8821
6.4232
7.6832
1.0698
Mean
2.30e?03
1.49e?03
1.49e103
1.49e103
2.46e?03
SD
1.23e?03
9.54e?02
7.95e102
1.05e?03
1.32e?03
Mean
2.65e?02
2.00e102
2.00e102
2.00e102
3.31e?02
SD
8.50e-14
9.91e-14
7.71e-14
6.42e214
1.06e-13
Mean
5.44e?02
6.34e?02
4.93e?02
4.11e102
6.80e?02
SD
1.39e?01
1.26e?01
1.05e101
1.62e?01
1.74e?01
Mean
6.88e?02
6.24e?02
5.20e102
8.02e?02
8.60e?02
SD
8.48e-01
7.69e-01
0.6409
9.89e-01
1.06e?00
Mean
1.22e?03
1.14e?03
8.88e?02
7.40e102
9.79e?02
SD
1.84e?01
1.71e?01
1.33e?01
1.11e101
1.47e?01
f1 (20)
f2 (20)
f3 (20)
f4 (20)
f5 (20) Mean SD f1 (50)
f2(50)
f3(50)
f4(50)
f5 (50) Best values are highlighted in bold
5.3 Sensitivity in relation to parameters of HABC 5.3.1 Effect of Tp for Powell’s search The experimental results of HABC with various Tp in optimizing 20-dimensional and 50-dimensional benchmarks f1–f5 are shown in Table 4. Tp is increased from 20 to 80 in steps of 20, which was relevant with the involved benchmark dimension D. The other parameters are assigned as follows: the control parameter Fadapt to adjust reproduction and death criterion is 50, and the reproduction and death criterion Freproduce is 5. The halted criteria are jfbest j\e, where e is a halted precision value setting ahead. The maximum number of function evaluations is set at 100,000. As for 20-dimensional test problems, from Table 4, it is clearly visible that Tp has a certain impact on the performance of the proposed algorithm. Too large or small values
of Tp make the fitness of objective function deteriorate. A lot of tuning experiments on this parameter indicate that when Tp was 60, HABC performed superior in terms of mean values and convergence rate on f1, f3, f4 and f5 (four out of the five test functions). As for 50-dimensional case, when Tp was 20 or 80, HABC can perform well on most benchmarks. Hence, according to the above results, Tp can be chosen equal to 60 as an optimal value for the next experiments.
5.3.2 Sensitivity in relation to Freproduce and Fadapt In this section, the similar experiments conducted on benchmarks f1–f5 are repeated to further investigate the effect of the parameters Freproduce and Fadapt. The experimental results in terms of mean values of 30 runs were
123
Neural Comput & Applic Table 5 Results of HABC on benchmarks f1–f5 with different Freproduce and Fadapt
Freproduce/Fadapt
0/20
5/20
10/20
0/50
5/50
10/50
f1 (20) Mean
5.43e?03
2.43e?03
5.65e?02
1.54e?03
1.02e102
2.34e?02
SD
4.83e-010
5.56e-015
6.32e-020
2.43e-010
3.43e2050
3.54e-20
Mean
2.43e?02
6.43e?02
2.03e?02
1.63e?03
2.12e102
2.45e?02
SD
1.46e-10
3.54e-07
2.65e-10
2.44e-05
3.53e-10
2.54e210
Mean
3.54e?03
7.34e?02
6.53e?02
2.04e?03
4.00e102
5.03e102
SD
4.54e-15
1.43e-14
5.34e-10
1.53e-20
0
2.54e-040
Mean
6.53e?02
8.43e?02
3.34e?03
8.43e?02
5.12e?02
5.02e102
SD
2.54e-30
3.54e-25
3.54e-25
6.54e-23
6.15e250
1.36e-25
f2 (20)
f3 (20)
f4 (20)
f5 (20) Mean SD f1 (50)
5.21e?03
6.43e?02
8.54e?02
9.54e?02
6.10e102
6.56?02
2.54e-010
3.43e2022
5.45e-020
8.34e-015
2.45e-020
4.54e-010
Mean
2.44e?03
1.49e103
1.99e?03
2.29e?03
1.49e103
1.50e?03
SD
1.30e?03
9.81e?02
1.06e?03
1.22e?03
7.95e102
9.53e?02
Mean
2.00e102
3.27e?02
2.17e?02
2.07e?02
2.00e102
2.00e102
SD
7.69e-14
1.05e-13
8.57e-14
9.85e-14
6.42e214
7.92e-14
Mean
4.93e?02
5.07e?02
5.48e?02
6.31e?02
4.12e102
4.12e102
SD
1.26e?01
1.30e?01
1.40e?01
1.61e?01
1.05e?01
1.02e101
Mean
6.23e?02
6.42e?02
6.94e?02
7.98e?02
5.20e102
8.50e?02
SD
7.68e-01
7.91e-01
8.55e-01
9.83e-01
6.41e201
1.05e?00
f2 (50)
f3 (50)
f4 (50)
f5 (50)
In bold are the best results
Mean
8.87e?02
9.13e?02
9.87e?02
1.14e?03
7.40e102
1.21e?03
SD
1.33e?01
1.37e?01
1.48e?01
1.70e?01
1.11e101
1.81e?01
illustrated Table 5. The values of Freproduce were settled as 0, 5, 90 and 10, while the relevant Fadapt was chosen to be 20 or 50. The values of the control parameter Tp is 60. From Table 5, it was clearly visible that these parameters had a certain impact on the performance of the proposed algorithm. As for 20-dimensional case, when Freproduce/Fadapt were 5/50, HABC achieved most best experimental results in terms of mean values and standard deviations on all involved benchmarks except f4. For the only benchmark f4, HABC with Freproduce/Fadapt equaling to 10/50 performed just a little better than with Freproduce/ Fadapt equaling to 5/50. As for 50-dimensional case, the similar results are obtained that the optimal setting for Freproduce/Fadapt is 5/50. Hence, according to the above results, Freproduce/Fadapt can be chosen equal to 5/50 as an optimal value for the next experiments.
123
5.4 Experiment 1: numerical results and comparison 5.4.1 Results for the 20-dimensional problems The statistical results tabulated in Table 6 have been simulated on a suit of 15 CEC 2005 benchmarks with 20 variables (20-D functions) by taking 30 independent runs of each competing algorithm. The termination criterion in this experiment is to run HABC until the number of function evaluations reaches the maximum value 100,000. Table 6 shows the statistical values including the maximum, mean, minimum and standard deviation values of the 30 trial results where the best results among those algorithms are shown in bold. Figure 3a–g demonstrate the average convergence rates of each algorithm for each benchmark.
Neural Comput & Applic Table 6 Performances of all algorithms on 20-dimensional CEC 2014 test suite Func.
HABC
PABC
BFOLS
ABC
CMA_ES
PSO
EGA
Mean
1.0000e102
8.5712e?06
1.8049e?08
1.5994e?07
6.3569e?05
1.2378e?07
2.5214e?08
SD
3.2602e215
4.3865e?06
1.5528e?08
5.6903e?06
3.0645e?05
1.4113e?07
1.8788e?08
Min
1.0000e102
2.3869e?06
6.2867e?06
6.7591e?06
1.9293e?05
1.4667e?06
2.9189e?07
Max
1.0000e102
1.9355e?07
5.4018e?08
2.9257e?07
1.3441e?06
5.1707e?07
7.2068e?08
Mean
2.0000e102
1.2593e?05
1.6679e?10
1.4561e?03
1.7852e?04
1.4033e?08
6.2534e?08
SD
0
3.9657e?05
7.2351e?09
1.8033e?03
1.2928e?04
3.4203e?08
3.6051e?08
Min
2.0000e102
4.7031e?02
2.9232e?09
2.2217e?02
3.0598e?02
1.2730e?07
2.3314e?08
Max
2.0000e102
1.8037e?06
3.1489e?10
7.8098e?03
3.3572e?04
1.4886e?09
1.5218e?09
f3 Mean
f1
f2
4.0060e102
5.2950e?02
1.5965e?03
4.5892e?02
4.6635e?02
5.4182e?02
7.7484e?02
SD
1.4605
3.7082e?01
8.2700e?02
2.8298e?01
3.7064e?01
4.0474e?01
8.2786e?01
Min
4.0000e102
4.6299e?02
6.0895e?02
4.0399e?02
4.0173e?02
4.8132e?02
6.3742e?02
Max
4.0399e102
6.0216e?02
3.9749e?03
4.8162e?02
5.3177e?02
6.3365e?02
9.3590e?02
Mean
5.2010e?02
5.2001e?02
5.2013e?02
5.2040e?02
5.2000e102
5.2037e?02
5.2104e?02
SD
2.9889e-01
2.3186e-02
1.7483e-01
3.1761e-02
2.8083e206
1.0156e-01
8.9720e-02
Min
5.2000e102
5.2000e?02
5.2000e?02
5.2031e?02
5.2000e102
5.2015e?02
5.2086e?02
Max
5.2101e?02
5.2010e?02
5.2048e?02
5.2046e?02
5.2000e102
5.2058e?02
5.2116e?02
Mean
6.4049e?02
6.2365e?02
6.2600e?02
6.1654e102
6.2270e?02
6.2962e?02
6.4206e?02
SD
6.4002
2.8510
4.2240
1.5997
2.7656
3.5530
2.0144
Min
6.3094e?02
6.1936e?02
6.1604e?02
6.1193e102
6.1644e?02
6.2041e?02
6.3781e?02
Max
6.4807e?02
6.2996e?02
6.3327e?02
6.1923e102
6.2678e?02
6.3550e?02
6.4473e?02
Mean SD
7.0001e?02 3.8574e-03
7.0028e?02 2.0946e-01
8.7898e?02 9.2969e?01
7.0010e?02 8.2189e-02
7.0000e102 1.9752e204
7.0273e?02 3.3539
8.2857e?02 3.1718e?01
Min
7.0000e?02
7.0008e?02
7.5428e?02
7.0000e?02
7.0000e102
7.0105e?02
7.7921e?02
Max
7.0001e102
7.0081e?02
1.0588e?03
7.0027e?02
7.0001e102
7.1088e?02
8.8828e?02
Mean
9.3860e?02
8.1638e?02
9.2430e?02
8.0000e102
8.0214e?02
1.2318e?03
1.0913e?03
SD
2.1324e?01
6.8495
2.9543e?01
2.1888e204
1.6547
9.2917e?01
2.9524e?01
Min
9.0607e?02
8.0796e?02
8.6865e?02
8.0000e102
8.0000e?02
1.1025e?03
1.0219e?03
Max
9.7852e?02
8.3583e?02
9.7511e?02
8.0001e102
8.0697e?02
1.3811e?03
1.1627e?03
Mean
3.5423e103
3.1461e?06
1.7138e?07
4.9890e?06
4.0571e?05
4.9941e?05
5.0248e?07
SD
5.2122e102
2.6133e?06
1.5370e?07
2.5510e?06
2.2561e?05
6.8161e?05
3.8463e?07
Min
2.6382e103
2.6598e?05
1.7367e?06
1.3727e?06
9.4013e?04
2.7363e?04
4.2202e?06
Max
4.6532e103
1.1531e?07
5.7275e?07
1.0093e?07
7.5230e?05
2.0373e?06
1.2366e?08
Mean SD
2.2869e103 1.5032e102
6.2590e?03 4.5331e?03
1.2133e?08 3.2761e?08
1.5080e?04 8.7779e?03
4.9241e?03 4.4261e?03
5.0709e?03 3.9156e?03
6.6773e?06 5.0399e?06
Min
2.1077e?03
1.9935e?03
1.9965e?03
5.2362e?03
1.8886e103
2.0287e?03
1.1313e?06
Max
2.6569e?03
1.8110e?04
1.2991e?09
3.1342e?04
1.7150e?04
1.9249e103
2.0834e?07
Mean
1.9175e?03
1.9218e?03
2.0001e?03
1.9167e?03
1.9083e103
1.9299e?03
2.0930e?03
SD
1.5664
2.3616e?01
8.3018e?01
2.1563e?01
9.8475e201
2.5001e?01
9.5803e?01
f4
f5
f6
f7
f8
f9
f10
123
Neural Comput & Applic Table 6 continued Func.
HABC
PABC
BFOLS
ABC
CMA_ES
PSO
EGA
Min
1.9137e?03
1.9070e?03
1.9126e?03
1.9065e?03
1.9056e103
1.9143e?03
2.0030e?03
Max
1.920e?03
1.9826e?03
1.9875e?03
1.9875e?03
1.9095e103
1.987e?03
2.334e?03
f11 Mean
2.7453e103
1.5719e?04
3.9508e?03
9.4246e?03
3.9508e?03
3.1817e?03
4.8650e?04
SD
4.3419e102
5.4654e?03
2.8427e?03
4.4497e?03
2.8427e?03
8.1783e?02
2.2421e?04
Min
2.2658e103
5.4742e?03
2.1302e?03
4.9291e?03
2.1302e?03
2.3122e?03
6.7335e?03
Max
4.0191e103
2.4070e?04
1.3648e?04
2.4228e?04
1.3648e?04
4.7922e?03
8.6894e?04
Mean
2.6140e103
2.6161e?03
2.6153e?03
2.6156e?03
2.6153e?03
2.6191e?03
2.7782e?03
SD
8.4755e213
8.4394e-01
6.6770e-03
3.5540e-01
6.6770e-03
2.8964
4.0295e?01
Min
2.6140e103
2.6155e?03
2.6153e?03
2.6153e?03
2.6153e?03
2.6154e?03
2.7206e?03
Max
2.6140e103
2.6192e?03
2.6153e?03
2.6165e?03
2.6153e?03
2.6265e?03
2.8812e?03
Mean
2.7323e?03
2.6308e?03
2.6280e103
2.6288e?03
2.6288e?03
2.6473e?03
2.8117e?03
SD
2.3557e?02
2.6498
7.3929e201
3.8526
3.8526
8.3163
2.2537e?01
Min
2.6260e?03
2.6229e?03
2.6262e103
2.6218e?03
2.6218e?03
2.6300e?03
2.7654e?03
Max
3.5831e?03
2.6350e?03
2.6295e103
2.6424e?03
2.6424e?03
2.6585e?03
2.8396e?03
f14 Mean
2.7013e103
2.7227e?03
2.7216e?03
2.7103e?03
2.7216e?03
2.7195e?03
2.7566e?03
SD
5.0770
6.1581
6.1232
1.8608
6.1232
5.8866
9.6087
Min
2.7002e103
2.7138e?03
2.7108e?03
2.7076e?03
2.7108e?03
2.7088e?03
2.7392e?03
Max
2.7229e103
2.7362e?03
2.7351e?03
2.7131e?03
2.7351e?03
2.7309e?03
2.7737e?03
Mean
2.7105e?03
2.7005e103
2.7304e?03
2.7704e?03
2.7304e?03
2.7655e?03
2.7389e?03
SD
3.0618e?01
6.0912e202
4.6751e?01
4.6916e?01
4.6751e?01
4.8545e?01
5.2490e?01
Min
2.7003e?03
2.7004e103
2.004e?03
2.7004e?03
2.7004e?03
2.7004e?03
2.7049e?03
Max
2.8000e?03
2.7006e103
2.8001e?03
2.8007e?03
2.8001e?03
2.8007e?03
2.8546e?03
f12
f13
f15
In bold are the best results
Table 6 demonstrates that HABC achieves approving results on most of the 15 functions. As for the benchmarks f1, f2, f3, f4, f5, f6, f8, f10 and f15, the maximum, mean and minimum values of the 30 runs are all equal or very close to the optimal values listed in Table 2. But when solving the functions f7, f9, f11, f12, f13 and f14, HABC does not get accurate optimal results. For these hybrid and composition functions, most of the solutions are obviously worse than the optimal values. The reason for the poor performance is that the four composition functions (f12–f15) are more challenging problems with randomly located global optimum and several randomly located deep local optima. They are asymmetrical multimodal problems, with different properties in different areas. Due to the complex shape of the composition functions, it is difficult to get the same accurate results as the benchmark functions. However, when compared to other algorithms, HABC seems somewhat superior. From Table 6, HABC performs much better than the original ABC and the other compared algorithms in solving most of the test functions, including
123
f1, f2, f3, f8, f9, f11, f12 and f14. Particularly, HABC finds the global minimum of the function f2 every run and can also consistently find the minimum of multimodal function f1 and f5 within relatively fewer FEs. For minority of the functions, i.e., f4, f5, f6, f10, f13 and f15, HABC performs slightly worse than CMA-ES and PABC. Fortunately, in our experimental scenario, there was no benchmark on which HABC did obviously worse than the compared algorithms. From Fig. 3, we can observe that HABC is the fastest one for finding good results on most benchmarks within relatively few generations. 5.4.2 Results for the 50-dimensional problems Table 7 lists the statistical results of each involved algorithm in optimizing a suit of 50-dimensional benchmarks based on 30 independent runs. The maximum number of function evaluations is set at 500,000. The other parameters are the same as those for 20-D benchmarks. From the experimental results in terms of the maximum, mean, minimum and
Neural Comput & Applic
6
10
Fitness(log)
8
8 6
4
4
2
2
0
2
4
6
HABC PABC BFOLS ABC CMA-ES PSO EGA
8
10
0
2
4
10
2.7165
4
6
8
evaluationCount
2.81 2.805 2.8
2.79
10
0
2
4
6
8
6
8
evaluationCount
6
4
0
2
4
3.4
6
8
10
6
4
0
2
4
6
8
3.45
(m)
3.6
x 10
0
2
6
8
10 x 10 4
6
8
10
x 10 4
3.65
HABC PABC BFOLS ABC CMA-ES PSO EGA
3.55 3.5
3.4
4
evaluationCount
4
HABC PABC BFOLS ABC CMA-ES PSO EGA
3.6
3.45
evaluationCount
10
x 10 4
HABC PABC BFOLS ABC CMA-ES PSO EGA
3.8
3.2
10
Fitness(log)
3.5
8
(l)
3.6
Fitness(log)
3.55
6
4
3.65
3.6
4
evaluationCount
(k) HABC PABC BFOLS ABC CMA-ES PSO EGA
4
2
3.4
evaluationCount
3.65
2
0
(i)
8
2
10
10
x 10 4
4.2
(j)
0
8
x 10 4
HABC PABC BFOLS ABC CMA-ES PSO EGA
x 10 4
evaluationCount
Fitness(log)
8
Fitness(log)
3.6
Fitness(log)
Fitness(log)
3.8
8
HABC PABC BFOLS ABC CMA-ES PSO EGA
6
2
10 HABC PABC BFOLS ABC CMA-ES PSO EGA
6
10
(h)
4
3.4
6
evaluationCount
x 10 4
4.2
4
4
4
(g)
2
2
12
HABC PABC BFOLS ABC CMA-ES PSO EGA
8
2
10
10 x 10 4
(f)
2.95
0
0
evaluationCount
Fitness(log)
3
Fitness(log)
3.1 3.05
4
3.2
2.8
10
10
HABC PABC BFOLS ABC CMA-ES PSO EGA
2
3.4
x 10 4
evaluationCount
x 10 4
3.2
8
HABC PABC BFOLS ABC CMA-ES PSO EGA
3.6
(e)
3.15
6
3
(d)
0
4
3.8
HABC PABC BFOLS ABC CMA-ES PSO EGA
2.795
2
2
evaluationCount
Fitness(log)
2.717
0
0
x 10 4
(c)
2.815
Fitness(log)
Fitness(log)
8
2.5
2.82
HABC PABC BFOLS ABC CMA-ES PSO EGA
2.7175
3.2
4 3.5
(b)
2.718
Fitness(log)
6
evaluationCount
(a)
2.716
4.5
3
x 10 4
evaluationCount
HABC PABC BFOLS ABC CMA-ES PSO EGA
5
Fitness(log)
HABC PABC BFOLS ABC CMA-ES PSO EGA
10
Fitness(log)
5.5
12
12
3.55 3.5 3.45
0
2
4
6
evaluationCount
(n)
8
10 x 10 4
3.4
0
2
4
6
evaluationCount
8
10
x 10 4
(o)
Fig. 3 Median convergence results of all algorithms on 20-dimenstional CEC 2014 functions. a–o Correspond to 20-dimensional f1–f15, respectively
123
Neural Comput & Applic Table 7 Performances of all algorithms on 50-dimensional CEC 2014 test suite Func.
HABC
PABC
BFOLS
ABC
CMA_ES
PSO
EGA
Mean
1.4921e103
1.2786e?08
8.2059e?08
1.0434e?08
2.0372e?08
1.3168e?08
3.8636e?08
SD
7.9519e102
5.0397e?07
2.6638e?084
1.3511e?07
4.1411e?06
5.1731e?07
1.1880e?08
Min
4.0151e102
5.1886e?07
4.2723e?08
7.7926e?07
1.2095e?07
5.8996e?07
1.9161e?08
Max
3.2163e103
2.6429e?08
1.3557e?09
1.3893e?08
2.7317e?07
2.8013e?08
5.5432e?08
Mean
2.0000e102
5.1720e?10
1.9761e?11
9.2284e?04
1.9964e?08
8.9402e?09
1.4597e?11
SD
6.4218e214
1.4309e?10
1.4684e?10
9.2622e?04
2.6775e?08
4.0474e?09
4.2153e?10
Min
2.0000e102
2.2630e?10
1.6777e?11
5.7512e?03
1.2407e?07
4.2277e?09
7.6506e?10
f1
f2
Max
2.0000e102
7.8858e?10
2.2488e?11
4.2771e?05
1.2456e?09
2.0814e?10
2.2948e?11
f3 Mean
4.1074102
6.3108e?03
2.5346e?04
5.9294e?02
9.4061e?02
1.1825e?03
2.3665e?03
SD
1.0484e101
5.7318e?03
7.9890e?04
2.8561e?01
2.5262e?02
2.9583e?02
2.5999e?02
Min
4.0000e102
1.7459e?03
1.1793e?04
5.3644e?02
6.9752e?02
8.9842e?02
1.9496e?03
Max
4.2552e102
2.8029e?04
4.1009e?04
6.5330e?02
1.8900e?03
2.0880e?03
2.8824e?03 5.2143e?02
f4 Mean
5.2041e?02
5.2037e?02
5.2024e?02
5.2085e?02
5.2001e102
5.2104e?02
SD
0.6409
0.0595
0.2650
0.0345
0.0165
0.0663
0.0217
Min
5.2000e?02
5.2029e?02
5.2000e?02
5.2077e?02
5.2000e102
5.2093e?02
5.2138e?02
Max
5.2140e?02
5.2048e?02
5.2081e?02
5.2092e?02
5.2006e102
5.2118e?02
5.2147e?02
Mean
7.4035e?02
6.9612e102
7.3707e?02
7.3083.e?02
7.1731e?02
7.4248e?02
7.6720e?02
SD
1.1078e?01
2.9545
1.1954e?01
5.6752
6.0173
6.9284
3.4163
Min
7.1648e?02
6.9130e102
7.0979e?02
7.1838e?02
7.0817e?02
7.3031e?02
7.6110e?02
Max
7.6461e?02
7.0141e102
7.5583e?02
7.3888e?02
7.3068e?02
7.5719e?02
7.7370e?02
Mean SD
7.0000e102 4.9440e203
1.0952e?03 1.1760e?02
2.6341e?03 1.8596e?02
7.0006e?02 2.6791e-02
7.0490e?02 4.0241
7.8424e?02 5.0649e?01
2.5361e?03 2.7590e?02
Min
7.0000e102
9.4421e?02
2.2572e?03
7.0003e?02
7.0130e?02
7.3993e?02
2.0665e?03
Max
7.0002e102
1.3831e?03
2.9432e?03
7.0012e?02
7.1783e?02
9.6113e?02
3.1127e?03
Mean
8.0973e102
1.2396e?03
1.7525e?03
2.3263e?03
9.4351e?02
1.5865e?03
2.4698e?03
SD
1.8709
5.02432e?01
6.8980e?01
1.6652e?02
2.3242e?01
4.0260e?01
1.1034e?02
Min
8.0731e102
1.1281e?03
1.6127e?03
2.0616e?03
9.0813e?02
1.4976e?03
2.2406e?03
Max
8.1416e102
1.3207e?03
1.8727e?03
2.6576e?03
1.0079e?03
1.6744e?03
2.6962e?03
Mean
2.9532e105
3.0928e?08
5.8451e?08
4.5617e?07
1.3680e?08
1.0850e?07
2.4217e?08
SD
1.4335e105
1.2987e?08
2.6740e?08
1.1038e?07
5.9902e?07
4.7608e?06
7.1037e?07
Min
9.4318e104
1.1979e?08
1.6970e?08
2.9109e?07
3.9430e?07
4.5338e?06
1.0851e?08
Max
7.4857e105
6.2698e?08
1.1283e?09
6.6359e?07
2.8482e?08
2.3804e?07
3.8794e?08
Mean SD
3.8296e103 3.0287e102
9.6613e?09 3.7999e?09
2.3075e?10 5.2333e?09
5.1388e?05 3.4058e?05
6.9184e?09 3.5451e?09
6.2238e?07 1.3061e?08
2.5266e?09 8.8145e?08
Min
3.3224e103
3.6959e?09
1.4115e?10
1.1706e?05
1.8936e?09
2.9732e?06
1.1668e?09
Max
4.4704e103
2.0751e?10
3.2519e?10
1.5096e?06
1.3158e?10
4.2299e?08
4.4927e?09
Mean
1.9785e103
3.2547e?03
2.0058e?03
5.8705e?03
2.2342e?03
2.1407e?03
3.0637e?03
SD
2.5014e?01
6.4250e?02
1.7046e101
1.2471e?03
1.8454e?02
6.4739e?01
2.1329e?02
f5
f6
f7
f8
f9
f10
123
Neural Comput & Applic Table 7 continued Func.
HABC
PABC
BFOLS
ABC
CMA_ES
PSO
EGA
Min
1.9601e103
2.4479e?03
1.9793e?03
3.7542e?03
2.0242e?03
2.0631e?03
2.6400e?03
Max
2.0407e?03
4.5998e?03
2.0285e103
8.6992e?03
2.6786e?03
2.2889e?03
3.3589e?03
f11 Mean
4.7373e?05
2.0716e?05
6.2074e?04
1.1618e?05
8.6992e103
5.5121e?04
2.5526e?05
SD
3.2841e?05
6.0638e?04
2.3391e?04
1.8153e104
1.2497e?05
2.2503e?04
7.6170e?04
Min
1.4728e?05
1.1198e?05
2.6740e104
6.9809e?04
8.1492e?04
1.6040e?04
1.3504e?05
Max
1.3364e?06
3.1621e?05
1.1364e?05
1.4996e?05
6.4115e?05
9.9848e104
4.7047e?05
Mean
2.5001e103
2.6988e?03
2.6455e?03
2.6532e?03
2.6529e?03
2.7595e?03
4.1771e?03
SD
7.3251e-01
1.1776e?01
7.3251e-01
3.8428
1.3296
2.7302e?01
2.8541e?02
Min
2.500e103
2.6812e?03
2.6451e?03
2.6487e?03
2.6512e?03
2.7207e?03
3.7712e?03
Max
2.5010e103
2.7233e?03
2.6484e?03
2.6662e?03
2.6568e?03
2.8134e?03
4.8776e?03
Mean
2.6010e103
2.8628e?03
3.2361e?03
2.7679e?03
2.7624e?03
2.9847e?03
3.7985e?03
SD
3.5321e220
2.2780e?01
8.4682e?02
1.9890
6.7360
3.9038e?01
1.2087e?02
Min
2.6000e103
2.8282e?03
2.8003e?03
2.7648e?03
2.7394e?03
2.9160e?03
3.4957e?03
Max
2.6020e103
2.9094e?03
5.7318e?03
2.7732e?03
2.7712e?03
3.0528e?03
4.0197e?03
f14 Mean
2.7000e103
2.8558e?03
2.7032e?03
2.7653e?03
2.8244e?03
2.8291e?03
3.2556e?03
SD
3.6133e201
2.0859e?01
1.4321e-01
5.4552
1.6263e?01
1.3881e?01
1.0201e?02
Min
2.7014e103
2.8281e?03
2.7010e?03
2.7552e?03
2.7965e?03
2.8111e?03
3.1018e?03
Max
2.7029e103
2.9072e?03
2.7100e?03
2.7747e?03
2.8506e?03
2.8651e?03
3.4156e?03
2.7902e103
2.8097e?03
2.8002e?03
2.7920e?03
2.8010e?03
2.8074e?03
3.1709e?03
f12
f13
f15 Mean SD
3.0598e101
3.2117
1.5342
3.9365e?01
2.0475e-01
1.6886
5.6717e?01
Min
2.7007e103
2.8050e?03
2.8001e?03
2.7007e?03
2.8007e?03
2.8053e?03
3.0806e?03
Max
2.8008e103
2.8154e?03
2.8020e?03
2.8108e?03
2.8016e?03
2.8116e?03
3.2754e?03
In bold are the best results
standard deviation values shown in Table 7, it is observed that the proposed HABC achieves even better ranking than that in the 20-D test problems. HABC performs best on 12 out of the 15 CEC 2005 functions, including f1, f2, f3, f6, f7, f8, f9, f10, f12, f13, f14 and f15. Furthermore, on the more complex hybrid and composition functions (f8–f11, f12–f15), HABC cannot solve these functions effectively, but it still obtains the best results among all the involved algorithms. Although the 50-D functions become more difficult to be tacked than their 20-D counterparts, HABC still performs significantly powerful on most test cases, which means that HABC using three effective strategies is more competent in tackling complex problems. Additionally, in order to further demonstrate the performance of HABC, three competitive algorithms, namely IPOP-CMA-ES, MPSO and CCEA, are employed to further compare with HABC on a suite of ten 50-D functions including f1, f2, f3, f4, f5, f6, f7, f8 f9 and f10. Results have
been averaged on 30 independent runs, and the mean and standard deviation values are given in Table 8. From Table 8, compared with MPSO and CCEA, HABC can obtain significantly better results on most benchmarks, which indicates its superiority. When compared to IPOP-CMA-ES, HABC seems a little laggard, because HABC did not obtain the accurate optimal solutions on f1, f3 and f8, but IPOP-CMA-ES got them. However, HABC still performs powerfully on some functions, such as f2, f5, f9 and f10. The experimental results on these benchmarks suggest that the life-cycle mechanism improves the performance of HABC in terms of tracking and locating multiple optima in a complex fitness landscape. In life-cycle model, a bee can shift its states (i.e., born, reproduction, upgrowth and death) periodically according to the environment (nectar) dynamic change, resulting in that the population size and the foraging behavior can be dynamically adaptive to the
123
Neural Comput & Applic Table 8 Performances of four involved algorithms on ten 50-D CEC 2014 test suite
Func.
HABC
IPOPCMA_ES
MPSO
CCEA
f1 Mean
1.4922e?03
1.0000e102
6.5423e?03
7.6532e?03
SD
3.9518e?01
1.7632e201
2.0923e?01
3.4123e?02
Mean
2.0000e102
2.0000e102
5.5000?02
4.5000e?02\
SD
6.6533e214
1.6232
5.6523
2.5632e?01
f2
f3 Mean
4.1002?02
4.0000e102
5.6533e?02
4.9862e?02
SD
1.0056e?01
2.7432e201
3.6558e-01
3.5638e?01
f4 Mean
5.2032e?02
5.0000e102
7.7845e?02
6.8756e?02
SD
0.6321
2.3412e?02
3.7835
2.8945e?02
f5 Mean
7.0000e102
7.0000e102
7.0000e102
7.0125e?02
SD
4.9345e203
2.7645e-02
2.6436e-02
6.7645e?01
f6 Mean
7.0000e102
7.0000e102
7.0545e?02
1.0435e?03
SD
4.9094e-03
1.3253e205
3.7644e-03
1.7642e?01
Mean
8.1523e?02
8.0001e102
2.0085e?03-
8.0001e103
SD
1.7812
6.2231e?01
2.5621e?01
5.0231
f7
f8 Mean
2.9487e?05
1.9000e103
2.0212e?04
2.4345e?04
SD
1.5872e?05
1.7129e102
2.7524e?02
2.5127e?03
Mean
3.7812e103
3.8100e?03
5.2342e?03
6.8754e?04
SD
3.0387e102
4.1265e?02
3.7534e?02
6.9545e?02
Mean
1.9231e103
1.9500e?03
2.2873e?03
2.7645e?03?
SD
2.6123e?01
4.0232e202
3.9834e-02
6.0434
f9
f10 Best values are highlighted in bold
Table 9 Wilcoxon signed-rank test results. HABC shows an improvement over PABC, BFOLS, ABC, CMA_ES, PSO and EGA in terms of averaged value Comparison
R-
R?
p values
HABC versus PABC
1.1322
1.0192e?02
2.1232e-02
HABC versus BFOLS
2.1022e?01
9.1022e?01
9.2032e-02
HABC versus ABC
4.1302e-01
9.2830e?01
2.2332e-02
HABC versus CMA_ES HABC versus PSO
1.2330e?01 1.2130
9.4530e?01 1.0310e?02
4.3243e-02 5.2338e-03
HABC versus EGA
1.5460
1.2120e?02
1.6375e-02
complexity of the objective functions, which also reduces the computational complexity of the optimization process by altering different operations. In addition, the comprehensive learning serves as the enhanced information exchange strategy helping HABC quickly explore the nearoptimal area, while the Powell’s search will be adapted to
123
fine tune the best solutions found by HABC. The effect of such life-cycle mechanism will be investigated in detail in next experiment. 5.4.3 Statistical result analysis 5.4.3.1 Pairwise comparisons using Wilcoxon’s test Wilcoxon’s test serves as the pairwise comparison criterion to identify significant differences between two sample methods [45]. When using Wilcoxon’s test in our experimental study, the first step is to compute the R? and R- related to the comparisons between HABC and other algorithms, in which R? represents the sum of ranks for the problems where the first one outperformed the second, and R- denotes the sum of ranks for the opposite. Once they have been obtained, their associated p values can be computed. Table 9 reports the statistical results produced by Wilcoxon’s test from the experimental data in Tables 6 and 7,
Neural Comput & Applic x 10
8
x 10
11
x 10
4
4 2
5
3
1.5
Fitness
Fitness
Fitness
10
1
1
0.5 0
0 A1
A2
A4
A3
A5
A6
0 A1
A7
A2
A3
A4
A5
A6
A2
A1
A7
(a)
A3
A4
A5
A6
A7
Various Algorithms
Various Algorithms
Various Algorithms
(b)
(c)
521.5
3000 760
520.5
2500
Fitness
Fitness
521
Fitness
2
740 720
2000 1500
520 1000
700
519.5 A1
A2
A3
A4
A5
A6
A1
A7
A2
A3
(d)
A5
A6
A7
A1
x 10
x 10
6 4
A4
A5
A6
10
2 1.5 1
0 A1
A7
A2
Various Algorithms
A3
A4
A5
A6
A7
A1
Various Algorithms
(g)
A2
A3
x 10
A4
A5
A6
A7
Various Algorithms
(h)
8000
A7
0.5
0 A3
A6
2.5
2
1000
A5
3
Fitness
Fitness
1500
A4
(f)
8
8
2000
A2
A3
Various Algorithms
10
A1
A2
(e)
2500
Fitness
A4
Various Algorithms
Various Algorithms
(i)
5
5000
15
4000
Fitness
Fitness
Fitness
4500
6000
10
4000 3500
5 3000
2000
2500
0
A1
A2
A3
A4
A5
A6
A1
A7
A2
A3
A5
A6
A7
A1
Various Algorithms
Various Algorithms
(j)
A2
A3
A4
A5
A6
A7
Various Algorithms
(k)
(l) 3300
3400
5000
3200
4500
3200
3500
3100
Fitness
4000
Fitness
Fitness
A4
3000
3000
2900 2800
2800
2500
3000
2700
A1
A2
A3
A4
A5
A6
Various Algorithms
(m)
A7
A1
A2
A3
A4
A5
A6
Various Algorithms
(n)
A7
A1
A2
A3
A4
A5
A6
A7
Various Algorithms
(o)
Fig. 4 ANOVA results of all algorithms. Here a–o correspond to 50-dimensional f1–f15, 1–7 is index of HABC, PABC, BFOLS, ABC,CMA-ES, PSO and EGA, respectively
123
Neural Comput & Applic Fig. 5 Population evolution of HABC model on twodimensional Rastrigin function
5
FEs=0
5
0
-5 -5 5
0
0 FEs=5000
5
0
5.4.3.2 Multiple comparisons using the analysis of variance (ANOVA) test In order to further investigate the efficacy and robustness of the proposed HABC, the analysis of variance (ANOVA) test was also employed to determine the statistical characteristics of each of the tested algorithms over the others. The box plots shown in Fig. 4 demonstrate the statistical performance representation of all algorithms on CEC 2014 test suits. Looking at these box plots, the general features of the distribution can be noticed. From this box plot representation, it is clearly visible and proved that HABC achieved good variance distribution of compromise solutions on most test functions. Note that the PABC algorithm also exhibited its robustness on almost some functions.
5
-5 -5
5
FEs=1000
0
0 FEs=8000
0
for the pairwise comparison among the averaged value performances of two groups. Such groups have been organized as HABC versus other cases (i.e., PABC, BFOLS, ABC, PSO, CMA_ES and EGA). A significant difference between two approaches is considered by the alternative hypothesis. All p values reported in Table 9 are \0.05 (5 % significance level) which is a strong evidence against the null hypothesis as it indicates that the HABC results are statistically significant and that HABC shows a significant improvement over other algorithms.
123
-5 -5 5
0
-5 -5
FEs=100
-5 5 -5 5
0 FEs=10000
5
0
5
0
0
-5 5 -5
5.5 Experiment 2: simulation results for life cycle 5.5.1 Population evolution of bee colony This simulation is conducted to investigate how the HABC population based on the comprehensive learning self-adaptively grows along with the generations on the benchmark environments. Here the parameters setting for HABC were the same as in Sect. 5.2. The population evolution based on HABC mode was simulated on two-dimensional Rastrigin function. Figure 5 shows the positions of the individuals and the population variation in different phases, where each red circle represents a bee. We can directly see from Fig. 5 that HABC can converge to global optimum rapidly with the help of the item new comprehensive learning-based equation. Initially, the initial bees are distributed randomly over the nutrient map defined by the two-dimensional sphere. From the second phase (FEs = 100) to fifth phase (FEs = 8000), the population moves toward the optimal position of the sphere. It is noted that, after reaching a peak in the fourth phase, the population continues to decline due to exhaustion of nutrients. Finally, in the last phase (FEs = 10,000), with the guidance of the item Xbest, HABC can pull many bees to swarm together toward the global optimum.
Neural Comput & Applic 700
5.5.2 Dynamic population size of bee colony
HABC
Lag phase At the beginning of the bees entering into the strange environment, the population remains temporarily unchanged. Although there is no apparent bee proliferation, the bees have been ready to reproduce by gathering nectar from the new foods source. Log phase After bees gather enough nectar from the nutrient environment, all the bees start multiplying exponentially, doubling in the number every few iterations. From Fig. 6, we can observe that the bees proliferate at a different rate depending upon the composition of the predefined reproduction criterion and the environmental conditions. Stable phase The log growth cannot maintain all the time in a stationary environment, due to the exhaustion of nutrients and space. During the stable phase, it cannot be determined whether some bees are dying and an equal number of bees are reproducing, or the population of bees has simply stopped growing and reproducing. Death phase A bee is eliminated once it reaches the limitation of its life span. With the environmental nutrition exhausted, the death process becomes dominant. During the death phase, the bee population decreases exponentially, essentially the opposition of growth during the log phase. As we can see, the proposed life-cycle strategy plays an important role on the performance of HABC because it permits the bee to shift its search phases periodically according to the dynamic change in the environments 140
Population size
130
f1 f2 f3 f4 f5 f6 f7
Lag phase
120
Log phase
110
Death phase
100 90 80
500 400
PABC BFOLS ABC PSO CMA-ES EGA
300 200 100 0
A1
A2
A3
A4
A5
Objective functions
Fig. 7 Computing time of all algorithms on different benchmark problems A1–A5 corresponds to f1, f3, f9, f11 and f15, respectively
adaptively. Whenever the bee encounters a poor nutrient environment in Fig. 6, as more and more bees are competing for the gradually decreasing food and space, booming proliferation stagnates, which helps reduce the computational complexity of the optimization process. Oppositely, the bee forager starts searching intensive in the promising region. Clearly, this captures the important aspects of the self-adaptive evolution mechanism that takes place in nature. 5.5.3 Computation time analysis Algorithm complexity analysis is presented briefly as follows. Assuming that the computation cost of one individual in the HABC is Cost_a, the cost of the Powell’s search is Cost_p, S is the population size, D is the problem dimension, then, the total computation cost of HABC for one generation is S*Cost_a ? S/T*Cost_a* Cost_p, where Cost_p = D*S* Cost_a. Hence, the worst time complexity of this procedure is O(S2). From Fig. 7, it is observed that HABC and BFOLS always take the less computing time on most of selected benchmark functions. This is due to the fact that by the life-cycle strategy, the population size of these HABC can dynamically adaptive to the complexity of the objective functions. Hence, the proposed HABC algorithms have the potential to solve complex real-world problems.
Stable phase
70
6 Conclusions
60 50 40
Computing time(s)
In order to further investigate the impact of life-cycle mechanism, the population size variations of the proposed HABC on some test function are recorded in Fig. 6. From this figure, the lag phase, log phase, stable phase and death phase can be explicitly observed.
600
0
1
2
3
EvaluationCount
4
5
6 x 10 4
Fig. 6 Variation of population size of the bee colony in HABC
In order to apply ABC algorithm to solve complex optimization problems efficiently, this paper proposes a new hybrid artificial bee colony algorithm based on BLCM, namely HABC. Different from the canonical ABC model in which all individuals are identified as the same state
123
Neural Comput & Applic
characteristics, BLCM is a more realist life-cycle process and enriches the individual operating patterns in the system by incorporating various individual properties (state variables and parameters), which demonstrates the most significant merit that honeybee evolution becomes openended. Furthermore, the bee life cycle successfully casts classical ABC frame into the adaptive and varyingpopulation fashion, which leads to that the population size of HABC can be dynamically adaptive to the complexity of the objective functions, ensuring its powerful ability to deal with complex problems. Meanwhile, the computational complexity of the optimization process can be reduced. In addition, the combination of Powell’s search and comprehensive learning plays an important role on balancing the exploration and exploitation trade-off, due to that Powell’s search encourages fine exploitation when an individual enters the promising region with high fitness, while enhanced information sharing between excellent bees improves the exploration when the individual finds difficulties during exploitation. To prove the effectiveness and robustness of the proposed algorithms using different strategies, the proposed HABC has been compared with the PABC, BFOLS, ABC, CMA_ES, PSO and EGA algorithms on both classical and CEC 2005 benchmarks. The population variation of the proposed algorithmic model was also studied from biological evolution point of view. Based on this comprehensive analysis of HABC performance, we believe that HABC has a great potential of being applied to a variety of complex real-world problems. Acknowledgments This research is partially supported by National Natural Science Foundation of China and Grants 51205389, and 71271140; the National High Technology Research and Development Program of China (863 Program) (No. 2014AA052101-3).
References 1. Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of the 1995 IEEE international conference on neural networks, vol 4, pp 1942–1948 2. Dorigo M, Gambardella LM (1997) Ant colony system: a cooperating learning approach to the travelling salesman problem. IEEE Trans Evol Comput 1(1):53–66 3. Passino KM (2002) Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst Mag 22:52– 67 4. Clerc M, Kennedy J (2002) The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans Evol Comput 6(1):58–73 5. Sumathi S, Hamsapriya T, Surekha P (2008) Evolutionary intelligence: an introduction to theory and applications with Matlab. Springer, Berlin 6. Hansen N, Ostermeier A (2001) Completely derandomized selfadaptation in evolution strategies. Evol Comput 9(2):159–195
123
7. Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 8. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39(3):459–471 9. Karaboga D, Basturk B (2007) Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems. In: Lecture notes in computer science, vol 4529, pp 789–798 10. Pan QK, Tasgetiren MF, Suganthan PN, Chua TJ (2011) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci 181:2455–2468 11. Karaboga D, Akay B, Ozturk C (2007) Artificial bee colony (ABC) optimization algorithm for training feed-forward neural networks. In: Modeling decisions for artificial intelligence, Springer, Berlin, pp 318–329 12. Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 214:108–132 13. Biswas S, Kundu S, Das S, Vasilakos AV (2013) Information sharing in bee colony for detecting multiple niches in non-stationary environments. In: Christian B (ed) Proceeding of the fifteenth annual conference companion on genetic and evolutionary computation conference companion (GECCO 13 Companion), Amsterdam, The Netherlands. ACM, NY, USA, pp 1–2 14. Akbari R, Hedayatzadeh R, Ziarati K, Hassanizadeh B (2012) A multi-objective artificial bee colony algorithm. Swarm Evol Comput 2:39–52 15. Zhu GP, Kwong S (2010) Gbest-guided artificial bee colony algorithm for numerical function optimization. Appl Math Comput 217(7):3166–3173 16. Banharnsakun A, Achalakul T, Sirinaovakul B (2011) The bestso-far selection in artificial bee colony algorithm. Appl Soft Comput 11(2):2888–2901 17. Gao W, Liu S, Huang L (2013) A novel artificial bee colony algorithm based on modified search equation and orthogonal learning. IEEE Trans Cybern 43(3):1011–1024 18. Gao W, Liu S, Huang L (2013) A novel artificial bee colony algorithm with Powell’s method. Appl Soft Comput 13(9):3763–3775 19. Basturk B, Karaboga D (2012) A modified artificial bee colony algorithm for real-parameter optimization. Inf Sci 192:120–142 20. Kang F, Li JJ, Ma ZY (2011) Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions. Inf Sci 181:3508–3531 21. Alatas B (2010) Chaotic bee colony algorithms for global numerical optimization. Expert Syst Appl 37:5682–5687 22. Coelho LS, Alotto P (2011) Gaussian artificial bee colony algorithm approach applied to Loneys solenoid benchmark problem. IEEE Trans Magn 47(5):1326–1329 23. Schmickl T, Crailsheim K (2007) HoPoMo: a model of honeybee intracolonial population dynamics and resource management. Ecol Model 204:219–245 24. Beshers SN, Huang ZY, Oonoa Y, Robinson GE (2001) Social inhibition and the regulation of temporal polyethism in honey bees. J Theor Biol 213:461–479 25. Huang ZY, Robinson GE (1996) Regulation of honey bee division of labor by colony age demography. Behav Ecol Sociobiol 39:147–158 26. Khoury DS, Myerscough MR, Barron AB (2011) A quantitative model of honeybee colony population dynamics. PLoS One 6:e18491 27. Oster GF, Wilson EO (1978) Caste and ecology in the social insects. Princeton University Press, Princeton, NJ 28. Huang ZY, Robinson GE (1992) Honeybee colony integration: worker–worker interactions mediate hormonally regulated plasticity in division of labor. Proc Natl Acad Sci USA 89:11726–11729
Neural Comput & Applic 29. Jeanne RL (1986) The evolution of the organization of work in social insects. Monit Zool Ital 20:119–133 30. Seeley TD (1982) The adaptive significance of the age polyethism schedule in honeybee colonies. Behav Ecol Sociobiol 11:287–293 31. Cox MD, Myerscough MR (2003) A flexible model of foraging by a honey bee colony: the effects of individual behaviour on foraging success. J Theor Biol 223:179–197 32. DeGrandi-Hoffman G, Roth SA, Loper GL et al (1989) BEEPOP: a honeybee population dynamics simulation model. Ecol Model 45:133–150 33. Gheorghe M, Holcombe M, Kefalas P (2001) Computational models of collective foraging. BioSystems 61:133–141 34. Niu B, Zhu YL, He XX et al (2008) A lifecycle model for simulating bacterial evolution. Neurocomputing 72(1):142–148 35. Krink T, Løvbjerg M (2002) The lifecycle model: combining particle swarm optimisation, genetic algorithms and hillclimbers. In: Parallel problem solving from nature—PPSN VII. Springer, Berlin, pp 621–630 36. Powell MJD (1977) Restart procedures for the conjugate gradient method. Math Program 12:241–254 37. Ma L, Hu K, Zhu Y et al (2014) Discrete and continuous optimization based on hierarchical artificial bee colony optimizer. J Appl Math 2014:1–20
38. Rashedi E, Nezamabadi-pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inf Sci 179(13):2232–2248 39. Liang JJ, Qin AK, Suganthan PN, Baskar S (2006) Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evol Comput 10(3):281–295 40. Salomon R (1996) Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms. Biosystems 39:263–278 41. Yan X, Zhu Y, Zhang H et al (2012) An adaptive bacterial foraging optimization algorithm with lifecycle and social learning. Discrete Dyn Nat Soc 2012:1–10 42. Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: Evolutionary computation, 2005. The 2005 IEEE congress on IEEE, vol 2, pp 1769–1776 43. Chen H, Zhu Y (2008) Optimization based on symbiotic multispecies coevolution. Appl Math Comput 205(1):47–67 44. Potter MA, de Jong KA (2000) Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evol Comput 8:1–29 45. Derrac J, Garcı´a S, Molina D et al (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3–18
123