The Global Convergence Analysis of the Bat Algorithm Using a Markovian Framework and Dynamical System Theory
Si Chen Guo-Hua Peng Xing-Shi He Xin-She Yang








The Global Convergence Analysis of the Bat Algorithm
 Using a Markovian Framework and Dynamical System Theory
    Si Chen^1, Guo-Hua Peng^1 

Department of Mathematics, College of Science, 

Northwestern Polytechnical University, Xi'an 710072, P. R. China. 

Xingshi He^2 

College of Science, Xi'an Polytechnic University, 

No. 19 Jinhua South Road, Xi'an 710048, P. R. China 

Xin-She Yang^3 

School of Science and Technology, Middlesex University, 

London NW4 4BT, UK.

    
=============================================================================================================================================================================================================================================================================================================================================================================





The bat algorithm (BA) has been shown to be effective to solve a wider range of optimization problems. However, there is not much theoretical analysis concerning its convergence and stability. In order to prove the convergence of the bat algorithm, we have built a Markov model for the algorithm and proved that the state sequence of the bat population forms a finite homogeneous Markov chain, satisfying the global convergence criteria. Then, we prove that the bat algorithm can have global convergence. In addition, in order to enhance the convergence performance of the algorithm, we have designed an updated model using the dynamical system theory in terms of a dynamic matrix, and the parameter ranges for the algorithm stability are then obtained. We then use some benchmark functions to demonstrate that BA can indeed achieve global optimality efficiently for these functions. 


Keywords:
Bat algorithm,  Global convergence, Markov chain theory, Dynamic matrix theory, Parameters selection, Optimization, Swarm intelligence.



Citation Details: Si Chen, Guo-Hua Peng, Xing-Shi He, Xin-She Yang, Global convergence analysis of the bat algorithm using a Markovian framework and dynamical system theory, Expert Systems with Applications, vol. 114, 173–182 (2018). 
https://doi.org/10.1016/j.eswa.2018.07.036






§ INTRODUCTION

With the development of computational intelligence <cit.>, nature-inspired algorithms have been shown to be effective and thus become widely used for various optimization problems <cit.>. However, there is still a significant gap between theory and practice. Though the applications of algorithms are very successful, the relevant fundamental theory lacks behind or no theory at all.
For example, the bat algorithm (BA), developed by Xin-She Yang in 2010 <cit.>, has been shown to very efficient in  practice, but there is no mathematical theory for analyzing this algorithm.  In fact, most of the swarm intelligence based algorithms for computational intelligence have no or little theoretical analyses, except for a few algorithms, such as the well known particle swarm optimization <cit.> and genetic algorithms <cit.>. Though we know these algorithms can work well in practice, we rarely understand why they work so well and under what conditions or parameter ranges. These key challenges require further in-depth theoretical studies.

Recent studies started to focus on this area and some preliminary results have been obtained. Sheng et al. analyzed the convergence of BA algorithm according to the global convergence criterion of stochastic optimization algorithm <cit.>, while Li et al. defined the two modes of speed and position updating for the bat algorithm, followed by the analysis of the two modes defined by the characteristic equation <cit.>. Huang et al. constructed a class of globally convergent BA algorithm to prove its global convergence, while applying it to solve large-scale optimization problems <cit.>. However, these studies have focused on the modified version of the bat algorithm, and there still lacks rigorous results about the standard bat algorithm, concerning both its convergence and stability.

Therefore, the main aim of this work is to prove the convergence of the standard bat algorithm using both Markov chain theory and then dynamic matric so as to gain insight into the working mechanisms of this algorithm. The paper is thus organized as follows. We will first introduce the basics of the BA in Section 2, followed by the introduction of the global convergence criteria of random search algorithms in Section 3. We will then build a proper Markov model for BA, and outline the main steps of proof of convergence in Section 4. A further updating model of the bat algorithm is defined in Section 5 so as to study the parameter variations and convergence conditions for the algorithm. The numerical experiments of some selected benchmark functions and their convergence behaviour are then presented in Section 6. Finaly, we draw sone brief conclusions in Section 7.




§ STANDARD BAT ALGORITHM

The standard bat algorithm was developed by Yang in 2010 <cit.> to solve continuous optimization problems. It has been extended to multiobjective optimization <cit.> with many different applications <cit.>.

