Firefly algorithm

The firefly algorithm (FA) is a metaheuristic algorithm, inspired by the flashing behaviour of fireflies. The primary purpose for a firefly's flash is to act as a signal system to attract other fireflies. Xin-She Yang formulated this firefly algorithm by assuming:

1. All fireflies are unisexual, so that any individual firefly will be attracted to all other fireflies;
2. Attractiveness is proportional to their brightness, and for any two fireflies, the less bright one will be attracted by (and thus move towards) the brighter one; however, the intensity (apparent brightness) decrease as their mutual distance increases;
3. If there are no fireflies brighter than a given firefly, it will move randomly.

The brightness should be associated with the objective function.

Firefly algorithm is a nature-inspired metaheuristic optimization algorithm.

Algorithm description

The pseudo code can be summarized as:

Begin
   1) Objective function: $f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,...,x_d)$;
   2) Generate an initial population of fireflies $\mathbf{x}_i \quad (i=1,2,\dots,n)$;.
   3) Formulate light intensity I so that it is associated with $f(\mathbf{x})$
      (for example, for maximization problems, $I \propto f(\mathbf{x})$ or simply $I=f(\mathbf{x})$;)
   4) Define absorption coefficient γ
 
   While (t < MaxGeneration)
      for i = 1 : n (all n fireflies)
         for j = 1 : n (n fireflies)
            if ($I_j>I_i$),
               move firefly i towards j;
               Vary attractiveness with distance r via $\exp(-\gamma \; r)$;
               Evaluate new solutions and update light intensity;
            end if 
         end for j
      end for i
      Rank fireflies and find the current best;
   end while

   Post-processing the results and visualization;

end

The main update formula for any pair of two fireflies $\mathbf{x}_i$ and $\mathbf{x}_j$ is

$\mathbf{x}_i^{t+1}=\mathbf{x}_i^t + \beta \exp[-\gamma r_{ij}^2] (\mathbf{x}_j^t - \mathbf{x}_i^t) +\alpha_t \boldsymbol{\epsilon}_t$

where $\alpha_t$ is a parameter controlling the step size, while $\boldsymbol{\epsilon}_t$ is a vector drawn from a Gaussian or other distribution.

It can be shown that the limiting case $\gamma \rightarrow 0$ corresponds to the standard Particle Swarm Optimization (PSO). In fact, if the inner loop (for j) is removed and the brightness $I_j$ is replaced by the current global best $g^*$, then FA essentially becomes the standard PSO.

Implementation Guides

The $\gamma$ should be related to the scales of design variables. Ideally, the $\beta$ term should be order one, which requires that $\gamma$ should be linked with scales. For example, one possible choice is to use $\gamma=1/\sqrt{L}$ where $L$ is the average scale of the problem. In case of scales vary significantly, $\gamma$ can be considered as a vector to suit different scales in different dimensions. Similarly, $\alpha_t$ should also be linked with scales. For example, $\alpha_t \leftarrow 0.01 L \alpha_t$. It is worth pointing out the above description does not include the randomness reduction. In fact, in actual implementation by most researchers, the motion of the fireflies is gradually reduced by an annealing-like randomness reduction via $\alpha=\alpha_0 \delta^t$ where $0< \delta <1 (e.g., \delta=0.97)$, though this value may depend on the number of iterations. In some difficult problem, it may be helpful if you increase $\alpha_t$ at some stages, then reduce it when necessary. This non-monotonic variation of $\alpha_t$ will enable the algorithm to escape any local optima when in the unlikely case it might get stuck if randomness is reduced too quickly.

Parametric studies show that n (number of fireflies) should be about 15 to 40 for most problems. A python implementation is also available, though with limited functionalities.

Recent studies shows that the firefly algorithm is very efficient, and could outperform other metaheuristic algorithms including particle swarm optimization. Most metaheuristic algorithms may have difficulty in dealing with stochastic test functions, and it seems that firefly algorithm can deal with stochastic test functions very efficiently. In addition, FA is also better for dealing with noisy optimization problems with ease of implementation.

Chatterjee et al. showed that the firefly algorithm can be superior to particle swarm optimization in their applications, the effectiveness of the firefly algorithm was further tested in later studies. In addition, firefly algorithm can efficiently solve non-convex problems with complex nonlinear constraints. Further improvement on the performance is also possible with promising results.

Theoretical Analysis

Although much progress has been achieved FA-based algorithms since 2008, significant efforts are required to further improve the performance of FA:

• Theoretical analysis for convergence trajectory;
• Deriving the sufficient and necessary conditions for the selections of control coefficients;
• Efficient strategies or mechanisms for the selections of the control parameters;
• Non-homogeneous update rules for enhancing the search ability, was proposed in ref.

Variants of Firefly Algorithm

A recent, comprehensive review showed that the firefly algorithm and its variants have been used in almost all areas of science There are more than twenty variants:

Adaptive Firefly Algorithm (AdaFa)

An adaptive variant of firefly algorithm, termed AdaFa, was proposed in ref. In AdaFa, the parameter selection and adaptation strategies are investigated. There are three strategies in AdaFa including (1) a distance-based light absorption coefficient; (2) a gray coefficient enhancing fireflies to share difference information from attractive ones efficiently; and (3) five different dynamic strategies for the randomization parameter. Promising selections of parameters in the strategies are analyzed to guarantee the efficient performance of AdaFa.

Discrete Firefly Algorithm (DFA)

A discrete version of Firefly Algorithm, namely, Discrete Firefly Algorithm (DFA) proposed recently by M. K. Sayadi, R. Ramezanian and N. Ghaffari-Nasab can efficiently solve NP-hard scheduling problems. DFA outperforms existing algorithms such as the ant colony algorithm.

