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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм пчелиной колонии (алгоритм оптимизации подражанием пчелиной колонии, англ. 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. 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, Soft Computing, 1-33.