The BA algorithm, inspired by the echolocation behavior of microbat species, is a population-based
algorithm using the frequency tuning with varying pulse emission rates and loudness so as to mimic the main nature of bats' echolocation when hunting for prey. The intention of BA is to act as a global optimizer using sufficient randomization and autoswitching between local and global moves, controlled by the actual emission rates and loudness of individuals <cit.>.

Based on the original bat algorithm <cit.>, each bat has a position vector x_i^t and a flying velocity v_i^t at iteration t in a d-dimensional search space. Their main algorithmic equations can be written as follows:

    f_i=f_min+(f_max-f_min)β, 
           v_i^t+1=ω v_i^t+(p-x_i^t)f_i, 
           x_i^t+1=x_i^t+v_i^t+1,

where f_i is the acoustic frequency of the i-th bat in the range of [f_min, f_max]. Here, ω indicates the inertia weight in the update of velocity, and in the standard bat algorithm ω=1 was used. For generality, we can use ω∈ (0, 1). In addition, β∈ [0,1] is a uniformly distributed random variable and p corresponds to the current best solution found by all the bats.

In a local search move, a new solution will be generated randomly around the old solution, often the current best solution. That is

    X_new=X_old+εA^t,

where X_old is a solution chosen from the current best solution set, A^t is the mean of the bats' loudness at t, and ε is the random number in [-1,1]. The loudness A_i and the velocity r_i of the bats can be updated as follows:

    A_i^t+1=αA_i^t,    r_i^t+1=r_i^0[1-exp(-γ t)],

where α and γ are constants (0<α<1, 0<γ).

For the convenience of the discussions below, we can rewrite the above equations (1) to (3) in the following form:

    v_t+1=ω v_t+(p-x_t) w_i,

which is valid for each individual bat. Here, we use w_i to denote frequencies to avoid potential confusion with the objective function f(x) later. The position vectors can be updated iteratively as

    x_t+1=(1+ω-f_i,t)x_t+p w_i

The stopping condition is usually  the maximum number of iterations, or when the optimal value searched by the population satisfies the set minimum fitness value.

The bat algorithm has many variants with a diverse range of applications <cit.>, such as fuzzy clustering, prediction, classification, image processing, feature selection, scheduling, and data mining.



§ CONVERGENCE CRITERIA

Depending on the actual algorithms and the framework of theoretical analysis, the convergence of an algorithm can be tested by certain criteria. One of the commonly used criteria is based on the two conditions outlined by Solis and Wets <cit.>.

Let ⟨ H,f⟩ be the optimization problem with a fitness function and a feasible solution space H. A stochastic optimization S iterates for t iterations and the new solution x_t+1
can be obtained from solution x_t by

    x_t+1 =S (x_t, ζ),

where ζ is the solution set found by the algorithm S during the iterative process.

Let us define the bounds of the search on the Lebesgue metric space as the infinum

    θ=inf{k:v[x ∈ H | f(x)<k]>0},

where v[X] is the measure on set X, which means that there are non-empty subsets in the search space and the fitness value corresponding to the element in the non-empty subset can be infinitely close to θ. Thus, the neighbourhood or region of optimal solutions can be defined as

    R_ε ,M={x∈ H|f(x)<θ+ε},    -∞<θ<∞, 
    {x∈ H|f(x)<M},   θ=-∞,

where ε >0 and M<0. If a stochastic algorithm finds a point in R_ε, M, then we can consider that the algorithm finds the global optimal solution or an approximation to the global optimal solution.

In general, for two settings, two conditions are necessary to guarantee the global optimality is achievable:

Condition 1: An optimization algorithm S should guarantees that the sequence  {f(x^t)}_t=0^∞ is decreasing. If there is f(S(x,ζ))≤ f(x) , and at the same time there is established ζ∈ H , we have

    f(S(x,ζ))≤ f(ζ).


Condition 2: For all subsets ∀ B ∈ H subject to v(B)>0,
we have

    ∏_t=0^∞ (1-u(B))=0,

where u_t(B) represents the probability measure of the t-th iterative result of the random algorithm S on B.

Mathematically speaking, a stochastic optimization algorithm that can have a guaranteed global convergence is based on the following lemma or criterion <cit.>


 For f is measurable and the feasible solution space H is a measurable subset on R^n, if the stochastic algorithm S satisfies both Condition 1 and Condition 2, sequence {x_t}_t=0^∞ is generated by the algorithm S will lead to

    lim_t→∞ P(x_t ∈ R_ε,M) = 1,

