Algorytm pszczół

Nie mylić z algorytmem sztucznej kolonii pszczół .

W informatyce i badaniach operacyjnych algorytm pszczół jest algorytmem wyszukiwania opartym na populacji , który został opracowany przez Pham, Ghanbarzadeh i in. w 2005 r. Naśladuje zachowanie kolonii pszczół miodnych w poszukiwaniu pożywienia. Algorytm w swojej podstawowej wersji wykonuje swego rodzaju przeszukiwanie sąsiedztwa połączone z przeszukiwaniem globalnym i może być stosowany zarówno do optymalizacji kombinatorycznej , jak i optymalizacji ciągłej . Jedynym warunkiem zastosowania algorytmu pszczół jest zdefiniowanie pewnej miary odległości między rozwiązaniami. Skuteczność i specyficzne możliwości algorytmu pszczół zostały udowodnione w wielu badaniach.

Metafora

Kolonia pszczół miodnych może rozprzestrzeniać się na duże odległości (ponad 14 km) iw wielu kierunkach jednocześnie, aby zbierać nektar lub pyłek z wielu źródeł pożywienia (grządki kwiatowe). Niewielka część kolonii nieustannie przeszukuje środowisko w poszukiwaniu nowych grządek kwiatowych. Te pszczoły zwiadowcze poruszają się losowo po obszarze otaczającym ul, oceniając opłacalność (wydajność energetyczną netto) napotkanych źródeł pożywienia. Po powrocie do ula zwiadowcy odkładają zebraną żywność. Osoby, które znalazły wysoce dochodowe źródło pożywienia, udają się do obszaru ula zwanego „parkietem tanecznym” i wykonują rytuał zwany tańcem machania . Poprzez taniec pszczoła zwiadowcza przekazuje miejsce swojego odkrycia bezczynnym obserwatorom, którzy przyłączają się do eksploatacji grządki kwiatowej. Ponieważ długość tańca jest proporcjonalna do oceny źródła pożywienia przez zwiadowcę, rekrutuje się więcej zbieraczy do zbierania najlepiej ocenianych grządek kwiatowych. Po tańcu zwiadowca wraca do znalezionego źródła pożywienia, aby zebrać więcej pożywienia. Tak długo, jak są oceniane jako opłacalne, bogate źródła pożywienia będą reklamowane przez zwiadowców po powrocie do ula. Zrekrutowani zbieracze mogą również tańczyć, zwiększając rekrutację do wysoko nagradzanych łat kwiatowych. Dzięki temu procesowi autokatalitycznemu rodzina pszczół jest w stanie szybko zmienić punkt ciężkości żerowania na najbardziej dochodowych grządkach kwiatowych.

Algorytm

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

Algorytm pszczół składa się z procedury inicjalizacji i głównego cyklu wyszukiwania, który jest powtarzany określoną liczbę T razy lub do momentu znalezienia rozwiązania o akceptowalnej sprawności. Każdy cykl wyszukiwania składa się z pięciu procedur: rekrutacji, wyszukiwania lokalnego, zmniejszania sąsiedztwa, porzucania lokalizacji i wyszukiwania globalnego. 

 Pseudokod standardowego algorytmu pszczół  1 dla i=1,…,ns i scout[i]=Initialise_scout() ii flower_patch[i]=Initialise_flower_patch(scout[i]) 2 wykonuj dopóki warunek_zatrzymania=TRUE i Recruitment() ii dla 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 dla i = nb,...,ns 1 kwiat_patch[i]=Globalne_wyszukiwanie(kwiaty_patch[i])}

W procedurze inicjalizacji pszczoły zwiadowcze ns są losowo umieszczane w przestrzeni poszukiwań i oceniają dopasowanie rozwiązań tam, gdzie wylądują. Dla każdego rozwiązania wyznaczane jest sąsiedztwo (zwane łatą kwiatową).

W procedurze rekrutacji zwiadowcy, którzy odwiedzili nb ≤ ns najodpowiedniejsze rozwiązania (najlepsze miejsca) wykonują taniec machania. Oznacza to, że rekrutują zbieraczy, aby przeszukiwać dalej okolice najbardziej obiecujących rozwiązań. Zwiadowcy, którzy zlokalizowali najlepsze ne ≤ nb (miejsca elitarne), rekrutują każdego zbieracza nre , podczas gdy pozostali zwiadowcy nb - ne rekrutują każdego zbieracza nrb ≤ nre . Zatem liczba rekrutowanych zbieraczy zależy od rentowności źródła pożywienia.

