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

Алгоритм светлячков (англ. Firefly Algorithm, FA) — это метаэвристический алгоритм роевого интеллекта, предназначенный для решения задач глобальной оптимизации. Алгоритм был разработан в 2008 году британским учёным Синь-Шэ Яном (Xin-She Yang) и вдохновлён поведением светлячков, которые используют биолюминесценцию для привлечения партнёров и коммуникации. Основная идея метода заключается в моделировании движения особей (агентов) к более ярким источникам света, что соответствует поиску оптимального решения в многомерном пространстве параметров.

Принцип работы

Алгоритм основан на трёх идеализированных правилах, сформулированных Яном:

1. Все светлячки являются однополыми, поэтому каждый из них может привлекать любого другого.
2. Привлекательность (аттрактивность) светлячка пропорциональна его яркости (интенсивности света). Для двух светлячков менее яркий (с меньшей интенсивностью) будет двигаться к более яркому. Если два светлячка имеют одинаковую яркость, они движутся случайным образом.
3. Яркость светлячка определяется значением целевой функции (фитнес-функции) в его текущем положении. В задачах максимизации яркость прямо пропорциональна значению функции; в задачах минимизации — обратно пропорциональна.

Математическая модель

Положение каждого светлячка в пространстве решений описывается вектором \( \mathbf{x}_i \). Интенсивность света \( I_i \) в точке \( \mathbf{x}_i \) обычно приравнивается к значению целевой функции \( f(\mathbf{x}_i) \). Однако при распространении в среде свет ослабевает с расстоянием, поэтому воспринимаемая интенсивность \( I_{ij} \) для светлячка \( i \) от светлячка \( j \) рассчитывается по закону обратных квадратов с учётом коэффициента поглощения среды \( \gamma \):

\[ I_{ij} = I_j \cdot e^{-\gamma r_{ij}^2} \]

где \( r_{ij} = ||\mathbf{x}_i - \mathbf{x}_j|| \) — евклидово расстояние между светлячками \( i \) и \( j \).

Привлекательность \( \beta \) светлячка пропорциональна воспринимаемой интенсивности и определяется аналогично:

\[ \beta_{ij} = \beta_0 \cdot e^{-\gamma r_{ij}^2} \]

где \( \beta_0 \) — привлекательность на нулевом расстоянии (обычно \( \beta_0 = 1 \)).

Движение светлячка \( i \) к более яркому светлячку \( j \) описывается формулой:

\[ \mathbf{x}_i^{t+1} = \mathbf{x}_i^t + \beta_0 \cdot e^{-\gamma r_{ij}^2} \cdot (\mathbf{x}_j^t - \mathbf{x}_i^t) + \alpha \cdot \epsilon_i \]

где:

• \( \mathbf{x}_i^{t} \) — положение светлячка \( i \) на итерации \( t \);
• \( \beta_0 \) — базовая привлекательность;
• \( \gamma \) — коэффициент поглощения света (параметр среды);
• \( \alpha \) — параметр случайного шага (обычно \( \alpha \in [0, 1] \));
• \( \epsilon_i \) — вектор случайных чисел, равномерно распределённых на отрезке \( [-0.5, 0.5] \) или из гауссова распределения.

Первое слагаемое сохраняет текущее положение, второе — направляет светлячка к более яркому соседу, третье — добавляет стохастическую компоненту для исследования пространства.

Параметры алгоритма

Эффективность алгоритма светлячков существенно зависит от настройки трёх ключевых параметров:

• Коэффициент поглощения света (\( \gamma \)) — определяет, как быстро уменьшается привлекательность с расстоянием. При \( \gamma \to 0 \) привлекательность одинакова для всех расстояний, что приводит к равномерному движению всех светлячков к глобальному оптимуму, но замедляет сходимость. При \( \gamma \to \infty \) привлекательность становится практически нулевой, и алгоритм вырождается в случайный поиск. Обычно \( \gamma \) задают в диапазоне \( [0.01, 100] \) в зависимости от масштаба задачи.
• Параметр случайного шага (\( \alpha \)) — управляет степенью случайности движения. Высокие значения \( \alpha \) способствуют глобальному исследованию, низкие — локальной точной настройке. Часто \( \alpha \) уменьшают со временем (линейно или экспоненциально), аналогично температуре в алгоритме имитации отжига.
• Число светлячков (\( n \)) — размер популяции. Типичные значения — от 20 до 100. Большее число агентов повышает шанс найти глобальный оптимум, но увеличивает вычислительную сложность.

Варианты и модификации

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

