|
In [[mathematical optimization]], the '''firefly algorithm''' is a [[metaheuristic]] proposed by [[Xin-She Yang]] and inspired by the flashing behavior of [[firefly|fireflies]].<ref>{{cite book |first=X. S. |last=Yang |title=Nature-Inspired Metaheuristic Algorithms |publisher=[[Luniver Press]] |year=2008 |isbn=978-1-905986-10-1 }}</ref>
<!-- Please do not remove or change this AfD message until the issue is settled -->
{{Article for deletion/dated|page=Firefly algorithm|timestamp=20160715142505|year=2016|month=July|day=15|substed=yes|help=off}}
<!-- Once discussion is closed, please place on talk page: {{Old AfD multi|page=Firefly algorithm|date=15 July 2016|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
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>
== Algorithm ==
#All fireflies are unisexual, so that any individual firefly will be attracted to all other fireflies;
In pseudocode the algorithm can be stated as:
#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;
#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: {{nowrap|<math>f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,...,x_d) </math>;}}
2) Generate an initial population of fireflies {{nowrap|<math> \mathbf{x}_i \quad (i=1,2,\dots,n)</math>;.}}
3) Formulate light intensity {{mvar|I}} so that it is associated with {{nowrap|<math>f(\mathbf{x})</math>}}
(for example, for maximization problems, {{nowrap|<math>I \propto f(\mathbf{x})</math> or simply <math>I=f(\mathbf{x})</math>;)}}
4) Define absorption coefficient {{mvar|γ}}
'''While''' (t < MaxGeneration)
'''for''' i = 1 : n (all n fireflies)
'''for''' j = 1 : n (n fireflies)
{{nowrap|'''if''' (<math>I_j>I_i </math>),}}
move firefly i towards j;
Vary attractiveness with distance r via {{nowrap|<math> \exp(-\gamma \; r) </math>;}}
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;
'''while''' (t < MaxGeneration)
'''for''' i = 1 : n (all n fireflies)
'''for''' j = 1 : i (n fireflies)
{{nowrap|'''if''' (<math>I_j>I_i </math>),}}
Vary attractiveness with distance r via {{nowrap|<math> \exp(-\gamma \; r) </math>;}}
move firefly i towards j;
Evaluate new solutions and update light intensity;
'''end if'''
'''end for''' j
'''end for''' i
Rank fireflies and find the current best;
'''end while'''
'''end'''
Note that the number of objective function evaluations per loop is one evaluation per firefly, even though the above pseudocode suggests it is ''n''×''n''. (Based on Yang's [[MATLAB]] code.) Thus the total number of objective function evaluations is (number of generations) × (number of fireflies).
The main update formula for any pair of two fireflies <math>\mathbf{x}_i </math> and <math>\mathbf{x}_j </math> is
:: <math display="block">\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 [[Particleparticle Swarmswarm Optimizationoptimization]] (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 GuidesCriticism ==
Nature-inspired [[metaheuristic]]s in general have attracted [[List of metaphor-inspired metaheuristics#Criticism of the metaphor methodology|criticism in the research community]] for hiding their lack of novelty behind metaphors. The firefly algorithm has been criticized as differing from the well-established [[particle swarm optimization]] only in a negligible way.<ref>{{cite journal|first1=Omid N.|last1=Almasi| first2=Modjtaba|last2= Rouhani|year=2016|title=A new fuzzy membership assignment and model selection approach based on dynamic class centers for fuzzy SVM family using the firefly algorithm|journal=Turkish Journal of Electrical Engineering & Computer Sciences|volume=4| pages=1–19|doi=10.3906/elk-1310-253|quote= Practical application of FA on UCI datasets.|doi-access=free}}</ref><ref>{{cite book|first=Michael A.|last=Lones|title=Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation |chapter=Metaheuristics in nature-inspired algorithms |year=2014|pages=1419–1422|chapter-url=http://www.macs.hw.ac.uk/~ml355/common/papers/lones-gecco2014-metaheuristics.pdf|doi=10.1145/2598394.2609841|quote=FA, on the other hand, has little to distinguish it from PSO, with the inverse-square law having a similar effect to crowding and fitness sharing in EAs, and the use of multi-swarms in PSO.|isbn=9781450328814|citeseerx=10.1.1.699.1825|s2cid=14997975 }}</ref><ref>{{cite journal|first=Dennis|last=Weyland|year=2015|title=A critical analysis of the harmony search algorithm—How not to solve sudoku|journal=Operations Research Perspectives|volume=2|pages=97–105|doi=10.1016/j.orp.2015.04.001|quote=For example, the differences between the particle swarm optimization metaheuristic and "novel" metaheuristics like the firefly algorithm, the fruit fly optimization algorithm, the fish swarm optimization algorithm or the cat swarm optimization algorithm seem negligible.|doi-access=free|hdl=10419/178253|hdl-access=free}}</ref>
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>, though this value may depend on the number of iterations.<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>https://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 |doi=10.1504/ijbic.2010.032124}}</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>{{cite journal | last1 = Chatterjee | first1 = A. | last2 = Mahanti | first2 = G. K. | last3 = Chatterjee | first3 = A. | year = 2012 | title = Design of a fully digital controlled reconfigurable switched beam conconcentric ring array antenna using firefly and particle swarm optimization algorithm | url = | journal = Progress in Elelectromagnetic Research B | volume = 36 | issue = | pages = 113–131 | doi=10.2528/pierb11083005}}</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>{{cite journal | last1 = Yang | first1 = X. S. | last2 = Hosseini | first2 = S. S. | last3 = Gandomi | first3 = A. H. | year = | title = Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect | url = | journal = Applied Soft Computing | volume = 12 | issue = 3| pages = 1180–1186 | doi=10.1016/j.asoc.2011.09.017}}</ref><ref>{{cite journal | last1 = Abdullah | first1 = A. | last2 = Deris | first2 = S. | last3 = Mohamad | first3 = M. S. | last4 = Hashim | first4 = S. Z. M. | year = 2012 | title = A new hybrid firefly algorithm for complex and nonlinear problem, in: Distributed Computing and Artificial Intelligence | url = | journal = Advances in Intelligent and Soft Computing | volume = 151 | issue = | pages = 673–680 | doi = 10.1007/978-3-642-28765-7_81 }}</ref>
Further improvement on the performance is also possible with promising results.<ref>{{cite journal | last1 = Farahani | first1 = S. M. | last2 = Abshouri | first2 = A. A. | last3 = Nasiri | first3 = B. | last4 = Meybodi | first4 = M. R. | year = 2012 | title = Some hybrid models to improve firefly algorithm performance | url = | journal = Int. J. Artificial Intelligence | volume = 8 | issue = S12| pages = 97–117 }}</ref><ref>{{cite journal | last1 = Nasiri | first1 = B. | last2 = Meybodi | first2 = M. R. | year = 2012 | title = Speciation-based firefly algorithm for optimization in dynamic environments | url = | journal = Int. J. Artificial Intelligence | volume = 8 | issue = S12| pages = 118–132 }}</ref>
== Theoretical Analysis ==
Although much progress has been achieved FA-based algorithms since 2008, significant efforts are required to further improve the performance of FA:<ref>{{cite journal |first=Ngaam J. |last=Cheung |first2=X.-M.|last2=Ding |first3=H.-B. |last3=Shen |title=A Non-Homogeneous Firefly Algorithm and Its Convergence Analysis |journal=Journal of Optimization Theory and Applications |volume= |issue= |pages= |year=2016 |url=http://godzilla.uchicago.edu/pages/ngaam/NAdaFa/index.html |doi=10.1007/s10957-016-0875-4}}</ref>
* 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.<ref>{{cite journal |first=Ngaam J. |last=Cheung |first2=X.-M.|last2=Ding |first3=H.-B. |last3=Shen |title=Adaptive Firefly Algorithm: Parameter Analysis and its Application |journal=PLOS ONE |volume=9 |issue=11 |pages= e112634 |year=2014 |url=http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0112634 |doi=10.1371/journal.pone.0112634}}</ref>
Further, classical variants of the algorithm have unexpected parameter settings and limited update laws, notably the homogeneous rule needs to be improved in order to do more search on different fitness landscape. Ref. analyzes the trajectory of a single firefly in the traditional algorithm and an adaptive variant, respectively. These analyses lead to a general model of the algorithms including a set of the boundary conditions for the parameters guaranteeing the convergence tendencies of the two algorithms.<ref>{{cite journal |first=Ngaam J. |last=Cheung |first2=X.-M.|last2=Ding |first3=H.-B. |last3=Shen |title=A Non-Homogeneous Firefly Algorithm and Its Convergence Analysis |journal=Journal of Optimization Theory and Applications |volume= |issue= |pages= |year=2016 |url=http://godzilla.uchicago.edu/pages/ngaam/NAdaFa/index.html |doi=10.1007/s10957-016-0875-4}}</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<ref>{{cite journal | last1 = Fister | first1 = I. | last2 = Fister | first2 = Jr. | last3 = Yang | first3 = X. S. | last4 = Brest | first4 = J. | year = 2013 | title = A comprehensive review of firefly algorithms | url = | journal = Swarm and Evolutionary Computation | volume = 13 | issue = 1| pages = 34–46 | doi=10.1016/j.swevo.2013.06.001}}</ref> There are more than twenty variants:
=== Adaptive Firefly Algorithm (AdaFa) ===
An adaptive variant of firefly algorithm, termed AdaFa,<ref>http://godzilla.uchicago.edu/pages/ngaam/AdaFa/index.html</ref> was proposed in ref.<ref>{{cite journal |first=Ngaam J. |last=Cheung |first2=X.-M.|last2=Ding |first3=H.-B. |last3=Shen |title=Adaptive Firefly Algorithm: Parameter Analysis and its Application |journal=PLOS ONE |volume=9 |issue=11 |pages= e112634 |year=2014 |url=http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0112634 |doi=10.1371/journal.pone.0112634}}</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.<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 |doi=10.5267/j.ijiec.2010.01.001}}</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>{{cite journal | last1 = Giannakouris | first1 = G. | last2 = Vassiliadis | first2 = V. | last3 = Dounias | first3 = G. | year = 2010 | title = Experimental study on a hybrid nature-inspired algorithm for financial portfolio optimization | url = | journal = SETN | volume = 6040 | issue = | pages = 101–111 | doi=10.1007/978-3-642-12842-4_14}}</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>
=== 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 .,<ref>{{cite journal | last1 = Tilahun | first1 = S. L. | last2 = Ong | first2 = H. C. | year = | title = Modified Firefly Algorithm | url = | journal = Journal of Applied Mathematics | volume = 2012 | issue = | page = 467631 }}</ref> in which the updating process of the brightest firefly is modified to keep the best result throughout the iterations. Another example is a modified firefly algorithm to solve univariate nonlinear equations having real as well as complex roots.<ref>{{Cite journal|last = Ariyaratne|first = M. K. A.|last2 = Fernando|first2 = T. G. I.|last3 = Weerakoon|first3 = S.|date = 2015-08-01|title = A modified firefly algorithm to solve univariate nonlinear equations with complex roots|url = http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7377683|journal = 2015 Fifteenth International Conference on Advances in ICT for Emerging Regions (ICTer)|pages = 160–167|doi = 10.1109/ICTER.2015.7377683}}</ref>
==See also==
* [[Evolutionary multi-modal optimization]]
* [[Glowworm swarm optimization]] (GSO)
* [[Metaheuristic]]
* [[Swarm intelligence]]
== References ==
{{Reflist|<ref>Ariyaratne MKA, Pemarathne WPJ (2015) A review of recent advancements of firefly algorithm: a modern nature inspired algorithm. In: Proceedings of the 8th international research conference, 61–66, KDU, Published November 2015, http://ir.kdu.ac.lk/bitstream/handle/345/1038/com-047.pdf?sequence=1&isAllowed=y</ref>}}
{{Reflist}}
==External links==
* [https://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm] Files of the Matlab programs included in the book: Xin-She Yang, Nature-Inspired Metaheuristic Algorithms, Second Edition, Luniver Press, (2010).
== External links ==
* [https://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}}
{{collective animal behaviour}}
[[Category:Nature-inspired metaheuristics]]
| 