Bat algorithm based on simulated annealing and Gaussian perturbations

Abstract

Bat algorithm (BA) is a new stochastic optimization technique for global optimization. In the paper, we introduce both simulated annealing and Gaussian perturbations into the standard bat algorithm so as to enhance its search performance. As a result, we propose a simulated annealing Gaussian bat algorithm (SAGBA) for global optimization. Our proposed algorithm not only inherits the simplicity and efficiency of the standard BA with a capability of searching for global optimality, but also speeds up the global convergence rate. We have used BA, simulated annealing particle swarm optimization and SAGBA to carry out numerical experiments for 20 test benchmarks. Our simulation results show that the proposed SAGBA can indeed improve the global convergence. In addition, SAGBA is superior to the other two algorithms in terms of convergence and accuracy.

1 Introduction

Bat algorithm (BA) was developed by Xin-She Yang in 2010 [1], and BA is a metaheuristic algorithm, based on echolocation behavior of microbats. As a nature-inspired algorithm, BA uses frequency-tuning and swarm intelligence, and has been found to be very efficient. In terms of accuracy and effectiveness, BA has some advantages over other algorithms, and the number of adjustable parameters is fewer. Consequently, BA has been used for solving engineering design optimization [2–4], classifications [5], fuzzy cluster [6], prediction [7] and neural networks [8] and other applications.

In the paper, we will introduce both simulated annealing and Gaussian perturbations into the standard BA so as to further enhance its search performance. As a result, we propose a simulated annealing Gaussian bat algorithm (SAGBA) for global optimization. Our proposed algorithm not only inherits the simplicity and efficiency of the standard BA with a capability of searching for global optimality, but also speeds up the global convergence rate as we will demonstrate in the rest of this paper. We have used BA, simulated annealing particle swarm optimization (SAPSO) and SAGBA to carry out numerical experiments for 20 test benchmarks. Our simulation results show that our proposed SAGBA can indeed improve the global convergence. In addition, SAGBA is superior to the other two algorithms in terms of convergence and accuracy. Therefore, the rest of this paper is organized as follows: Sect. 2 provides a brief overview of the standard bat algorithm, followed by a brief introduction to simulated annealing in Sect. 3. Section 4 describes in detail the proposed algorithm, and then, we present a detailed comparison study in Sect. 5. In addition, we also present some statistical testing for the comparison studies in Sect. 5. Finally, we conclude and discuss relevant issues in Sect. 6.

2 Bat algorithm

Bats are the only mammals with wings, and they also use echolocations [9]. Most microbats use bi-sonar for navigation and hunt for prey. These bats typically emit a very loud but short sound impulse and then listen for the echoes reflected from the surrounding objects. Different species of bats may have different rates of pulse emission and frequency [1].

Based on the echolocation characteristics and hunting behavior of microbats, it is possible to design optimization algorithms. For example, in the standard bat algorithm, Yang used the following idealized rules [1]:

• 1. All bats use the echolocation to sense the distance and difference between food/prey and barriers;

• 2. Bats fly randomly with velocity v _i at position x _i with a varied frequency f _min with a varying wavelength λ to search for prey. It also has the loudness A ₀. They can automatically adjust the wavelength (or frequency), depending on the proximity of their target;

• 3. Although the loudness can vary in different ways, it assumes that the loudness varies from a large value A ₀ to a minimum value A _min.

Based on these idealized rules, the steps of BA can be summarized as follows:

• 1. Initialize the position x _i and velocity $v_{i}$ of bat i (i = 1,2 … n)

• 2. Initialize frequency f _i , pulse rates r _i and the loudness A _i

• 3. While (t < the max number of iterations)

• 4. Generate new solutions by adjusting frequency, and update velocities and solutions using Eqs. (1)–(3)

• 5. If (rand > r _i )

• 6. Select a solution from the best solutions

• 7. Generate a local solution around the selected best solution

• 8. End If

• 9. Generate a new solution by flying randomly

• 10. If (rand < A _i and f(x _i ) < f($x_{*}$))

• 11. Accept the new solutions

• 12. Increase r _i and reduce A _i

• 13. End If

• 14. Rank the fitness values of the bats and find the current best $x_{*}$

• 15. End While

For the BA, some approximations are made, including no ray tracing and constant speed of sound. Usually, the range of frequency is $[f_{\hbox{min} } ,f_{\hbox{max} } ]$, and the corresponding wavelength range is $[\lambda_{\hbox{min} } ,\lambda_{\hbox{max} } ]$. However, the exact ranges can be flexible and should depend on the scales of the problem of interest.

