Levy Flights in Metaheuristics Optimization Algorithms – A Review

ABSTRACT

In recent years, Levy flight (LF) is increasingly being employed as search mechanism in metaheuristics optimization algorithms (MOA) to solve complex real world problems. LF-based algorithms are found to exhibit superior or equivalent results to their non-LF counterparts and are expected to be advantageous in situations where no prior information is accessible, the targets are challenging to ascertain, and the distribution of targets is scarce. It has emerged as an alternative to Gaussian distribution (GD) to achieve randomization in MOA and have applications in diverse biological, chemical, and physical phenomena. The purpose of this article is to make the readers acquainted with the applicability of LF in some of the latest optimization algorithm applied in the field of metaheuristics. Also the present study deals with examination of basic underlying principle in the working of LF along with their related properties.

Introduction

Optimization (Rao 2009; Tayarani and Bennett 2014) is an act of obtaining the best results under the given set of conditions or constraints. In design and development of any engineering system, engineers have to take many technological and managerial decisions at different levels. The ultimate goal of every such decision is to minimize the effort required, as well as, to maximize the desired benefits. Optimization can, thus, be defined as the process of finding the conditions that give the maximum or minimum value of a function while satisfying or respecting certain constraints of the problem under consideration. Mathematically, it can be expressed as (Yang 2010a):

(1) $\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}{e}_{x\in R^n}{f}_i\left(x\right),\left(i=1,2,\dots ..,M\right)$(1)

(2) $\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}to{h}_j\left(x\right)=0,\left(j=1,2,\dots \dots ,J\right)$(2)

(3) $g_k\left(x\right)\le 0,\left(k=1,2,\dots \dots ,K\right)$(3)

(4) $x=(x_{1,}{x}_2,\dots ..,x_n{)}^T$(4)

where $f_i\left(x\right)$, $h_j\left(x\right)$, and $g_k\left(x\right)$ are functions of the design vector. Function $f_i\left(x\right)$ is called as objective function (Koziel, Leiffson, and Yang 2014) or cost function or energy function which is to be maximized or minimized. The component $x_i$ of x is called as decision variable or design variable. It can be discrete or continuous or combination of the two. The space spanned by the decision variables is called as design space or search space $R^n$, while the space formed by the objective function values is called the solution space or response space. Function $h_j\left(x\right)$ is called as equality constraint while the function $g_k\left(x\right)$ is called as inequality constraint of the optimization problem.

Optimization problems are encountered in almost all fields of science and engineering. Traditional optimization techniques are derivative-based, robust and have proven their effectiveness in solving different types of optimization problems. However, such techniques often encounter limitations such as getting trapped in local minima, highly sensitive to starting point, too much computational complexity and being or not being applicable to particular classes of objective functions (Radosavljević 2016). These led to the necessity of developing an alternative class of solution methods that could overcome these limitations. Metaheuristics (Blum and Roli 2003) are such methods developed in this direction. In recent years, metaheuristic algorithms are based upon the principle of evolutionary computation (Karafotias, Hoogendoorn, and Eiben 2015; Sutcliffe and Neville 2014) and have been successfully applied to hard (He, Chen, and Yao 2015) optimization problems. These are capable of solving general N-dimensional, linear and nonlinear optimization problems.

Metaheuristics

Metaheuristic is a solution blueprint which makes use of trial-and-error approach to determine admissible solutions (Hosny 2010; Sun, Garibaldi, and Hodgman 2012) to a circuitous problem within the time coercion. While the primary motive is to determine the feasible solutions, the complexity of the problem, sometimes, makes it impractical to explore every admissible solution in a legitimate timeframe. Further, there is no assurance that the best solutions will be explored. The endeavor is that an efficient and practical algorithm is developed that works most of the time and is able to produce good quality solutions. It is expected that among the best quality solutions, some are nearly optimal, though again there is no guarantee for such optimality (Osman and Laporte 1996; Talbi 2009; Yang 2010b).

