|
TheIn [[mathematical optimization]], the '''firefly algorithm (FA)''' is a [[metaheuristic]] proposed by [[algorithmXin-She Yang]], and inspired by the flashing behaviourbehavior of fireflies. The primary purpose for a firefly's flash is to act as a signal system to attract other fireflies. [[Xin-she Yangfirefly|Xin-She Yangfireflies]] 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=1905986106978-1-905986-10-1 }}</ref>
== Algorithm description == ▼#All fireflies are unisex, so that one 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 brighter one will attract (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.
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 <math>{{mvar|I </math>}} 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 <math>\{{mvar|&gamma </math>;}}▼
While '''while''' (t < MaxGeneration) ▼ '''for ''' i = 1 : n (all n fireflies) ▼
'''for ''' j = 1 : n i (n fireflies) ▼
{{nowrap|'''if ''' (<math>I_j>I_i </math>), }}▼
Vary attractiveness with distance r via {{nowrap|<math> \exp(-\gamma \; r ^2) </math>; }}▼
move firefly i towards j; ▼
Evaluate new solutions and update light intensity; ▼
Rank fireflies and find the current best; ▼
'''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).
Firefly algorithm is a nature-inspired [[metaheuristic]] [[Optimization (mathematics)|optimization]] [[algorithm]].
The main update formula for any pair of two fireflies <math>\mathbf{x}_i </math> and <math>\mathbf{x}_j </math> is
▲== Algorithm description ==
<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>
The pseudo code can be summarized as:
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[[particle 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 . In addition, the <math>\gamma</math> should be related to the scales of design variables. ▼▲ 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;
▲ Vary attractiveness with distance r via <math> \exp(-\gamma \; r^2) </math>;
▲ Evaluate new solutions and update light intensity;
▲ Rank fireflies and find the current best;
Post-processing the results and visualization;
end
== Criticism ==
▲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. In addition, the <math>\gamma</math> should be related to the scales of design variables.
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>
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>
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 |id={{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 |id={{arXiv|1003.1409}} }}</ref> very efficiently. In addition, FA is also better for dealing with noisy optimization problems with ease of implementation.<ref>{{cite paper |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 paper |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>
== 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.
== 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>
== Digital Image Compression ==
Very recently, an FF-LGB 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.<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>
==See also==
* [[MetaheuristicSwarm intelligence]]
* [[Glowworm swarm optimization]] (GSO)
== 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).
* [http://code.google.com/p/csc6810project/ Firefly Algorithm implemented in Python]
{{Optimization algorithms}} ▼{{collective animal behaviour}}
▲{{Optimization algorithms}}
[[Category:OptimizationNature-inspired algorithmsmetaheuristics]]
[[Category:Mathematical programming]]
[[Category:Image processing]]
| 