Алгоритм пчел
В информатике и исследовании операций алгоритм пчел на основе популяции представляет собой алгоритм поиска , разработанный Фамом, Ганбарзаде и др. в 2005 году. [1] Он имитирует поведение пчелиных семей при поиске пищи. В своей базовой версии алгоритм выполняет своего рода поиск окрестностей в сочетании с глобальным поиском и может использоваться как для комбинаторной, так и для непрерывной оптимизации . Единственным условием применения алгоритма пчел является определение некоторой меры расстояния между решениями. Эффективность и специфические возможности алгоритма пчел были доказаны в ряде исследований. [2] [3] [4] [5] [6]
Метафора [ править ]
Колония медоносных пчел может распространяться на большие расстояния (более 14 км). [7] и одновременно в нескольких направлениях для сбора нектара или пыльцы из нескольких источников пищи (цветочных грядок). Небольшая часть колонии постоянно обыскивает окружающую среду в поисках новых цветочных участков. Эти пчелы-разведчики беспорядочно перемещаются по территории вокруг улья, оценивая рентабельность (чистый выход энергии) встречающихся источников пищи. [7] Вернувшись в улей, разведчики складывают собранную еду. Те особи, которые нашли высокодоходный источник пищи, отправляются в место в улье, называемое «танцпол», и исполняют ритуал, известный как виляющий танец . [8] Посредством виляющего танца пчела-разведчик сообщает место своей находки праздным зрителям, которые присоединяются к освоению цветочного участка. Поскольку продолжительность танца пропорциональна рейтингу разведчика источника пищи, для сбора цветочных грядок с лучшим рейтингом нанимается больше собирателей. После танца разведчик возвращается к обнаруженному им источнику пищи, чтобы собрать еще еды. Пока они оцениваются как прибыльные, разведчики будут рекламировать богатые источники пищи, когда вернутся в улей. Нанятые собиратели также могут танцевать, увеличивая количество желающих получить весьма ценные цветочные грядки. Благодаря этому автокаталитическому процессу пчелиная семья может быстро переключить фокус усилий по поиску пищи на наиболее прибыльные цветочные участки. [7]
Алгоритм [ править ]
Алгоритм пчел [2] [9] имитирует стратегию кормления медоносных пчел, чтобы найти лучшее решение проблемы оптимизации. Каждое решение-кандидат рассматривается как источник пищи (цветок), а популяция (колония) из n для поиска в пространстве решений используется агентов (пчел). Каждый раз, когда искусственная пчела посещает цветок (приземляется на раствор), она оценивает его рентабельность (пригодность).
Алгоритм пчел состоит из процедуры инициализации и основного цикла поиска, который повторяется заданное количество раз T или до тех пор, пока не будет найдено решение приемлемого соответствия. Каждый цикл поиска состоит из пяти процедур: набор персонала, локальный поиск, сокращение района, оставление объекта и глобальный поиск.
Pseudocode for the standard bees algorithm[2] 1 for i=1,…,ns i scout[i]=Initialise_scout() ii flower_patch[i]=Initialise_flower_patch(scout[i]) 2 do until stopping_condition=TRUE i Recruitment() ii for 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]=Neighbourhood_shrinking(flower_patch[i]) iii for i = nb,...,ns 1 flower_patch[i]=Global_search(flower_patch[i])}
В процедуре инициализации пчелы - разведчики случайным образом размещаются в пространстве поиска и оценивают пригодность решений, в которых они приземляются. Для каждого решения выделяется окрестность (называемая цветочным пятном).
В процессе набора разведчики, посетившие nb ≤ ns наиболее подходящих решений (лучшие площадки), исполняют танец виляния. То есть они набирают фуражиров для дальнейшего поиска окрестностей наиболее перспективных решений. Разведчики, обнаружившие лучшие решения ne ≤ nb (элитные участки), набирают по nre собирателей каждый, в то время как оставшиеся nb - ne разведчики набирают по nrb ≤ nre собирателей каждый. Таким образом, количество набираемых собирателей зависит от прибыльности источника пищи.
При процедуре локального поиска набранные собиратели случайным образом разбрасываются по цветочным грядкам, окружающим растворы, которые посетили разведчики (локальная эксплуатация). Если какой-либо из собирателей на цветочном участке попадает на решение с более высокой пригодностью, чем решение, которое посетил разведчик, этот собиратель становится новым разведчиком. Если ни один собиратель не находит более подходящего решения, размер цветочного участка уменьшается (процедура сокращения соседства). Обычно цветочные пятна изначально определяются на большой площади, а их размер постепенно уменьшается в результате процедуры сокращения окрестностей. В результате объем местных исследований постепенно сосредотачивается на территории, непосредственно близкой к лучшим местам для фитнеса. Если в течение заданного числа циклов поиска на данном цветочном участке не зафиксировано улучшения приспособленности, локальный максимум приспособленности считается найденным, участок покидают (покидание участка) и случайным образом генерируется новый разведчик.
Как и в биологических пчелиных семьях, [7] небольшое количество разведчиков продолжает исследовать пространство решений в поисках новых регионов с высокой пригодностью (глобальный поиск). Процедура глобального поиска повторно инициализирует последние ns – nb цветочных патчей со случайно сгенерированными решениями.
В конце одного цикла поиска популяция скаутов снова состоит из ns скаутов: nr скаутов, созданных процедурой локального поиска (некоторые из которых могли быть повторно инициализированы процедурой оставления сайта), и ns - nb скаутов, сгенерированных процедурой локального поиска. процедура глобального поиска. Общий размер искусственной пчелиной семьи составляет n = ne • nre +( nb - ne ) • nrb + ns (элитные участки фуражиров + оставшиеся лучшие участки фуражиров + разведчики) пчел.
Варианты [ править ]
В дополнение к основному алгоритму пчел, [9] Существует ряд улучшенных или гибридных версий БА, каждая из которых ориентирована на некоторые недостатки базового БА. Эти варианты включают (но не ограничиваются ими) нечеткий или расширенный BA (EBA), [10] групповой БА (GBA), [5] гибридно-модифицированный БА (MBA) [11] и так далее. Псевдокод для сгруппированного БА (GBA) [5] заключается в следующем.
function GBA
%% Set the problem parameters
maxIteration = ..; % number of iterations (e.g. 1000-5000)
maxParameters = ..; % number of input variables
min = [..] ; % an array of the size maxParameters to indicate the minimum value of each input parameter
max = [..] ; % an array of the size maxParameters to indicate the maximum value of each input parameter
%% Set the grouped bees algorithm (GBA) parameters
R_ngh = ..; % patch radius of the neighborhood search for bees in the first group (e.g. 0.001 - 1)
n = ..; % number of scout bees (e.g. 4-30)
nGroups = ..; % number of groups, excluding the random group
%% GBA's automatic parameter settings
k = 3 * n / ((nGroups+1)^3 - 1); % GBA's parameter to set the number of scout bees in each group
groups = zeros(1,nGroups); % An array to keep the number of scout bees for each group
recruited_bees = zeros(1,nGroups); % An array to keep the number of recruited bees for each group
a = (((max - min) ./ 2) - R_ngh) ./ (nGroups^2 - 1); % GBA's parameter for setting neighborhood radiuses
b = R_ngh - a; % GBA's parameter for setting neighborhood radiuses
for i=1:nGroups % For each group
groups(i) = floor(k*i^2); % determine the number of scout bees in each group
if groups(i) == 0
groups(i) = 1; % there has to be at least one scout bee per each group
end
recruited_bees = (nGroups+1-i)^2; % set the number of recruited bees for each group
ngh(i) = a * i*i + b; % set the radius patch for each group
end
group_random = n - sum(groups); % assign the remainder bees (if any) to random search
group_random = max(group_random,0); % make sure it is not a negative number
%% initialize the population matrix
population = zeros(n,maxParameters+1); % A population of n bees including all input variables and their fitness
for i=1:n
population(i,1:maxParameters)= generate_random_solution(maxParameters,min, max); % random initialization of maxParameters variables between max and min
population(i,maxParameters+1) = evalulate_fitness(population(i,:)); % fitness evaluation of each solution and saving it at the last index of the population matrix
end
sorted_population = sortrows(population); % sort the population based on their fitnesses
%% Iterations of the grouped bees algorithm
for i=1:maxIteration % GBA's main loop
beeIndex = 0; % keep track of all bees (i.e, patches)
for g=1:nGroups % for each group of scout bees
for j = 1 : groups(g) % exploit each patch within each group
beeIndex = beeIndex + 1; % increase the counter per each patch
for i = 1 : recruited_bees(g) % for each recruited bees of the group
solution = bee_waggle_dance(sorted_population(beeIndex,1:maxParameters),ngh(g)); % search the neighborhood around selected patch/solution within the radius of ngh
fit = evaluate_fitness(solution); % evaluate the fitness of recently found solution
if fit < sorted_population(beeIndex,maxParameters+1) % A minimization problem: if a better location/patch/solution is found by the recuiter bee
sorted_population(beeIndex,1 : maxParameters+1) = [solution(1 : maxParameters),fit]; % copy new solution and its fitness to the sorted population matrix
end
end
end
end
for i= 1 : group_random % For the remaining random bees
beeIndex = beeIndex + 1;
solution(beeIndex,1:maxParameters)= generate_random_solution(maxParameters,min, max); % generate a new random solution at the index beeIndex
solution(beeIndex,maxParameters+1)= evaluate_fitness(solution); % evaluate its fitness
sorted_population(beeIndex,:) = [solution(1 : maxParameters),fit]; % copy the new random solution and its fitness to the sorted population matrix
end
sorted_population=sortrows(sorted_population); % sort the population based on their fitnesses
Best_solution_sofar=sorted_population(1,:);
disp('Best:');disp(Best_solution_sofar); % Display the best solution of current iteration
end % end of GBA's main loop
end % end of main function
%% Function Bee Waggle Dance
function new_solution=bee_waggle_dance(solution, ngh, maxParameters)
new_solution(1:maxParameters) = (solution-ngh)+(2*ngh.*rand(1, maxParameters));
end
См. также [ править ]
- Алгоритмы оптимизации муравьиной колонии
- Алгоритм искусственной пчелиной семьи
- Эволюционные вычисления
- Гипотеза полета Леви о поиске пищи
- Производственный инженерный центр
- Математическая оптимизация
- Метаэвристический
- Оптимизация роя частиц
- Роевой интеллект
Ссылки [ править ]
- ^ Фам Д.Т., Ганбарзаде А., Коч Э., Отри С., Рахим С. и Заиди М. Алгоритм пчел. Техническое примечание, Центр производственного инжиниринга, Кардиффский университет, Великобритания, 2005 г.
- ↑ Перейти обратно: Перейти обратно: а б с Фам Д.Т., Кастеллани М. (2009), Алгоритм пчел – моделирование поведения при поиске пищи для решения задач непрерывной оптимизации . Учеб. ИмехЭ, Часть С, 223(12), 2919-2938.
- ^ Фам, Д.Т. и Кастеллани, М. (2013), Сравнительный анализ и сравнение вдохновленных природой алгоритмов непрерывной популяционной оптимизации , Soft Computing, 1-33.
- ^ Фам, Д.Т. и Кастеллани, М. (2015), Сравнительное исследование алгоритма пчел как инструмента оптимизации функций , Cogent Engineering 2 (1), 1091540.
- ↑ Перейти обратно: Перейти обратно: а б с Насринпур, Х.Р., Масса Бавани, А., Тешнехлаб, М. (2017), Алгоритм сгруппированных пчел: сгруппированная версия алгоритма пчел , Компьютеры 2017, 6(1), 5; ( doi : 10.3390/computers6010005 )
- ^ Баронти, Лука и Кастеллани, Марко и Фам, Д. (2020), Анализ поисковых механизмов алгоритма пчел. , Рой и эволюционные вычисления. 59. 100746. 10.1016/j.swevo.2020.100746
- ↑ Перейти обратно: Перейти обратно: а б с д Терешко В., Лоенгаров А., (2005) Коллективное принятие решений в динамике кормления медоносных пчел. Архивировано 1 февраля 2014 г. в Wayback Machine . Журнал вычислительных и информационных систем, 9 (3), 1-7.
- ^ Фон Фриш, К. (1967) Язык танца и ориентация пчел. Издательство Гарвардского университета, Кембридж, Массачусетс.
- ↑ Перейти обратно: Перейти обратно: а б Фам Д.Т., Ганбарзаде А., Коч Э., Отри С., Рахим С., Заиди М., Алгоритм пчел, новый инструмент для решения сложных задач оптимизации [ мертвая ссылка ] , Материалы 2-й Международной виртуальной конференции по интеллектуальным производственным машинам и системам (IPROMS 2006), Оксфорд: Elsevier, стр. 454-459, 2006.
- ^ Фам Д.Т., Хадж Дарвиш А., (2008), А. Нечеткий выбор локальных сайтов поиска в алгоритме пчел . Труды инновационных производственных машин и систем (ИПРОМС, 2008 г.)
- ^ Фам QT, Фам Д.Т., Кастеллани М., Модифицированный алгоритм пчел и статистический метод настройки его параметров. Труды Института инженеров-механиков (ImechE), Часть I: Журнал систем и управления Eng., 2011 ( дои : 10.1177/0959651811422759 )
Внешние ссылки [ править ]
- Сайт алгоритма пчел
- Боффинс заставил танцующих пчел работать – BBC News
- Мастер-класс по алгоритмам пчел
 | ||||