where P(x_t ∈ R_ε,M) represents the probability that the best solution obtained by algorithm S after t iterations belongs to R_ε,M.


In other words, the above criterion means that the algorithm will converge with a probability one as the number of iterations is sufficiently large, which equivalently means that the algorithm can have almost guaranteed global convergence.



§ GLOBAL CONVERGENCE ANALYSIS


In order to prove the convergence of the bat algorithm, we will introduce some preliminaries.
If the position of each bat individual in the BA algorithm is considered as a state x, then the process of states x_t with pseudotime or iteration counter t can be considered as a random process. For such a stochastic process, the Markov chain can be an effective tool to analyze its convergence in a probability sense.



 §.§ Preliminaries

Let us first define the state, state space and other relevant concepts that will be later used for proving the global convergence of the BA.

The states of bats and the state space can be defined as follows:

The position of a bat individual x with velocity v and historical best position p forms its state or status, denoted by a=(x,v,p), where x, p ∈ H.

In addition, we have f(p)≤ f(x) and v∈[v_min,v_max]. All possible states of all bats form a state space for bats, denoted by

    A={a=(x,v,p)|x,p ∈ H,   f(p)≤ f(x),   v ∈ [v_min,v_max]}.


Furthermore, the states and state space of the bats population or group can be defined as follows:

The set of all N bat individuals is called the bat group, and the states of this bat group can be denoted by b=(a_1, a_2, …, a_N). The collection of all possible bat group status or states forms the bat group status space, denoted by

    B={b=(a_1, a_2, …, a_N), a_i ∈ A (1≤ i ≤ N)}.



From the above definitions, it is obvious that the definition of bat group status B already contains the best position (or the best solution vector) in the group history. Furthermore, the state transition for the positions of bats representing solutions can be defined as follows:

For ∀ a_1=(x_1,v_1,p_1)∈ A and ∀ a_2=(x_2,v_2,p_2)∈ A during the iterations of the BA algorithm, the state transition from a_1 to a_2 can be denoted by

    F_A(a_1)=a_2,

where F_A is the transition function from a_1 to a_2 in the state space A.

Similarly,   for ∀ b_i=(a_i,1, a_i,2, …, a_i,N)∈ H and ∀ b_j=(a_j,1, a_j,2, …, a_j,N) ∈ H, the iterative process of the BA algorithm in essence transfers the bat group states from b_i to b_j. That is

    F_b(b_i)=b_j.




 §.§ Markov Chain Model for BA


In order to prove the convergence using a Markov chain framework, we have to build a Markov chain model for the bat algorithm. Let us first start with a theorem:

In the BA algorithm, the bat status a_1 is essentially shifted in one step to the status a_2, and its transition probability is the joint probability

    P(F_A(a_1)=a_2)=P(x_1→ x_2) P(v_1→ v_2) P(p_1→ p_2),

where P(x_1→ x_2) is the transition probability of the bat position
from x_1 to x_2, P(v_1→ v_2) is the transition probability of the bat velocity from v_1 to v_2, and P(p_1 → p_2) is the transition probability of the best position (in the whole history) from p_1 to p_2.



The status of a bat is transferred via a_1(x_1, v_1, p_1) → a_2(x_2, v_2, p_2). That is, x_1→ x_2, v_1→ v_2, and p_1→ p_2 are carried out simultaneously. The joint probability of F_A(a_1)→ a_2 is

    P(F_A(a_1)=a_2)=P(x_1→ x_2) P(v_1→ v_2) P(p_1→ p_2).


From the updating equations for velocities and positions (see Eqs.(2) and (3)), it is easy to see that the transition probability of the positions of bats can be calculated by

    P(x_1→ x_2)=1/|f(p_g-x_1)|,
        v_2∈ [x_1+ω v_1,ω v_1+w_i(p_g-x_1)], 
    
    0,     v_2∉ [x_1+ω v_1,ω v_1+w_i(p_g-x_1)].

Similarly, the transition probability concerning the velocities of bats can be calculated by

    P(v_1→ v_2)=1/|f(p_g-x_1)|,     v_2∈ [ω v_1,ω v_1+w_i(p_g-x_1)], 
    
    0,     v_2 ∉ [ω v_1,ω v_1+ w_i(p_g-x_1)].

In addition,  the transition probability of the best position p of all bats is

    P(p_1→ p_2)=
    1,     f(p_2)<f(p_1), 
    
    0,     f(p_2)≥ f(p_1).