2.1 Movement of virtual bats

In a d-dimensional search space, the position $x_{i}^{t}$ and the speed $v_{i}^{t}$ of a bat (say, i) can be updated according to the following equations [1]:

$$f_{i} = f_{\hbox{min} } + (f_{\hbox{max} } - f_{\hbox{min} } )\beta$$

(1)

$$v_{i}^{t} = v_{i}^{t - 1} + (x_{i}^{t - 1} - x_{*} )f_{i}$$

(2)

$$x_{i}^{t} = x_{i}^{t - 1} + v_{i}^{t}$$

(3)

where f _i is the varying frequency. Here, $\beta \in [0,1]$ is a random vector drawn from a uniform distribution in [0,1]. Here, $x_{*}$ is the current global best solution found so far by comparing all the solutions.

When selecting a solution among the current best solutions, every bat can generate a new local solution by flying randomly or performing a local random walk [1]:

$$x_{\text{new}} = x_{\text{old}} + \varepsilon A^{t}$$

(4)

where $\varepsilon \in [ - 1,1]$ is a random number, and $A^{t} = A_{i}^{t}$ is the average loudness of all the bats at this time step. In a way, the update of the velocities and positions is similar to those of the standard particle swarm optimization [10].

2.2 Loudness and pulse emission

In order to mimic the feature that when a bat is homing for its prey, its loudness will decrease and the pulse emission will increase, we can use the following formulas to vary pulse emission and loudness [1]:

$$A_{i}^{t + 1} = \alpha A_{i}^{t} ,\quad r_{i}^{t + 1} = r_{i}^{0} [1 - \exp ( - \gamma t)] ,$$

(5)

where α and γ are constants. For any $0 < \alpha < 1,\gamma > 0$, we have

$$A_{i}^{t} \to 0,\quad r_{i}^{t} \to r_{i}^{0} ,\quad {\text{as}}\quad t \to \infty$$

(6)

For simplicity, we can usually use $0 < \alpha < 1,\gamma > 0$ for most applications.

3 Simulated annealing

Simulated annealing (SA) is one of the simplest and most popular heuristic algorithms [11]. SA is a global search algorithm, based on annealing process of metal processing. It has been proved that it can have global convergence, though the convergence rate can be very slow. The advantage of SA is that its transition probability can be controlled by controlling the temperature, which can effectively allow the system to jump out of any local optimum. In principle, we can consider SA as a Markov chain, and its pseudo code can be written as follows:

• 1. Initialize the temperature T ₀ and the solutions x ₀

• 2. Set the final temperature T _f and the maximum number of iterations N

• 3. Define cooling table $T \mapsto \alpha T,\;(0 < \alpha < 1)$

• 4. While (T > T _f and t < N)

• 5. Generate new solutions randomly $x_{t + 1} = x_{t} + \varepsilon$

• 6. Calculate $\varDelta f = f_{t + 1} (x_{t + 1} ) - f_{t} (x_{t} )$

• 7. Accept the new solution when it is better

• 8. If (the new solution is not accepted)

• 9. Generate a random number r

• 10. If ($p = \exp [ - \varDelta f/T] > r$)

• 11. Accept

• 12. End if

• 13. Update the optimal solution x* and the optimal value f ^*

• 14. t = t + 1;

• 15. End while

There are many studies to combine simulated annealing and other optimization algorithms to produce hybrid algorithms [12–15], such combination may have some advantages, which deserves further investigation. In fact, many nature-inspired algorithms have become very popular, due to their simplicity, flexibility and efficiency [15–18].

Therefore, this paper is the first attempt to combine simulated annealing with the standard bat algorithm. We also introduce Gaussian perturbations to further enhance the performance.

4 Bat algorithm based on simulated annealing and Gaussian perturbations

In the rest of this paper, we introduce both simulated annealing and Gaussian perturbations into the standard bat algorithm so as to enhance its search performance. As a result, we propose a simulated annealing Gaussian bat algorithm (SAGBA) for global optimization.

The basic idea and procedure can be summarized as two key steps: Once an initial population is generated, the best solutions are replaced by new solutions generated by using SA, followed by the standard updating equations of BA. Then, the Gaussian perturbations are used to perturb the locations/solutions to generate a set of new solutions.

At each iteration, Gaussian perturbations can be considered as mutation operations, and the new position to replace the original position can be generated by

$$X^{t + 1} = X^{t} + a\;\varepsilon$$

