Firefly algorithm: Difference between revisions

Revision as of 18:55, 31 August 2016

Latest revision as of 01:16, 9 February 2025

(36 intermediate revisions by 18 users not shown)

Line 1:

In [[Optimization (mathematics)|mathematical optimization]], the '''firefly algorithm''' is a [[metaheuristic]] proposed by [[Xin-She Yang]] and inspired by the flashing behaviourbehavior 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-61 }}</ref>

== Metaphor ==

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:

#All fireflies are unisexual, so that any individual 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 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.

== Algorithm ==

Line 14 ⟶ 5:

'''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|&gamma;}}

'''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;

'''Whilewhile''' (t < MaxGeneration)

'''for''' i = 1 : n (all n fireflies)

'''for''' j = 1 : ni (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''' ij

'''end for''' ji

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.

== Criticism ==

Nature-inspired metaheuristics[[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 an elaborate metaphormetaphors. The firefly algorithm has been criticized as differing from the well-established [[particle swarm optimization]] only in a negligible way.<ref>{{cite journal|firstfirst1=MichaelOmid AN.|lastlast1=LonesAlmasi| first2=Modjtaba|last2= Rouhani|year=20142016|title=MetaheuristicsA innew Nature-Inspiredfuzzy Algorithmsmembership 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 Conference|GECCOchapter=Metaheuristics in nature-inspired algorithms '14]]|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|url=http://www.sciencedirect.com/science/article/pii/S221471601500010X|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>

==See also==

Line 52 ⟶ 42:

== 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|2}}

==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).

{{Optimization algorithms}}