The word heuristic has its origin from the Greek word “heuriskein”, which means the art of discovering new strategies (rules) to solve problems. The term “meta” is also a Greek word which means “upper level methodology”. Metaheuristic is thus defined as an upper level general methodology that can be used as guiding strategies in designing underlying heuristics to solve specific complex optimization problems (Vob et al. 1999; Yang 2013). However there are no agreed definitions of heuristics and metaheuristics and both the terms are interchangeably used in the literature. Some examples of metaheuristic algorithms (Slowik and Kwasnicka 2018) are Ant colony optimization (Korouzhdeh, Naddaf, and Nik 2017), Artificial bee colony algorithm (Karaboga and Basturk 2007), Bacterial foraging optimization algorithm (Das et al. 2009), Bat algorithm (Yang 2010e), Biogeography based optimization (Simon 2008), Cuckoo search (CS) (Yang and Deb 2009), Firefly algorithm (FA) (Yang 2009), Eagle strategy (ES) (Yang and Deb 2010b), Flower pollination algorithm (FPO) (Yang 2012), Genetic algorithm (GA) (Goldberg 1989), and Particle swarm optimization (PSO) (Kennedy and Eberhart 1995). These approaches provide near optimal solution in shorter time (Rezende, Lima, and Guimarães 2018) when exhaustive search is not a viable methods specifically for NP hard problems. Further if any algorithm ‘A’ supersedes/outperforms another algorithm ‘B’ in order to search for maxima or minima of an objective function, then algorithm ‘B’ will supersede/outperform ‘A’ over other objective functions (Yuen, Chow, Zhang, and Lou 2016). This implies that on an average algorithms ‘A’ as well as algorithm ‘B’ will perform equally well over all possible function space (Ho and Pepyne 2001; Wolpert and Macready 1997). Randomization avoids the situation that the solutions are getting trapped at local optima and at the same time it increases the diversity of the solutions. A good combination of selection of the best and randomization ensures that the global optimality (Ren, Zhang, and Koh 2013) is achieved and one of the most efficient ways of achieving randomization is the use of random walk (RW).

Random walk (RW)

A RW is a random process which consists of taking a series of arbitrary steps given by:

(5) $S_N={\sum }_{i=1}^N{X}_i=X_1+\dots +X_N,$(5)

where $S_N$ denotes the sum of each consecutive random step $X_i$ drawn from a random distribution. Equation (5)(5) $S_N={\sum }_{i=1}^N{X}_i=X_1+\dots +X_N,$(5) can also be written as:

(6) $S_N={\sum }_{i=1}^{N-1}{X}_i+X_N=S_{N-1}+X_N$(6)

which shows that the next state $S_N$ depends on the current existing state $S_{N-1}$ and the transition from existing state to next state. In order to find the solution to an optimization problem, we can explore the search space by conducting a RW beginning from an appropriate initial but random expected solution. Variety of solutions is often realized via randomization. However, simple or blind RW is not efficient. To be computationally efficient and potent in exploring for new solutions, the best solutions found so far may be retained, and the mobility of the RW should be increased so as to explore the search space more effectively. RW should be disciplined in such a way that it can travel in the direction of optimal solutions more swiftly, rather than depart from the possible best solutions. The search of food by many animals such as wolf is operated in a random or quasi random manner whereby the next move in its foraging direction depends upon its current location and transition probability to the next location and thus constitutes a RW (Labed, Fizazi, Mahi, and Galvan 2018).

As RWs are widely used for randomization and local search, a proper step size is very important. The step size in RW determines how much distance a random walker can travel for a given number of iterations. If it is too large, then the new solution generated will be too far away from the old solution. Then, such a move is unlikely to be accepted. If it is too small, the variation is too minute to be practical significance, and hence such search is again not efficient. So a proper step size is important to maintain an efficient search throughout the search space (Yang 2014).

From the theory of simple isotropic RWs, average distance r travelled in a d dimensional space is given by:

(7) $r^2=2dDt$(7)

where D is the effective diffusion coefficient given by:

(8) $D=s^2/2\tau$(8)

where $\tau$ is the time taken for each step size s. Solving Equations (7)(7) $r^2=2dDt$(7) and (8(8) $D=s^2/2\tau$(8) ) we get:

(9) $s^2=\frac{\tau r^2}{td}$(9)

As the iterations are discrete, we can take τ = 1 and for a typical length scale L of a dimension of interest, the local search is typically limited in the region of L/10.Therefore Equation (9)(9) $s^2=\frac{\tau r^2}{td}$(9) is simplified to:

(10) $s=\frac{r}{\sqrt{td}}=\frac{L/10}{\sqrt{td}}$(10)

Step size in a RW can be determined using Equations (9)(9) $s^2=\frac{\tau r^2}{td}$(9) and (10(10) $s=\frac{r}{\sqrt{td}}=\frac{L/10}{\sqrt{td}}$(10) ). Levy walk and Brownian motion (BM) are a kind of RW which are described in the subsequent sections.