(7)

where ε ~ N(0,1) is a random vector with the same size as $X^{t}$ are two random matrices of. To avoid excessive fluctuations, we can use a scaling factor (a) to adjust the search range of this random walk.

Schematically, the steps of the SAGBA can be summarized as follows:

• A. Initialize the bat positions, velocities, frequency ranges, pulse rates and the loudness

• B. Evaluate the fitness of each bat, store the current position and the fitness of each bat, and store the optimal solution of all individuals in the pbest

• C. Determine the initial temperature

• D. According to the following formula to determine the adaptation value of each individual in the current temperature

  $${\text{TF}}(x_{i} ) = \frac{{{\text{e}}^{{ - (f(x_{i} ) - f({\text{pbest}}))/t}} }}{{\sum\nolimits_{i = 1}^{N} {{\text{e}}^{{ - (f(x_{i} ) - f({\text{pbest}}))/t}} } }}$$

  (8)

• E. Among all bats, we can use roulette strategy to determine an alternative value pbest and then update the velocity and position as follows:

  $$v_{i}^{t} = v_{i}^{t - 1} + (x_{i}^{t-1} - {\text{pbest}}^\prime)f_{i}$$

  (9)
  $$x_{i}^{t} = x_{i}^{t - 1} + v_{i}^{t}$$

  (10)

• F. Calculate the new objective or fitness value of each bat, update the positions/solution if it is better. Then, carry out Gaussian perturbations, and compare the position before and after Gaussian perturbations to find the optimal position pbest and its corresponding optimal value

• G. Update the cooling schedule

• H. If the stop condition is met (usually, the accuracy or the number of iterations), the search stops and output the results, otherwise go to Step D.

The initial temperature and cooling method can have certain influence to behavior of the algorithm. Based on parametric studies, we found that the following settings work well [20]

$$t_{k + 1} = \lambda t_{k}$$

(11)

$$t_{0} = f({\text{pbest}})/\ln 5$$

(12)

where λ in [0.5, 1] is a cooling schedule parameter.

The above steps have been summarized and represented in the flow chart shown in Fig. 1.

Fig. 1

Flow chart of the proposed SAGBA

5 Numerical experiments and results

In order to evaluate the effectiveness of our proposed SAGBA, we have to compare its performance with those of other algorithms for a set of test benchmarks in the literature. In principle, test functions should be as diverse as possible. For this purpose, we have used BA, SAPSO [19, 20] and SAGBA to carry out numerical experiments for 20 well-selected test benchmarks, and the results will be discussed in this section.

5.1 Test benchmarks and parameter settings

For all the algorithms used, we have to provide their proper settings so as to obtain a fair comparison. The parameter settings of the three algorithms as given in Table 1:

Table 1 The parameter settings of the three algorithms

The 20 test benchmarks used here are based on the test function library for global optimization [21, 22]. In Table 2, we list all the known global values where ‘−’ means that there are many different optimal points, as shown in Table 2:

Table 2 The 20 test benchmarks

In order to evaluate the convergence performance of an algorithm, we can either calculate the minimum value it can achieve for a given fixed number of iterations, or estimate the number of iterations for a fixed accuracy or tolerance. Here, we have used the first approach and set the max number of iterations to 2,000. We also carried out 50 different individual runs for each algorithm, and we will use the average value of the global minimum of the test benchmarks as performance indicators. We then use t test [23] to analyze the performance of the three algorithms.

5.2 Analysis of experimental results

From the extensive simulations, we can summarize the results in two ways: convergence rates and comparison. Now, let us first show the convergence rates of all three algorithms for a given function. For the 20 benchmark functions, their convergence rates are shown below in Figs. 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21. The horizontal axis shows the number of iterations, and the vertical axis shows the logarithmic value of the fitness [i.e., log (fitness value)].

Fig. 2

Convergence for Ackley function

Fig. 3

Convergence for Beale function

Fig. 4

Convergence for Bohachevsky function

Fig. 5

Convergence for Booth function

Fig. 6

Convergence for Branin function

Fig. 7

Convergence for Dixon and Price function

Fig. 8

Convergence for Goldstein and Price function

Fig. 9

Convergence for Griewank function

Fig. 10

Convergence for Hartmann function

Fig. 11

Convergence for Hump function

Fig. 12

Convergence for Levy function

Fig. 13

Convergence for Matyas function

Fig. 14

Convergence for Powell function

Fig. 15

Convergence for Rastrigin function

Fig. 16

Convergence for Rosenbrock function

