Algoritme firefly

El algoritme firefly (FA per les seues sigles en anglés, "firefly algorithm"; algoritme luciérnaga en espanyol) és un algoritme metaheurístico, inspirat en el comportament del centelleo de les luciérnagas. El propòsit primari d'una luciérnaga és generar centelleigs/centellejos de llum per a actuar com a sistema de senyal per a atraure a atres luciérnagas. Xin-She Yang va formular este algoritme en les següents premisses:

1. Totes les luciérnagas són "unisexuales", de modo que qualsevol luciérnaga individual serà atreta per totes les demés;
2. L'atracció és proporcional a la seua lluentor, i per a qualsevol parell de luciérnagas, la menys lluenta serà atreta per (i per lo tant es desplaçarà cap a) la més lluenta; aixina i tot, l'intensitat (la lluentor aparent) decreix quan aumenta la distància entre abdós;
3. Si no hi ha luciérnagas més lluents que una donada, esta es mou aleatoriamente.

La lluentor és associada en els valors d'una funció objectiu.

L'algoritme firefly és un procediment metaheurístico d'optimisació inspirat en la naturalea.

Descripció de l'algoritme

El pseudocódigo pot ser resumit com:

Inici
   1) Funció Objectiu: $f(𝐱),𝐱=(x_1,x_2,\mathrm{...},x_d)$;
   2) Generar una població inicial de luciérnagas ${𝐱}_i(i=1,2,\dots ,n)$;.
   3) Formular l'intensitat de la llum I de modo que estiga associada en $f(𝐱)$
      (eixemple, per a problemes d'maximización, $I\propto f(𝐱)$ or simply $I=f(𝐱)$;)
   4) Definir el coeficient d'absorció γ

   While (t < MaxGeneration)
      for i = 1 : n (all n luciérnagas)
         for j = 1 : n (n luciérnagas)
            if ($I_j>I_i$),
               moure luciérnaga i cap a j;
               Variar atracció en la distancia r via $\exp (-\gamma r)$;
               Evaluar les noves solucions i actualisar l'intensitat de la llum;
            end if 
         end for j
      end for i
      Ordenar les luciérnagas i buscar la més lluminosa;
   end while

   Post-processe dels resultats i visualisació;

final

La fòrmula d'actualisació principal per a qualsevol parell de dos luciérnagas ${𝐱}_i$ i ${𝐱}_j$ és

${𝐱}_i^{t+1}={𝐱}_i^t+\beta \exp [-\gamma r_{ij}^2]({𝐱}_j^t-{𝐱}_i^t)+{\alpha }_t{𝝐}_t$

a on ${\alpha }_t$ és un paràmetro que controla la mida del pas, mentres que ${𝝐}_t$ és un vector extret d'una distribució Gaussiana o una atra distribució.

Pot demostrar-se que el cas limitativo $\gamma \to 0$ correspon a l'optimisació per eixam de partícules estàndar (PSO). De fet, si el bucle interior (for j) és eliminat i la lluentor $I_j$ és reemplaçat pel millor actual global $g^{*}$, llavors FA essencialment es convertix en l'estàndart PSO.

Guies d'implementació

$\gamma$ té que ser relacionat en l'escala de variables de disseny. Idealment, el terme $\beta$ tindria que ser d'orde un, lo que requerix que $\gamma$ tindria que ser enllaçat en les escales. Per eixemple, una possible elecció és utilisar

$\gamma =1/\sqrt{L}$ , a on $L$ és l'escala mija del problema. En el cas de que les escales varien significativament, $\gamma$ pot ser considerat com un vector per a adoptar escales diferents en dimensions diferents. De modo paregut, ${\alpha }_t$ també tindria que ser enllaçada en les escales. Per eixemple, ${\alpha }_t\leftarrow 0.01L{\alpha }_t$. Es pot senyalar que la descripció anterior no inclou la reducció aleatòria. De fet, en la seua implementació real per diversos investigadors, el moviment de les luciérnagas és gradualment reduït per una espècie de suavizamiento aleatori com $\alpha ={\alpha }_0{\delta }^t$ a on$0<\delta <1(e.g.,\delta =0.97)$, encara que este valor pot dependre del número de iteraciones. En algun problema difícil, puga ser útil aumentar ${\alpha }_t$ en algunes etapes, i reduir-ho quan siga necessari. Esta variació no-monòtona de ${\alpha }_t$ capacita a l'algoritme per a eixir de qualsevol òptim local com en el cas improvable de que poguera bloquejar-se si el terme aleatori és reduït massa corrents.

Estudis paramètrics mostren que n (el número de luciérnagas) tindria que ser aproximadament entre 15 i 40 per a la majoria de problemes. Hi ha una versió disponible de l'algoritme programada en python, encara que en funcionalitats llimitades.

Estudis recents mostren que l'algoritme firefly és molt eficaç, i pot superar a atres algorítmics metaheurísticos que inclouen optimisació per eixam de partícules. Atres algoritmes metaheurísticos poden tindre dificultat en tractar funcions de prova estocàstica, i sembla que l'algoritme firefly pot tractar la prova estocàstica de forma molt eficientemente. Ademés, també és millor en el tractament de problemes d'optimisació de soroll, en una notable facilitat d'implementació.

Chatterjee i atres han demostrat que l'algoritme firefly pot ser superior a l'optimisació per eixam de partícules en les seues aplicacions. Ademés, pot solucionar eficientemente problemes no convexos en condicions de contorn complexes no llineals. S'han fet millores posteriors en el rendiment en resultats prometedors.

Vore també

• Evolutiu multi-optimisació modal
• Glowworm Optimisació d'eixam (GSO)
• Metaheuristic
• Inteligència d'eixam