Algorytm sztucznej kolonii pszczół - Artificial bee colony algorithm

W informatyce i badań operacyjnych , algorytm sztucznej pszczela ( ABC ) jest algorytmem optymalizacji w oparciu o inteligentne zachowanie żerowania z roju pszczół, proponowanego przez Dervişem Karaboğa ( Erciyes University ) w 2005 roku.

Algorytm

W modelu XYZ kolonia składa się z trzech grup pszczół: pszczół pracujących, gapiów i harcerzy. Zakłada się, że na każde źródło pożywienia przypada tylko jedna sztuczna pszczoła. Innymi słowy, liczba zatrudnionych pszczół w kolonii jest równa liczbie źródeł pożywienia wokół ula. Zatrudnione pszczoły udają się do źródła pożywienia, wracają do ula i tańczą na tym terenie. Zatrudniona pszczoła, której zrezygnowano z pożywienia, zostaje zwiadowcą i zaczyna szukać nowego źródła pożywienia. Widzowie obserwują tańce zatrudnionych pszczół i dobierają źródła pożywienia w zależności od tańców. Główne kroki algorytmu podano poniżej:

• Początkowe źródła pożywienia są produkowane dla wszystkich zatrudnionych pszczół
• POWTARZAĆ
  • Każda zatrudniona pszczoła trafia do źródła pożywienia w swojej pamięci i określa najbliższe źródło, następnie ocenia ilość nektaru i tańczy w ulu
  • Każdy obserwator obserwuje taniec zatrudnionych pszczół i w zależności od tańców wybiera jedno z ich źródeł, a następnie udaje się do tego źródła. Po wybraniu wokół tego sąsiada ocenia ilość nektaru.
  • Porzucone źródła pożywienia są określane i zastępowane nowymi źródłami pożywienia odkrytymi przez zwiadowców.
  • Zarejestrowano najlepsze znalezione do tej pory źródło pożywienia.
• DO TYLKO (wymagania są spełnione)

W ABC, algorytmie opartym na populacji, pozycja źródła pożywienia reprezentuje możliwe rozwiązanie problemu optymalizacji, a ilość nektaru źródła pożywienia odpowiada jakości (przydatności) skojarzonego rozwiązania. Liczba zatrudnionych pszczół jest równa liczbie roztworów w populacji. W pierwszym kroku generowana jest losowo rozłożona populacja początkowa (pozycje źródeł żywności). Po inicjalizacji populacja poddawana jest powtarzaniu cykli procesów poszukiwawczych odpowiednio pszczół zatrudnionych, gapiów i harcerek. Zatrudniona pszczoła dokonuje w swojej pamięci modyfikacji pozycji źródła i odkrywa nową pozycję źródła pożywienia. Pod warunkiem, że ilość nektaru nowego jest wyższa niż poprzedniego źródła, pszczoła zapamiętuje nową pozycję źródła i zapomina stare. W przeciwnym razie zachowuje w pamięci pozycję tego. Po tym, jak wszystkie zatrudnione pszczoły ukończą proces wyszukiwania, dzielą się informacjami o pozycji źródeł z obserwatorami na obszarze tańca. Każdy obserwator ocenia informacje o nektarze pobrane od wszystkich zatrudnionych pszczół, a następnie wybiera źródło pożywienia w zależności od ilości źródeł nektaru. Podobnie jak w przypadku zatrudnionej pszczoły, dokonuje modyfikacji pozycji źródłowej w swojej pamięci i sprawdza ilość jej nektaru. Zakładając, że jej nektar jest wyższy niż poprzedniego, pszczoła zapamiętuje nową pozycję i zapomina starą. Porzucone źródła są ustalane i losowo produkowane są nowe źródła, które sztuczni zwiadowcy zastępują tymi porzuconymi.

Algorytm sztucznej kolonii pszczół

Algorytm sztucznej kolonii pszczół (ABC) to technika optymalizacji, która symuluje zachowanie żerowania pszczół miodnych i została z powodzeniem zastosowana do różnych problemów praktycznych. ABC należy do grupy algorytmów inteligencji roju i zostało zaproponowane przez Karabogę w 2005 roku.

Zbiór pszczół miodnych, zwany rójką, może z powodzeniem realizować zadania poprzez współpracę społeczną. W algorytmie ABC istnieją trzy rodzaje pszczół: pszczoły pracujące, pszczoły gapiów i pszczoły harcerskie. Zatrudnione pszczoły szukają w pamięci pożywienia wokół źródła pożywienia; w międzyczasie dzielą się informacjami o tych źródłach pokarmu z obserwującymi pszczoły. Pszczoły obserwujące mają tendencję do wybierania dobrych źródeł pożywienia spośród tych znalezionych przez zatrudnione pszczoły. Źródło pożywienia o wyższej jakości (fitness) będzie miało dużą szansę na wybór przez widza pszczoły niż to o niższej jakości. Pszczoły harcerskie są tłumaczone z kilku zatrudnionych pszczół, które porzucają swoje źródła pożywienia i szukają nowych.