It is worth pointing out that we treat the optimization problem as a minimization problem. Thus, p_2 is better than p_1 if f(p_2)<f(p_1).


With these results, we can now prove the following theorem:

In the iterative process of the BA algorithm, the transition probability of the bat group status b_i to b_j is given by

    P(F_b(b_i)=b_j)=∏_t=1^N P(F_A(a_it)=a_jt),

where N is the total number of iterations so far.



 As F_b(b_i)=b_j indicates that each state in the bat group state, b_i is simultaneously transferred to group state b_j; that is 
    F_A(a_i1)=a_j1, F_A(a_i2)=a_j2, …, F_A(a_iN)=a_jN.

Then, the transition probability of a group transition of the bat group should
be the joint probability of each iteration step. Thus, we have

    P(F_b(b_i)=b_j)   =P(F_A(a_it)=a_jt)P(F_A(a_it)=a_jt) … P(F_A(a_iN)=a_jN)
       =∏ _t=1^NP(F_A(a_it)=a_jt),

which concludes the proof.


Now we have to show that the state sequence a is finite, homogeneous Markov chain.

In the BA algorithm, the bat group state sequence a is indeed a finite homogeneous Markov chain.



For any optimization algorithm, its search space during the whole iterative process is finite because both the population size and the number of iterations are finite, so each of the bat state a=(x, v, p) among the x, v, p are finite, which leads to the fact that the bat state space is finite.

From the algorithmic equations outlined in Section 2, the position updates of each bat individual is a second-order equation, so the random process of positions of the BA algorithm changes with time, which is not the Markov process. However,
if we can group the position, velocity and global optimal values together as one state B, then state B(t+1) is only related to state B(t), not its history. Then, sequence B has proper Markov chain properties.

From Eqs.(1)-(3), β∈ [0,1] is a random vector that is uniformly distributed, and the algorithmic equations [i.e., (1) to (3)] form a stochastic
system. It is straightforward to show that the state B(t-1)  of the system at time t transferring to the new state B(t) is completely determined by its state at time t. In addition, the factor γ and ω as well as the pseudotime t in the iterative formulas are independent of the state of the system before time t.

From B(t-1) to B(t) of bats group state sequence {B(t); t≥ o}, the transition probability P(F_B(B(t-1))=B(t)) of the two states is determined by the transition probability of all individuals in the bats group, and the probability of transition can be calculated by the joint probability
 of P(x(t-1)→ x(t)), P(v(t-1)→ v(t)), and P(p(t-1)→ p(t)), according to Theorem 1.

In addition, P(x(t-1)→ x(t)) and P(v(t-1)→ v(t)) are only related to x, v, p at time t-1. Thus, P(F_B(B(t-1))=B(t)) is only related to the state a_i(t-1), 1≤ i ≤ N of all bats at time t-1. Therefore, the  Markov chains are finite.

Furthermore, from Theorem 1, P(F_A(a(t-1))=a(t)) is independent of time t-1.
Similar argument also indicates that P(F_B(B(t-1))=B(t)) is also independent of t-1. Therefore, the finite Markov chains are homogeneous.




 §.§ Global Convergence of the BA 

With the above definitions and theorems, let us proceed to prove the convergence of the bat algorithm.

For the true optimal solution g for an optimization problem ⟨ H, f⟩ with an objective function f(x) where x is a vector, the optimal state set can be defined as

    L={a=(x,v,p) |f(p)=f(g), a ∈ A}.

Obviously we have L ⊆ A as L should be a subset of A. If in any case
L=A, any solution in A is equally optimal, which means that objective landscape is flat (thus it is equivalent to a feasibility problem in which the objective does not exert any selection pressure on different solutions). This is just a special case and the optimal solution is already achieved, and thus we will not discuss this case any further.

In addition, for the optimal solution g to an optimal problem
⟨ H, f⟩, the optimal bat group state set can be defined as

    U={B=(a_1, a_2, …, a_N)| ∃ a_i ∈ L, 1≤ i≤ N},

which means that the optimal bat groups state set U is the set of all bat groups such that at least one bat individual in the population
with its state belong to L.

Using the same methodology as outlined in <cit.> (Theorems 7 and 8 in their paper) and the results in <cit.>, we can prove the following three theorems:

When U⊂ B, there is no closed set I other than B such that I ⋂ U=∅.


 If a Markov chain has a non-empty set Z with no closed set D satisfying Z⋂ D=∅, then lim_t→∞P(x_t=j)=π_j, only if j ∈ Z, and lim_t→∞ P(x_t=j)=0 only if j ∉ Z.