Levy flight: basic concepts

Levy flights (LFs) are a class of non-Gaussian random processes whose stationary increments are distributed according to a Levy stable distribution (Yang et al. 2013a). The term ‘Levy’ in LF is originated from the name of French mathematician Paul Pierre Levy who first studied the Levy motion. Here the term flight is defined as the maximum straight line distance between two points that an object in motion covers without directional variation or halt. In literature, LF or Levy walk have been used interchangeably. It has been observed that scenario in which birds or animals acquire very little or no knowledge on where the resources might actually be present, LF can provide encounters with seldom and randomly distributed targets (e.g., prey) more effectively than BM which are efficient where targets are plenty and are more foreseeable (Yang 2014).

LF is a RW whose step size is derived from the Levy distribution (LD), which is a distribution of the sum of N identically and independently distributed random variables whose Fourier transform takes the following form:

(11) $F_N\left(k\right)=\mathrm{e}\mathrm{x}\mathrm{p}\left[-N{\left|k\right|}^{\beta }\right]$(11)

and the LD is given by the integral:

(12) $L\left(s\right)=\frac{1}{\pi }\underset{0}{\overset{\mathrm{\infty }}{\int }}\mathrm{c}\mathrm{o}\mathrm{s}\left(\tau s\right)e^{-\alpha {\tau }^{\beta }}d\tau ,(0<\beta \le 2)$(12)

where τ is short time interval during each step s and $\alpha$ is a constant which controls the scaling of the distribution and can take any positive value. For most applications the value of α is set equal to unity.

Equation (12)(12) $L\left(s\right)=\frac{1}{\pi }\underset{0}{\overset{\mathrm{\infty }}{\int }}\mathrm{c}\mathrm{o}\mathrm{s}\left(\tau s\right)e^{-\alpha {\tau }^{\beta }}d\tau ,(0<\beta \le 2)$(12) can be approximated as:

(13) $L\left(s\right)\sim s^{-1-\beta }$(13)

which is heavy tailed. The variance of such a power-law distribution is infinite for $0<\beta <2$. Index $\beta$ is a constant and is known as shape parameter. It controls the heaviness of the distribution. It means that it determines the decay of the tail. A small value of $\beta$ implies that the tail of the distribution contains considerable accumulation of the data, i.e., the random variable values are more likely to be far away from the mean of the distribution. On the other hand, a larger value of $\beta$ indicates that values of the random variable are at small distances from the mean of the distribution. Two special cases are β = 1 and β = 2. For β = 1, Equation (12)(12) $L\left(s\right)=\frac{1}{\pi }\underset{0}{\overset{\mathrm{\infty }}{\int }}\mathrm{c}\mathrm{o}\mathrm{s}\left(\tau s\right)e^{-\alpha {\tau }^{\beta }}d\tau ,(0<\beta \le 2)$(12) is called as the Cauchy distribution and for β = 2, it becomes the normal distribution. In this case, LF becomes the standard BM (Yang 2010a). In the d dimensional space, the variance of Brownian RW can be written as:

(14) ${\sigma }^2\left(t\right)=|v_0{|}^2{t}^2+\left(2dD\right)t$(14)

where $v_0$ is the drift velocity of the system and D is the is the effective diffusion coefficient which is related to the step size, s, over a short time interval τ during each step given by:

(15) $D=\frac{s^2}{2\tau }$(15)

BM thus obeys a GD with zero mean and time-dependent variance. A diffusion process when obeys the GD can be viewed as a series of BM.

Properties and attributes of LF

LF represents a widely used tool in the description of anomalous stochastic processes. By their mathematical definition, LF is Markovian and their statistical limit distribution emerges from independent identically distributed random variables, by virtue of the generalized central limit theorem. Various properties and attributes of LF are as follows.

Stable distribution

LD is a stable distribution whereby the sum of two independent random variables having a β stable distribution with index β is again β stable with the same index β. This invariance property, however, does not hold for different values of β.

Infinite mean and infinite variance

The mean as well the variance of LF is infinite (Rehman, Ali, and Khan 2017). All stable distribution with fatter tails than the GD has infinite variance (Yang 2010b). The key property of an infinite variance distribution is the average of independent draws is no less uncertain than a single draw. Tails with infinite mean and variance progress to zero slowly, while normal distribution goes to zero relatively rapidly.

Heavy tailed probability distribution