W procedurze poszukiwania lokalnego zwerbowani zbieracze są losowo rozproszeni w grządkach kwiatowych otaczających odwiedzane przez harcerzy roztwory (eksploatacja lokalna). Jeśli któryś z zbieraczy na grządce kwiatowej wyląduje na rozwiązaniu o wyższym stopniu przydatności niż rozwiązanie odwiedzone przez zwiadowcę, ten zbieracz zostaje nowym zwiadowcą. Jeśli żaden zbieracz nie znajdzie rozwiązania o większej przydatności, rozmiar grządki kwiatowej jest zmniejszany (procedura zmniejszania sąsiedztwa). Zwykle łaty kwiatowe są początkowo definiowane na dużym obszarze, a ich rozmiar jest stopniowo zmniejszany przez procedurę zmniejszania sąsiedztwa. W rezultacie zakres lokalnej eksploracji stopniowo koncentruje się na obszarze bezpośrednio zbliżonym do lokalnej najlepszej sprawności. Jeśli nie zostanie odnotowana poprawa sprawności w danej grządce kwiatowej przez określoną liczbę cykli poszukiwań, uważa się, że znaleziono lokalne maksimum sprawności, grządka zostaje porzucona (opuszczenie miejsca) i losowo generowany jest nowy zwiadowca.

Podobnie jak w biologicznych koloniach pszczół, niewielka liczba zwiadowców wciąż eksploruje przestrzeń rozwiązań w poszukiwaniu nowych regionów o wysokiej sprawności (wyszukiwanie globalne). Globalna procedura wyszukiwania ponownie inicjalizuje ostatnie ns - nb płatów kwiatowych z losowo generowanymi rozwiązaniami.

