Алгоритм пчелиной колонии (Glikjnmb hcylnukw tklkunn)

Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Алгоритм пчелиной колонии может применяться для решения дискретных (комбинаторных) и непрерывных[англ.] задач глобальной оптимизации[2][3] и имеет достаточную степень схожести с мультистарт-алгоритмами[англ.]. Обычно он включает в себя начальную разведку и последующую работу пчел улья. При инициализации (начальной разведке) производится выполнение разведки пространства признаков с целью определения его наиболее перспективных точек с наилучшими значениями целевой функции (в простейшем случае с использованием метода случайного перебора[англ.]), которые запоминаются в улье. После этого в окрестностях выбранных точек производится локальная разведка в пределах заданного радиуса разведки с целью попытки уточнения решения (улучшения рекорда), при этом при достижении улучшения в улье сохраняется обновленное значение рекорда и соответствующий ему вектор параметров целевой функции . Комбинируя работу пчел-разведчиков и рабочих пчел на протяжении заданного числа итераций алгоритм обеспечивает постепенное улучшение запоминаемой выборки из решений. По завершении его работы из указанного множества решений выбирается наилучшее, что является результатом работы алгоритма.


Примечания

[править | править код]
  1. D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.
  2. Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems Архивная копия от 9 ноября 2016 на Wayback Machine. Proc. ImechE, Part C, 223(12), 2919-2938.
  3. Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms Архивная копия от 26 октября 2017 на Wayback Machine, Soft Computing, 1-33.