If the number of iteration approaches infinity or sufficiently large, the group state sequence will converge to the optimal state set U.


From the above four theorems, it is straightforward to prove the following global convergence theorem:

The bat algorithm with the Markov chain model defined in Section 4.2
has guaranteed global convergence.



From the convergence criterion (Criterion 1), we know that if a stochastic optimization algorithm can satisfy both condition 1 and condition 2, it will converge to global optimality. In essence, the first condition (Condition 1) can guarantee that the fitness value f(x) of the stochastic optimization algorithm is decreasing. From the above discussions, we know that, in the iterative process of the BA algorithm, it is obvious that f(p) ≤ f(x_t)

Furthermore, the previous theorem means that the group state sequence will converge towards the optimal set after a sufficiently large number of iterations, which means that the probability of not reaching the globally optimal solution is asymptotically zero. This means that the second convergence condition is also satisfied. As a result, a conclusion can be drawn that BA has guaranteed global convergence towards its global optimality with a probability one.


This proof is based on the Markov chain framework, and thus the convergence is in a probabilistic sense. It is an important result because it shows that the bat algorithm can indeed converge. However, there is no information about the rate of convergence and how the parameters may affect the convergence behaviour of this algorithm.

It is worth pointing out that the above proof has been based on a simplified Markov model for the bat algorithm. The standard bat algorithm also includes the variation of pulse emission rate and loudness, which has not been considered here. However, the overall convergence behaviour can be very similar.

In order to gain further insight into the parameter values and their effect on the convergence of the bat algorithm, we now use a completely different approach
to analyze the algorithm in terms of dynamic matrix theory.



§ CONVERGENCE ANALYSIS BASED ON DYNAMIC MATRIX THEORY


The advantage of algorithm analysis using dynamic matrix theory is that the matrix can be constructed from the updating equations of the algorithm, and the insight can be gained about the possible parameter ranges for the algorithm to converge.

For this purpose and for simplicity of calculations without losing generality,
it is assumed that the current optimal solution in the bat algorithm population is  a constant vector p (even though it is updated at each iteration). It is assumed that the frequency f_i is a constant m ≥ 0. Within this framework, the velocities and positions of bats during the iterations can be written as

    v_k+1=l v_k+(p-x_k) m,


    x_k+1=c x_k+uv_k+1,

where coefficient m is essentially the average of the frequencies, while l, c and u are the weight coefficients so that we can analyze the algorithm in general.  The attraction point p in the d-dimensional space is the current optimal position. The algorithm represented by the system (<ref>)
and (<ref>)
now have four parameters to be tuned. They are l, m, c, u.
We will show that two of these parameters are key parameters.



 §.§ Dynamic Matrix Model for the Bat Algorithm


From the algorithmic equations (<ref>) and (<ref>), we can rewrite (<ref>) equivalently using the previous iteration as

    x_k = c x_k-1 + u v_k,

and then multiply its both sides by l and re-arrange slightly, we have

    l u v_k=l x_k-c l x_k-1.

Combining (<ref>) and (<ref>), we have

    x_k+1= c x_k + u v_k+1 = c x_k + u [l v_k +(p-x_k) m]


    =c x_k + u l v_k + u m p - u m x_k
    =c x_k + [l x_k - c l x_k-1 ] + u m p - u m x_k,

where we have used Eq.(<ref>).

By re-arranging the above equation, we have a recursive relationship for x_k

    m u p=x_k+1+(m u-c-l)x_k + l c x_k-1.

It is obvious that mu always appear as a factor, not individually. This means that only their product matters. Thus, for simplicity (without loss of generality), we can set

    u ≡ 1.

Therefore, we have a reduced system of algorithmic equations for the bat algorithm as 
    v_k+1    =     lv_k+m(p-x_k), 
    
    x_k+1    =     c x_k+ v_k+1.


In addition, as the number of iterations k increases, it can be expected that the series should converge to p (the current best solution found by all the bats). That is

    lim_k →∞ x_k =p,   lim_k →∞ x_k+1 =p,
      lim_k →∞ x_k-1 =p.

Taking the limit of (<ref>) and using the above results, we have

    mp = p + (m-c-l) p + l c p,

which gives that

    p (l-1) (c-1)=0.

Thus, either p=0 (a trivial solution or special solution), or l=1, or c=1. Considering the role of c in the algorithm, we can set c=1 for the moment as it does not affect the update of the position vectors.