W algorytmie ABC pierwsza połowa roju składa się z pszczół zatrudnionych, a druga połowa to pszczoły obserwacyjne.

Liczba zatrudnionych pszczół lub pszczół gapiów jest równa liczbie roztworów w roju. ABC generuje losowo rozłożoną początkową populację roztworów SN (źródła pożywienia), gdzie SN oznacza wielkość roju.

Niech stanowią rozwiązanie w roju, gdzie jest wielkość wymiar. ${\ Displaystyle X_ {i} = \ {x_ {i, 1}, x_ {i, 2}, \ ldots, x_ {i, n} \}}$${\ Displaystyle i ^ {th}}$${\ Displaystyle n}$

Każda zatrudniona pszczoła generuje nowe rozwiązanie kandydujące w sąsiedztwie swojej obecnej pozycji, zgodnie z poniższym równaniem: ${\ Displaystyle X_ {i}}$${\ Displaystyle V_ {i}}$

${\ Displaystyle V_ {i, k} = x_ {i, k} + \ Phi _ {i, k} \ razy (x_ {i, k} -x_ {j, k})}$

gdzie jest losowo wybranym rozwiązaniem kandydującym ( ), jest losowym indeksem wymiaru wybranego ze zbioru i jest liczbą losową w obrębie . Po wygenerowaniu nowego kandydata na rozwiązanie następuje selekcja zachłanna. Jeśli wartość dopasowania jest lepsza niż jego rodzica , zaktualizuj za pomocą ; w przeciwnym razie pozostaw bez zmian. Po zakończeniu poszukiwań przez wszystkie zatrudnione pszczoły; dzielą się informacjami o swoich źródłach pożywienia z widzami pszczół poprzez tańce machania. Pszczoła obserwatora ocenia informacje o nektarze pobrane od wszystkich zatrudnionych pszczół i wybiera źródło pożywienia z prawdopodobieństwem związanym z ilością nektaru. Ten probabilistyczny wybór jest tak naprawdę mechanizmem wyboru koła ruletki, który jest opisany jako równanie poniżej: ${\ Displaystyle X_ {j}}$${\displaystyle i\neqj}$${\displaystyle k}$${\displaystyle \{1,2,\ldots,n\}}$${\ Displaystyle \ Phi _ {i, k}}$${\displaystyle [-1,1]}$${\ Displaystyle V_ {i}}$${\ Displaystyle V_ {i}}$${\ Displaystyle X_ {i}}$${\ Displaystyle X_ {i}}$${\ Displaystyle V_ {i}}$${\ Displaystyle X_ {i}}$

${\ Displaystyle P_ {i} = {\ Frac {\ operatorname {dopasowanie} _ {i}}{\ suma _ {j}{\ operatorname {dopasowanie} _ {j}}}}}$

gdzie jest wartość sprawności rozwiązania w roju. Jak widać, im lepsze rozwiązanie , tym większe prawdopodobieństwo wyboru źródła pożywienia. Jeśli pozycja nie może zostać poprawiona powyżej określonej liczby (zwanej limitem) cykli, wówczas źródło pożywienia jest porzucane. Załóżmy, że porzuconym źródłem jest , a następnie pszczoła zwiadowcza odkrywa nowe źródło pożywienia, które należy zastąpić, zgodnie z poniższym równaniem: ${\ Displaystyle \ operatorname {dopasowanie} _ {i}}$${\ Displaystyle i ^ {th}}$${\displaystyle i}$${\ Displaystyle i ^ {th}}$${\ Displaystyle X_ {i}}$${\ Displaystyle i ^ {th}}$

${\ Displaystyle x_ {i, k} = lb_ {k} + \ Phi _ {i, k} \ razy (ub_ {k}-lb_ {k})}$

gdzie jest liczbą losową w oparciu o rozkład normalny i są odpowiednio dolną i górną granicą wymiaru. ${\ Displaystyle \ Phi _ {i, k} = \ operatorname {rand} (0,1)}$${\displaystyle [0,1]}$${\displaystyle lb_{k},ub_{k}}$${\ Displaystyle k ^ {th}}$

Zobacz też

• Obliczenia ewolucyjne
• Ewolucyjna optymalizacja multimodalna
• Optymalizacja roju cząstek
• Inteligencja roju
• Algorytm pszczół
• Wyszukiwanie szkół ryb
• Lista metaheurystyk opartych na metaforach

Bibliografia

Zewnętrzne linki

• Strona główna algorytmu sztucznej kolonii pszczół (ABC) , Turcja: Intelligent Systems Research Group, Wydział Inżynierii Komputerowej, Uniwersytet Erciyes