^{1}Department of International Trade, National Taichung University of Science and Technology, Taichung City 404, Taiwan
^{2}Department of Computer Science and Information Engineering National Chin-Yi University of Technology, Taichung City 41170, Taiwan
Received date: December 29, 2015; Accepted date: January 19, 2016; Published date: January 25, 2016
Citation: Lee CL, Lin CJ (2016) A Novel Strategy Adaptation Based Bacterial Foraging Algorithm for Numerical Optimization. Int J Swarm Intel Evol Comput 5:128. doi:10.4172/2090-4908.1000128
Copyright: © 2016 Lee CL, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at International Journal of Swarm Intelligence and Evolutionary Computation
In this paper, a strategy-adaptation-based bacterial foraging optimization (SABFO) algorithm is proposed to
solve the optimization of complex problems. The proposed SABFO algorithm adopts the strategic approach into
chmotaxis step of traditional bacterial foraging optimization (BFO). The proposed method makes each bacterium
swim on different run-lengths, and increases bacterial diversity as well. Five optimization problems of nonlinear
benchmark functions are used to verify the performance of SABFO. Simulation results show that the SABFO obtains
better global optimal solutions than other methods.
Bacterial foraging optimization; Strategy evolution; Numerical optimization
Recently, soft computing methods [1-3], such as fuzzy logic, artificial neural networks, and evolutionary computation, have been capable of handling and tackling a wide range of real-world application problems in society and nature. The evolutionary algorithms are computational models of evolutionary computation, which simulate the natural evolution processes based on Darwinian principle. Genetic algorithm (GA) [4,5] and differential evolution (DE) [6] are two popular evolutionary algorithms that optimize a problem by iteratively improving candidate solutions in terms of a given measurement of objective function. These algorithms can efficiently explore a large global solution space, but they may trap into local minimums and not guarantee an optimal solution being ever found [7]. Therefore, some researchers [8-10] have proposed various improved-GAs to solve global optimization problems.
In artificial intelligence, swam intelligence (SI), a subset of evolutionary computation, is the collective behavior in a decentralized and self-organized system, which is made up by a population of simple individuals interacting locally with one another and with their environments. Inspired by the social behavior of animals, such as bird flocking, fish schooling and swarm theory, Kennedy and Eberhart [10] developed a new optimization algorithm called particle swarm optimization (PSO) in 1995, which has come to be widely used as a problem solving method in engineering and computer science. PSO is easy to understand and implement, and it requires less computational bookkeeping. However, one major drawback of the PSO is its slow convergence speed. Other algorithms inspired by biological systems and natural phenomena were also proposed, such as ant colony optimization (ACO) [11], bacterial foraging optimization (BFO) [12], artificial immune system (AIS), fish schooling search (FSS), fireworks algorithms (FWA).
A number of studies have been aimed to improve the evolutionary algorithm. Some researchers combined two different evolutionary algorithms to create new means of solving the engineering problems. For example, the combination of DE based mutation operator and bacterial chemotaxis was made to solve the nonlinear benchmark functions [13], the conjunction of the foraging behavior of E. coli bacteria and PSO was utilized to tune PID controller [8], and the improved method of introducing a PSO-like swarming mechanism into chemotaxis step of BFO was implemented in numerical optimization [7].
BFO is inspired by the foraging behavior of E. coli found in the intestines, and the advantage of this algorithm is the parallelizable searching ability of swarm intelligence, which tends to jump out of local minimum values. In complex optimization problems, however, BFO is hard to converge to the optimal solution and its performance heavily depends on the chemotaxis step length. Thus, Yan et al. [9] proposed social cooperation and adaptive step size strategies, which guided the bacteria tumbling towards better directions. Majhi et al. [14] adaptively adjusted the run-length of bacterial and applied it into two new forecasting models. Chen et al. [15,16] improved the convergence rate of BFO by verifying the influence of the size of bacteria run-length on the execution results. Besides, studies on mathematical analyses of the chemotaxis step [17] and reproduction step [18] have been proposed.
The run-length of original BFO is fixed, which makes it easy to fall into local optimal solution in complex problem. In this paper, we propose an improved algorithm, strategy-adaptation-based bacterial foraging optimization (SABFO), which adopts the strategy adaptation method in chemotaxis step. This adaptation method assesses three successive fitness values of each bacterium in the searching direction, and adjusts the run-length parameter, based on our newly-designed mathematical formulas.
The rest of this paper is organized as follows. In section 2, we introduce the traditional Bacterial Foraging Optimization. Section 3 is devoted to the proposed SABFO, and section 4 to its performance testing on a set of benchmark functions. Finally, discussion and conclusion are drawn in Sections 5 and 6, respectively.
The E. coli bacterium, the most famous bacteria in the intestinal tract of humans and animals, has two movement patterns, swim and tumble, achieved by the rotation of a set of tensile flagella. The movements of bacterium can help it avoid noxious substances and push its body towards abundant nutrient region while foraging. According to the studies of modern biology, E. coli bacterium grows very fast in a suitable environment, which can carry the reproduction out in every twenty minutes. By simulating the foraging process of bacteria, Passino [12] proposed the Bacterium Foraging Optimization (BFO) algorithm (Figure 1).
BFO employs three dominant mechanisms, chemotaxis, reproduction and elimination-dispersal, to solve the optimization problems. The followings describe these mechanisms in detail and the complete flowchart is shown in Figure 1.
Chemotaxis
Chemotaxis is the behavior of bacteria gathering to nutrient concentration in environment, and it consists of a tumble and several swims. The unit step of the movement in any direction is defined as the tumble. When bacteria complete a tumble, if the fitness value of the new position has improved, it will continue to move several steps in the same direction. This process is defined as the swim, and it continues until the fitness value gets worse or the number of movement reaches the predetermined threshold.
The location of a bacterium is the solution of optimization problem, which can be expressed as a D-dimensional vector, where S represents the population size of bacteria. The chemotaxis step formula is expressed as follows:
(1)
where C_{i} is the run-length of the bacteria tumble movement, represents the location of i-th bacterium at j-th chemotaxis, k-th reproduction and l-th elimination-dispersal steps, and Δ(i) is the randomly selected direction, whose elements lies in [-1, 1].
The population of bacteria can be written as and each cluster message signaling among bacteria is represented as the following equation:
(2)
Where four parameters, and, are chosen appropriately to describe the attractant and repellent behavior of bacteria, and J_{cc} is the updated value of fitness function. The new bacteria fitness function is as follows:
If the fitness value of bacterium gets improved and the maximum number of swim length (Ns) has not been reached, a new run will take place; otherwise, the next bacterium will be dealt with.
Reproduction
At the end of the above process, the times of chemotaxis reached the predefined threshold, so that the bacteria would conduct the reproduction process. In this process, poor half of the bacteria will die, and the others will survive and each will split into two subbacteria of equal part. The sub-bacteria inherit the parent-bacteria’s characteristics of biological, including the same position and runlength. Moreover, the population size of bacteria remains constant after the reproduction process. The health of bacteria is defined as the following:
where N_{c} is the number of chemotactic steps and cumulate the bacterial fitness value for each chemotaxis step. Thus, the higher the expressed the lower degree of health; on the contrary, the higher the health degree.
Elimination dispersal
The chemotaxis process ensures the local search ability of bacteria, and the reproduction process can accelerate their search speed. However, when dealing with complex optimization problems, the chemotaxis process is unable to avoid bacteria trapping into local minimum. Therefore, elimination-dispersal process strengthens the ability of global optimization of the BFO algorithm. The dispersalelimination process will conduct after every N_{re} times of reproduction steps. If the random number, generated between 0 and 1 for each bacterium, is less than a predetermined threshold, the bacterium will be eliminated and a new bacterium is generated in arbitrary position within the search space. Consequently, the chemo taxis step can leap from the local optimum to find the global optimum solution.
The Proposed Strategy-adaptation-based Bacterial Foraging Optimization
In this study, a Strategy-adaptation-based Bacterial Foraging Optimization (SABFO) is proposed. SABFO adopts the strategy adaptation method in the chemotaxis step of traditional BFO algorithm to solve the problems of prolonged execution time in multi-dimensional problem and trap into local optimal solution problem. The strategy concept was derived from Cooren et al. which used independent Gassians and pivot strategy to improve the performance of PSO [19,20]. Besides, it has been researched that the bacterial run-length size will affect the solution found in the optimization problem [21]. When bacteria are farther away from the best global optimal solution, the run-length size needs to be set larger; otherwise, the size needs to be set smaller. Therefore, we update the run-length for each bacterium corresponding to its current position, and it will be used on next moving action. The proposed strategy adaptation method records the previous and the current values of the fitness function for each bacterium, and compares these two values for conducting an assessment. If the current value (see Eq. (3)) is better than the previous one, a representative sign is marked as “+”, and if the current value is worse than the previous one, the sign is marked as “–”; otherwise, the sign is “=”. Derived from three consecutive fitness values, a gathered adaptability status in the strategy is a compound of two consecutive signs.
For example, the status (= +) means that the health and of bacteria i are the same and is better than . All the possible statuses are tabulated in Table 1, where Gbest is the best of global optimal solution of each generalization and the Pbest is the best of local optimal solution in each bacterium of each generalization.
Case | Gathered adaptability statuses | Evolutionary Strategy |
---|---|---|
1 2 3 |
(=+),(+ +) (+=),(– +) (– –), (= –), (+–), (– =), (= =) |
move to the Gbestdirection move to the Pbestdirection move arounditself |
Table 1: Gathered adaptability statuses and corresponding evolutionary strategies.
As shown in Table 1, the status is divided into three different cases, and we adjust the position and calculate the next run-length ( C_{i} ) of bacterium i according to the corresponding evolutionary strategies. In case 1, statuses (= +) and (+ +) represent that bacterium has always found out a better region approaching the optimal solution, so we move this bacterium toward the global best direction of the current generation. Next, statuses (+ =) and (– +) in case 2 represent the bacterium cannot continually find out a better region, but it also does not fall into a worse area, so that we direct the bacteria to the location of the local best () and of the global best (). Finally, in case 3, we make the bacterium swims along its direction.
We adopt these evolution strategies in the chemotaxis step of BFO algorithm, and the designed formulae of the bacterial position and runlength for different strategies are shown in Eqs. (5) - (10).
Case 1
Where0
Case 2
where
Case 3
Where θ^{i} represents the current position of bacterium i, C_{i}– the current bacterium’s run-length, - the fitness value of bacterium i for chemotaxis step j, and - the best location and the best fitness value of current bacterium, and and - the best location and the best global optimal solution among the bacteria. In short, the adjustment of the bacterium’s run-length in next movement is based on its current location.
The formulae of the run-length and position adjustment are different in each case, where the sum of three fitness values , and is regarded as the denominator, and each parameter is also held as the molecular. In case 1, the bacterium finds a better region, so it moves toward to and uses the as molecular in Eq.6, which makes the run-length C_{i} smaller.In the following, we show the details of the proposed strategy-adaptation-based bacterial foraging optimization (SABFO) in the form of pseudo codes.
Proposed algorithm: Strategy-adaptation-based Bacterial Foraging Optimization (SABFO)
Let is the number of swim length of the bacteria in chemotaxis step, is the number of chemotaxis step, is the number of reproduction step, is the number of eliminationdispersal step, C_{i} is the run-length of each bacterium, is the fitness value of each bacterium, is the best fitness value among the bacteria in each iteration, and is the better fitness value of each bacterium.
[Step 1] Initialize parameters, S, CI, N_{S}, N_{re}, and ped then randomly generate the positions of bacteria in solution space, and store this position in () For each bacterium. Next, calculate the fitness values () and store the smallest one and its position in () and () , respectively. Initially, C_{i} is set 0.1 to make each bacterium move at the same run-length, and parameter SA_{i}, gathered adaptability status, is marked as “+” indicating a better searching direction.
[Step 2] Elimination-dispersal loop: l = l +1;
[Step 3] Reproduction loop: k = k +1;
[Step 4] Chemotaxis loop: j = j +1
For bacteria i, i =1,2,..S, take a chemotaxis step.
For swim length m =1, 2,..N_{s} ,
Conduct strategic assessment according to the definitions of Cases 1-3, calculate the fitness value and the bacterium’s new location, and update C_{i} and SA_{i} for the next run.
[Step 5] If j < N_{c}, go to [step 4]. Continue the chemotaxis step since the life of the bacteria is not over.
[Step 6] Reproduction: calculate the health of bacteria by Eq. (4). After the fitness values are sorted, the bacteria of size S_{r} with the higher fitness values will die, and the other bacteria with the smaller fitness value will split into two sub-bacteria of equal part. In here, S_{r} is the half the number of population size.
[Step 7] If k < N_{re}, go to [step 3]. In this case, the specified reproduction step has not yet reached, so it starts the next generation of chemotaxis loop.
[Step 8] Elimination-dispersal: If a generated random number is less than Probability p, the bacterium is randomly assigned a new position in the solution space and the parameter SA_{i} is signed as “+”.
If l < p_{ed} , then go to [step 2]; otherwise end.
There are some modifications of original BFO algorithm. In the unusual chemotaxis step, the bacteria stop swimming when the fitness value gets worse. In contract, the proposed method makes each bacterium conduct swimming operation no matter whether the fitness value worsens or not. In the elimination-dispersal step, if the bacterium is eliminated and randomized dispersed, the adaptation status SA_{i} will be updated as “+”, exactly the same as the initialization step does. The flowchart of the proposed method is illustrated in Figure 2.
Five minimizations of nonlinear benchmark function are measured to evaluate the performance of the Strategy-adaptation-based Bacterial Foraging Optimization (SABFO). These well-known benchmark functions are commonly used in the literatures evaluating the global optimization algorithm [22], and their global optimum and search range are shown in Table 2. The parameter of D represents the dimension and f is the function value. In fact, all these nonlinear benchmark functions have an optimum of zero. Each benchmark function for dimension of 30, 45 and 60 is independently executed 50 times, and their mean and standard deviation of the best-of-run solution are calculated. In order to evaluate the convergence rate of each algorithm, the number of Function Evaluations (FEs) is used, and its maximum is set differently according to the complexity of the problem. In addition, when the objective function value is less than 0.001, the stop criterion is executed. In addition, we compare the experimental results of SABFO with that of BFO and the recently proposed three algorithms, ABFOA1 [17], ABFOA2 [17] and ABFOF [23].
Functions | Mathematical Representation | Global optimum | Rangeof search |
---|---|---|---|
Sphere | (-100,100)^{P} | ||
Rosenbrock | (-100,100)^{P} | ||
Rastrigin | (-10,10)^{P} | ||
Griewank | (-600,600)^{P} | ||
Ackley | (-32,32)^{P} |
Table 2: Numerical benchmark functions.
In these experiments, the initial run-length value λ in the ABFOA1 and ABFOA2 formula is 400, the values Ψ, a real number ranging from 0 to 1, and λ in ABFOF are 0.8 and 400, and initial run-length in SABFO and traditional BFO is 0.1. The related parameters set for these algorithms are listed in Table 3.
S | N_{s} | N_{c} | N_{re} | N_{ed} | p_{re} | d_{attractant} | w_{attractant} | h_{repellent} | w_{repellent} |
100 | 12 | 100 | 16 | 4 | 0.25 | 0.1 | 0.2 | 10 | 0.1 |
Table 3: Initial parameters setting of each algorithm.
Tables 4-8 show the experimental results. Based on the obtained results shown in Tables 4, 5 and 7, we can clearly demonstrate that our method is superior than other compared algorithms in Sphere (f1), Rosenbrock (f2) and Griewank (f4) functions. Table 9 expresses the actual execution FEs of the proposed algorithm in the five functions. Although the mean best values of our algorithm in Rastrigin (f3) and Ackley (f5) functions are slightly larger than those of ABFOF, our proposed algorithm is much simpler to execute and takes less computation time.
Dim | Max FEs | Mean best value (Standard deviation) | ||||
---|---|---|---|---|---|---|
BFO | ABFOA1 | ABFOA2 | ABFOF | SABFO | ||
30 | 1 ×10^{5} | 0.084 (0.003) |
0.022 (0.0063) |
0.044 (0.0721) |
0 (0) |
0 (0) |
45 | 5 ×10^{5} | 0.776 (0.156) |
0.208 (0.0664) |
0.419 (0.2096) |
0.0014 (0.0008) |
0 (0) |
60 | 1 ×10^{5} | 1.728 (0.213) |
0.427 (0.1472) |
0.632 (0.5747) |
0.0038 (0.0047) |
0 (0) |
Table 4: Average of the best-of-run solution on sphere function.
Dim | Max FEs | Mean best value(Standard deviation) | ||||
---|---|---|---|---|---|---|
BFO | ABFOA1 | ABFOA2 | ABFOF | SABFO | ||
30 | 1 ×10^{5} | 58.216 (14.33) |
4.572 (3.0631) |
6.748 (2.6625) |
0.1599 (0.0773) |
0 (0) |
45 | 5×10^{5} | 96.873 (26.14) |
24.663 (10.864) |
39.736 (30.626) |
0.3116 (0.034) |
0 (0) |
60 | 1 ×10^{6} | 154.71 (40.16) |
91.257 (32.628) |
84.6473 (53.273) |
0.4915 (0.0451) |
0 (0) |
Table 5: Average of the best-of-run solution on Rosenbrock function.
Dim | Max FEs | Mean best value(Standard deviation) | ||||
---|---|---|---|---|---|---|
BFO | ABFOA1 | ABFOA2 | ABFOF | SABFO | ||
30 | 1×10^{5} | 17.525 (9.896) |
2.5372 (0.382) |
2.9823 (0.572) |
0.0084 (0.001) |
0.0428 (0.0203) |
45 | 5×10^{5} | 32.952 (10.01) |
6.0236 (1.454) |
8.1121 (4.363) |
0.0344 (0.0191) |
0.0727 (0.0186) |
60 | 1×10^{6} | 41.482 (17.66) |
8.3343 (0.292) |
9.4637 (6.792) |
0.0923 (0.041) |
0.4469 (0.048) |
Table 6: Average of the best-of-run solution on Rastrigin function.
Dim | Max FEs | Mean best value(Standard deviation) | ||||
---|---|---|---|---|---|---|
BFO | ABFOA1 | ABFOA2 | ABFOF | SABFO | ||
30 | 1×10^{5} | 0.3729 (0.035) |
0.1914 (0.012) |
0.2028 (0.153) |
0.0142 (0.017) |
0 (0) |
45 | 5×10^{5} | 0.6351 (0.052) |
0.3069 (0.053) |
0.3065 (0.092) |
0.0096 (0.010) |
0 (0) |
60 | 1×10^{6} | 0.8324 (0.075) |
0.5638 (0.345) |
0.6074 (0.573) |
0.0055 (0.005) |
0 (0) |
Table 7: Average of the best-of-run solution on Griewank function.
Dim | Max FEs | Mean best value(Standard deviation) | ||||
---|---|---|---|---|---|---|
BFO | ABFOA1 | ABFOA2 | ABFOF | SABFO | ||
30 | 1×10^{5} | 2.3243 (1.883) |
0.5038 (0.551) |
0.7316 (0.675) |
0.0063 (0.007) |
0.0141 (0.010) |
45 | 5×10^{5} | 3.4564 (3.439) |
1.5532 (0.195) |
1.3672 (0.462) |
0.0067 (0.005) |
0.0187 (0.018) |
60 | 1×10^{6} | 4.3247 (1.561) |
1.7832 (0.458) |
1.9272 (0.7734) |
0.0069 (0.0024) |
0.0196 (0.018) |
Table 8: Average of the best-of-run solution on Ackley function.
Functions | Dim | Max FEs | Actual Execution FEs ofour Method |
---|---|---|---|
Sphere | 30 | 1 × 10^{5} | 5 |
45 | 5 ×10^{5} | 5 | |
60 | 1 ×10^{6} | 5 | |
Rosenbrock | 30 | 1 ×10^{5} | 2028 |
45 | 5 ×10^{5} | 780 | |
60 | 1 ×10^{6} | 805 | |
Rastrigin | 30 | 1 ×10^{5} | 1 ×10^{5} |
45 | 5 ×10^{5} | 5 ×10^{5} | |
60 | 1 ×10^{6} | 1 ×10^{6} | |
Griewank | 30 | 1 ×10^{5} | 484 |
45 | 5 ×10^{5} | 409 | |
60 | 1 ×10^{6} | 19 | |
Ackley | 30 | 1 ×10^{5} | 1 ×10^{5} |
45 | 5 ×10^{5} | 5 ×10^{5} | |
50 | 1 ×10^{6} | 1 ×10^{6} |
Table 9: Actual execution FEs of the proposed method in five functions.
In Tables 4, 5 and 7, experimental results show that the performance of the proposed method is better than other algorithms. Moreover, our algorithm can achieve 0 for objective function value in a short time in f1, f2, f4 functions. According to the mean and standard deviation of the best-of-run solution in the Tables 4-8, the proposed method obtains a smaller the variation of standard deviation. Therefore, we can find that the proposed method is better convergent stability than other methods. In Table 9, the proposed method only requires less number of the actual execution FEs to obtain the optimal solution of the objective function.
In this study, an efficient Strategy-adaptation-based Bacterial Foraging Optimization (SABFO) algorithm is proposed for numerical optimization. The advantages of the proposed SABFO are to use the strategy adaptation method in the chemotaxis step for improving the exploratory capability of each bacterium in the search space. The status of the proposed strategy adaptation method in the chemotaxis step is divided into three different cases. The position and the next run-length of a bacterium are adjusted and calculated according to the corresponding evolutionary strategies. Experimental results demonstrate that the proposed SABFO has superior performance than other methods in most cases.