View source for Modal depth


The '''firefly algorithm (FA)''' is a metaheuristic [[algorithm]], inspired by the flashing behaviour of [[firefly|fireflies]]. The primary purpose for a firefly's flash is to act as a signal system to attract other fireflies. [[Xin-she Yang|Xin-She Yang]] formulated this firefly algorithm by assuming:<ref>{{cite book |first=X. S. |last=Yang |title=Nature-Inspired Metaheuristic Algorithms |location=Frome |publisher=Luniver Press |year=2008 |isbn=1-905986-10-6 }}</ref>

#All fireflies are unisexual, so that one firefly will be attracted to all other fireflies;
#Attractiveness is proportional to their brightness, and for any two fireflies, the less bright one will be attracted by (and thus move to) the  brighter one; however, the brightness can decrease as their distance increases;
#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 (mathematics)|optimization]] [[algorithm]].

== Algorithm description ==
The pseudo code can be summarized as:

 '''Begin'''
    1) Objective function: <math>f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,...,x_d) </math>;
    2) Generate an initial population of fireflies <math> \mathbf{x}_i \quad (i=1,2,\dots,n)</math>;.
    3) Formulate light intensity <math>I</math> so that it is associated with <math>f(\mathbf{x})</math>
       (for example, for maximization problems, <math>I \propto f(\mathbf{x})</math> or simply <math>I=f(\mathbf{x})</math>;
    4) Define absorption coefficient <math>\gamma </math>
  
    '''While''' (t < MaxGeneration)
       '''for''' i = 1 : n (all n fireflies)
          '''for''' j = 1 : n (n fireflies)
             '''if''' (<math>I_j>I_i </math>), 
                move firefly i towards j;
             '''end if''' 
             Vary attractiveness with distance r via <math> \exp(-\gamma \; r) </math>;
             Evaluate new solutions and update light intensity;
          '''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 <math>\mathbf{x}_i </math> and <math>\mathbf{x}_j </math> is
:: <math>\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 </math>
where <math>\alpha_t </math> is a parameter controlling the step size, while <math>\boldsymbol{\epsilon}_t </math> is a vector drawn from a Gaussian or other
distribution.

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

== Implementation Guides ==

The <math>\gamma</math> should be related to the scales of design variables. Ideally, the <math>\beta</math> term should be order one, which
requires that <math>\gamma </math> should be linked with scales. For example, one possible choice is to use
<math>\gamma=1/\sqrt{L} </math> where <math>L </math> is the average scale of the problem. In case of scales vary significantly, <math>\gamma </math> can be considered as a vector to suit different scales in different dimensions. Similarly, <math>\alpha_t</math> should also be linked with scales. For example, <math>\alpha_t \leftarrow 0.01 L \alpha_t </math>. 
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 <math>\alpha=\alpha_0 \delta^t</math> where <math> 0< \delta <1 (e.g. \delta=0.97) </math>.<ref>http://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm/content/fa_mincon.m</ref> In some difficult problem, it may be helpful if you increase <math>\alpha_t </math> at some stages, then reduce it when necessary. This non-monotonic variation of <math>\alpha_t </math> 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.<ref>A simple demo Matlab code [http://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm is available]</ref> A python implementation is also available, though with limited functionalities.<ref>http://code.google.com/p/csc6810project/</ref>

Recent studies shows that the firefly algorithm is very efficient,<ref>{{cite book |first=X. S. |last=Yang |chapter=Firefly algorithms for multimodal optimization |title=Stochastic Algorithms: Foundations and Applications, SAGA 2009 |series=Lecture Notes in Computer Sciences |volume=5792 |pages=169–178 |year=2009 |arxiv=1003.1466 }}</ref> and could outperform other metaheuristic algorithms including [[particle swarm optimization]].<ref>{{cite book |first=S. |last=Lukasik |first2=S. |last2=Zak |title=Firefly algorithm for continuous constrained optimization task |work=ICCCI 2009, Lecture Notes in Artificial Intelligence (Eds. N. T. Ngugen, R. Kowalczyk, S. M. Chen) |volume=5796 |pages=97–100 |year=2009 }}</ref>
Most metaheuristic algorithms may have difficulty in dealing with stochastic test functions, and it seems that firefly algorithm can deal with stochastic test functions<ref>{{cite journal |last=Yang |first=X.-S. |title=Firefly algorithm, stochastic test functions and design optimisation |journal=Int. J. Bio-inspired Computation |volume=2 |issue=2 |pages=78–84 |year=2010 |arxiv=1003.1409 }}</ref> very efficiently. In addition, FA is also better for dealing with noisy optimization problems with ease of implementation.<ref>{{cite journal |first=N. |last=Chai-ead |first2=P. |last2=Aungkulanon |first3=P. |last3=Luangpaiboon |title=Bees and firefly algorithms for noisy  non-linear optimisation problems |work=Prof. Int. Multiconference of Engineers and Computer Scientists 2011 |year=2011 |volume=2 |pages=1449–1454 }}</ref><ref>{{cite journal |first=P. |last=Aungkulanon |first2=N. |last2=Chai-ead |first3=P. |last3=Luangpaiboon |title=Simulated manufacturing process improvement via particle swarm optimisation and firefly algorithms |work=Prof. Int. Multiconference of Engineers and Computer Scientists 2011 |volume=2 |pages=1123–1128 |year=2011 }}</ref>

Chatterjee et al.<ref>A. Chatterjee, G. K. Mahanti, and A. Chatterjee, Design of a fully digital controlled reconfigurable switched beam conconcentric ring array antenna using firefly and particle swarm optimization algorithm, Progress in Elelectromagnetic Research B, Vol. 36, 113-131(2012)</ref> 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.<ref>X. S. Yang, S. S. Hosseini, A. H. Gandomi, Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect, Applied Soft Computing, Vol. 12(3), 1180-1186(2012)</ref><ref>A. Abdullah, S. Deris, M. S. Mohamad and S. Z. M. Hashim, A new hybrid firefly algorithm for complex and nonlinear problem, in: Distributed Computing and Artificial Intelligence, Advances in Intelligent and Soft Computing, 2012, Volume 151/2012, 673-680, {{doi|10.1007/978-3-642-28765-7_81}}</ref>
Further improvement on the performance is also possible with promising results.<ref>S. M. Farahani, A. A. Abshouri, B. Nasiri, M. R. Meybodi, Some hybrid models to improve firefly algorithm performance, Int. J. Artificial Intelligence, Vol. 8 S(12), 97-117 (2012)</ref><ref>B. Nasiri, M. R. Meybodi, Speciation-based firefly algorithm for optimization in dynamic environments, Int. J. Artificial Intelligence, Vol. 8 (S12), 118-132 (2012)</ref>

== Variants of Firefly Algorithm ==

A recent, comprehensive review showed that the firefly algorithm and its variants have been used in almost area of science<ref>I. Fister, I. Fister Jr., X. S. Yang, J. Brest,  A comprehensive review of firefly algorithms, Swarm and Evolutionary Computation, vol. 13, no. 1, pp. 34-46 (2013).</ref> There are more than twenty variants:
=== 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.<ref>{{cite journal |first=M. K. |last=Sayadi |first2=R. |last2=Ramezanian |first3=N. |last3=Ghaffari-Nasab |title=A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems |journal=Int. J. of Industrial Engineering Computations |volume=1 |issue= |pages=1–10 |year=2010 |url=http://growingscience.com/ijiec/VOL1/IJIEC_2010_7.pdf }}</ref> 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.<ref>T. Hassanzadeh, H. Vojodi and A. M. E. Moghadam, An image segmentation approach based on maximum variance intra-cluster method and firefly algorithm, in: Proc. of 7th Int. Conf. on Natural Computation (ICNC), pp. 1817-1821 (2011).</ref> Meanwhile, a good implementation of a discrete firefly algorithm for  QAP problems has been carried out by Durkota.<ref>K. Durkota, 
Implementation of a discrete firefly algorithm for the QAP problem within the sage framework, BSc thesis, Czech Technical University, (2011).
http://cyber.felk.cvut.cz/research/theses/papers/189.pdf</ref>

=== Multiobjective FA ===
An important study of FA was carried out by Apostolopoulos and Vlachos,<ref>{{cite journal |first=T. |last=Apostolopoulos |first2=A. |last2=Vlachos |title=Application of the Firefly Algorithm for Solving the Economic Emissions Load Dispatch Problem |journal=International Journal of Combinatorics |volume=2011 |year=2011 |page=Article ID 523806 |url=http://www.hindawi.com/journals/ijct/2011/523806.html }}</ref> 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.<ref>Rampriya B., Mahadevan K. and Kannan S., Unit commitment in deregulated power system using Lagrangian firefly algorithm, Proc. of IEEE Int. Conf. on Communication Control and Computing Technologies (ICCCCT), pp. 389-393 (2010).</ref>

=== Chaotic FA ===
A chaotic firefly algorithm (CFA) was developed and found to outperform the previously   best-known solutions available.<ref>L. dos Santos Coelho, D. L. de Andrade Bernert, V. C. Mariani, a chaotic firefly algorithm applied to reliability-redundancy optimization, in: 2011 IEEE Congress on Evolutionary Computation (CEC'11), pp. 517-521 (2011).</ref>

=== Hybrid Algorithms ===

A [[hybrid algorithm|hybrid]] intelligent scheme has been developed by combining the firefly algorithm with the ant colony optimization.<ref>G. Giannakouris, V. Vassiliadis and G. Dounias, Experimental study on a hybrid nature-inspired algorithm for financial portfolio optimization, SETN 2010, LNAI 6040, pp. 101-111 (2010).</ref>

=== 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.<ref>Zhongyi Hu, Yukun Bao, and Tao Xiong, Electricity Load Forecasting using Support Vector Regression with Memetic Algorithms, The Scientific World Journal, 2014, http://www.hindawi.com/journals/tswj/aip/292575/</ref>

=== 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.<ref>E. F. P. Luz, H. F. Campos Velho, J. C. Becceneri, Firefly Algorithm with Predation: A parallel implementation applied to inverse heat conduction problem, in: Proc. of 10th World Congress on Computational Mechanics (WCCM 2012), (2012).</ref>

== 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 [[Particle swarm optimization|PSO]]-LBG and HBMO-LBG (particle swarm optimization and honey-bee mating optimization; variations on the [[Linde–Buzo–Gray algorithm]]).<ref>Horng M.-H. and Jiang T. W., The codebook design of image vector quantization based on the firefly algorithm, in: Computational Collective Intelligence, Technologies and Applications, LNCS, Vol. 6423, pp. 438-447 (2010).</ref>
<ref>M.-H. Horng, vector quantization using the firefly algorithm for image compression, Expert Systems with Applications, Vol. 38,  (article in press) 12 Aug. (2011).</ref> For minimum cross entropy thresholding, firefly-based algorithm uses the least computation time<ref>M.-H. Horng and R.-J Liou, Multilevel minimum cross entropy threshold selection based on the firefly algorithm, Expert Systems with Applications, Vol. 38, Issue 12, 14805-14811 (2011).</ref> Also, for gel electrophoresis images, FA-based method is very efficient.<ref>M. H. M. Noor, A. R. Ahmad, Z. Hussain, K. A. Ahmad, A. R. Ainihayati, Multilevel thresholding of gel electrophoresis images using firefly algorithm, in: Proceedings of Control System, Computing and Engineering (ICCSCE2011), pp. 18-21 (2011).</ref>

=== Eigenvalue optimization ===
Eigenvalue optimization of isospectral systems has solved by FA and multiple optimum points have been found efficiently.<ref>R. Dutta, R. Ganguli and V. Mani, Exploring isospectral spring-mass systems with firefly algorithm, Proc. Roy. Soc. A., 
Vol. 467, (2011)http://rspa.royalsocietypublishing.org/content/early/2011/06/16/rspa.2011.0119.abstract</ref>

=== Feature selection and fault detection ===
Feature selection can be also carried out successfully using firefly algorithm.<ref>H. Banati and M. Bajaj, Firefly based feature selection approach, Int. J. Computer Science Issues, vol. 8, No. 2, 473-480 (2011).</ref> Real-time fault identification in large systems becomes viable, based on the recent work on fault identification with binary adaptive firefly optimization.<ref>R. Falcon, M. Almeida and A. Nayak, Fault identification with binary adaptive fireflies in parallel and distributed systems, IEEE Congress on Evolutionary Computation, (2011).</ref>

===Antenna Design===
Firefly algorithms outperforms ABC for optimal design of linear array of isotropic sources <ref>B. Basu and G. K. Mahanti, Firefly and artificial bees colony algorithm for synthesis of scanned and broadside linear array antenna, Progress in Electromagnetic Research B., Vol. 32, 169-190 (2011).</ref> and digital controllable array antenna.<ref>A. Chatterjee, G. K. Mahanti, and A. Chatterjee, Design of a fully digital controlled reconfigurable switched beam conconcentric ring array antenna using firefly and particle swarm optimization algorithm, Progress in Elelectromagnetic Research B, Vol. 36, 113-131(2012)</ref>

===Structural Design===
For mixed-variable problems, many optimization algorithms may struggle. However, firefly algorithm can efficiently solve optimization problems with mixed variables.<ref>A. H. Gandomi, X. S. Yang, A. H. Alavi, Mixed variable structural optimization using firefly algorithm, Computers and Structures, Vol. 89, No. 23-24, pp. 2325-2336 (2011). {{doi|10.1016/j.compstruc.2011.08.002}}</ref>

=== Scheduling and TSP ===
Firefly-based algorithms for scheduling task graphs and job shop scheduling requires less computing than all other metaheuristics.<ref>U. Hönig, A firefly algorithm-based approach for scheduling task graphs in homogenous systems, Proceeding Informatics, {{doi|10.2316/P.2010.724-033}}, 724 (2010).</ref><ref>A. Khadwilard, S. Chansombat, T. Thepphakorn, P. Thapatsuwan, W. Chainat, P. Pongcharoen,
 Application of firefly algorithm and its parameter setting for job shop scheduling, First Symposius on
 Hands-On Research and Development, (2011).</ref>
A binary firefly algorithm has been developed to tackle the knapsack 
cryptosystem efficiently<ref>S. Palit, S. Sinha, M. Molla, A. Khanra, M. Kule, 
A cryptanalytic attack on the knapsack cryptosystem using binary Firefly algorithm,
in: 2nd Int. Conference on Computer and Communication Technology (ICCCT), 15-17 Sept 2011,India, pp. 428-432 (2011).</ref> Recently, an evolutionary discrete FA has been developed for solving   [[travelling salesman problem]]s<ref>G. K. Jati and S. Suyanto, Evolutionary discrete firefly algorithm for travelling salesman problem, ICAIS2011, Lecture Notes in Artificial Intelligence (LNAI 6943), pp.393-403 (2011).</ref> 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.<ref>C. B. Pop, V. R. Chifu, I. Salomie,R. B. Baico, M. Dinsoreanu, G. Copil, A hybrid firefly-inspired approach for optimal semantic web service composition, in: Proc. of 2nd Workshop on Software Services: Cloud Computing and Applications, June, 2011.</ref>

=== Chemical Phase equilibrium ===

For phase equilibrium calculations and stability analysis, FA was found to be the most reliable compared with other techniques.<ref>S. E. Fateen, A. Bonilla-Petrociolet, G. P. Rangaiah, Evaluation of covariance matrix adaptation evolution strategy, shuffled complex evolution and firefly algorithms for phase stability, phase equilibrium and chemical equilibrium problems, Chemical Engineering Research and Design, May (2012). http://dx.doi.org/10.1016/j.cherd.2012.04.011</ref>

=== Clustering ===

Performance study for clustering also suggested that firefly algorithm is very efficient.<ref>J. Senthilnath,  S. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, June (2011). {{doi|10.1016/j.swevo.2011.06.003}}</ref>

===Dynamic Problems===

Firefly algorithm can solve optimization problems in dynamic environments very efficiently.
<ref>S. M. Farahani, B. Nasiri and M. R. Meybodi, A multiswarm based firefly algorithm in dynamic environments, Third Int. Conference on Signal Processing Systems (ICSPS2011), Aug 27-28, Yantai, China, pp. 68-72 (2011)</ref><ref>A. A. Abshouri, M. R. Meybodi and A. Bakhtiary, New firefly algorithm based on multiswarm and learning automata in dynamic environments, Third Int. Conference on Signal Processing Systems (ICSPS2011), Aug 27-28, Yantai, China, pp. 73-77 (2011).</ref>

===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 <ref>Yudong Zhang and Lenan Wu, A Novel Method for Rigid Image Registration based on Firefly Algorithm, International Journal of Research and Reviews in Soft and Intelligent Computing, vol.2, no.2, pp. 141-146 (2012).</ref>

=== Protein Structure Prediction ===
Prediction of protein structures is NP-hard, and a recent study by Maher et al.<ref>
B. Maher, A. Albrecht, M. Loomes, X. S. Yang, K. Steinhofel,  A firefly-inspired method for protein structure prediction in lattice models, Biomolucules, vol. 4, no. 1, pp. 56-75 (2014).</ref> 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.<ref>Yudong Zhang, Lenan Wu, and Shuihua Wang, Solving Two-Dimensional HP model by Firefly Algorithm and Simplified Energy Function, Mathematical Problems in Engineering, 2013, doi: 10.1155/2013/398141</ref>

===  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.<ref>Tao Xiong, Yukun Bao, Zhongyi Hu: Multiple-output support vector regression with a firefly algorithm for interval-valued stock price index forecasting. Knowl.-Based Syst. 55: 87-100 (2014), http://www.sciencedirect.com/science/article/pii/S0950705113003237</ref>

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.<ref>Zhongyi Hu, Yukun Bao, and Tao Xiong, Electricity Load Forecasting using Support Vector Regression with Memetic Algorithms, The Scientific World Journal, 2014, http://www.hindawi.com/journals/tswj/aip/292575/</ref>

==See also==
* [[Metaheuristic]]
* [[Glowworm swarm optimization]] (GSO)

== References ==
{{Reflist}}

== External links ==
* [http://code.google.com/p/csc6810project/ Firefly Algorithm implemented in Python]
* [https://github.com/firefly-cpp/Firefly-algorithm--FFA- Firefly Algorithm in C/C++]
* [http://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm Firefly Algorithm in Matlab or Octave]
{{collective animal behaviour}}
{{Optimization algorithms}}

[[Category:Optimization algorithms and methods]]
[[Category:Image processing]]
[[Category:Swarm Intelligence]]
[[Category:Metaheuristic]]