Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с алгоритмом искусственной пчелиной семьи .

В информатике и исследование операций , то алгоритм пчела является популяционном алгоритмом поиска , который был разработан Ф, Ghanbarzadeh и др. в 2005 г. [1] Он имитирует поведение семей медоносных пчел в поисках пищи. В своей базовой версии алгоритм выполняет своего рода поиск окрестности в сочетании с глобальным поиском и может использоваться как для комбинаторной оптимизации, так и для непрерывной оптимизации . Единственным условием применения алгоритма пчел является определение некоторого расстояния между решениями. Эффективность и особенности алгоритма пчел были доказаны в ряде исследований. [2][3] [4] [5]

Метафора [ править ]

Колония медоносных пчел может распространяться на большие расстояния (более 14 км) [6] и в нескольких направлениях одновременно для сбора нектара или пыльцы из нескольких источников пищи (цветочных пятен). Небольшая часть колонии постоянно обыскивает окружающую среду в поисках новых цветочных участков. Эти пчелы-разведчики беспорядочно перемещаются по территории вокруг улья, оценивая прибыльность (чистый выход энергии) обнаруженных источников пищи. [6] Когда они возвращаются в улей, разведчики кладут собранную пищу. Те люди, которые нашли очень прибыльный источник пищи, идут в место в улье, называемое «танцполом», и исполняют ритуал, известный как танец виляния . [7] Посредством танца виляния пчела-разведчик сообщает о месте своего открытия праздным наблюдателям, которые участвуют в эксплуатации цветочного поля. Поскольку продолжительность танца пропорциональна оценке разведчика источника пищи, набирается больше собирателей, чтобы собрать лучшие по рейтингу цветочные участки. После танцев разведчик возвращается к обнаруженному им источнику еды, чтобы собрать больше еды. Пока они считаются прибыльными, разведчики будут рекламировать богатые источники пищи, когда они вернутся в улей. Нанятые фуражиры также могут покачиваться в танце, увеличивая вербовку для получения очень ценных цветочных участков. Благодаря этому автокаталитическому процессу пчелиная семья может быстро переключить усилия по поиску пищи на наиболее прибыльные цветочные участки. [6]

Алгоритм [ править ]

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

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

Псевдокод для стандартного алгоритма пчел [2] 1 для i = 1,…, нс i scout [i] = Initialise_scout () ii flower_patch [i] = Initialise_flower_patch (разведчик [i]) 2 делать, пока не stop_condition = TRUE i Набор персонала ()  ii для i = 1, ..., na 1 flower_patch [i] = Local_search (flower_patch [i]) 2 flower_patch [i] = Site_abandonment (flower_patch [i]) 3 flower_patch [i] = Окрестности_сжатия (flower_patch [i]) iii для i = nb, ..., ns 1 flower_patch [i] = Global_search (flower_patch [i])}

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

В процедуре набора скауты, посетившие nb ≤ ns наиболее подходящих решений (лучших участков), исполняют танец виляния. То есть они вербуют собирателей для дальнейшего поиска окрестностей наиболее многообещающих решений. Разведчики , которые расположены самые лучшие пе ≤ Н.Б. решений (элитные сайты) призывник Nre фуражиров каждый, в то время как оставшиеся нб - NE разведчики вербовать НРБ ≤ ЯРД фуражиров каждый. Таким образом, количество нанимаемых фуражиров зависит от прибыльности источника корма.

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

Как и в случае с биологическими пчелиными семьями, [6] небольшое количество разведчиков продолжает исследовать пространство решений в поисках новых регионов высокой пригодности (глобальный поиск). Процедура глобального поиска повторно инициализирует последние ns - nb цветочные патчи со случайно сгенерированными решениями.

В конце одного цикла поиска популяция скаутов снова состоит из ns скаутов: nr скаутов, созданных процедурой местного поиска (некоторые из которых, возможно, были повторно инициализированы процедурой закрытия участка), и ns - nb скаутов, созданных процедура глобального поиска. Общий размер колонии искусственных пчел составляет n = ne • nre + ( nb - ne ) • nrb + ns ( собиратели на элитных участках + оставшиеся сборщики лучших участков + разведчики) пчел.