Now we have finally obtained the reduced dynamic system for the bat algorithm

    v_k+1    =     l v_k+m(p-x_k)= -m x_k + l v_k + mp, 
    
    x_k+1    =       x_k+ v_k+1= x_k + [-m x_k + l v_k + mp],

which leads to

    v_k+1    =     -mx_k+lv_k+mp, 
    
    x_k+1    =     x_k+lv_k+mp-mx_k.


We can rewrite the above dynamic system in a matrix form as

    Y_k+1 = C Y_k+M p,

where

    Y_k=[ x_k; v_k ],     
    C=[ 1-m   l;  -m   l;     ],     
    M=[ m; m ].

Here, the Y_k column vector corresponds to the states of positions and velocities of the bats at iteration k. Matrix C is the dynamic matrix that governs the main properties of this dynamic system. M is the input of the frequencies and p is the current best solution in the system.

As the iterations continue and the bat population move towards p, the velocity of the bat population will approach zero. That is

    lim_k →∞ v_k=0.

Therefore, the final fixed point or point of convergence in the state space Y_k is

    Y*=[ p; 0 ].

The final state of convergence is that lim_k →∞ x_k=p and
lim_k →∞ v_k=0 if there is no perturbation.



 §.§ Algorithm Convergence and Parameter Selection

The main properties of the dynamic system is now determined by
the eigenvalues of the dynamic matrix C. That is

    |
    
    1-m  -λ    l 
     -m     l -λ| =0,

which gives

    (1-m -λ) (l -λ) + ml=0,

or simply

    λ^2 + λ (m-l-1) + l=0.

Thus, their solutions are

    λ=-(m-l-1) ±√((m-l-1)^2-4l)/2,

which gives two eigenvalues λ_1 and λ_2.
For the dynamic system to be stable, their modules must be smaller than one |λ| ≤ 1. From Vieta's formulas for polynomials,
we know that λ_1 ·λ_2 = l
whose modulus should also be less than one, so we have |l| ≤ 1 or -1 ≤ 1 ≤ 1.

In addition, Vieta's formulas also indicate that

    λ_1+λ_2=-(m-l-1)=l-m+1 ≤ 2,

which must be less than 2 (i.e., λ_1+λ_2 ≤ 2) so that
each eigenvalue is potentially less than 1. We have

    l ≤ m+1,


For the conditions that the modulus of the biggest eigenvalue must be smaller than one |λ| ≤ 1, we have

    (l-m+1) ±√((m-l-1)^2-4l)/2≤ +1,

or

    -1 ≤(l-m+1) ±√((m-l-1)^2-4l)/2.

The first equation (<ref>) becomes

    (l-m-1) ≤∓√((m-l-1)^2 -4l),

or 
    (l-m-1)^2 ≥ (m-l-1)^2 -4l,

which gives

    (l-m-1)^2 - [(m-1-1)^2-4l] = 4m ≥ 0,

or simply m ≥ 0. Here, we have used the fact l ≤ m+1 (or l-m-1 ≤ 0),
thus the inequality should be reversed when taking the square.


Similarly, the other condition becomes

    -(l-m+3) ≤±√((m-l-1)^2 - 4l),

or 
    (l-m+3)^2 ≥ (m-l-1)^2 - 4l,

which gives 
    (l-m+3)^2 - [(m-l-1)^2-4l] =4 (2l+2 -m) ≥ 0,    or     2l+2 ≥ m.

Therefore, the conditions for stability and convergence are

    -1≤ l ≤ +1, 
    
    m ≥ 0, 
    
    2l-m+2 ≥ 0.

which form a triangular region in the parameter space of l and m, as shown in Fig. <ref>.

The above analysis shows that within the parameter ranges of m and l, the bat algorithm will not only converge towards the optimality, it will also converge stably. In this case, the algorithm will behave stable and converge quickly in practice. However, it should be emphasized that the dynamic model presented in this paper has not considered the variation of pulse emission rate and loudness, thus the actual parameter ranges may be different from the above results. Even so, this simplified model has enabled us to understand the influence of parameter values for the bat algorithm.

In the rest of the paper, we will use some selected benchmarks to show such convergence properties.




§ VALIDATION BY NUMERICAL EXPERIMENTS

