Algoritmo delle api - Bees algorithm

In informatica e ricerca operativa , l' algoritmo di api è un basato sulla popolazione algoritmo di ricerca che è stato sviluppato da Pham, Ghanbarzadeh et al. nel 2005. Imita il comportamento di foraggiamento alimentare delle colonie di api mellifere. Nella sua versione base l'algoritmo esegue un tipo di ricerca quartiere combinato con la ricerca globale, e può essere utilizzato sia per l'ottimizzazione combinatoria e ottimizzazione continua . L'unica condizione per l'applicazione dell'algoritmo delle api è che sia definita una certa misura di distanza tra le soluzioni. L'efficacia e le capacità specifiche dell'algoritmo delle api sono state dimostrate in numerosi studi.

Metafora

Una colonia di api da miele può estendersi su lunghe distanze (oltre 14 km) e in più direzioni contemporaneamente per raccogliere nettare o polline da più fonti di cibo (macchie di fiori). Una piccola frazione della colonia cerca costantemente nell'ambiente alla ricerca di nuovi appezzamenti floreali. Queste api esploratrici si muovono casualmente nell'area circostante l'alveare, valutando la redditività (resa energetica netta) delle fonti alimentari incontrate. Quando tornano all'alveare, gli esploratori depositano il cibo raccolto. Quelle persone che hanno trovato una fonte di cibo altamente redditizia si recano in un'area nell'alveare chiamata "pista da ballo", ed eseguono un rituale noto come danza agitata . Attraverso la danza delle scodinzolanti un'ape scout comunica il luogo della sua scoperta a spettatori oziosi, che partecipano allo sfruttamento del campo fiorito. Poiché la lunghezza della danza è proporzionale alla valutazione della fonte di cibo da parte dello scout, vengono reclutati più raccoglitori per raccogliere le macchie di fiori più votate. Dopo aver ballato, l'esploratore torna alla fonte di cibo che ha scoperto per raccogliere altro cibo. Finché saranno valutate come redditizie, le ricche fonti di cibo saranno pubblicizzate dagli scout quando torneranno all'alveare. I raccoglitori reclutati possono anche danzare, aumentando il reclutamento per appezzamenti di fiori altamente gratificanti. Grazie a questo processo autocatalitico, la colonia di api è in grado di spostare rapidamente l'attenzione dello sforzo di foraggiamento sulle macchie di fiori più redditizie.

Algoritmo

L'algoritmo delle api imita la strategia di foraggiamento delle api mellifere per cercare la migliore soluzione a un problema di ottimizzazione. Ogni soluzione candidata è pensata come una fonte di cibo (fiore) e una popolazione (colonia) di n agenti (api) viene utilizzata per cercare lo spazio della soluzione. Ogni volta che un'ape artificiale visita un fiore (atterra su una soluzione), ne valuta la redditività (fitness).

L'algoritmo delle api consiste in una procedura di inizializzazione e un ciclo di ricerca principale che viene iterato per un dato numero T di volte, o fino a quando non viene trovata una soluzione di idoneità accettabile. Ogni ciclo di ricerca è composto da cinque procedure: reclutamento, ricerca locale, riduzione del vicinato, abbandono del sito e ricerca globale.

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

Nella inizializzazione di routine ns esploratore api sono collocati in modo casuale nello spazio di ricerca, e valutare l'idoneità delle soluzioni dove si terra. Per ogni soluzione, viene delimitato un vicinato (chiamato fiore patch).

Nella procedura di reclutamento, gli scout che hanno visitato le soluzioni nb ≤ ns più adatte (i migliori siti) eseguono la danza del waggle. Cioè, reclutano raccoglitori per cercare ulteriormente nei quartieri le soluzioni più promettenti. Gli scout che trova le migliori ne ≤ nb soluzioni (siti d'elite) recluta NRE raccoglitori ciascuno, mentre il restante nb - ne scout reclutare NRB ≤ nre raccoglitori ciascuno. Pertanto, il numero di raccoglitori reclutati dipende dalla redditività della fonte di cibo.

Nella procedura di ricerca locale, i raccoglitori reclutati vengono sparsi in modo casuale all'interno delle macchie di fiori che racchiudono le soluzioni visitate dagli scout (sfruttamento locale). Se uno qualsiasi dei raccoglitori in un appezzamento di fiori atterra su una soluzione di fitness superiore alla soluzione visitata dallo scout, quel raccoglitore diventa il nuovo esploratore. Se nessun raccoglitore trova una soluzione di maggiore fitness, la dimensione del fiore si riduce (procedura di restringimento del vicinato). Di solito, le macchie di fiori sono inizialmente definite su una vasta area e le loro dimensioni vengono gradualmente ridotte dalla procedura di restringimento del vicinato. Di conseguenza, l'ambito dell'esplorazione locale è progressivamente focalizzato sull'area immediatamente prossima alla migliore forma fisica locale. Se nessun miglioramento della forma fisica viene registrato in un dato cerotto floreale per un numero predefinito di cicli di ricerca, il massimo locale di idoneità viene considerato trovato, il cerotto viene abbandonato (abbandono del sito) e viene generato un nuovo scout in modo casuale.

Come nelle colonie di api biologiche, un piccolo numero di scout continua a esplorare lo spazio delle soluzioni alla ricerca di nuove regioni di alta idoneità (ricerca globale). La procedura di ricerca globale reinizializza le ultime patch di fiori ns - nb con soluzioni generate casualmente.

Alla fine di un ciclo di ricerca, la popolazione scout è nuovamente composta da ns scout: nr scout prodotti dalla procedura di ricerca locale (alcuni dei quali potrebbero essere stati reinizializzati dalla procedura di abbandono del sito), e ns - nb scout generati da la procedura di ricerca globale. La dimensione totale della colonia artificiale di api è n = ne • nre + ( nb - ne ) • nrb + ns (siti d'élite raccoglitori + rimanenti migliori siti raccoglitori + esploratori) api.

Varianti

Oltre all'algoritmo di base delle api, ci sono un certo numero di versioni migliorate o ibride del BA, ognuna delle quali si concentra su alcune carenze del BA di base. Queste varianti includono (ma non sono limitate a) BA fuzzy o migliorato (EBA), BA raggruppato (GBA), BA ibrido modificato (MBA) e così via. Lo pseudo codice per il raggruppamento BA (GBA) è il seguente.

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

Guarda anche

• Algoritmi di ottimizzazione delle colonie di formiche
• Algoritmo di colonie di api artificiali
• Calcolo evolutivo
• Ipotesi di foraggiamento del volo di Lévy
• Centro di ingegneria di produzione
• Ottimizzazione matematica
• Metaeuristico
• Ottimizzazione dello sciame di particelle
• Intelligenza sciame

Riferimenti

link esterno

• Il sito web dell'algoritmo delle api
• Boffins mettono al lavoro le api danzanti - BBC News