LF are a special class of generalized RW in which the step span during the walk are described by a heavy or fat tailed probability distribution or LD. The significance of the term “tail being heavy” here means that the tail of LD falls off much more gently as compared to a GD (Yang et al. 2013b). Further heavy tailed distribution is not exponentially bounded.

Inherent ability to escape local optimum

Variance of LD exhibits divergence characteristics. As a result, enormously long jumps may happen, and classical flights are self-similar, on all scales displaying bunches of smaller jumps intermingled by lengthy expeditions (Yang and Deb 2010b). The advantage of this kind of flight pattern is that it permits effective and efficient search of the distant regions of the function landscape in global optimization problems and aids the algorithm to escape local minimum particularly when the function landscape has profound and widespread basins.

Faster algorithm convergence

Use of LF minimizes the likelihood of returning back to already explored locations in the problem search space. This enhances the performance of the algorithm as the solution is not struck in any local optima and escapes out from it to explore another solution. It has been found that the number of iterations required to execute the program reduces by a factor of ${10}^4$ by the use of LF as compared to GD. It further reduces by a factor of ${10}^8$ by the use of ES in combination with LF and thus speeds up the overall convergence of the algorithm. The same is being mathematically explained in the subsequent sections.

Implementation of random numbers with LF

Implementation of random numbers with LF consists of two phases. The first phase consists of selecting the random direction and the second phase takes into consideration the generation of steps that follow the chosen LD. The selection of random direction is drawn from a uniform distribution.

The step length s can be calculated by:

(16) $s=\frac{u}{{\left|v\right|}^{1/\beta }}$(16)

where u and v are drawn from normal distributions. This implies that:

(17) $u\sim N\left(0,{\sigma }_u^2\right),v\sim N\left(0,{\sigma }_v^2\right),{\sigma }_u={\left\{\frac{\mathrm{\Gamma }\left(1+\beta \right)sin\left(\pi \beta /2\right)}{\mathrm{\Gamma }\left[\left(1+\beta \right)/2\right]\beta 2^{\left(\beta -1\right)/2}}\right\}}^{1/\beta },{\sigma }_v=1$(17)

This distribution follows the LD for $\left|s\right|$ $\ge \left|s_o\right|$, where $s_o$ is the smallest step.

Search efficiency of LF

LF has been witnessed among foraging activities of eagle, honeybee, shark, spider monkey and many other birds, animals and insects to name a few. Physical phenomena involving diffusion process of fluorescent molecules, the noise characteristics and cooling behavior also yields LF features under the accurate set of conditions. Studies have shown that LF-based algorithms yield superior or comparable outcomes from their non-LF counterparts in situations where no information about the availability of resources is available beforehand, the targets are difficult to detect, and the distribution of targets is meagre. Further, it has been found that LF has weaker fine-tuning capability than Gaussian distributed RW for small to mid-range search regions. The algorithms based on the GD control the search of the problem search space by varying its mean and standard deviation (σ). However, this mechanism of searching the solution space cannot be used due to infinite variance of LD.

If we consider a $d$ – dimensional space with characteristic length $L$ and accuracy $\delta$, the number of steps or iterations $N_{max}$ needed by RW which obeys the GD is given by the relationship:

(18) $N_{max}\approx \frac{L^2}{{\delta }^{2}d}$(18)

In Equation (18)(18) $N_{max}\approx \frac{L^2}{{\delta }^{2}d}$(18) , if we substitute the value of L = 10, d = 10 and $\delta ={10}^{-5}$, then the value of $N_{max}$ comes out to be approximately,

(19) $N_{max}\approx {10}^{11}$(19)

Now if employ LF instead of GD, the value of $N_{max}$ can be approximated (Yang 2014) as:

(20) $N_{max}\approx {\left(\frac{L^2}{{\delta }^{2}d}\right)}^{1/3-\beta },\beta =1.5,N_{max}\approx 2\ast {10}^7$(20)

Thus it can be inferred from Equation (20)(20) $N_{max}\approx {\left(\frac{L^2}{{\delta }^{2}d}\right)}^{1/3-\beta },\beta =1.5,N_{max}\approx 2\ast {10}^7$(20) that LF reduces the number of iterations by about 4 orders [O(10⁴)] from [O(10¹¹)] to [O(10⁷)]. Reduction can be even more, if other values of β are used. ES in combination with LF can further reduce the number of iterations more significantly, from [O(10¹¹)] to [O(10³)] (Yang 2014).

LF in metaheuristics