In order to verify the BA algorithm and show the convergence characteristics discussed above in this paper, we have conducted some numerical experiments using
a few selected benchmark functions with very difficult properties and modalities.
These functions are listed in Table 1 where the dimensionality is chosen as D=30 for all functions.



For each function, the bat algorithm has been executed with a maximum number of iterations t_max=500 with a population size n=12, m=2 and l=0.5. The dimensions for all functions are D=30.

The convergence plots for all the functions are shown in Fig. <ref>.

It can be observed clearly from this figure that all functions can converge
quickly, specially at the early stage of the iterations. However, if the parameter ranges lie outside the stable domain, the rate of convergence can be significantly lower, and the very slow convergence or even premature convergence can occur
as can see from Fig. <ref> where m=-3 and l=4 are used, even though all the other parameters remain the same.


All the above have demonstrated that the algorithm can converge both quickly and robustly. Thus, the algorithm can be suitable for difficult optimization problems where
optimal or nearly optimal solutions are needed quickly.



§ CONCLUSIONS


The bat algorithm has been shown to be effective in practice, but there is not theoretical analysis in the literature. This paper provides some theoretical analysis of the standard bat algorithm using both a simplified Markov chain model and a dynamic matrix model. The Markov model shows that the algorithm can converge to the global optimality with probability one as the number of iterations becomes sufficiently large. The dynamic model looks at the algorithm from a different perspective. By extending the models with more parameters, we have then obtained some insight why some parameters are not important, while others can be tuned. As a result, the parameter ranges of some key parameters have been identified.

Following the theoretical analyses, we have used some benchmark test functions to validate the bat algorithm using the appropriate parameters. Good convergence has been observed for all functions, which is consistent with the theoretical results.

It is worth pointing out that the models used in this paper are simplified models
without considering the variation of pulse emission rate and loudness. Future work will try to extend to investigate the effect of such factors in the convergence properties of the bat algorithm. In addition, even we now understand why the bat algorithm converge with a clear parameter region, it still lacks the information on the rate of convergence and how the parameter values will affect the rate of convergence. Future work will also investigate this issue further with more rigorous analyses.





§ REFERENCES

100

Engelbrecht A. P. Engelbrecht. Computational Intelligence: An Introduction. John Wiley  Sons, 2007:5-24.

Yang X.S. Yang, Nature-Inspired Optimization Algorithms, Elsevier Insight, London. (2014).

Yang01 X.S. Yang,  Bat Algorithm for Multi-Objective Optimisation. International Journal of Bio-Inspired Computation. 2011, 3(5): 267-274.

Yang02 X.S. Yang, A New Met Heuristic Bat-Inspired Algorithm, Nature Inspired Cooperative Strategies for Optimization. 2010: 65-74.

Gandomi A. H. Gandomi, X. S. Yang, A. H. Alavi and S. Talatahari. Bat Algorithm for Constrained Optimization Tasks. Neural Computing Applications. 2013, 22(6): 1239-1255.

Natarajan  A. Natarajan, S. Subramanian and K. Premalatha. A Comparative Study of Cuckoo Search and Bat Algorithm for Bloom Filter Optimisation in Spam Filtering. International Journal of Bio-Inspired Computation. 2012, 4(2): 89-99.


Yang03 X. S. Yang,  A. H. Gandomi. Bat Algorithm: A Novel Approach for Global Engineering Optimization. Engineering Computations. 2012, 29(5): 464-483.

Baziar A. Baziar, M. Rostami and M. Akbari-Zadeh. An Intelligent Approach Based On Bat Algorithm for Solving Economic Dispatch with Practical Constraints. Journal of Intelligent Fuzzy Systems. 2014,27(3): 1601-1607.

Ramesh B. Ramesh, V. C. J. Mohan and V. V. Reddy. Application of Bat Algorithm for Combined Economic Load and Emission Dispatch. International Journal of Electricl Engineering and Telecommunications. 2013, 2(1): 1-9.

Clerc M. Clerc and J. Kennedy, The particle swarm - explosion, stability, and convergence in a multidimensional complex space, IEEE Trans. Evolutionary Computation, 2002, 6 (1):58-73.

Huang G.Q. Huang, W.J. Zhao, Q.Q. Lu, Bat algorithm with global convergence for solving large-scale optimization problem, Application Research of Computers, 2013,30 (5): 1323-1328.

Jiang M. Jiang, Y.P. Luo, and S.Y. Yang. Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm, Information Processing Letters, 2007, 102(1): 8-16.