Pod koniec jednego cyklu poszukiwań populacja zwiadowców ponownie składa się z ns zwiadowców: nr zwiadowców utworzonych przez lokalną procedurę wyszukiwania (niektóre z nich mogły zostać ponownie zainicjowane przez procedurę opuszczania terenu) oraz ns - nb zwiadowców wygenerowanych przez globalną procedurę wyszukiwania. Całkowity rozmiar sztucznej kolonii pszczół wynosi n = ne • nre +( nb - ne ) • nrb + ns (elitarne miejsca zbierania + pozostałe najlepsze miejsca zbierania + zwiadowcy) pszczół.

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. 

 
 
  			
  			
   				
   				

 
  	            
  					
  			

 
         	
      		
  	
            	
    											
  
      			
       0
          					
    
	  	
	      				

    			
  0		

 
   	
 
      	
      					


   

 
          	
	  0				
	  			
		       	
			    		
			     	
				  			
				  															
				     
					      	
					
			
		
	

	     
		    
		   	
		 							
		     						
	
	
	 	
	
	
	 
 
 


 
       
 funkcja  GBA  %% Ustaw parametry problemu  maxIteration  =  ..;  % liczby iteracji (np. 1000-5000)  maxParameters  =  ..;  % liczba zmiennych wejściowych  min  =  [..]  ;  % tablica o rozmiarze maxParameters wskazująca minimalną wartość każdego parametru wejściowego  max  =  [..]  ;  % tablica o rozmiarze maxParameters wskazująca maksymalną wartość każdego parametru wejściowego  %% Ustaw parametry algorytmu grupowania pszczół (GBA)  R_ngh  =  ..;  % promień płata sąsiedztwa poszukiwań pszczół z pierwszej grupy (np. 0,001 - 1)  n  =  ..;  % liczby zwiadowców (np. 4-30)  nGrupy  =  ..;  % liczba grup, z wyłączeniem grupy losowej  %% automatyczne ustawienia parametrów GBA  k  =  3  *  n  /  ((  nGroups  +  1  )  ^  3  -  1  );  Parametr % GBA do ustawienia liczby pszczół zwiadowczych w każdej grupie groups  =  zera  (  1  ,  nGroups  )  ;  % Tablica do przechowywania liczby pszczół zwiadowczych dla każdej grupy  zrekrutowane_pszczoły  =  zera  (  1  ,  nGroups  );  % Tablica do przechowywania liczby rekrutowanych pszczół dla każdej grupy  a  =  (((  max  -  min  )  ./  2  )  -  R_ngh  )  ./  (  nGroups  ^  2  -  1  );  % Parametr GBA do ustawiania promieni sąsiedztwa  b  =  R_ngh  -  a  ;  % Parametr GBA do ustawiania promieni sąsiedztwa  dla  i  =  1  :  nGroups  % Dla każdej grupy groups  (  i  )  =  floor  (  k  *  i  ^  2  )  ;  % określ liczbę pszczół zwiadowczych w każdej grupie,  jeśli  grupy  (  i  )  ==  grupy  (  i  )  =  1  ;  % musi być co najmniej jedna pszczoła zwiadowcza na każdą grupę  end  rekruted_bees  =  (  nGroups  +  1  -  i  )  ^  2  ;  % ustaw liczbę rekrutowanych pszczół dla każdej grupy  ngh  (  i  )  =  a  *  i  *  i  +  b  ;  % ustawia promień poprawki dla każdej grupy  end  group_random  =  n  -  sum  (  groups  );  % przypisz pozostałe pszczoły (jeśli istnieją) do losowego wyszukiwania  group_random  =  max  (  group_random  ,  );  % upewnij się, że nie jest to liczba ujemna  %% zainicjuj macierz populacji  populacja  =  zera  (  n  ,  maxParameters  +  1  );  % Populacja n pszczół, w tym wszystkie zmienne wejściowe i ich dopasowanie  do  i  =  1  :  n  populacji  (  i  ,  1  :  maxParameters  )=  generowanie_losowego_rozwiązania  (  maxParameters  ,  min  ,  max  );  % losowej inicjalizacji zmiennych maxParameters pomiędzy max i min  populacja  (  i  ,  maxParameters  +  1  )  =  evalulate_fitness  (  populacja  (  i  ,:));  % ocena przydatności każdego rozwiązania i zapisanie jej pod ostatnim indeksem macierzy populacji  end  sorted_population  =  sortrows  (  populacja  );  % sortuje populację na podstawie jej sprawności  %% Iteracje algorytmu pogrupowanych pszczół  dla  i  =  1  :  maxIteration  % Główna pętla GBA  beeIndex  =  ;  % śledź wszystkie pszczoły (tj. łatki)  dla  g  =  1  :  nGrupy  % dla każdej grupy pszczół zwiadowczych  dla  j  =  1  :  grupy  (  g  )  % wykorzystują każdy łat w każdej grupie  beeIndex  =  beeIndex  +  1  ;  % zwiększ licznik na każdą łatę  dla  i  =  1  :  zrekrutowane_pszczoły  (  g  )  % dla każdej zrekrutowanej pszczoły z grupy  rozwiązanie  =  bee_waggle_dance  (  sorted_population  (  beeIndex  ,  1  :  maxParameters  ),  ngh  (  g  ));  % szukaj okolicy wokół wybranej poprawki/rozwiązania w promieniu ngh  fit  =  ewaluacja_fitness  (  rozwiązanie  );  % ocenia przydatność ostatnio znalezionego rozwiązania  , jeśli  pasuje  <  sorted_population  (  beeIndex  ,  maxParameters  +  1  )  % Problem minimalizacji: jeśli rekruter znajdzie lepszą lokalizację/poprawkę/rozwiązanie bee  sorted_population  (  beeIndex  ,  1  :  maxParameters  +  1  )  =  [  rozwiązanie  (  1  :  maxParameters  ),  dopasowanie  ];  % kopiowania nowego rozwiązania i jego dopasowania do posortowanej macierzy populacji  koniec  koniec  koniec  koniec  dla  i  =  1  :  group_random  % Dla pozostałych losowych pszczół  beeIndex  =  beeIndex  +  1  ;  rozwiązanie  (  beeIndex  ,  1  :  maxParameters  ) =  wygeneruj losowe_rozwiązanie  (  maxParameters  ,  min  ,  max  );  % generuje nowe losowe rozwiązanie w indeksie  rozwiązanie beeIndex   (  beeIndex  ,  maxParameters  +  1  )=  ocena_fitness  (  rozwiązanie  );  % ocenia jego przydatność  sorted_population  (  beeIndex  ,:)  =  [  rozwiązanie  (  1  :  maxParameters  ),  fit  ];  % kopiuje nowe rozwiązanie losowe i jego dopasowanie do macierzy populacji posortowanej  end  sorted_population  =  sortrows  (  sorted_population  );  % sortuje populację na podstawie jej sprawności  Best_solution_sofar  =  sorted_population  (  1  ,:);  disp  (  'Najlepszy:'  );  disp  (  Najlepsze_rozwiązanie_daleko  );  % Wyświetl najlepsze rozwiązanie bieżącej iteracji  koniec  % koniec pętli głównej GBA koniec  %  koniec funkcji main  %% Funkcja Bee Waggle Dance  function  new_solution  =  bee_waggle_dance  (  solution, ngh, maxParameters  )  new_solution  (  1  :  maxParameters  )  =  (  rozwiązanie  -  ngh  )  +  (  2  *  ngh  .*  Rand  (  1  ,  maxParameters  ));  koniec

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Bees_algorithm&oldid=1098932820 ”