LF has been successfully applied to some of the latest optimization algorithms (Fister et al. 2013b) in the field of metaheuristics such as FA, CS, Bat algorithm, FPO, ES, and many more. These recent algorithms have been efficaciously realized in wide range of problems in engineering and sciences. The usage of LF in these algorithms is described as follows.

Flower pollination algorithm

FPA is inspired from the pollination process among flowering plants in which the reproduction between flowers takes place by transfer of pollen from one flower to another (Yang 2012). Pseudocode and rules governing the FPA are described in (Chakravarthy and Rao 2015; Yang, Karamanoglu, and He 2013).

In the global pollination process, flower pollen gametes are carried by pollinators such as insects, and pollen can travel over a long distance because insects can often fly and move in a much longer range obeying Levy walk characteristics (Gautam, Malmathanraj, and Srivastav 2015). This can be represented mathematically as:

(21) $x_i^{t+1}=x_i^t+\gamma L\left(x_i^t-g_{\ast }\right)$(21)

where $x_i^t$ is the pollen $i$ or solution vector $x_i$ at iteration $t$, and $g_{\ast }$ is the current best solution found among all solutions at the current generation/iteration. Here $\gamma$ is a scaling factor to control the step size. Since insects may move over a long distance with various distance steps, LF can be used to mimic this characteristic efficiently. LD for L > 0 is given by:

(22) $L\sim \frac{\beta \mathrm{\Gamma }\left(\beta \right)\mathrm{s}\mathrm{i}\mathrm{n}(\pi \beta /2)}{\pi }\frac{1}{s^{1+\beta }},(s\gg s_0>0)$(22)

here, Γ $\beta$ is the standard gamma function, and this distribution is valid for large steps s > 0 and $s_0$ is the smallest step.

Local pollination (Huang et al. 2015) can be mathematically represented as:

(23) $x_i^{t+1}=x_i^t+ϵ\left(x_j^t-x_k^t\right)$(23)

where $x_j^t$ and $x_k^t$ are pollen from different flowers of the same plant species. If $x_j^t$ and $x_k^t$ comes from the same species or selected from the same population, it becomes a local RW if $ϵ$ is drawn from a uniform distribution.

Cuckoo search

CS algorithm was developed by Yang and Deb in 2009. In CS each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The aim is to use the new and potentially better solutions (cuckoos) to replace a not-so-good solution in the nests (Rajabioun 2011) .For pseudocode, rules governing CS and its detailed mathematical analysis readers may refer to Yang and Deb (2009).

When generating new solutions $x_i^{\left(t+1\right)}$ for, say cuckoo i, a LF is performed as:

(24) $x_i^{\left(t+1\right)}=x_i^{\left(t\right)}+\alpha \oplus \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}\left(\beta \right)$(24)

where α > 0 is the step size which is related to the scales of the problem of interest. The product $\oplus$ means entry-wise multiplications. $\mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}\left(\beta \right)$ is the LF which provides a RW and their random steps are drawn from a LD given by Equation (22)(22) $L\sim \frac{\beta \mathrm{\Gamma }\left(\beta \right)\mathrm{s}\mathrm{i}\mathrm{n}(\pi \beta /2)}{\pi }\frac{1}{s^{1+\beta }},(s\gg s_0>0)$(22) . The consecutive jumps/steps of a cuckoo form a RW process which obeys a power-law step length distribution with a heavy tail. In the real world, if a cuckoo’s egg is very similar to a host’s eggs, then this cuckoo’s egg is less likely to be discovered. Thus the fitness is related to the difference in solutions (Chawla and Duhan 2014; Yang and Deb 2013). The comparative study of the CS on a small set of test functions by Yang and Deb (2010a) against PSO and GA showed that the convergence behavior of CS in terms of mean and standard deviation of number of function evaluations is superior to both GA and PSO. The use of LF in the CS (Rehman, Ali, and Khan 2017) suggests that it is possible to find all the optima in a problem search space for multimodal functions.

Eagle strategy

Foraging activity of an eagle is a two-stage approach (Yang, Deb, and He 2013). Initially, in search of food an eagle flies freely in a random manner much like a LF and executes the Levy walk in the entire territory. Once it is able to detect a target it shifts to a chase stratagem so as to get hold of the target as efficiently as possible. ES mixes a good combination of exploration with an intensive and efficient local search method. In order to evade the solution being stuck locally, an exploratory search is executed again followed by exploitation search and the procedure is repeated iteratively (Yang et al. 2014). ES uses two diverse algorithms at varied stages and at different times of the iterations. It employs LF for global exploration. This first step provides adequate randomness to search the function landscape as distinctly and efficiently as probable. In the second step process, the algorithm used for the intensive local search should be an efficient local optimizer such as PSO or FPA or any other metaheuristics to find the local optimum within a minimum number of function evaluations. This stage is fast and efficient compared to the first global exploration stage. It has been tested that ES outperformed PSO and other metaheuristics in terms of efficiency and success rate (Yang and Deb 2012).

