Algoritmus včel - Bees algorithm

Nesmí být zaměňována s algoritmem umělých včelstev .

V počítačové vědě a operačním výzkumu je včelí algoritmus populační vyhledávací algoritmus, který vyvinuli Pham, Ghanbarzadeh et al. v roce 2005. Napodobuje potravní chování včelstev. V základní verzi algoritmus provádí druh vyhledávání v sousedství kombinovaný s globálním vyhledáváním a lze jej použít jak pro kombinatorickou optimalizaci, tak pro kontinuální optimalizaci . Jedinou podmínkou pro použití algoritmu včel je, že je definována určitá míra vzdálenosti mezi řešeními. Účinnost a specifické schopnosti algoritmu včel byly prokázány v řadě studií.

Metafora

Kolonie včel se může rozšířit na velké vzdálenosti (přes 14 km) a současně do několika směrů a sklízet nektar nebo pyl z různých zdrojů potravy (květinové skvrny). Malá část kolonie neustále hledá prostředí a hledá nové květinové skvrny. Tyto průzkumné včely se náhodně pohybují v oblasti obklopující úl a vyhodnocují ziskovost (čistý energetický výnos) nalezených zdrojů potravy. Když se vrátili do úlu, skauti uložili sklizené jídlo. Ti jedinci, kteří našli vysoce ziskový zdroj potravy, jdou do oblasti v úlu zvané „taneční parket“ a provádějí rituál známý jako kývavý tanec . Prostřednictvím kývavého tance skautská včela sděluje místo svého objevu nečinným divákům, kteří se připojí k využívání květinové náplasti. Vzhledem k tomu, že délka tance je úměrná skautovu hodnocení zdroje potravy, získává se více sekáčů, kteří sklízejí nejlépe hodnocené květinové skvrny. Po tanci se zvěd vrací ke zdroji potravy, který objevil, aby nasbíral více jídla. Dokud budou skauti po návratu do úlu vyhodnoteni jako ziskové, budou po nich potravinové zdroje bohaté reklamy inzerovat. Náboroví sběrači mohou také kývat tancem, což zvyšuje nábor vysoce hodnotných květinových záplat. Díky tomuto autokatalytickému procesu je včelstvo schopné rychle změnit zaměření úsilí při hledání potravy na nejziskovější květinové skvrny.

Algoritmus

Algoritmus včel napodobuje strategii shánění potravy včel, aby hledal nejlepší řešení problému optimalizace. Každé kandidátské řešení je považováno za zdroj potravy (květina) a k prohledání prostoru řešení se používá populace (kolonie) n agentů (včel). Pokaždé, když umělá včela navštíví květinu (přistane na řešení), vyhodnotí její ziskovost (vhodnost).

Algoritmus včel sestává z inicializačního postupu a hlavního vyhledávacího cyklu, který je iterován pro daný počet T krát, nebo dokud není nalezeno řešení přijatelné vhodnosti. Každý vyhledávací cyklus se skládá z pěti postupů: nábor, místní vyhledávání, zmenšování sousedství, opuštění stránek a globální vyhledávání. 

Pseudocode for the standard bees algorithm
   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])}

V inicializace rutinní ns vyhledávaly včely se náhodně umístí do vyhledávacího prostoru a zhodnotit vhodnost řešení, kde přistát. U každého řešení je ohraničeno sousedství (tzv. Květinová záplata).

V náborovém řízení skauti, kteří navštívili nb ≤ ns nejvhodnější řešení (nejlepší stránky), provádějí kývavý tanec. To znamená, že přijímají pracovníky, kteří hledají další sousedství nejslibnějších řešení. Zvědové která leží ty nejlepší ne ≤ nb řešení (elitní památky) rekrutovat NRE pohonem každý, zatímco zbývající nb - ne zvědi rekrutovat NRB ≤ NRE pohonem každý. Počet přijímaných sekaček tedy závisí na ziskovosti zdroje potravy.

Při postupu místního hledání jsou rekrutovaní sekačky náhodně rozptýleni v květinových záplatách obklopujících řešení navštívená skauty (místní vykořisťování). Pokud některý z řezačů v květináči přistane na řešení s vyšší kondicí, než jaké navštívil průzkumník, stane se z tohoto hledače novým zvědem. Pokud žádný forager nenajde řešení s vyšší kondicí, zmenší se velikost květinové náplasti (postup zmenšování okolí). Obvykle jsou květinové skvrny původně definovány na velké ploše a jejich velikost se postupně zmenšuje postupem zmenšování okolí. Výsledkem je, že rozsah místního průzkumu se postupně zaměřuje na oblast bezprostředně blízkou místním nejlepším fitness. Pokud v dané květinové záplatě není zaznamenáno žádné zlepšení kondice pro přednastavený počet vyhledávacích cyklů, považuje se místní maximum kondice za nalezené, oprava je opuštěna (opuštění stránky) a náhodně je vygenerován nový skaut.

Stejně jako v biologických včelstvech stále malý počet skautů prozkoumává prostor řešení a hledá nové oblasti s vysokou kondicí (globální vyhledávání). Postup globálního vyhledávání znovu inicializuje poslední květinové skvrny ns - nb s náhodně generovanými řešeními.

Na konci jednoho vyhledávacího cyklu je populace skautů opět složena z ns skautů: nr skauti vyprodukovaní procedurou lokálního vyhledávání (někteří z nich mohli být znovu inicializováni procedurou opuštění stránky) a ns - nb skauti vygenerovaní postup globálního vyhledávání. Celková velikost umělých včelstev je n = ne • nre + ( nb - ne ) • nrb + ns (elitní stanoviště pro sběrače + zbývající nejlepší stanoviště pro sběrače + zvědy) včely.

Varianty

Kromě základního včelího algoritmu existuje řada vylepšených nebo hybridních verzí BA, z nichž každá se zaměřuje na některé nedostatky základní BA. Tyto varianty zahrnují (ale nejsou omezeny na) fuzzy nebo vylepšenou BA (EBA), skupinovou BA (GBA), hybridní modifikovanou BA (MBA) atd. Pseudokód pro seskupenou BA (GBA) je následující. 

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

Viz také

Reference

externí odkazy