Algorytm pszczół - Bees algorithm

Nie mylić z algorytmem sztucznej kolonii pszczół .

W informatyce i Badań Operacyjnych The algorytm pszczoły jest populacyjne algorytm wyszukiwania , który został opracowany przez Pham, Ghanbarzadeh et al. w 2005 r. Naśladuje zachowanie żerowania rodzin pszczół miodnych. W swojej podstawowej wersji algorytm wykonuje rodzaj przeszukiwania sąsiedztwa w połączeniu z przeszukiwaniem globalnym i może być używany zarówno do optymalizacji kombinatorycznej, jak i do optymalizacji ciągłej . Jedynym warunkiem zastosowania algorytmu pszczół jest zdefiniowanie jakiejś miary odległości między roztworami. Skuteczność i specyficzne możliwości algorytmu pszczół zostały udowodnione w wielu badaniach.

Metafora

Kolonia pszczół miodnych może rozciągać się na duże odległości (ponad 14 km) iw wielu kierunkach jednocześnie, aby zbierać nektar lub pyłki z wielu źródeł pożywienia (grządki kwiatowe). Niewielka część kolonii nieustannie przeszukuje otoczenie w poszukiwaniu nowych płatów kwiatowych. Te pszczoły zwiadowcze poruszają się losowo po obszarze otaczającym ula, oceniając opłacalność (uzysk energii netto) napotkanych źródeł pożywienia. Kiedy wracają do ula, zwiadowcy zdeponują zebrane pożywienie. Osoby, które znalazły wysoce dochodowe źródło pożywienia, udają się do obszaru ula zwanego „parkietem tanecznym” i odprawiają rytuał zwany tańcem machania . Pszczoła zwiadowcza poprzez taniec machania przekazuje bezczynnym obserwatorom miejsce swojego odkrycia, które włącza się w eksploatację grządki kwiatowej. Ponieważ długość tańca jest proporcjonalna do oceny źródła pożywienia przez zwiadowcę, do zbierania najlepiej ocenianych grządek kwiatowych rekrutuje się więcej zbieraczy. Po tańcu zwiadowca wraca do odkrytego źródła pożywienia, aby zebrać więcej jedzenia. Dopóki zostaną ocenione jako dochodowe, bogate źródła pożywienia będą reklamowane przez zwiadowców po powrocie do ula. Zrekrutowani zbieracze również mogą machać tańcem, zwiększając rekrutację na wysoce satysfakcjonujące grządki kwiatowe. Dzięki temu autokatalitycznemu procesowi kolonia pszczół jest w stanie szybko skierować nacisk na żerowanie na najbardziej dochodowe obszary kwiatowe.

Algorytm

Algorytm pszczół naśladuje strategię żerowania pszczół miodnych w celu znalezienia najlepszego rozwiązania problemu optymalizacji. Każde rozwiązanie kandydujące jest traktowane jako źródło pożywienia (kwiat), a populacja (kolonia) n czynników (pszczół) jest wykorzystywana do przeszukiwania przestrzeni roztworu. Za każdym razem, gdy sztuczna pszczoła odwiedza kwiat (ląduje na roztworze), ocenia jego opłacalność (kondycję).

Algorytm pszczół składa się z procedury inicjalizacji i głównego cyklu poszukiwań, który jest powtarzany przez określoną liczbę T razy lub do momentu znalezienia rozwiązania o akceptowalnej przydatności. Każdy cykl wyszukiwania składa się z pięciu procedur: rekrutacja, wyszukiwanie lokalne, zmniejszanie sąsiedztwa, porzucanie witryn i wyszukiwanie globalne. 

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])}

W procedurze inicjalizacji ns pszczoły zwiadowcze są losowo umieszczane w przestrzeni poszukiwań i oceniają przydatność rozwiązań na miejscu, w którym wylądują. Dla każdego rozwiązania wyznaczone jest sąsiedztwo (zwane płatem kwiatowym).

W procedurze rekrutacyjnej harcerze, którzy odwiedzili nb ≤ ns najlepiej przystosowane rozwiązania (najlepsze miejsca), wykonują taniec wahadłowy. Oznacza to, że rekrutują zbieraczy do dalszego przeszukiwania okolic najbardziej obiecujących rozwiązań. Zwiadowcy, którzy zlokalizowali najlepsze rozwiązania ne ≤ nb (elitarne miejsca), rekrutują po nre zbieraczy, podczas gdy pozostali nb - ne zwiadowcy rekrutują po po nrb ≤ nre . Zatem liczba rekrutowanych zbieraczy zależy od opłacalności źródła pożywienia.

W procedurze poszukiwań lokalnych rekrutowane zbieracze są losowo rozrzucane w obrębie grządek kwiatowych obejmujących rozwiązania odwiedzane przez zwiadowców (eksploatacja lokalna). Jeśli któryś ze zbieraczy w grządce kwiatów znajdzie rozwiązanie o wyższej sprawności niż rozwiązanie odwiedzone przez zwiadowcę, ten zbieracz staje się nowym zwiadowcą. Jeśli żaden zbieracz nie znajdzie rozwiązania o wyższej sprawności, rozmiar płatu kwiatowego jest zmniejszany (procedura obkurczania okolicy). Zwykle płaty kwiatowe są początkowo definiowane na dużym obszarze, a ich wielkość jest stopniowo zmniejszana przez procedurę obkurczania okolicy. W rezultacie, zakres lokalnej eksploracji jest stopniowo skupiany na obszarze bezpośrednio zbliżonym do lokalnej najlepszej kondycji. Jeśli nie odnotuje się poprawy kondycji w danym gaju kwiatowym przez z góry ustaloną liczbę cykli wyszukiwania, uważa się, że lokalne maksimum sprawności zostało znalezione, łata zostaje porzucona (porzucenie strony) i losowo generowany jest nowy zwiad.

Podobnie jak w przypadku biologicznych kolonii pszczół, niewielka liczba zwiadowców nieustannie bada przestrzeń rozwiązań w poszukiwaniu nowych regionów o wysokiej sprawności (wyszukiwanie globalne). Procedura wyszukiwania globalnego ponownie inicjuje ostatnie łaty kwiatowe ns - nb z losowo wygenerowanymi rozwiązaniami.

Pod koniec jednego cyklu poszukiwań populacja harcerska ponownie składa się z ns scoutów: nr scoutów utworzonych przez lokalną procedurę wyszukiwania (z których część mogła zostać ponownie zainicjowana przez procedurę porzucenia lokalizacji) oraz ns - nb scoutów wygenerowanych przez globalna procedura wyszukiwania. Całkowity rozmiar kolonii sztucznych pszczół wynosi n = ne • nre + ( nb - ne ) • nrb + ns (elitarne zbieracze + pozostałe najlepsze miejsca zbierające + zwiadowcy) pszczoły.

Warianty

Oprócz podstawowego algorytmu pszczół istnieje szereg ulepszonych lub hybrydowych wersji BA, z których każda koncentruje się na pewnych niedociągnięciach podstawowego BA. Warianty te obejmują (ale nie są do nich ograniczone) rozmyte lub wzmocnione BA (EBA), zgrupowane BA (GBA), zmodyfikowane hybrydowo BA (MBA) i tak dalej. Pseudokod dla zgrupowanego BA (GBA) jest następujący. 

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

Zobacz też

Bibliografia

Linki zewnętrzne