Firefly algorithm

FA developed by Yang is based on the idealized behavior of the flashing characteristics of fireflies. Rules governing the FA and its pseudocode can be found in literature (Yang 2010c, 2010d).

Attractiveness of a firefly is determined by its brightness or light intensity which in turn is associated with the encoded objective function. For optimization problems (Marichelvam, Prabaharan, and Yang 2014; Yang 2015), the brightness of a firefly at a particular location x can be chosen as $I\left(x\right)$. This brightness is proportional to the value of the objective function $f\left(x\right)$. The brightness of a firefly can be mathematically expressed as:

(25) $I=I_0{e}^{-\gamma r^2}$(25)

where $I_0\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{I}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{y}$, r is the distance between two fireflies and $\gamma$ is the light absorption coefficient.

The distance between any two fireflies $i$ and $j$ at $x_i$ and $x_j$, respectively, is given by:

(26) $r_{ij}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$(26)

The attractiveness β between two fireflies is given by:

(27) $\beta ={\beta }_0{e}^{-\gamma r^2}$(27)

where ${\beta }_0\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{t}r=0.$ Theoretically the value of $\gamma ϵ$[0, $\mathrm{\infty }).$ It characterizes the variation of the attractiveness, and its value is crucially important in determining the speed of the convergence and how the FA algorithm behaves.

The movement of a firefly $i$ is attracted to another more attractive (brighter) firefly $j$ is determined by:

(28) $x_i=x_i+{\beta }_0{e}^{-\gamma r_{ij}^2}\left(x_j-x_i\right)+\alpha sign\left(rand-\frac{1}{2}\right)\oplus \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}$(28)

where the second term is due to the attraction while the third term is randomization via LF with $\alpha ϵ\left[0,1\right]$ being the randomization parameter. The $sign\left(rand-\frac{1}{2}\right)$ where $rand$ ε [0, 1] essentially provides a random sign or direction while random step length is drawn from LD. $\mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}$ is same as described in Equation (22)(22) $L\sim \frac{\beta \mathrm{\Gamma }\left(\beta \right)\mathrm{s}\mathrm{i}\mathrm{n}(\pi \beta /2)}{\pi }\frac{1}{s^{1+\beta }},(s\gg s_0>0)$(22) . Ever since its inception FA has been applied to almost all fields of engineering including industrial optimization, image processing, antenna design, business optimization, civil engineering, robotics, semantic web, meteorology, wireless sensor networks (Fister et al. 2013a).

Bat algorithm

Bat algorithm (BA) is based upon the echolocation behavior of bats (Yang 2010a). Echolocation works as a type of sonar. Bats, mainly microbats, emit a loud and short pulse of sound, wait for it to strike an object and, after a fraction of time, the echo returns back to their ears . Thus, bats can compute how far they are from an object. Echolocation capabilities of microbats can be associated with the objective function to be optimized and optimization algorithms can be formulated that mimic this bat behavior in finding the optimal solution (Chawla and Duhan 2015).

To understand the pseudocode of BA along with its defined set of rules as to how the BA works, readers may refer to Yang (2011).

New solutions are generated by adjusting frequencies, loudness and pulse emission rates of the bats, while the proposed solution is accepted or not depends on the quality of the solutions controlled or characterized by loudness and pulse rate which are in turn related to the closeness or the fitness of the locations/solution to the global optimal solution (Pandya, Dabhi, and Joshi 2015).

For BA to be used in simulation analysis, rules are defined as to how their positions $x_i$ and velocities $v_i$ are updated in $d$-dimensional search space. The new solutions, $x_i^t$ and velocities, $v_i^t$ at time step t are given by:

(29) $v_i^t=v_i^{t-1}+\left(x_i^t-x_{\ast }\right)f_i$(29)

(30) $x_i^t=x_i^{t-1}+v_i^t$(30)

where $x_{\ast }$ is the current global best location (solution) which is located after comparing all the solutions among all the n bats at each iterations $t$. Frequency $f_i$ is used to adjust the velocity change and is given by:

(31) $f_i=f_{min}+\left(f_{max}-f_{min}\right)\beta$(31)

