Firefly algorithm

From Quire, the open reference·Metaheuristic proposed by Xin-She Yang·3 min read

In mathematical optimization, the firefly algorithm is a metaheuristic proposed by Xin-She Yang and inspired by the flashing behavior of fireflies.^[1]

Algorithm#edit

In pseudocode the algorithm can be stated as:

Begin
    1) Objective function: 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>f</mi>
        <mo stretchy="false">(</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">x</mi>
        </mrow>
        <mo stretchy="false">)</mo>
        <mo>,</mo>
        <mspace width="1em"></mspace>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">x</mi>
        </mrow>
        <mo>=</mo>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>1</mn>
          </mrow>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>x</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>2</mn>
          </mrow>
        </msub>
        <mo>,</mo>
        <mo>.</mo>
        <mo>.</mo>
        <mo>.</mo>
        <mo>,</mo>
        <msub>
          <mi>x</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>d</mi>
          </mrow>
        </msub>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})}</annotation>
  </semantics>
;
    2) Generate an initial population of fireflies 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msub>
          <mrow class="MJX-TeXAtom-ORD">
            <mi mathvariant="bold">x</mi>
          </mrow>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>i</mi>
          </mrow>
        </msub>
        <mspace width="1em"></mspace>
        <mo stretchy="false">(</mo>
        <mi>i</mi>
        <mo>=</mo>
        <mn>1</mn>
        <mo>,</mo>
        <mn>2</mn>
        <mo>,</mo>
        <mo>…</mo>
        <mo>,</mo>
        <mi>n</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \mathbf {x} _{i}\quad (i=1,2,\dots ,n)}</annotation>
  </semantics>
;.
    3) Formulate light intensity I so that it is associated with 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>f</mi>
        <mo stretchy="false">(</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">x</mi>
        </mrow>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )}</annotation>
  </semantics>

       (for example, for maximization problems, 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>I</mi>
        <mo>∝</mo>
        <mi>f</mi>
        <mo stretchy="false">(</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">x</mi>
        </mrow>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle I\propto f(\mathbf {x} )}</annotation>
  </semantics>
 or simply 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>I</mi>
        <mo>=</mo>
        <mi>f</mi>
        <mo stretchy="false">(</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">x</mi>
        </mrow>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle I=f(\mathbf {x} )}</annotation>
  </semantics>
;)
    4) Define absorption coefficient γ

    while (t < MaxGeneration)
        for i = 1 : n (all n fireflies)
            for j = 1 : i (n fireflies)
                if (
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msub>
          <mi>I</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>j</mi>
          </mrow>
        </msub>
        <mo>></mo>
        <msub>
          <mi>I</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>i</mi>
          </mrow>
        </msub>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle I_{j}>I_{i}}</annotation>
  </semantics>
),
                    Vary attractiveness with distance r via 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>exp</mi>
        <mo>⁡</mo>
        <mo stretchy="false">(</mo>
        <mo>−</mo>
        <mi>γ</mi>
        <mspace width="thickmathspace"></mspace>
        <mi>r</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \exp(-\gamma \;r)}</annotation>
  </semantics>
;
                    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 ${\displaystyle \mathbf {x} _{i$ and ${\displaystyle \mathbf {x} _{j$ is ${\displaystyle \mathbf {x} _{i}^{t+1}=\mathbf {x} _{i}^{t}+\beta \exp[-\gamma r_{ij}^{2}](\mathbf {x} _{j}^{t}-\mathbf {x} _{i}^{t})+\alpha _&#$ where ${\displaystyle \alpha _{t$ is a parameter controlling the step size, while ${\displaystyle {\boldsymbol {\epsilon _{t$ is a vector drawn from a Gaussian or other distribution.

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

Criticism#edit

Nature-inspired metaheuristics in general have attracted 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.^[2]^[3]^[4]

References#edit

Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press. ISBN 978-1-905986-10-1.
Almasi, Omid N.; Rouhani, Modjtaba (2016). "A new fuzzy membership assignment and model selection approach based on dynamic class centers for fuzzy SVM family using the firefly algorithm". Turkish Journal of Electrical Engineering & Computer Sciences. 4: 1–19. doi:10.3906/elk-1310-253. Practical application of FA on UCI datasets.
Lones, Michael A. (2014). "Metaheuristics in nature-inspired algorithms" (PDF). Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation. pp. 1419–1422. doi:10.1145/2598394.2609841. ISBN 978-1-4503-2881-4. S2CID 14997975. 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.
Weyland, Dennis (2015). "A critical analysis of the harmony search algorithm—How not to solve sudoku". Operations Research Perspectives. 2: 97–105. doi:10.1016/j.orp.2015.04.001. hdl:10419/178253. 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.
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

External links#edit

[1] Files of the Matlab programs included in the book: Xin-She Yang, Nature-Inspired Metaheuristic Algorithms, Second Edition, Luniver Press, (2010).

References#

^ Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press. ISBN 978-1-905986-10-1.
^ Almasi, Omid N.; Rouhani, Modjtaba (2016). "A new fuzzy membership assignment and model selection approach based on dynamic class centers for fuzzy SVM family using the firefly algorithm". Turkish Journal of Electrical Engineering & Computer Sciences. 4: 1–19. doi:10.3906/elk-1310-253. Practical application of FA on UCI datasets.
^ Lones, Michael A. (2014). "Metaheuristics in nature-inspired algorithms" (PDF). Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation. pp. 1419–1422. doi:10.1145/2598394.2609841. ISBN 978-1-4503-2881-4. S2CID 14997975. 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.
^ Weyland, Dennis (2015). "A critical analysis of the harmony search algorithm—How not to solve sudoku". Operations Research Perspectives. 2: 97–105. doi:10.1016/j.orp.2015.04.001. hdl:10419/178253. 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.

Categories Nature-inspired metaheuristics

This article is mirrored from “Firefly algorithm” on English Wikipedia, revision 1368856634, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1368856634 · just now