Алгоритъм на светулката

Алгоритъмът на светулката (на английски: firefly algorithm) е метаевристичен алгоритъм, предложен за първи път от британския математик Син-Шъ Ян през 2008 година. Алгоритъмът се прилага за оптимизация на бенчмарк функции и използва популационно търсене, т.е. кандидат-решенията използват като градивни блокове части от различни решения.

Биологична метафора

Алгоритъмът е вдъхновен от поведението на светулките, което използва биолуминесценция като форма на комуникация с други светулки, за търсене на храна и за отблъскване на хищници. Поведението им съдържа характеристики на интелигентност в рояк (swarm intelligence) чрез самоорганизация и децентрализирано вземане на решения. Биолуминесценцията служи и да сигнализрат при търсенето на партньор, като яркостта е индикатор за приспособимостта на мъжките екземпляри.

Описание на алгоритъма

За нуждите на алгоритъма, се приема, че светулките са безполови, а поведението им се заключава в три основни правила:

1. Светулката бива привличана от други светулки (без значение от техния пол),
2. Привлекателността на една светулка е пропорционална на яркостта ѝ и намалява при увеличаването на разстоянието между светулките, и
3. Видът на целевата функция определя яркостта на светулката.

Допускането при алгоритъма е, че популация от $n$ кандидат-решения на една оптимизационна задача са агенти от вида на светулката. Тези агенти представляват вектори от размерност $d$, представляваща променливите на задачата. Качеството (оптималността) на всяко решение ${\overrightarrow {x}}_{i}=[x_{i1},x_{i2},\dots ,x_{id}]$ се оценява посредством фитнес функция $f({\overrightarrow {x}}_{i}),i=1,\dots ,n$. Всеки агент „свети“ пропорционално на качеството си, което заедно с привлекателността му ($\beta$), определя колко силно привлича други агенти от рояка.

Два други потребителски дефинирани параметъра са стойността на максималната привлекателност ($\beta _{0}$) и коефициента на абсорбция ($\gamma$), който определя вариацията на привлекателността на светулката с увеличението на разстоянието до светулката, с която тя комуникира.

Псевдокод

Алгоритъмът на светулката е обобщен като псевдокод по следния начин.

1  Parameters: $n,\beta _{0},\gamma$

2  Initialise the fireflies population ${\overrightarrow {x}}_{i}$ randomly

3  Compute $f({\overrightarrow {x}})$

4  while stop condition not met do

5     $i^{min}=\arg \min _{i}{f({\overrightarrow {x}}_{i})}$

6     $x_{i}^{min}=\arg \min _{{\overrightarrow {x}}_{i}}{f({\overrightarrow {x}}_{i})}$

7     for $i=1$ to $n$ do

8        for $j=1$ to $n$ do

9           if  $f({\overrightarrow {x}}_{j})<f({\overrightarrow {x}}_{i})$ then {Move firefly $i$ towards $j$}

10             Calculate distance $r_{j}$

11             Obtain attractiveness: $\beta \leftarrow \beta _{0}e^{-\gamma r_{j}}$

12             Generate a random solution ${\overrightarrow {u}}_{i}$

13             for $k=1$ to $d$ do

14                $x_{i,k}=(1-\beta )x_{i,k}+\beta x_{j,k}+u_{i,k}$

15             end for

16          end if

17       end for

18    end for

19    Generate a random solution ${\overrightarrow {u}}$

20    for $k=1$ to $d$ do {Best firefly moves randomly}

21       $x_{i^{min},k}=x_{i^{min},k}+u_{k}$

22    end for

23    Compute ${\overrightarrow {x}}_{i}$

24    Find the current best

25 end while

26 Postprocess results and visualisation