A New Metaheuristic Bat-Inspired Algorithm – Xin-She Yang, 2010

Today it’s the turn of bats!

The bat algorithm is an attempt to combine some of the major advantages of previous algorithms such as the firefly algorithm and harmony search (inspired by music composition). It is based on the echo-location behaviour of bats.

Bats are fascinating animals. They are the only mammals with wings and they also have advanced capability of echolocation. It is estimated that there are about 996 different species which account for up to 20% of all mammal species. Their size ranges from the tiny bumblebee bat (of about 1.5 to 2g) to the giant bats with wingspan of about 2m and weight up to about 1 kg. Microbats typically have forearm length of about 2.2 to 11cm. Most bats uses echolocation to a certain degree; among all the species, microbats are a famous example as microbats use echolocation extensively while megabats do not.

(I think they missed a trick by not calling the megabats monoliths 😉 ).

Microbats use a type of sonar, called, echolocation, to detect prey, avoid obstacles, and locate their roosting crevices in the dark. These bats emit a very loud sound pulse and listen for the echo that bounces back from the surrounding objects. Their pulses vary in properties and can be correlated with their hunting strategies, depending on the species. Most bats use short, frequency-modulated signals to sweep through about an octave, while others more often use constant-frequency signals for echolocation. Their signal bandwidth varies depends on the species, and often increased by using more harmonics.

Microbats emit about 10-20 sound bursts per second. When hunting this can go up to about 200 pulses a second as they get near their prey. “Such short sound bursts imply the fantastic ability of the signal processing power of bats. In fact, studies shows the integration time of the bat ear is typically about 300 to 400 µs.” The wavelengths are in the same order as their prey sizes. Fortunately these pulses are in the ultrasonic region because they are astonishingly loud – up to about 110 dB. (That’s roughly the same volume as a live rock concert, or a jackhammer).

The loudness also varies from the loudest when searching for prey and to a quieter base when homing towards the prey. The travelling range of such short pulses are typically a few metres, depending on the actual frequencies. Microbats can manage to avoid obstacles as small as thin human hairs. Studies show that microbats use the time delay from the emission and detection of the echo, the time difference between their two ears, and the loudness variations of the echoes to build up three dimensional scenario of the surrounding. They can detect the distance and orientation of the target, the type of prey, and even the moving speed of the prey such as small insects. Indeed, studies suggested that bats seem to be able to discriminate targets by the variations of the Doppler effect induced by the wing-flutter rates of the target insects.

Bats are pretty amazing really! By equating the echo-location behaviour of bats with an objective function to be optimised, we can formulate new optimisation algorithms.

We will use the following rules/simplifications for our idealized bats:

• Echolocation is used to sense distance (ignore any eyesight etc.).
• Bats fly randomly with a velocity v_i , at position x_i.
• They emit pulses at a fixed wavelength λ, with varying frequency f and loudness A to search for prey.
• The rate of pulse emission r ∈ [0,1] varies depending on the proximity of the target
• Loudness varies from a large positive A₀ to a minimum constant value A_min

Another obvious simplification is that no ray tracing is used in estimating the time delay and three dimensional topography (!). Though this might be a good feature for the application in computational geometry, however, we will not use this as it is more computationally extensive in multidimensional cases.

Starting out with an initial population of bats spread over the solution space, the algorithm proceeds in iterations. Each bat is randomly assigned a start frequency drawn from [f_min,f_max] – for example, 0..100. Each bat is also given a random initial loudness and pulse emission rate r ∈ [0,1] close to zero.

For each iteration, we update the frequency, position and velocity of each bat in the search space as follows.

Draw a random number between 0 and 1, if it is less than or equal to the current rate of bat i, then update the bat’s location using:

• f_i = f_min + β(f_max – f_min) , where β is a random number between 0 and 1.
• v_i = v_i + f_i(x_i – x_G), where x_G is the current global best location (solution)
• x_i = x_i + v_i

However, if the random number is greater than r_i, then instead move the bat to a new location generated by taking a random walk from the current best solution:

• x_i = x_G + εA , where A is the average loudness of all bats at this time, and ε is a random number drawn from [-1,1].

Now we evaluate the objective function at the new location for the bat. If the fitness has improved and a random number drawn between A₀ and A_min is less than the current loudness for the bat, then we accept (move it to) the the location.

Finally we update the loudness and rate of pulse emission for the bat:

• A_i = αA_i
• r_i^t+1 = r_i⁰[1 – exp(-λt)], where t represents the time step (iteration)

α and λ are constants, both set to 0.9 in the simulation in the paper.

At the end of our chosen number of iterations, the bat at the best location (solution) is the winner.

Note that the algorithm description given in the paper I found quite confusing, and ended up piecing together the above from a combination of the paper and the pseudo-code in Xin-She Yang’s book.

[In tests,] the Bat Algorithm is much superior to other algorithms [Genetic Algorithms and PSO] in terms of accuracy and efficiency. This is not surprising as the aim of developing the new algorithm was to try to use the advantages of existing algorithms and other interesting feature inspired by the fantastic behaviour of echolocation of microbats.

The Bat Algorithm subsumes (is more powerful than) PSO and Harmony Search:

If we replace the variations of the frequency f_i by a random parameter and setting A_i = 0 and r_i= 1, the bat algorithm essentially becomes the standard Particle Swarm Optimization (PSO). Similarly, if we do not use the velocities, but we use fixed loudness and rate: A_i and r_i – for example, A_i = r_i= 0.7 – this algorithm is virtually reduced to a simple Harmony Search (HS) as the frequency/wavelength change is essentially the pitch adjustment, while the rate of pulse emission is similar to the harmonic acceptance rate (here with a twist) in the harmony search algorithm. The current studies implies that the proposed new algorithm is potentially more powerful and thus should be investigated further in many applications of engineering and industrial optimization problems.