For image segmentation, the FA-based method is far more efficient to Otsu's method and recursive Otsu. Meanwhile, a good implementation of a discrete firefly algorithm for QAP problems has been carried out by Durkota.

Multiobjective FA

An important study of FA was carried out by Apostolopoulos and Vlachos, which provides a detailed background and analysis over a wide range of test problems including multobjective load dispatch problem.

Lagrangian FA

An interesting, Lagrangian firefly algorithm is proposed to solve power system optimization unit commitment problems.

Chaotic FA

A chaotic firefly algorithm (CFA) was developed and found to outperform the previously best-known solutions available.

Hybrid Algorithms

A hybrid intelligent scheme has been developed by combining the firefly algorithm with the ant colony optimization.

Firefly Algorithm Based Memetic Algorithm

A firefly algorithm (FA) based memetic algorithm (FA-MA) is proposed to appropriately determine the parameters of SVR forecasting model for electricity load forecasting. In the proposed FA-MA algorithm, the FA algorithm is applied to explore the solution space, and the pattern search is used to conduct individual learning and thus enhance the exploitation of FA.

Parallel Firefly Algorithm with Predation (pFAP)

An implementation for shared memory environments with the addition of a predation mechanism that helps the method to escape local optimum.

Modified Firefly Algorithm

Many variants and modifications are done to increase its performance. A particular example will be modified firefly algorithm by Tilahun and Ong ., in which the updating process of the brightest firefly is modified to keep the best result throughout the iterations.

Applications

Digital Image Compression and Image Processing

Very recently, an FF-LBG algorithm for vector quantization of digital image compression was based on the firefly algorithm, which proves to be faster than other algorithms such as PSO-LBG and HBMO-LBG (particle swarm optimization and honey-bee mating optimization; variations on the Linde–Buzo–Gray algorithm). For minimum cross entropy thresholding, firefly-based algorithm uses the least computation time Also, for gel electrophoresis images, FA-based method is very efficient.

Eigenvalue optimization

Eigenvalue optimization of isospectral systems has solved by FA and multiple optimum points have been found efficiently.

Nanoelectronic Integrated Circuit and System Design

The multiobjective firefly algorithm (MOFA) has been used for the design optimization of a 90 nm CMOS based operational amplifier (OP-AMP) which could perform simultaneous power minimization and slew rate maximization within 500 iterations.

Feature selection and fault detection

Feature selection can be also carried out successfully using firefly algorithm. Real-time fault identification in large systems becomes viable, based on the recent work on fault identification with binary adaptive firefly optimization. A hybrid filter-wrapper feature selection for load forecasting is proposed based on Firefly Algorithm.

Antenna Design

Firefly algorithms outperforms ABC for optimal design of linear array of isotropic sources and digital controllable array antenna. It has found applications in synthesis of satellite footprint patterns as well.

Structural Design

For mixed-variable problems, many optimization algorithms may struggle. However, firefly algorithm can efficiently solve optimization problems with mixed variables.

Scheduling and TSP

Firefly-based algorithms for scheduling task graphs and job shop scheduling requires less computing than all other metaheuristics. A binary firefly algorithm has been developed to tackle the knapsack cryptosystem efficiently Recently, an evolutionary discrete FA has been developed for solving travelling salesman problems Further improvement in performance can be obtained by using preferential directions in firefly movements.

Semantic Web Composition

A hybrid FA has been developed by Pop et al. for selecting optimal solution in semantic web service composition.

Chemical Phase equilibrium

For phase equilibrium calculations and stability analysis, FA was found to be the most reliable compared with other techniques.

Clustering

Performance study for clustering also suggested that firefly algorithm is very efficient.

Dynamic Problems

Firefly algorithm can solve optimization problems in dynamic environments very efficiently.

Rigid Image Registration Problems

Firefly algorithm can solve the rigid image registration problems more efficient than genetic algorithm, particle swarm optimization, and artificial bee colony

Protein Structure Prediction

Prediction of protein structures is NP-hard, and a recent study by Maher et al. shows that firefly-based methods can speed up the predictions. Firefly algorithm can solve two dimensional HP model. In their experiment, they took 14 sequences of different chain lengths from 18 to 100 as the dataset and compared the FA with standard genetic algorithm and immune genetic algorithm. The averaged energy convergence results show that FA achieves the lowest values.

Parameter Optimization of SVM

Firefly algorithm (FA)is applied to determine the paraemters of MSVR (Multiple-output support vector regression) in interval-valued stock price index forecasting.

Meanwhile, a firefly algorithm (FA) based memetic algorithm (FA-MA) is proposed to appropriately determine the parameters of SVR forecasting model for electricity load forecasting. In the proposed FA-MA algorithm, the FA algorithm is applied to explore the solution space, and the pattern search is used to conduct individual learning and thus enhance the exploitation of FA.

IK-FA, Solving Inverse Kinematics using FA

FA, heuristic is used as inverse kinematics solver. The proposal is called IK-FA, for inverse Kinematics using Firefly Algorithm. Inverse kinematic consists in finding a valuable joints solution allowing achieving a specific end segment position. The proposed method used a forward kinematics model, the FA heuristic, a fitness function and a set of motions constraints, to solve inverse kinematics.

See also

• Evolutionary multi-modal optimization
• Glowworm swarm optimization (GSO)
• Metaheuristic
• Swarm intelligence

External links

• Firefly Algorithm implemented in Python
• Firefly Algorithm in C/C++
• Firefly Algorithm in Matlab or Octave