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

Алгоритъмът на светулката (Шаблон:Lang) е метаевристичен алгоритъм, предложен за първи път от британския математик Син-Шъ Ян през 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 \underset{i}{\min }f({\overrightarrow{x}}_i)$

6     $x_i^{min}=\arg \underset{{\overrightarrow{x}}_i}{\min }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