Villa M. Villalobos-Arias, C.A. Coello Coello, O. Hernández-Lerma, Asymptotic convergence of metaheuristics for multiobjective optimization problems, Soft Computing, 2005, 10(8): 1001-1005.

Hexs X.S. He, F. Wang, Y. Wang, X.S. Yang, Global convergence analysis of cuckoo search using Markov theory, in: Nature-Inspired Algorithms and Applied Optimization (Eds. X.S. Yang), Springer Nature,
     Cham, Switzerland, pp. 53-67.

Kennedy J. Kennedy, R.C. Eberhart, R. C., Particle swarm optimization, in: Proc. Of IEEE International Conference on Neural Networks, Piscataway, NJ. 1995, pp. 1942-1948.

Deb K. Deb, A. Pratap, S. Agarwal and T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation. 2002, 6(2): 182-197.

Koziel S. Koziel, X.S. Yang, Computational Optimization, Methods and Algo-rithms, Springer, Berlin, (2011).

Khan K. Khan, A. Nikov, A. Sahai,  A fuzzy bat clusterig method for ergonomic screening of office workplaces, S3T 2011, Advances in Intelligent and Soft Computing. 2011: 59-66.

Jain L. C. Jain, S. C. Tan and C. P. Lim. An Introduction to Computational Intelligence Paradigms. Springer, 2008: 36-75.

Sheng M.L. Sheng, X.S. He, W.J. Ding, Analysis of bat algorithm's global convergence, Basic Sciences Journal of Textiles Universities,
    2013, 26(4): 543-547.

ZLi Z.Y. Li, L. Ma, H.Z. Zhang, Convergence Analysis of Bat Algorithm. Mathematical in Practice and Theory, 2013, 43 (12): 182-190.

Kang M. Kang, J. Kim and J. Kim. Reliable Fault Diagnosis for Incipient Low-Speed Bearings Using Feature Analysis Based On a Binary Bat Algorithm. Information Sciences. 2015, 294: 423-438.

Jaddi N. S. Jaddi, S. Abdullah and A. R. Hamdan. Optimization of Neural Network Model Using Modified Bat-Inspired Algorithm. Applied Soft Computing. 2015, 37: 71-86.

Tsai P. W. Tsai, J. S. Pan, B. Y. Liao, M. J. Tsai and V. Istanda. Bat Algorithm Inspired Algorithm for Solving Numerical Optimization Problems. Applied Mechanics and Materials. 2011,148(1):134-137.

Eberhart R. C. Eberhart and J. Kennedy. A New Optimizer Using Particle Swarm Theory.Proceedings of the 6th International Symposium on Micro Machine and Human Science.
    1995: 39-43.

Akerkar R. Akerkar and P. S. Sajja. Bio-Inspired Computing: Constituents and Challenges. International Journal of Bio-Inspired Computation. 2009, 1(3): 135-150.

Ren Z.H. Ren, J. Wang, and Y.L. Gao, The global convergence analysis of particle swarm optimization algorithm based on Markov chain, Control Theory and     Applications (in Chinese), 2012,8(4): 462-466.

Solis F. Solis, R. Wets, Minimization by random search techniques[J].Mathematics of Operations Research, 1981(6): 19-30.

Mishra S. Mishra, K. Shaw and D. Mishra. A New Meta-Heuristic Bat Inspired Classification Approach for Microarray Data. Procedia Technology. 2012. 802-806.

Akhtar S. Akhtar, A. R. Ahmad and E. M. Abdel-Rahman. A Metaheuristic Bat-Inspired Algorithm for Full Body Human Pose Estimation. 2012: 369-375.

Bora T. C. Bora, L. D. S. Coelho and L. Lebensztajn. Bat-Inspired Optimization Approach for theBrushless DC Wheel Motor Problem. IEEE Transactions on Magnetics. 2012, 48(2): 947-950.

Niknam T. Niknam, F. Bavafa and R. Azizipanah-Abarghooee. New Self-Adaptive Bat-Inspired Algorithm for Unit Commitment Problem. IET Science Measurement Technology. 2014, 8(6): 505-517.

Wen-xiu W.X. Zhang, L. Yi, The Mathematical Basis of Genetic Algorithm (in Chinese), Xi'an Jiaotong University Press, 2003.

Leung Y. Leung, Y. Wang. An Orthogonal Genetic Algorithm with Quantization for Global Numerical Optimization. IEEE Transactions on Evolutionary Computation. 2001, 5(1): 41-53.