• FA с адаптивными параметрами — значения \( \alpha \) и \( \gamma \) динамически изменяются в процессе работы алгоритма на основе статистики популяции или успешности поиска.
• Леви-полётный FA — вместо равномерного или гауссова шума используется распределение Леви, что позволяет совершать редкие, но большие скачки, улучшая глобальное исследование.
• Дискретный FA — адаптация для задач комбинаторной оптимизации, где координаты светлячков принимают дискретные значения (например, в задаче коммивояжёра или раскраски графа).
• Многоцелевой FA — расширение для задач с несколькими целевыми функциями, где яркость определяется по Парето-доминированию.
• Гибридные версии — комбинация FA с другими алгоритмами, такими как генетический алгоритм, дифференциальная эволюция или метод роя частиц.

Применение

Благодаря простоте реализации и эффективности, алгоритм светлячков нашёл применение в различных областях науки и техники:

Инженерные задачи

• Оптимизация конструкций — подбор параметров ферм, балок и других механических систем для минимизации веса при заданной прочности.
• Проектирование антенн — настройка геометрии и параметров антенных решёток для достижения требуемой диаграммы направленности.
• Настройка регуляторов — поиск оптимальных коэффициентов ПИД-регуляторов в системах автоматического управления.

Компьютерные науки

• Обучение нейронных сетей — подбор весов и смещений нейронных сетей вместо градиентных методов, особенно в задачах с недифференцируемыми функциями активации.
• Кластеризация данных — поиск центров кластеров путём минимизации внутрикластерного расстояния.
• Обработка изображений — пороговая сегментация, обнаружение контуров, сжатие изображений.

Энергетика и экономика

• Планирование энергосистем — оптимизация режимов работы электростанций, распределение нагрузки между генераторами.
• Управление портфелем инвестиций — поиск оптимального соотношения активов для максимизации доходности при заданном риске.
• Логистика — задачи маршрутизации транспорта и размещения складов.

Сравнение с другими алгоритмами

Алгоритм светлячков часто сравнивают с другими методами роевого интеллекта, такими как алгоритм роя частиц (PSO) и алгоритм кукушки (CS). Основные отличия:

• Механизм притяжения — в PSO частицы движутся к двум «лидерам» (своему лучшему и глобальному лучшему), в FA каждый светлячок может притягиваться ко всем более ярким особям, что создаёт более гибкую структуру взаимодействия.
• Стохастичность — FA использует явный параметр случайного шага, который можно регулировать, в то время как в PSO случайность встроена в коэффициенты ускорения.
• Сходимость — FA, как правило, лучше исследует пространство на начальных этапах, но может быть медленнее в локальной точной настройке по сравнению с PSO.

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

Критика и ограничения

Несмотря на популярность, алгоритм светлячков подвергается критике за некоторые недостатки:

• Чувствительность к параметрам — неправильный выбор \( \gamma \) и \( \alpha \) может привести к тому, что алгоритм либо не сойдётся, либо преждевременно остановится в локальном экстремуме. Требуется ручная настройка или использование адаптивных схем.
• Вычислительная сложность — на каждой итерации для каждого светлячка необходимо вычислять расстояния до всех остальных, что даёт сложность \( O(n^2) \) по числу пар. Для больших популяций это может быть затратно.
• Отсутствие строгой теории сходимости — хотя эмпирические результаты хороши, математическое доказательство сходимости FA к глобальному оптимуму для общего случая отсутствует. Существующие доказательства справедливы лишь для упрощённых версий алгоритма.
• Проблема масштабирования — на задачах с большим числом измерений (сотни и тысячи параметров) FA часто уступает методам, основанным на градиенте или более специализированным алгоритмам.

Интересные факты

• Создатель алгоритма Синь-Шэ Ян является автором нескольких других популярных метаэвристик, включая алгоритм кукушки (2009) и алгоритм летучих мышей (2010).
• В 2012 году алгоритм светлячков был включён в список «10 лучших алгоритмов» по версии журнала «IEEE Computational Intelligence Magazine» (по результатам опроса исследователей).
• Название алгоритма часто вызывает путаницу: в русскоязычной литературе его также называют «метод светлячков», «роевой алгоритм светлячков» или «алгоритм Firefly».

Источники

• Yang X. S. Nature-Inspired Metaheuristic Algorithms. — Luniver Press, 2008.
• Yang X. S. Firefly algorithm, stochastic test functions and design optimisation // International Journal of Bio-Inspired Computation. — 2010. — Vol. 2, no. 2. — P. 78–84.
• Fister I., Fister I. Jr., Yang X. S., Brest J. A comprehensive review of firefly algorithms // Swarm and Evolutionary Computation. — 2013. — Vol. 13. — P. 34–46.
• Gandomi A. H., Yang X. S., Alavi A. H. Mixed variable structural optimization using firefly algorithm // Computers & Structures. — 2011. — Vol. 89, no. 23–24. — P. 2325–2336.