Fig. 17

Convergence for Shubert function

Fig. 18

Convergence for Sphere function

Fig. 19

Convergence for Sum Squares function

Fig. 20

Convergence for Trid function

Fig. 21

Convergence for Zakharov function

Figures 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 show the convergence curves of the 20 test benchmarks using BA, SAPSO and SAGBA, respectively. It can be seen clearly from the pictures that the convergence rate of SAGBA is obviously faster than those of the other two algorithms.

By looking at the convergence curves closely, we can conclude that SAGBA can obtain better results with high accuracy and steeper convergence rates, compared with the other two algorithms.

Obviously, the comparison of the convergence curves is just one way of presenting results. Another way is to compare the best values found by each algorithm for a fixed number of iterations. As we have set the number of iterations to 2,000, the mean values of 50 runs under the same conditions of numerical experiments are summarized in Table 3.

Table 3 The comparison of the global average optimal values

In Table 3, ‘−’indicates that the mean minimum value was not found in the experiments when the max number of iterations is 2,000 times and the number of running is 50 times.

The results of using BA, SAPSO and SAGBA in the 20 test benchmarks are presented in Table 3. As can be seen from this table, except for the Booth function and Matyas function, all results obtained by SAGBA are better than the results of using SAPSO. For the Griewank function, the result of SAGBA is similar to that of SAPSO, but worse than BA. Except for Goldstein and Price function, Hartmann function and Shubert function where the results by SAGBA are similar to the results by BA, the results obtained by SAGBA for other functions are better than those by BA and SAPSO. All these may suggest that SAGBA is in general superior to BA and SAPSO. However, this conclusion needs statistical testing to confirm. So in the next section, we will carry out standard t test.

5.3 Statistical testing

Since each algorithm has been run independently for 50 times on each test benchmark, each algorithm has 50 samples, and we can use the t test to analyze and compare the performance of these algorithms. The t test is a two-tailed test, where the number of degrees of freedom is 58, and the significant level is usually set to 0.95. The results of the t test are summarized and shown in Table 4, where ‘S+’ means the result by SAGBA corresponding to the row of the problem is significantly better than the corresponding algorithm in the column, ‘S−’ means the result by SAGBA corresponding to the row of the problem is significantly worse than the corresponding algorithm in the column. In addition, ‘~’ means the result of SAGBA corresponding to the row of the problem is similar to the corresponding algorithm in the column.

Table 4 The results of t test

We can see from Table 4 that compared with BA, SAGBA is statistically poorer than BA for Griewank function, while it is statistically similar to BA for Booth function, Hartmann function, Matyas function, Shubert function and Zakharov function. For all the other functions, SAGBA is statistically superior to BA. Furthermore, compared with SAPSO, SAGBA is statistically similar to SAPSO for Griewank function, Hartmann function and Matyas function. For all the other functions, SAGBA is statistically superior to SAPSO. Statistically speaking, we can draw the following conclusion: SAGBA is significantly superior to BA and SAPSO on most of test benchmarks.

6 Discussions and conclusions

The BA is a new type of stochastic optimization techniques for global optimization. In this paper, we have introduced simulated annealing into the standard bat algorithm and then use Gaussian perturbations to perturb the solutions in the population, which can enhance the BA, while retaining a certain degree of ‘elitism.’ As the search iterations continue, the temperature is gradually reduced, and consequently, the probability of accepting poor solutions is gradually reduced. As a result, the overall convergence is enhanced, and the proposed SAGBA retains the standard BA’s characteristics (e.g., simplicity and easy implement), but also speed up the global convergence and improves its accuracy. The numerical results using 20 diverse test functions show that the proposed algorithm (SAGBA) is better than the other two algorithms, which has been confirmed by statistical testing.

It is worth pointing out that we observed from our simulations that the performance will improve if randomness is reduced gradually in the right amount. Here, we have achieved this by using simulated annealing. It can be expected that simulated annealing can also be used to hybridize with other algorithms. In addition, the diversity of the solutions is controlled by using Gaussian perturbations, and thus, it may be useful to investigate how different perturbations and probability distributions may affect the convergence of an algorithm. It is highly needed to compare various probability distributions and their role in randomizing stochastic algorithms.

Furthermore, though these preliminary results are very promising, there is still room for improvement. In the future studies, the comparisons of SAGBA with other algorithms should be carried out. It will also be fruitful to apply SAGBA to multi-objective optimization. In addition, it will be extremely useful to apply the proposed algorithm to large-scale real-world design problems in engineering.