Optymalizacja za pomocą roju cząstek

Optymalizacja za pomocą roju cząstek (ang. Particle Swarm Optimization, w skrócie PSO) to algorytm metaheurystyczny służący do rozwiązywania problemów optymalizacyjnych.

Problem optymalizacyjny to problem, którego rozwiązanie polega na odnalezieniu optymalnej (największej lub najmniejszej) wartości pewnej funkcji, zwanej funkcją celu. Zakres wartości argumentów tej funkcji nazywany jest przestrzenią rozwiązań. Pojedynczy punkt w tej przestrzeni, wyznaczony przez ustalone wartości poszczególnych argumentów nazywany jest rozwiązaniem.

Przykładem problemu optymalizacyjnego jest problem plecakowy. Mając plecak o określonej pojemności oraz zestaw przedmiotów posiadających określoną wartość i rozmiar, należy określić zbiór przedmiotów o największej możliwej wartości, bez przekraczania pojemności plecaka. W podanym przykładzie rozwiązaniem jest jeden określony podzbiór przedmiotów, natomiast funkcje celu określa ich łączna wartość. Przestrzeń rozwiązań stanowi zbiór wszystkich możliwych kombinacji przedmiotów mieszczących się w plecaku.

Algorytmy metaheurystyczne, albo krócej metaheurystyki to algorytmy "uniwersalne", pozwalające na rozwiązywanie dowolnych problemów obliczeniowych. Metaheurystyki nie gwarantują odnalezienia optymalnego rozwiązania, a jedynie rozwiązania zbliżonego do optymalnego. Wykorzystywane są w sytuacjach, gdy uzyskanie najlepszego rozwiązania byłoby zbyt kosztowne obliczeniowo.

Zasada działania algorytmu PSO

Ideą algorytmu PSO jest iteracyjne przeszukiwanie przestrzeni rozwiązań problemu przy pomocy roju cząstek. Każda z cząstek posiada swoją pozycję w przestrzeni rozwiązań, prędkość oraz kierunek w jakim się porusza. Ponadto zapamiętywane jest najlepsze rozwiązanie znalezione do tej pory przez każdą z cząstek (rozwiązanie lokalne), a także najlepsze rozwiązanie z całego roju (rozwiązanie globalne). Prędkość ruchu poszczególnych cząstek zależy od położenia najlepszego globalnego i lokalnego rozwiązania oraz od prędkości w poprzednich krokach. Poniżej przedstawiony jest wzór pozwalający na obliczenie prędkości danej cząstki.

Gdzie:

• v - prędkość cząstki
• ω - współczynnik bezwładności, określa wpływ prędkości w poprzednim kroku
• φ_l - współczynnik dążenia do najlepszego lokalnego rozwiązania
• φ_g - współczynnik dążenia do najlepszego globalnego rozwiązania
• l - położenie najlepszego lokalnego rozwiązania
• g - położenie najlepszego globalnego rozwiązania
• x - położenie cząstki
• r_l, r_g - losowe wartości z przedziału <0,1>

Powyższy wzór pozwala na aktualizacje prędkości wszystkich cząstek na podstawie uzyskanej do tej pory wiedzy.

Schemat działania algorytmu

Schemat działania algorytmu przedstawia się następująco:

• Dla każdej cząstki ze zbioru:
• Wylosuj pozycje początkową z przestrzeni rozwiązań
• Zapisz aktualną pozycje cząstki jako najlepsze lokalne rozwiązanie
• Jeśli rozwiązanie to jest lepsze od najlepszego rozwiązanie globalnego, to zapisz je jako najlepsze
• Wylosuj prędkość początkową
• Dopóki nie zostanie spełniony warunek stopu (np. minie określona liczba iteracji):
• Dla każdej cząstki ze zbioru:
• Wybierz losowe wartości parametrów r_l i r_g
• Zaktualizuj prędkość cząstki wg powyższego wzoru
• Zaktualizuj położenie cząstki w przestrzeni
• Jeśli aktualne rozwiązanie jest lepsze od najlepszego rozwiązania lokalnego:
• Zapisz aktualne rozwiązanie jako najlepsze lokalnie
• Jeśli aktualne rozwiązanie jest lepsze od najlepszego rozwiązania globalnego:
• Zapisz aktualne rozwiązanie jako najlepsze globalnie

Parametry algorytmu

Działaniem algorytmu PSO można sterować za pomocą doboru jego parametrów. Od ich wartości zależy zachowanie poszczególnych cząstek, wielkość przestrzeni jaką przeszuka algorytm, oraz czas zbieżności cząstek do najlepszego rozwiązania.

Wartość współczynnika bezwładności (ω) wpływa na zdolność cząstek do zachowania poprzedniej prędkości. Wraz ze wzrostem wartości tego parametru, zwiększa się zdolność cząstek do przeszukiwania nowych rejonów przestrzeni rozwiązań.

φ_l - współczynnik dążenia do najlepszego lokalnego rozwiązania. Im większa wartość tego parametru tym większa skłonność cząstki do oscylacji wokół swojej najlepszej pozycji.

φ_g - współczynnik dążenia do najlepszego globalnego rozwiązania. Zwiększanie wartości tego parametru powoduje zwiększenie tendencji do grupowania się cząstek wokół najlepszego globalnego rozwiązania.

Wizualizator algorytmu PSO

Wizualizator pozwala na przeprowadzenie symulacji działania algorytmu PSO. Funkcje przedstawiane są na trójwymiarowym wykresie. Szukane optimum znajduję się w najwyższym punkcie wykresu. Białe punkty odzwierciedlają położenie cząstek. Wizualizator umożliwia sterowanie ilością cząstek oraz parametrami algorytmu.

Kliknij aby uruchomić w wybranym języku:

Program: Kinga Szymanowska

Prowadzący: Maciej Komosiński