Варианты [ править ]

В дополнение к базовому алгоритму пчел [8] существует ряд улучшенных или гибридных версий БА, каждая из которых фокусируется на некоторых недостатках базовой БА. Эти варианты включают (но не ограничиваются ими) нечеткую или улучшенную ВА (EBA), [9] сгруппированную BA (GBA), [5] гибридную модифицированную BA (MBA) [10] и так далее. Псевдокод для сгруппированной БА (GBA) [5] выглядит следующим образом.

функция GBA  %% Задайте параметры проблемыmaxIteration = ..; % количество итераций (например, 1000-5000)  maxParameters = ..; % количество входных переменных  мин = [..] ; % массив размера maxParameters для указания минимального значения каждого входного параметра   макс = [..] ; % массив размера maxParameters для указания максимального значения каждого входного параметра     %% Установить параметры алгоритма сгруппированных пчел (GBA)R_ngh = ..; % радиус участка поиска пчел в первой группе (например, 0,001 - 1)   п = ..; % количества пчел-разведчиков (например, 4-30)  nGroups = ..; % количество групп, исключая случайную группу   Автоматическая настройка параметров %% GBAk = 3 * n / (( nGroups + 1 ) ^ 3 - 1 ); Параметр% GBA для установки количества пчел-разведчиков в каждой группе         группы = нули ( 1 , nGroups ); % Массив для хранения количества пчел-разведчиков для каждой группы   recruited_bees = нули ( 1 , nGroups ); % Массив для хранения количества набранных пчел для каждой группы  = ((( макс - мин ) ./ 2 ) - R_ngh ) ./ ( nGroups ^ 2 - 1 ); Параметр% GBA для установки радиусов соседства            б = R_ngh - а ; Параметр% GBA для установки радиусов соседства    для i = 1 : nGroups % Для каждой группы   группы ( i ) = этаж ( k * i ^ 2 ); % определяет количество пчел-разведчиков в каждой группе   если группы ( i ) == 0    группы ( i ) = 1 ; % в каждой группе должна быть как минимум одна пчела-разведчик   конецrecruited_bees = ( nGroups + 1 - i ) ^ 2 ; % устанавливает количество набираемых пчел для каждой группы  ngh ( i ) = a * i * i + b ; % установить патч радиуса для каждой группы      конецgroup_random = n - сумма ( группы ); % назначить оставшихся пчел (если есть) для случайного поиска    group_random = макс ( group_random , 0 ); % убедитесь, что это не отрицательное число   %% инициализировать матрицу населениянаселение = нули ( n , maxParameters + 1 ); % Популяция из n пчел, включая все входные переменные и их приспособленность   для i = 1 : n  Население ( я , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % случайная инициализация переменных maxParameters между max и min   популяция ( i , maxParameters + 1 ) = eval_fitness ( популяция ( i , :)); % оценка пригодности каждого решения и сохранение ее в последнем индексе матрицы популяции  конецsorted_population = sortrows ( популяция ); % сортируют популяцию по степени пригодности    %% Итерации алгоритма сгруппированных пчелдля i = 1 : основной цикл maxIteration % GBA  beeIndex = 0 ; % отслеживать всех пчел (т.е. патчи)  для g = 1 : nGroups % для каждой группы пчел-разведчиков  для j = 1 : группы ( g ) % используют каждый патч в каждой группе      beeIndex = beeIndex + 1 ; % увеличить счетчик за каждый патч    для i = 1 : recruited_bees ( g ) % для каждой набранной пчелы группы     решение = bee_waggle_dance ( sorted_population ( beeIndex , 1 : maxParameters ), ngh ( g )); % искать окрестности вокруг выбранного патча / решения в радиусе ngh  fit = оценивать_фитнесс ( решение ); % оценить пригодность недавно найденного решения  if fit < sorted_population ( beeIndex , maxParameters + 1 ) % Проблема минимизации: если пчела-рекютер нашла лучшее место / патч / решение    sorted_population ( beeIndex , 1 : maxParameters + 1 ) = [ решение ( 1 : maxParameters ), соответствует ]; % копировать новое решение и его соответствие отсортированной матрице населения      конец конецконецконецдля i = 1 : group_random % Для оставшихся случайных пчел     beeIndex = beeIndex + 1 ;    решение ( beeIndex , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % сгенерировать новое случайное решение по индексу beeIndex   решение ( beeIndex , maxParameters + 1 ) = оценивать_пригодность ( решение ); % оценивают его пригодность sorted_population ( beeIndex , :) = [ решение ( 1 : maxParameters ), подходит ]; % скопировать новое случайное решение и его соответствие отсортированной матрице совокупности     конецsorted_population = sortrows ( отсортированное_популяция ); % сортируют популяцию по степени пригодности Best_solution_sofar = отсортированное_популяция ( 1 , :);disp ( 'Лучшее:' ); disp ( Best_solution_sofar ); % Показать лучшее решение текущей итерации end % конец основного цикла GBA конец % конец основной функции %% Функция Bee Waggle Danceфункция  new_solution = bee_waggle_dance ( решение, ngh, maxParameters ) new_solution ( 1 : maxParameters ) = ( решение - ngh ) + ( 2 * ngh . * rand ( 1 , maxParameters ));   конец

См. Также [ править ]

Ссылки [ править ]

  1. ^ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S и Zaidi M. Алгоритм пчел. Техническая записка, Технологический центр, Кардиффский университет, Великобритания, 2005 г.
  2. ^ a b c Фам, Д. Т., Кастеллани, М. (2009), Алгоритм пчел - моделирование собирательского поведения для решения задач непрерывной оптимизации . Proc. ImechE, Часть C, 223 (12), 2919-2938.
  3. ^ Фам Д.Т. и Кастеллани М. (2013), Бенчмаркинг и сравнение вдохновленных природой алгоритмов непрерывной оптимизации , основанных на популяциях , Мягкие вычисления, 1-33.
  4. ^ Фам Д.Т. и Кастеллани М. (2015), Сравнительное исследование алгоритма пчел как инструмента для оптимизации функций , Cogent Engineering 2 (1), 1091540.
  5. ^ a b c Насринпур, HR, Масса Бавани, А., Тешнехлаб, М., (2017), Алгоритм сгруппированных пчел: сгруппированная версия алгоритма пчел , Компьютеры 2017, 6 (1), 5; ( DOI : 10.3390 / computers6010005 )
  6. ^ a b c d Терешко В., Лоенгаров А., (2005) Коллективное принятие решений в динамике сбора меда пчелами . Журнал вычислительных и информационных систем, 9 (3), 1-7.
  7. ^ Фон Фриш, К. (1967) Язык танца и ориентация пчел. Издательство Гарвардского университета, Кембридж, Массачусетс.
  8. ^ a b Pham DT, Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., Алгоритм Bees, новый инструмент для сложных задач оптимизации , Proc 2nd Int Virtual Config on Intelligent Production Machines and Systems ( IPROMS 2006), Oxford: Elsevier, стр. 454-459, 2006.
  9. ^ Фам Д.Т., Хадж Дарвиш А. (2008), А. Нечеткий выбор локальных поисковых сайтов в алгоритме пчел . Труды инновационных производственных машин и систем (IPROMS 2008)
  10. ^ Фам QT, Фам Д.Т., Кастеллани М., Модифицированный алгоритм пчел и основанный на статистике метод настройки его параметров. Труды Института инженеровмехаников (IMechE), Часть I: Журнал систем и управления Eng, 2011 (. Дои : 10,1177 / 0959651811422759 )

Внешние ссылки [ править ]

  • Сайт алгоритма пчел
  • Боффинс заставил танцующих пчел работать - bbc news русская служба