PSO - Particle Swarm Optimization

Treść pochodzi z devblogu o sztucznej inteligencji:
jakubniwa.pl

Czasami zachodzi potrzeba optymalizacji parametrów jakiejś skomplikowanej, nieregularnej funkcji(np. sieć neuronowa); Do rozwiązania tego problemu możemy użyć metody gradientowe lub quasi-newtonowskie, lecz co zrobić, gdy funkcja jest nieróżniczkowalna a nawet nieciągła? Wtedy z pomocą przychodzą metody meta heurystyczne. Jedną z nich jest PSO, czyli optymalizacja rojem cząsteczek. Czym PSO odróżnia się od innych meta heurystyk? Mianowicie nadaje się do optymalizacji problemów dynamicznych lub z dynamicznie zmieniającą się dziedziną.

Więc z czego "składa się" taki rój cząsteczek:


Każdy rój składa się z :
- roju(jego parametrów)
- cząsteczek

Cząsteczki:
Pozycja : Wektor pozycji - rozmiar zależny od wymiarowości zadania;
Inicjalizowany liczbami pseudolosowymi o rozkładzie jednorodnym od zadanej wartości minimalnej do maksymalnej. Jednakże, jeżeli coś wiemy na temat optymalizowanego zadania możemy przyjąć liczby bliskie zakładanemu optimum.
Przyśpieszenie: Wektor przyśpieszenia -rozmiar zależny od wymiarowości zadania;
Inicjalizowany liczbami pseudolosowymi o rozkładzie jednorodnym od ujemnej różnicy zadanej wartości maksymalnej i minimalnej, do dodatniej wartości takiej różnicy .
Każdy element wektoru odnosi się do prędkości dla wymiaru n, gdzie n jest numerem elementu w wektorze.
Najlepsza pozycja: Wektor najlepszej pozycji - rozmiar zależny od wymiarowości zadania;
Inicjalizowany wektorem pozycji przy tworzeniu cząsteczki.
Jego wartość zostaje zmieniona, gdy cząsteczka znalazła lepiej oceniane położenie.
Wektor ten staje się później jednym z dwóch atraktorów cząsteczki.

Rój:
Cząsteczki: Wektor zawierający wszystkie cząsteczki roju jako obiekty.
Najlepsza pozycja: Wektor najlepszej pozycji -rozmiar zależny od wymiarowości zadania;
Inicjalizowany wektorem pozycji pierwszej stworzonej cząsteczki.
Jego wartość zostaje zmieniona, gdy jedna z cząsteczek roju znalazła lepiej oceniane położenie od swojego i jest ono lepiej oceniane niż aktualne najlepsze położenie roju. Wektor ten staje się później jednym z dwóch atraktorów cząsteczek.


Parametry algorytmu:
Omega:
Parametr odpowiadający za "wygasanie" ruchu cząsteczek.

dla Omega = 1: cząsteczki nie zwalniają z upływem czasu
dla Omega < 1: cząsteczki zwalniają z upływem czasu
dla Omega > 1: cząsteczki przyśpieszają z upływem czasu

fiCząsteczek:
Parametr odpowiedzialny za indywidualność cząsteczek. Bezpośrednio zależny od fi roju. Gdy jest większy niż fi roju cząsteczki stają się bardziej indywidualne - ważniejszym atraktorem jest ich własna najlepsza pozycja.

fi roju :
Parametr odpowiedzialny za grupowość-stadność cząsteczek. Bezpośrednio zależny od ficząsteczek. Gdy jest większy niż fi cząsteczek, cząsteczki stają się bardziej stadne - ważniejszym atraktorem jest najlepsza pozycja całego roju.


Znaczenie parametrów
To, że cząsteczki oscylują między swoimi atraktorami zgodnie z zasadą superpozycji nie jest złym / szkodliwym zjawiskiem - ponieważ przy dynamicznie zmieniającej się funkcji / dziedzinie zadania mają one większą szansę na szybsze znaleznienie nowego optimum całego roju, który stanie się atraktorem dla reszty cząsteczek.

Możemy to zobaczyć poniżej:


a tutaj w większej skali:


Purpurowe sfery są najlepszymi pozycjami wg najbliżej położonych cząsteczek.
Żółte sfery sa cząsteczkami.
optymalizowana jest funkcja funkcja Ackleya 2-D, mapa w skali logarytmicznej.

Algorytm:


terminalCondition:
Może być może być flagą informującą nas o tym, czy minęło x iteracji lub został znaleziony punkt z pewną dokładnością.
rP:
Losowy parametr odpowiedzialny za indywidualność cząsteczek. Działa bliźniaczo do fi cząsteczek, lecz losowany za każdym razem, a fi cząsteczek jest ustalony z góry. Liczba pseudo losowa o rozkładzie jednorodnym z zakresu 0 .. 1.
rS:
Losowy parametr odpowiedzialny za stadność cząsteczek. Działa bliźniaczo do fi roju, lecz losowany za każdym razem, a fi roju jest ustalony z góry. Liczba pseudo losowa o rozkładzie jednorodnym z zakresu 0 .. 1.


Działanie algorytmu
Zasada działania algorytmu jest dość prosta:
-Obliczamy przyspieszenie dla każdej cząsteczki z osobna
-zmieniamy jej pozycje zgodnie z wyliczonym przyśpieszeniem.
-wyliczamy wartość funkcji dla jej aktualnej pozycji
-następnie sprawdzamy czy aktualna pozycja jest lepsza od najlepszej pozycji wg. cząsteczki, jeżeli tak to ją zmieniamy i sprawdzamy czy jest lepsza od najlepszej pozycji wg roju, jeżeli tak, to też ją zmieniamy.

Postępujemy tak do czasu, gdy aktywuje się nasz warunek stopu.

Animacje prezentujące działanie algorytmu dla róznych funkcji można zobaczyć na moim kanale youtube:
http://www.youtube.com/user/kayou666



Dziękuję za przeczytanie tekstu. Wskazanie błędów/komentarze/prośby o wyjaśnienie mile widziane.

Gorąco zapraszam na http://jakubniwa.pl po więcej!

Mogę udostępnic kod w pythonie, proszę wysłać PW.