Algorytm Optymalizacji Wilków Szarych — GWO
- Autor metody
- Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
- Rok
- 2014
- Typ
- Swarm-intelligence metaheuristic
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm Optymalizacji Wilków Szarych (GWO) to metaheurystyka typu inteligencji roju, wprowadzona przez Mirjaliliego, Mirjaliliego i Lewisa w 2014 roku, która modeluje hierarchię społeczną i kooperacyjne zachowania łowieckie wilków szarych.
Populacja rozwiązań kandydujących jest dzielona na cztery rangi przywództwa — alfa, beta, delta i omega — a trzy najlepsze rozwiązania w każdej iteracji kierują całym rojem w stronę coraz lepszych obszarów przestrzeni poszukiwań.
Intuicja stojąca za metodą
Wyobraźmy sobie watahę wilków szarych tropiącą ofiarę w gęstym terenie. Wilk alfa podejmuje ostateczną decyzję, wilki beta i delta doradzają, a reszta watahy zmienia swoje położenie w odpowiedzi na wskazówki wszystkich trzech liderów. GWO dokładnie to naśladuje: trzy najsprawniejsze dotychczas znalezione rozwiązania działają jak nawigacyjne latarnie, a każdy inny kandydat dostosowuje swoją pozycję jako ważoną mieszankę kierunków wskazywanych przez te trzy latarnie. Pojedynczy parametr, a, jest stopniowo redukowany z 2 do 0 w miarę postępu iteracji, dzięki czemu wataha najpierw rozprzestrzenia się szeroko, aby eksplorować, a następnie zacieśnia krąg, aby eksploatować najlepiej znaleziony region.
Historia
GWO zostało zaproponowane przez Seyedali Mirjaliliego, Seyed Mohammada Mirjaliliego i Andrew Lewisa w 2014 roku w czasopiśmie „Advances in Engineering Software”. Algorytm czerpał inspirację z obserwacji ekologicznych struktury watahy wilków szarych: ścisłej hierarchii społecznej (alfa, beta, delta, omega) oraz trójfazowej strategii polowania polegającej na okrążaniu, nękaniu i atakowaniu ofiary. Mirjalili i in. porównali GWO z Optymalizacją Roju Cząstek (Particle Swarm Optimization), Algorytmem Poszukiwań Grawitacyjnych (Gravitational Search Algorithm) i Ewolucją Różnicową (Differential Evolution) na 29 funkcjach testowych i kilku problemach projektowania inżynierskiego, zgłaszając konkurencyjne lub lepsze wyniki. Od 2014 roku algorytm wygenerował znaczną literaturę uzupełniającą: Faris i in. (2018) dokonali przeglądu ponad dekady wariantów — binarnych, wieloobiektywnych, chaotycznych i hybrydowych rozszerzeń — oraz udokumentowali zastosowania w selekcji cech, systemach energetycznych, segmentacji obrazu i harmonogramowaniu.
Kiedy stosować
GWO pasuje do problemów optymalizacji ciągłej, gdzie funkcja celu jest kosztowna do analitycznej oceny lub jest czarną skrzynką. Nie wymaga informacji o gradiencie ani założeń dotyczących rozkładu danych. Metoda jest odpowiednia do zadań projektowania inżynierskiego, strojenia parametrów i selekcji cech. Ponieważ jest oparta na populacji, zalecany jest minimalny rozmiar populacji wynoszący około 10–30 agentów; bardzo małe populacje zmniejszają różnorodność i zwiększają ryzyko przedwczesnej konwergencji. GWO nie jest odpowiednie do problemów dyskretnych lub kombinatorycznych bez modyfikacji, ani do problemów, dla których istnieje dokładne rozwiązanie matematyczne.
Ograniczenia i uwagi
- Konwergencja do globalnego optimum nie jest gwarantowana; jakość zależy od różnorodności populacji i liczby iteracji.
- Nie jest natywnie przystosowany do dyskretnych, binarnych lub kombinatorycznych przestrzeni poszukiwań bez niestandardowego kodowania.
- Podobnie jak większość metod roju, może ulec stagnacji, jeśli trzej liderzy przedwcześnie zgrupują się w suboptymalnym regionie.
- Słabo skaluje się do bardzo wysokowymiarowych przestrzeni poszukiwań w porównaniu z solwerami opartymi na gradiencie, gdy funkcja celu jest gładka.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Bezgradientowy: działa na dowolnej funkcji celu, która zwraca wartość skalarną, włączając w to symulacje i modele czarnych skrzynek.
- Minimalna parametryzacja: należy ustawić tylko rozmiar populacji i liczbę iteracji; a zmniejsza się automatycznie.
- Równoważy eksplorację i eksploatację za pomocą pojedynczego liniowo malejącego parametru, co sprawia, że mechanizm równoważenia jest przejrzysty.
- Konkurencyjna wydajność w testach porównawczych projektowania inżynierskiego przy niskiej złożoności implementacji (poziom trudności 2 z 5).
Zastosowania
- Optymalizacja projektowania inżynierskiego: minimalizacja masy konstrukcji, projektowanie anten, estymacja parametrów systemów energetycznych.
- Strojenie hiperparametrów uczenia maszynowego i selekcja cech dla zadań klasyfikacji.
- Systemy energetyczne: optymalne dysponowanie w sieciach elektroenergetycznych i rozmieszczanie jednostek energii odnawialnej.
- Segmentacja obrazu i analiza obrazów medycznych poprzez optymalizację progowania.
- Problemy harmonogramowania i alokacji zasobów z ciągłą relaksacją.
Jak to działa
Jak to działa
Populacja rozwiązań kandydujących jest generowana równomiernie losowo w ramach zdefiniowanych dolnych i górnych granic przestrzeni poszukiwań. Rozmiar populacji i maksymalna liczba iteracji to jedyne dwa parametry, które muszą być ustawione przed rozpoczęciem działania.
Każde rozwiązanie kandydujące jest oceniane przez funkcję celu. Ponieważ GWO jest algorytmem bezgradientowym, funkcja może być czarną skrzynką — musi jedynie zwracać skalarną wartość dopasowania dla każdej pozycji kandydata.
Kandydaci są sortowani według dopasowania. Najlepsze rozwiązanie jest oznaczane jako alfa (α), drugie najlepsze jako beta (β), a trzecie najlepsze jako delta (δ). Wszystkie pozostałe rozwiązania to wilki omega (ω). Role te są ponownie przypisywane w każdej iteracji, tak aby etykiety zawsze odpowiadały trzem aktualnie najlepszym pozycjom.
Każdy wilk omega aktualizuje swoją pozycję, obliczając trzy wektory odległości — po jednym w kierunku α, β i δ — i przemieszczając się do centroidu trzech wynikowych pozycji docelowych. Parametr kontrolny a maleje liniowo od 2 do 0 w trakcie działania: duże wartości a sprzyjają eksploracji (kandydaci mogą przekraczać i przeszukiwać daleko od liderów), małe wartości sprzyjają eksploatacji (kandydaci ściśle zbiegają się wokół liderów).
Krok polowania jest powtarzany, aż do osiągnięcia maksymalnej liczby iteracji lub spełnienia kryterium zatrzymania. Pozycja wilka alfa w momencie zakończenia jest zwracana jako najlepsze znalezione rozwiązanie.
Częste pułapki
- Ustawienie zbyt małego rozmiaru populacji (poniżej około 10) wcześnie niszczy różnorodność; trzej liderzy zbiegają się przedwcześnie, a algorytm eksploruje tylko niewielki region.
- Zbyt mała liczba iteracji skutkuje niewystarczającym cyklem polowania; algorytm, który kończy działanie, gdy a jest nadal duże, nie wszedł w fazę eksploatacji.
- Zastosowanie GWO do problemów ze zmiennymi całkowitymi lub kategorialnymi bez schematu dyskretyzacji prowadzi do bezsensownych aktualizacji pozycji.
- Ignorowanie skali granic przestrzeni poszukiwań — bardzo szerokie granice w połączeniu z małą populacją pozostawiają większość przestrzeni niepróbkowaną we wczesnych iteracjach.
Najczęściej zadawane pytania
Jak wybrać rozmiar populacji i liczbę iteracji?
Częstym punktem wyjścia jest 30 agentów i 200–500 iteracji dla problemów o umiarkowanej wymiarowości (do około 30 zmiennych). Zwiększaj rozmiar populacji i liczbę iteracji wraz ze wzrostem wymiarowości problemu. Ponieważ GWO jest algorytmem stochastycznym, uruchom go co najmniej 20–30 razy z różnymi ziarnami losowymi i podaj średnią oraz odchylenie standardowe najlepszego dopasowania.
Czy GWO może obsługiwać zmienne dyskretne lub binarne?
Nie natywnie. Standardowe równania aktualizacji pozycji są zdefiniowane dla ciągłych przestrzeni rzeczywistych. W literaturze istnieją warianty binarne lub dyskretne — zazwyczaj wykorzystujące funkcję transferu do mapowania ciągłych pozycji na decyzje binarne — ale są to rozszerzenia, a nie oryginalny algorytm.
Jak GWO wypada w porównaniu z Optymalizacją Roju Cząstek?
Obie są metodami inteligencji roju o podobnym koszcie obliczeniowym. GWO wykorzystuje trzech liderów (alfa, beta, delta) zamiast jednego globalnego najlepszego i osobistego najlepszego każdej cząstki, co zazwyczaj dłużej zachowuje różnorodność. Mirjalili i in. (2014) stwierdzili, że GWO jest konkurencyjne lub lepsze od PSO w ich zestawie testowym, ale wydajność zależy od problemu; żadna z metod nie dominuje uniwersalnie.
Co kontroluje parametr a i czy muszę go dostrajać?
Parametr a maleje liniowo od 2 do 0 w trakcie działania i kontroluje, czy wilki eksplorują (wysokie a) czy eksploatują (niskie a). Ten harmonogram jest ustalony przez algorytm — nie dostrajasz a bezpośrednio. Jedyne dźwignie, które kontrolujesz, to rozmiar populacji i całkowita liczba iteracji, które razem określają, jak wolno lub szybko a spada.
Pokrewne metody
Źródła
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.
Otwórz odnośnik DOISkopiowano.Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.
Otwórz odnośnik DOISkopiowano.