What is Lévy Flight?

Lévy Flight or Lévy Step is commonly used in modern swarm-based algorithms, especially by Prof. Xin-She Yang's algorithms. The Lévy step is based on Lévy distribution, which allows the movement to be large or small. This is a closer mimic of the natural movement of swarms than the traditional Gaussian step. This is usually compared with the Gaussian step (Brownian) where the step length is quite uniform.

Lévy step is at the heart of XS Yang's metaheuristic search algorithms like Flower Pollination Algorithm (FPA, 2012), Cuckoo Search (CS, 2009), Firefly Algorithm (FA, 2009), Bat Algorithm (BA, 2010), for example.

x_t+1 = x+t + L=levy()*(best_soln - x_t)

The FPA applies Lévy step to attract the solution to the global best solution in the exploitation step.

Also Lévy step can be used in the perturbation step like

x_t+1 = x_t + eps*levy()

where eps is a scaling factor typically random number in [-1,1] or [0,1]

Here is a MATLAB function to compute a Lévy step

function step = levy(lambda, dim, scale)

% LEVY  Generate Lévy-flight step(s) using Mantegna's algorithm.

%   step = levy(lambda, dim, scale)

%   lambda : Lévy exponent, typical 1.2–1.8 (Yang often uses 1.5)

%   dim    : dimension of the step vector

%   scale  : overall scale factor (γ in Yang’s papers), e.g., 0.01–0.2

%

%   Returns:

%     step (1 x dim) Lévy-distributed step lengths.



if nargin < 3, scale = 0.1; end

if nargin < 2, dim   = 1;   end

if nargin < 1, lambda= 1.5; end



% Mantegna parameters

sigma_u = ( gamma(1+lambda) * sin(pi*lambda/2) / ...

           ( gamma((1+lambda)/2) * lambda * 2^((lambda-1)/2) ) )^(1/lambda);



u = sigma_u .* randn(1, dim);

v = randn(1, dim);

step = scale * ( u ./ (abs(v).^(1/lambda)) );

end

Compare Lévy step with Brownian's

What is the effect of Lambda?

It should be noted that the smaller value of Lambda brings the Lévy step close to the Brownian step.