Mehiläisten algoritmi - Bees algorithm

Ei pidä sekoittaa keinotekoisen mehiläispesäkkeen algoritmiin .

Vuonna tietotekniikassa ja Operations Research , The mehiläiset algoritmi on väestöpohjainen etsintäalgoritmilla joka oli kehitetty Pham, Ghanbarzadeh ym. vuonna 2005. Se jäljittelee mehiläispesien ruokailukäyttäytymistä. Perusversiossaan algoritmi suorittaa eräänlaisen naapuruston haun yhdistettynä globaaliin hakuun, ja sitä voidaan käyttää sekä kombinatoriseen että jatkuvaan optimointiin . Mehiläisten algoritmin soveltamisen ainoa ehto on, että määritetään jonkin verran ratkaisujen välistä etäisyyttä. Mehiläisten algoritmin tehokkuus ja erityiset kyvyt on osoitettu useissa tutkimuksissa.

Metafora

Siirtokunta mehiläisille voi ulottua itse pitkiäkin matkoja (yli 14 km) ja eri suuntiin samanaikaisesti sato nektaria ja siitepölyä useista elintarvikkeiden lähteistä (kukka laastaria). Pieni osa siirtokunnasta etsii jatkuvasti ympäristöä etsimällä uusia kukka-laastareita. Nämä partiolaiset mehiläiset liikkuvat satunnaisesti pesää ympäröivällä alueella arvioimalla havaittujen ruokalähteiden kannattavuuden (nettoenergiantuotto). Palattuaan pesään partiolaiset tallettavat korjatun ruoan. Ne ihmiset, jotka löysivät erittäin kannattavan ruokalähteen, menevät pesän alueelle, jota kutsutaan "tanssilattiaksi", ja suorittavat rituaalin, joka tunnetaan heilutustanssina . Heilutustanssin kautta partiolaiset mehiläiset ilmoittavat löytösijaintinsa tyhjäkäynnille katsojille, jotka osallistuvat kukka-laastarin hyväksikäyttöön. Koska tanssin pituus on verrannollinen partiolaisen antamaan arvioon ravinnonlähteestä, yhä useammat rehunvalmistajat rekrytoidaan keräämään parhaiten mitoitettuja kukka-laastareita. Tanssin jälkeen partiolainen palaa löytämänsä ruokalähteen keräämään lisää ruokaa. Niin kauan kuin ne arvioidaan kannattaviksi, partiolaiset mainostavat runsaita ruokalähteitä, kun he palaavat pesään. Rekrytoidut silppurit voivat myös heiluttaa tanssia, mikä lisää rekrytointia erittäin palkitseville kukka-laastareille. Tämän autokatalyyttisen prosessin ansiosta mehiläispesä kykenee nopeasti siirtämään ruokailutoiminnan painopisteen kannattavimmille kukka-laastareille.

Algoritmi

Mehiläisten algoritmi jäljittelee hunajamehiläisten ruokintastrategiaa etsimään parasta ratkaisua optimointiongelmaan. Jokaista ehdokasratkaisua pidetään ruokalähteenä (kukka), ja n aineen (mehiläisten) populaatiota (siirtomaa) käytetään etsimään ratkaisutilaa. Joka kerta kun keinotekoinen mehiläinen vierailee kukassa (laskeutuu ratkaisuun), se arvioi sen kannattavuuden (kunto).

Mehiläisten algoritmi koostuu alustamisprosessista ja päähakukierroksesta, joka toistetaan tietylle lukumäärälle T kertaa tai kunnes löydetään hyväksyttävän kuntoinen ratkaisu. Jokainen hakusykli koostuu viidestä menettelystä: rekrytointi, paikallinen haku, naapuruston kutistuminen, sivuston hylkääminen ja globaali haku. 

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

Alustamisrutiinissa ns partiolaiset mehiläiset sijoitetaan satunnaisesti hakutilaan ja arvioivat ratkaisujen kunto laskeutuessaan. Kullekin ratkaisulle rajataan naapurusto (kutsutaan kukka-laastariksi).

Rekrytointimenettelyssä partiolaiset, jotka vierailivat nb ≤ ns sopivimmissa ratkaisuissa (parhaat paikat), suorittavat heilutustanssin. Toisin sanoen he rekrytoivat rehunhakijoita etsimään edelleen lupaavimpien ratkaisujen lähialueita. Partiolaiset että paikalla parasta ne ≤ NB ratkaisut (eliitin sivustoja) rekrytoida NRE silppurit jokaisen, ja loput NB - NE partiolaiset rekrytoida NRB ≤ NRE silppurit kukin. Rekrytoitujen rehulaitosten määrä riippuu siis elintarvikelähteen kannattavuudesta.

Paikallisessa hakuprosessissa rekrytoidut silppurit hajautetaan satunnaisesti kukka-laastareihin, jotka sulkevat partiolaisten vierailemat ratkaisut (paikallinen hyväksikäyttö). Jos joku kukkarapun saalistajista laskeutuu parempikuntoiseen ratkaisuun kuin partiolaisen vierailema ratkaisu, tästä takomosta tulee uusi partiolainen. Jos mikään rehunhakija ei löydä ratkaisua korkeammalle kuntoon, kukkarapun koko pienenee (naapuruston kutistuminen). Yleensä kukka-laastarit määritellään aluksi suurelle alueelle, ja niiden koko kutistuu vähitellen naapuruston kutistumismenettelyllä. Tämän seurauksena paikallisen etsinnän laajuus keskittyy asteittain alueelle, joka on välittömästi lähellä paikallista kuntoa. Jos tietyssä kukka-laastarissa kuntoa ei ole kirjattu ennalta määrätyn määrän hakuja varten, paikallisen kuntoilmoituksen katsotaan löytyvän, laastari hylätään (sivuston hylkääminen) ja uusi partiolainen luodaan satunnaisesti.

Kuten biologisissa mehiläispesäkkeissä, pieni joukko partiolaisia ​​jatkaa tutkimustyötä ratkaisutilassa etsimään uusia korkealaatuisia alueita (globaali haku). Globaali hakumenettely alustaa viimeiset ns - nb kukka-laastarit satunnaisesti tuotetuilla ratkaisuilla.

Yhden hakusyklin lopussa partiopopulaatio koostuu jälleen ns- partiolaisista: paikallisella hakuprosessilla tuotetuista nr- partiolaisista (joista osa on saattanut olla alustettu uudelleen sivuston hylkäysmenettelyllä) ja ns - nb- partiolaisista, jotka yleinen hakumenettely. Mehiläispesien keinotekoinen koko on n = ne • nre + ( nb - ne ) • nrb + ns (eliittisivustojen rehunvalmistajat + jäljellä olevat parhaat paikanrehut + partiolaiset) mehiläiset.

Vaihtoehdot

Mehiläisten perusalgoritmin lisäksi on olemassa useita parannettuja tai hybridiversioita BA: sta, joista jokainen keskittyy joihinkin perus BA: n puutteisiin. Näitä muunnelmia ovat (mutta eivät rajoitu niihin) sumea tai tehostettu BA (EBA), ryhmitelty BA (GBA), hybridimodifioitu BA (MBA) ja niin edelleen. Ryhmätyn BA: n (GBA) näennäinen koodi on seuraava. 

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

Katso myös

Viitteet

Ulkoiset linkit