where $f_{min}$,$f_{max}$ are the minimum/maximum frequency of the pulse emitted by the bats; $\beta \in \left[0,1\right]$ is a random vector drawn from a uniform distribution. Once a solution is selected among the current fittest solution, a new solution for each bat is generated locally using RW given by:

(32) $x_{new}=x_{old}+ϵA^t$(32)

where $ϵ$ is a random number in the range [−1, 1] and $A^t=⟨A^t⟩$ is the average loudness of all the bats at this time step.

Once a bat has found a prey, its loudness decreases while the rate of pulse emission increases. The bat moves toward optimal solution according to two design equations given by:

(33) $A_i^{t+1}=\alpha A_i^t$(33)

(34) $r_i^{t+1}=r_i^0\left[1-exp\left(-\gamma t\right)\right]$(34)

where $\alpha$ and $\gamma$ are constants. The value of $\alpha$ lies between 0 and 1, i.e., $0<\alpha <1$,while that of $\gamma$ is greater than 0 .i.e., $\gamma >0$ $.A_i^{t+1}$ is the loudness of the bat at time step $t+1$ and $A_i^t$ is the loudness of the bat at time step t $r_i^{t+1}$ is the rate of pulse emission at time step $t+1$ and $r_i^0$ is the initial rate of pulse emission. As the time step, $t$ approaches infinite average loudness of the bat goes to zero, while the rate of pulse emission approaches initial rate of pulse emission. This can be expressed as:

(35) $A_i^t\to 0,r_i^t\to r_i^0,ast\to \mathrm{\infty }$(35)

LF was incorporated in BA employing chaotic sequence (Lin et al. 2012), whereby, Equation (32)(32) $x_{new}=x_{old}+ϵA^t$(32) was replaced by a new equation given by:

(36) $x_{new}=x_{old}+c_s\oplus \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}$(36)

where $C_s$ is the chaotic sequence and is given by:

(37) $C_s\left(t+1\right)=4C_s\left(t\right)\left(1-C_s\left(t\right)\right),0\le C_s\left(0\right)\le 1$(37)

Use of LF in BA was also successfully performed by Xie, Zhou, and Chen (2013).Here the bats perform the LF before the position updating and is given by:

(38) $x_i^t=x_i^{t-1}+\mu sign\left[rand-0.5\right]\oplus Levy$(38)

where $\mu$ is a random parameter drawn from a uniform distribution, $sign,randandLevy$ are same as used in Equation (28)(28) $x_i=x_i+{\beta }_0{e}^{-\gamma r_{ij}^2}\left(x_j-x_i\right)+\alpha sign\left(rand-\frac{1}{2}\right)\oplus \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}$(28) . BA is a very promising algorithm and has been proven to have good convergence properties on different benchmark functions (Jamil and Yang 2013).

Levy particle swarm

Use of LF in PSO (Kennedy and Eberhart 1995), modified PSO (Knypinski, Nowak, and Jedryczka 2015) was performed by Richer and Blackwell (2006) by replacing the motion of the particles with LF in order to solve optimization problem more effectively. In order to analyze the effectiveness of Levy based PSO, a series of experiments were conducted on problem set of nine different benchmark functions. It was found that Levy based PSO outperformed standard PSO in terms of faster convergence. The better performance of Levy PSO was due to LD with fat tail characteristics.

Fast evolutionary programming

Lee and Yao (2004) proposed fast evolutionary programming (FEP) by replacing Gaussian based mutation with a Cauchy distribution which is a special case of LD. FEP converged to a better solution compared to conventional evolutionary programming for many multivariate functions that were investigated in the study. The proposed algorithm (Lee and Yao 2004) was tested and compared on 14 different benchmark functions with three unimodal functions, six multimodal functions with many local minima, and five multimodal functions with relatively fewer local minima. Through a series of experiments carried out, it was observed that both the nonadaptive and adaptive Levy mutations were more robust compared to the evolutionary programming built on Gaussian and Cauchy mutations.

LF-based artificial bee colony optimization algorithm

LF-based artificial bee colony (ABC) optimization algorithm (Sharma, Bansal, Arya, and Yang 2016) designated as LFABC incorporates local and global search capability simultaneously by automatically tuning the step size by means of regulating the LF parameters. In this algorithm, new solutions were generated in the vicinity of best solutions depending upon the newly introduced parameter called as perturbation rate which was missing in the original ABC algorithm. Simulation results obtained by the authors revealed that LFABC outperformed other algorithms in the test performed on five real world optimization problems in terms of the accuracy, reliability, and efficiency.

