Алгоритм Светлячка

В математической оптимизации алгоритм светлячков — это метаэвристика, предложенная Синь-Ше Яном и вдохновленная мигающим поведением светлячков .

Алгоритм

В псевдокоде алгоритм можно записать так:

Begin
    1) Objective function: $f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})$;
    2) Generate an initial population of fireflies $\mathbf {x} _{i}\quad (i=1,2,\dots ,n)$;.
    3) Formulate light intensity I so that it is associated with $f(\mathbf {x} )$
       (for example, for maximization problems, $I\propto f(\mathbf {x} )$ or simply $I=f(\mathbf {x} )$;)
    4) Define absorption coefficient γ

    while (t < MaxGeneration)
        for i = 1 : n (all n fireflies)
            for j = 1 : i (n fireflies)
                if ($I_{j}>I_{i}$),
                    Vary attractiveness with distance r via $\exp(-\gamma \;r)$;
                    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

Обратите внимание, что количество оценок целевой функции на цикл составляет одно вычисление на светлячок, хотя приведенный выше псевдокод предполагает, что оно равно n × n . Янга (На основе кода MATLAB .) Таким образом, общее количество оценок целевой функции равно (количество поколений) × (количество светлячков).

Основная формула обновления для любой пары из двух светлячков $\mathbf {x} _{i}$ и $\mathbf {x} _{j}$ является

$\mathbf {x} _{i}^{t+1}=\mathbf {x} _{i}^{t}+\beta \exp[-\gamma r_{ij}^{2}](\mathbf {x} _{j}^{t}-\mathbf {x} _{i}^{t})+\alpha _{t}{\boldsymbol {\epsilon }}_{t}$

где $\alpha _{t}$ – параметр, управляющий размером шага, а ${\boldsymbol {\epsilon }}_{t}$ вектор, полученный из гауссовой или другой дистрибуция.zae

Можно показать, что предельный случай $\gamma \rightarrow 0$ соответствует стандартной оптимизации Particle Swarm (PSO). Фактически, если внутренний цикл (для j) удалить и яркость $I_{j}$ заменяется текущим мировым лучшим $g^{*}$, то FA по сути становится стандартным PSO.

Критика

Вдохновленная природой метаэвристика в целом вызвала критику в исследовательском сообществе за то, что она скрывает отсутствие новизны за метафорами. Алгоритм светлячка подвергался критике за то, что он отличается от хорошо зарекомендовавшей себя оптимизации роя частиц . лишь незначительно

См. также

• Роевой интеллект

Внешние ссылки

• [1] Файлы программ Matlab, включенные в книгу: Синь-Ше Ян, Природные метаэвристические алгоритмы, второе издание, Luniver Press, (2010).