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

Алгоритм пчелиной колонии (алгоритм оптимизации подражанием пчелиной колонии, англ. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.