LF-based ant colony optimization

The performance of original ant colony optimization (ACO) algorithm was improved by using LF to perform the local search. This new variant (Wang and Liang 2016) of ACO based on LF was given the name as Levy flight ant colony optimization (LFACO). The performance of LFACO was compared with ACO, GA, and PSO and found to have superior results on test performed on 20 different benchmark functions. The improvement in results was due to the reduced search time and search stagnation by the use of LF.

LF-based gray wolf optimizer with back propagation

Amirsadri, Mousavirad, and Komleh (2017) introduced LF-based gray wolf optimizer (GWO) blended with back propagation (BP) for training neural networks. In the first step, GWO algorithm was improved by utilizing LF capabilities which increases the exploration, and then in the next step improved GWO algorithm in combination with BP (which increases the exploitation capability) was applied to train the neural network. Each wolf in this new approach represented the weights and the biases set in the neural network. The performance of this new algorithm was experimentally evaluated by comparing it with well-known MOA on 12 function approximation and classification data sets and was found to have superior results.

LF animal migration optimization algorithm

LF animal migration optimization (LAMO) algorithm (Bhamb and Kumar 2016) emulate the foraging behavior of animals and how they get access to a secure habitat. This algorithm is simulated by intellectual demeanor of animals as to how they move from the present habitat to a new habitat and how some animal leave the group while few others add up to the group. There are two phases involved in this procedure. One is called as the migration, while the other is the population update. The population update step in the basic animal migration optimization (AMO) algorithm was improved using LF and thus was abbreviated as LAMO. The recital of LAMO was carried out on 21 benchmark functions and showed superior grades over AMO in terms of improved reliability, robustness, and efficiency.

LF trajectory based whale optimization algorithm

LF trajectory-based whale optimization algorithm (LWOA) developed by Ling, Zhou, and Luo (2017) enhances the performance of original whale optimization algorithm (WOA) by making the algorithm more robust, yielding faster results, and avoiding premature convergence. LWOA is characterized by quick convergence and high precision by the use of LF .The LF trajectory escalates the diversity of the populace against premature convergence and raises the potential of jumping out of local optimal optima. The performance of LWOA was evaluated on 23 benchmark functions and the results obtained were compared with other well-known MOA available in the literature. Comparison of simulation results exhibited superior performance of LWOA over existing techniques.

Other algorithms based on LF

Recently, there have been several other MOA incorporating LF to improve upon their performance characteristics as reported in the literature. Some of them includes LF moth flame optimization (LMFO) algorithm (Li, Zhou, Zhang, and Song 2016) inspired by the direction-finding technique of moth flies; patch levy-based bees algorithm (PLBA) (Husseina, Sahranb and Abdullah 2015) motivated by the food-searching behavior of swarm of honeybees; LF in binary optimization (Klimt, Kukal, and Mojzes 2013) introducing binary mutations inspired by LF; hybrid gravitational search with Levy flight (HGSLF) (Ali 2015) emulating the natural phenomenon of law of gravity and mass interactions; differential crow search algorithm (Xuejing, et al. 2018) based on LF for solving discount {0–1} knapsack problem and improved crow search algorithm (Díaz et al. 2018) using LF applied to energy problems.

Conclusions

A LF is a RW in which the steps are defined in terms of the step spans, which follow Levy probability distribution, with the directions of the steps being isotropic and arbitrary. In recent years, the use of LF has arisen as a substitute to GD to achieve randomization in metaheuristics optimization algorithms (MOA). Random walkers based on the LD spends a greater amount of CPU time in exploring a wide area of the search space and lesser time in exploiting the small local neighborhood compared to random walkers based on the GD. LF seems to be propitious in unraveling a vast domain of multimodal problems without the need to enact function stretching or niching procedures. These methods are commonly employed in MOA to help the algorithm find multiple solutions. The probability density functions of Levy stable laws decay in asymptotic power-law form with diverging variance due to their heavy tail and belongs to a special class of symmetric $\beta$ stable LD and thus appear instinctively in the determination of many vacillation processes with predominantly scattering statistics typified by bursts or vast outliers. Also, Levy stable laws provide statistical explanation for widespread class of operations in physical, chemical, biological and even financial domains. In the years to come, LF will certainly be used by the researchers in various disciplines of science and engineering all over the world to explore the search space more efficiently in order to solve real world global optimization problems.