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

В математической оптимизации алгоритм светлячков представляет собой метаэвристический метод, предложенный Синь-Ше Янгом и вдохновленный поведением мерцания светлячков . [1]

Алгоритм

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

Начало 1) Целевая функция: ; 2) Сгенерировать начальную популяцию светлячков ;. 3) Сформулировать интенсивность света I так, чтобы она была связана с (например, для задач максимизации, или просто ;) 4) Определить коэффициент поглощения γ    ф (  х  ) ,   х  = (  х  1   ,  х  2   , . . . ,  х  г   )   {\displaystyle f(\mathbf {x}),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})}       х   я    ( я = 1 , 2 , … , н )   {\displaystyle \mathbf {x} _{i}\quad (i=1,2,\точки,n)}     ф (  х  )   {\ displaystyle f (\ mathbf {x})}     я ∝ ф (  х  )   {\displaystyle I\propto f(\mathbf {x})}     я = ф (  х  )   {\displaystyle I=f(\mathbf {x} )}  while (t < MaxGeneration) for i = 1 : n (все n светлячков) for j = 1 : i (n светлячков) if ( ),     я  дж   >  я  я     {\displaystyle I_{j}>I_{i}}  Изменить привлекательность в зависимости от расстояния r с помощью ;    эксп ⁡ ( − γ  г )   {\displaystyle \exp(-\гамма \;r)}  переместить светлячка i в сторону j;  Оценить новые решения и обновить интенсивность освещения; конец, если  конец для j конец для i Ранжируйте светлячков и найдите лучшего на данный момент; конец пока конец

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

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

х я т + 1 = х я т + β эксп ⁡ [ − γ г я дж 2 ] ( х дж т − х я т ) + α т ϵ т {\displaystyle \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}}

где — параметр, управляющий размером шага, а — вектор, взятый из гауссовского или другого распределения.zae α т {\displaystyle \альфа _{т}} ϵ т {\displaystyle {\boldsymbol {\epsilon }}_{t}}

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

Критика

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

Смотрите также

Ссылки

  1. ^ Yang, XS (2008). Метаэвристические алгоритмы, вдохновленные природой . Luniver Press. ISBN 978-1-905986-10-1.
  2. ^ Almasi, Omid N.; Rouhani, Modjtaba (2016). «Новый подход к назначению нечеткого членства и выбору модели на основе динамических центров классов для семейства нечетких SVM с использованием алгоритма firefly». Turkish Journal of Electrical Engineering & Computer Sciences . 4 : 1–19. doi : 10.3906/elk-1310-253 . Практическое применение FA в наборах данных UCI.
  3. ^ Лонес, Майкл А. (2014). «Метаэвристика в алгоритмах, вдохновленных природой» (PDF) . Труды сопутствующей публикации ежегодной конференции 2014 года по генетическим и эволюционным вычислениям . стр. 1419–1422. CiteSeerX 10.1.1.699.1825 . doi :10.1145/2598394.2609841. ISBN  9781450328814. S2CID  14997975. С другой стороны, FA мало чем отличается от PSO, поскольку закон обратных квадратов имеет тот же эффект, что и скученность и совместное использование приспособленности в EA, а также использование множественных роев в PSO.
  4. ^ Weyland, Dennis (2015). "Критический анализ алгоритма поиска гармонии — Как не решать судоку". Operations Research Perspectives . 2 : 97–105. doi : 10.1016/j.orp.2015.04.001 . hdl : 10419/178253 . Например, различия между метаэвристикой оптимизации роя частиц и "новыми" метаэвристиками, такими как алгоритм светлячка, алгоритм оптимизации плодовой мушки, алгоритм оптимизации роя рыб или алгоритм оптимизации роя кошек, кажутся незначительными.
  5. ^ Ariyaratne MKA, Pemarathne WPJ (2015) Обзор последних достижений алгоритма светлячка: современный алгоритм, вдохновленный природой. В: Труды 8-й международной исследовательской конференции, 61–66, KDU, опубликовано в ноябре 2015 г., http://ir.kdu.ac.lk/bitstream/handle/345/1038/com-047.pdf?sequence=1&isAllowed=y
  • [1] Файлы программ Matlab, включенные в книгу: Xin-She Yang, Nature-Inspired Metaheuristic Algorithms, второе издание, Luniver Press, (2010).
Взято с "https://en.wikipedia.org/w/index.php?title=Алгоритм_Firefly&oldid=1193815375"