Przejdź do treści
Wróć do wyników wyszukiwania

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

Rozmiar czcionki

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

1

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.

2

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.

3

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.

4

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).

5

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

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    Otwórz odnośnik DOI
    Skopiowano.
  2. 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 DOI
    Skopiowano.