Алгоритъмът на светулката () е метаевристичен алгоритъм, предложен за първи път от британския математик Син-Шъ Ян през 2008 година. Алгоритъмът се прилага за оптимизация на бенчмарк функции и използва популационно търсене, т.е. кандидат-решенията използват като градивни блокове части от различни решения.
Биологична метафора Алгоритъмът е вдъхновен от поведението на светулките, което използва биолуминесценция като форма на комуникация с други светулки, за търсене на храна и за отблъскване на хищници. Поведението им съдържа характеристики на интелигентност в рояк (swarm intelligence) чрез самоорганизация и децентрализирано вземане на решения. Биолуминесценцията служи и да сигнализрат при търсенето на партньор, като яркостта е индикатор за приспособимостта на мъжките екземпляри.Kar, A.K. Bio inspired computing – A review of algorithms and scope of applications. Expert Systems with Applications, Volume 59 Issue C, October 2016, Pages 20-32 (ResearchGate)
Описание на алгоритъма За нуждите на алгоритъма, се приема, че светулките са безполови, а поведението им се заключава в три основни правила: Светулката бива привличана от други светулки (без значение от техния пол), Привлекателността на една светулка е пропорционална на яркостта ѝ и намалява при увеличаването на разстоянието между светулките, и Видът на целевата функция определя яркостта на светулката.
Допускането при алгоритъма е, че популация от кандидат-решения на една оптимизационна задача са агенти от вида на светулката. Тези агенти представляват вектори от размерност , представляваща променливите на задачата. Качеството (оптималността) на всяко решение се оценява посредством фитнес функция . Всеки агент „свети“ пропорционално на качеството си, което заедно с привлекателността му (), определя колко силно привлича други агенти от рояка.
Два други потребителски дефинирани параметъра са стойността на максималната привлекателност () и коефициента на абсорбция (), който определя вариацията на привлекателността на светулката с увеличението на разстоянието до светулката, с която тя комуникира.
Псевдокод Алгоритъмът на светулката е обобщен като псевдокод по следния начин.Parpinelli, R. S., Lopes, H. S. New inspirations in swarm intelligence: a survey. Int. J. Bio-Inspired Computation, Vol. 3, No. 1, 2011, 1-16.
1 Parameters:
2 Initialise the fireflies population randomly
3 Compute
4 while stop condition not met do
5
6
7 for to do
8 for to do
9 if then {Move firefly towards }
10 Calculate distance
11 Obtain attractiveness:
12 Generate a random solution
13 for to do
14
15 end for
16 end if
17 end for
18 end for
19 Generate a random solution
20 for to do {Best firefly moves randomly}
21
22 end for
23 Compute
24 Find the current best
25 end while
26 Postprocess results and visualisation
Източници
Категория:Метаевристични алгоритми