Алгоритм пчел - Bees algorithm

Не путать с Алгоритм искусственной пчелиной семьи.

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

Метафора

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

Алгоритм

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

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

Псевдокод стандартного алгоритма пчел[2]   1 для i = 1,…, ns i scout [i] = Initialise_scout () ii flower_patch [i] = Initialise_flower_patch (scout [i]) 2 делать, пока stopping_condition = TRUE i Recruitment () ii for i = 1, ... , nb 1 flower_patch [i] = Local_search (flower_patch [i]) 2 flower_patch [i] = Site_abandonment (flower_patch [i]) 3 flower_patch [i] = Neighbourhood_shrinking (flower_patch [i]) iii для i = nb, ... , ns 1 flower_patch [i] = Global_search (flower_patch [i])}

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

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

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

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

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

Варианты

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

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

Смотрите также

использованная литература

  1. ^ Фам Д.Т., Ганбарзаде А., Коч Э., Отри С., Рахим С. и Заиди М. Алгоритм пчел. Техническая записка, Технологический центр, Кардиффский университет, Великобритания, 2005
  2. ^ а б c Фам, Д.Т., Кастеллани, М. (2009), Алгоритм пчел - моделирование собирательского поведения для решения задач непрерывной оптимизации. Proc. ImechE, Часть C, 223 (12), 2919-2938.
  3. ^ Фам Д.Т. и Кастеллани М. (2013), Бенчмаркинг и сравнение вдохновленных природой алгоритмов непрерывной оптимизации популяций, Мягкие вычисления, 1-33.
  4. ^ Фам Д.Т. и Кастеллани М. (2015), Сравнительное исследование алгоритма пчел как инструмента оптимизации функций, Cogent Engineering 2 (1), 1091540.
  5. ^ а б c Насринпур, Х. Р., Масса Бавани, А., Тешнехлаб, М., (2017), Алгоритм сгруппированных пчел: сгруппированная версия алгоритма пчел, Компьютеры 2017, 6 (1), 5; (Дои:10.3390 / компьютеры6010005 )
  6. ^ а б c d Терешко В., Лоенгаров А., (2005) Коллективное принятие решений в динамике сбора медоносных пчел. Журнал вычислительных и информационных систем, 9 (3), 1-7.
  7. ^ Фон Фриш, К. (1967) Язык танца и ориентация пчел. Издательство Гарвардского университета, Кембридж, Массачусетс.
  8. ^ а б Фам Д.Т., Ганбарзаде А., Коч Э., Отри С., Рахим С., Заиди М., Алгоритм пчел, новый инструмент для решения сложных задач оптимизации, Proc 2nd Int Virtual Conference on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454-459, 2006.
  9. ^ Фам Д. Т., Хадж Дарвиш А. (2008), А. Нечеткий выбор локальных поисковых сайтов в алгоритме пчел. Труды инновационных производственных машин и систем (IPROMS 2008)
  10. ^ Фам К. Т., Фам Д. Т., Кастеллани М., Модифицированный алгоритм пчел и основанный на статистике метод настройки его параметров. Труды Института инженеров-механиков (ImechE), Часть I: Journal of Systems and Control Eng., 2011 (Дои:10.1177/0959651811422759 )

внешние ссылки