Алгоритм пчелиной колонии

Алгоритм пчелиной колонии (алгоритм оптимизации подражанием пчелиной колонии, англ. artificial bee colony optimization, ABC) — один из полиномиальных эвристических алгоритмов для решения оптимизационных задач в области информатики и исследования операций. Относится к категории стохастических бионических алгоритмов, основан на имитации поведения колонии медоносных пчел при сборе нектара в природе. Предложен Д. Карабога в 2005 г.

Стратегия сбора нектара медоносными пчелами в природе

Алгоритм пчелиной колонии как результат наблюдения за поведением колонии медоносных пчел при сборе нектара в природе

Основной целью работы пчелиной колонии в природе является разведка пространства вокруг улья с целью поиска нектара с последующим его сбором. Для этого в составе колонии существуют различные типы пчел: пчелы-разведчики и рабочие пчелы-фуражиры (кроме них, в колонии существуют трутни и матка, не участвующие в процессе сбора нектара). Разведчики ведут исследование окружающего улей пространства и сообщают информацию о перспективных местах, в которых было обнаружено наибольшее количество нектара (для обмена информацией в улье существует специальный механизм, именуемый танцем пчелы).

Стратегия оптимизации целевой функции

Схематичное изображение стратегии разведки двумерного пространства (жирные линии — вылеты разведчиков, тонкие линии — уточнение решений рабочими пчелами)

Алгоритм пчелиной колонии может применяться для решения дискретных (комбинаторных) и непрерывных задач глобальной оптимизации и имеет достаточную степень схожести с мультистарт-алгоритмами. Обычно он включает в себя начальную разведку и последующую работу пчел улья. При инициализации (начальной разведке) производится выполнение разведки пространства признаков с целью определения $K$ его наиболее перспективных точек с наилучшими значениями целевой функции $f(X)=f(x_{1},x_{2},...,x_{n})$ (в простейшем случае с использованием метода случайного перебора), которые запоминаются в улье. После этого в окрестностях выбранных точек производится локальная разведка в пределах заданного радиуса разведки $R$ с целью попытки уточнения решения (улучшения рекорда), при этом при достижении улучшения в улье сохраняется обновленное значение рекорда $f^{*}$ и соответствующий ему вектор параметров целевой функции $X^{*}$. Комбинируя работу пчел-разведчиков и рабочих пчел на протяжении заданного числа итераций $C$ алгоритм обеспечивает постепенное улучшение запоминаемой выборки ${\mathfrak {R}}=[X_{1},X_{2},...,X_{K}]$ из $K$ решений. По завершении его работы из указанного множества решений выбирается наилучшее, что является результатом работы алгоритма.

См. также

• Муравьиный алгоритм
• Метод роя частиц