Firefly Algorithm belongs to a broader set of nature inspired algorithms, namely evolutionary algorithms. In this case, the behavior of fireflies is our source of inspiration. This particular algorithm is credited to Xin she yang, who has also worked with various other evolutionary algorithms.
FA is a meta-heuristic algorithm, and although it doesn't give us the optimal solution, it does give a solution which is close enough approximation to the optimal solution.
It is suitable for those situations where the information is unkown or is only partially known. Even though it is still a relatively new algorithm, it is already showing to be a favorable choice to handle NP hard problems
The basic principle on which this algorithm runs is that all fireflies glow, and that the glow of a firefly is a measure of its attractiveness. Thus a firefly which perceives a more brightly glowing firefly nearby will be attracted towards it.
To get started on the algorithm, we first need to go through some terminology
1 A Population set X, where each member is characterized by its position.
2 An Objective Function f(x) to measure the glow at position xi .
The concepts involved are :
1. Attractiveness
Let us take a firefly at location i and examine how it perceives a firefly at location j. Now the attractiveness(brightness of light) emitted by firefly i at its own location is obtained by the value of objective function at i, that is Ii=f(i).
Also the firefly j also emits light, whose value at location j is given by Ij=f(j). Now its perceived brightness at location i is somewhat dampened by the absorbing nature of the medium in which the light travels (gamma). The exact formula is ,
Io* e(-gamma*d2) [ note - a faster variant would be to use the formuls Io/(1 +gamma*d2) ]
where,
Io = Ij
d = Euclidean distance between i and j
Now if this perceived brightness is more than Ii that means that for i, j appears more attractive and hence it should move towards it.
2. Movement
When we decide that firefly j is brighter than firefly i, then we move firefly i. The formula for calculating the new position of firefly i is given by
insert formula
where
the first term is the initial position
the second term is the direct move towards the brighter firefly j
the third move is the random step in any direction.
The pseudo code of basic FA is :
pop=random_populate(n); // initialize a random population X of size n and store in pop
f(x); // define a objective function f (x)
while(t<max_iterations) //loop counter to keep an upper limit on number of iterations
for i = 1....n
for j = 1...n // double loop for each pair of fireflies
if ( effect of light source at location j i.e f (pop.j) at location i > f (pop.i) ) // if firefly j is brighter than firefly i
move(pop.i); // move toward firefly j
end for j;
end for i;
t++;
//rank the fireflies according to the objective function and find the current best
end while;
keeping value of gamma as 0 means that the medium does not absorb any light, and that intensity due to firefly x at location i is same as that observed at j. for any i and j.Similarly keeping value of gamma as a very large number means that the medium is very dense. In that case the FA reduces to a random search in the search space.
keep value of alpha as a small fraction of the scale of dimension values we are dealing with(for a particular dimension), ideally 0.1 of the scale of the dimension.This helps in controlling the randomness a little while also not totally neglecting its contribution to the movement of the fireflies.
In practice it has been found out that firefly algorithm is generally superior to Genetic Algorithms(GA) or Particle Swarm Optimization algorithm(PSO).In fact, FA can find the global optima as well as all the local optima simultaneously in a very effective manner.Hence it is a multi-modal optimization algorithm.
It is possible to improve the solution quality by reducing the randomness gradually(in the movement step). We could vary the randomization parameter(alpha) so that it decreases gradually as the optima are approaching(as the number of iterations increases).
It is still a young algorithm, and more and more areas of its application are still coming up.For example, it can be used to tune parameters of a Neural Network, SVM and so forth. It is developing to be an exciting field of research.
