Optymalizacja rojem cząstek (PSO)
- Rok
- 1995
- Typ
- Population-based metaheuristic / swarm intelligence
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Optymalizacja rojem cząstek (PSO) to metaheurystyczny algorytm populacyjny wprowadzony przez Kennedy'ego i Eberharta w 1995 roku, inspirowany zbiorowym ruchem stad ptaków i ławic ryb.
Każde kandydackie rozwiązanie — zwane cząstką — porusza się w przestrzeni poszukiwań, aktualizując swoją prędkość i pozycję w oparciu o własne najlepsze doświadczenie i najlepsze doświadczenie całego roju, co umożliwia szybką zbieżność w przypadku ciągłych problemów optymalizacyjnych.
Intuicja stojąca za metodą
Wyobraźmy sobie stado ptaków przeszukujące duże pole w poszukiwaniu najbogatszego źródła pożywienia. Żaden ptak nie ma mapy, ale każdy pamięta najlepsze miejsce, które osobiście odwiedził, i jest świadomy najlepszego miejsca znalezionego przez jakiekolwiek ptaki w pobliżu. Każdy ptak kieruje swój lot częściowo w stronę własnej zapamiętanej najlepszej lokalizacji, a częściowo w stronę zbiorowego najlepszego miejsca stada, odpowiednio dostosowując prędkość. Po wielu takich dostosowaniach całe stado zbiega się do najbogatszego obszaru. PSO działa dokładnie w ten sposób: każda cząstka jest kandydackim rozwiązaniem, jej pozycja jest samym rozwiązaniem, a rój zbiorowo dąży do optimum, łącząc indywidualną i społeczną pamięć.
Historia
PSO zostało wprowadzone przez Jamesa Kennedy'ego i Russella Eberharta na Międzynarodowej Konferencji Sieci Neuronowych IEEE w 1995 roku, czerpiąc bezpośrednio z modeli symulacyjnych zachowań społecznych stad ptaków i ławic ryb. Fundamentalny artykuł z 1995 roku ustanowił równania aktualizacji prędkości i pozycji, które pozostają kluczowe dla algorytmu. W 1998 roku Shi i Eberhart wprowadzili parametr wagi inercji do aktualizacji prędkości, znacząco poprawiając kontrolę zbieżności i stając się standardową modyfikacją przyjętą przez późniejsze badania. PSO szybko zyskało na popularności jako praktyczna alternatywa dla algorytmów genetycznych w optymalizacji ciągłej, ze względu na swoją prostotę i konkurencyjną szybkość zbieżności, i od tego czasu jest stosowane w inżynierii, strojeniu hiperparametrów uczenia maszynowego, przetwarzaniu sygnałów i modelowaniu naukowym.
Kiedy stosować
PSO nadaje się do ciągłych problemów optymalizacyjnych, gdzie funkcja dopasowania może być oceniona w dowolnym punkcie przestrzeni poszukiwań, ale może być niedróżniczkowalna, multimodalna lub kosztowna do analitycznego obliczenia. Nie wymaga założenia o normalności ani minimalnej wielkości próby, co czyni go stosowalnym w różnych dziedzinach. Metoda działa najlepiej, gdy granice przestrzeni poszukiwań są znane z góry, gdy waga inercji i współczynniki przyspieszenia są starannie dostrojone, i gdy przydzielono wystarczającą liczbę iteracji. Jeśli liczba iteracji jest zbyt niska (mniej niż kilkaset w przypadku nietrywialnych problemów), przedwczesna zbieżność jest prawdopodobna, a optymalizacja bayesowska może być bezpieczniejszą alternatywą.
Ograniczenia i uwagi
- Zaprojektowany dla ciągłych przestrzeni poszukiwań; nie stosuje się bezpośrednio do problemów dyskretnych lub kombinatorycznych bez modyfikacji.
- Przedwczesna zbieżność jest znanym ryzykiem: rój może skupić się wokół lokalnego optimum, jeśli waga inercji i współczynniki są źle dobrane.
- Szybkość zbieżności i jakość rozwiązania są wrażliwe na wybór wagi inercji i współczynników przyspieszenia.
- Brak teoretycznej gwarancji znalezienia globalnego optimum w skończonej liczbie iteracji.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Szybka zbieżność w ciągłych przestrzeniach poszukiwań w porównaniu do wielu metod populacyjnych.
- Bardzo niewiele parametrów do dostrojenia — głównie waga inercji i dwa współczynniki przyspieszenia.
- Nie wymaga informacji o gradiencie ani pochodnej, co czyni go stosowalnym do niedróżniczkowalnych funkcji dopasowania typu czarnej skrzynki.
- Naturalnie skaluje się do problemów ciągłych o dużej wymiarowości.
- Koncepcyjnie prosty i łatwy do zaimplementowania.
Zastosowania
- Strojenie hiperparametrów modeli uczenia maszynowego w ciągłych przestrzeniach parametrów.
- Optymalizacja projektowania inżynierskiego — projektowanie systemów konstrukcyjnych, aerodynamicznych i elektrycznych.
- Trenowanie wag sieci neuronowych i wyszukiwanie architektury.
- Przetwarzanie sygnałów i projektowanie anten.
- Dyspozycja ekonomiczna i optymalizacja systemów energetycznych.
- Estymacja parametrów w modelach naukowych i symulacyjnych.
Jak to działa
Jak to działa
Rój cząstek jest umieszczany w losowych pozycjach w zdefiniowanej przestrzeni poszukiwań, a każdej cząstce przypisywana jest losowa prędkość początkowa. Każda cząstka zapisuje również swoją osobistą najlepszą pozycję — najlepsze rozwiązanie, jakie napotkała do tej pory — a rój śledzi globalnie najlepszą pozycję znalezioną przez jakąkolwiek cząstkę. Waga inercji, współczynnik poznawczy i współczynnik społeczny są ustawiane przed rozpoczęciem działania, ponieważ ich równowaga bezpośrednio decyduje o tym, czy rój szeroko eksploruje, czy wykorzystuje znane dobre regiony.
Funkcja dopasowania jest obliczana dla każdej cząstki w jej bieżącej pozycji. Jest to jedyny krok specyficzny dla problemu: PSO nie nakłada żadnych ograniczeń na formę funkcji dopasowania poza wymogiem, że może być ona oceniona w dowolnym punkcie ciągłej przestrzeni poszukiwań. Osobiste najlepsze pozycje każdej cząstki i globalnie najlepsza pozycja roju są aktualizowane, gdy nowa pozycja daje lepszą wartość dopasowania.
Prędkość każdej cząstki jest aktualizowana przy użyciu trzech składników: terminu inercji (skalowana poprzednia prędkość, promująca pęd), terminu poznawczego (przyciąganie do osobistego najlepszego miejsca cząstki) i terminu społecznego (przyciąganie do globalnie najlepszego miejsca roju). Nowa pozycja jest następnie obliczana przez dodanie zaktualizowanej prędkości do bieżącej pozycji. Waga inercji kontroluje kompromis między eksploracją a eksploatacją: wyższa wartość sprzyja szerokiej eksploracji, podczas gdy niższa wartość promuje drobnoziarnistą eksploatację znanych dobrych regionów.
Kroki oceny i aktualizacji są powtarzane przez określony czas. Rój stopniowo zawęża swoje poszukiwania wokół najbardziej obiecującego regionu. Działanie kończy się po osiągnięciu limitu iteracji, po czym globalnie najlepsza pozycja jest zgłaszana jako rozwiązanie. Wystarczająca liczba iteracji — zazwyczaj co najmniej kilkaset do tysiąca dla nietrywialnych problemów — jest konieczna, aby umożliwić rójowi zbieżność; zbyt wczesne zatrzymanie grozi zwróceniem suboptymalnego wyniku.
Częste pułapki
- Uruchamianie zbyt małej liczby iteracji — w przypadku nietrywialnych problemów niewystarczające iteracje uniemożliwiają zbieżność roju; preferuj optymalizację bayesowską, gdy budżet obliczeniowy jest bardzo ograniczony.
- Wybór wagi inercji zbyt wysokiej powoduje, że cząstki eksplorują w nieskończoność i opóźniają zbieżność; zbyt niska powoduje przedwczesne skupienie wokół lokalnego optimum.
- Ignorowanie granic przestrzeni poszukiwań — cząstki, które dryfują poza zamierzonymi granicami, eksplorują nieistotne regiony i zniekształcają globalne optimum.
- Traktowanie PSO jako odpowiedniego dla problemów dyskretnych lub kombinatorycznych bez adaptacji — standardowe równania aktualizacji prędkości i pozycji zakładają przestrzeń ciągłą.
- Przedwczesna zbieżność pozostaje niewykryta, jeśli postęp dopasowania nie jest monitorowany w kolejnych iteracjach; zawsze śledź globalnie najlepsze dopasowanie w funkcji liczby iteracji.
Najczęściej zadawane pytania
Czym PSO różni się od algorytmu genetycznego?
Oba są metaheurystykami populacyjnymi do optymalizacji, ale różnią się mechanizmem. Algorytm genetyczny ewoluuje populację poprzez selekcję, krzyżowanie i mutację, inspirowane ewolucją biologiczną. PSO zamiast tego przesuwa cząstki w przestrzeni ciągłej, aktualizując prędkości w oparciu o pamięć osobistą i społeczną — nie ma krzyżowania ani mutacji. PSO zazwyczaj ma mniej parametrów do dostrojenia i często zbiega szybciej w problemach ciągłych, podczas gdy algorytmy genetyczne można bardziej naturalnie dostosować do przestrzeni dyskretnych lub kombinatorycznych.
Jakie są kluczowe parametry i jak należy je ustawić?
Trzy podstawowe parametry to waga inercji (w), która kontroluje, jaka część poprzedniej prędkości jest zachowywana; współczynnik poznawczy (c1), który skaluje przyciąganie do osobistego optimum cząstki; oraz współczynnik społeczny (c2), który skaluje przyciąganie do globalnego optimum. Powszechnym punktem wyjścia z literatury jest w około 0,7–0,9, c1 i c2 około 1,5–2,0. Waga inercji jest często zmniejszana liniowo w kolejnych iteracjach, aby przesunąć rój od eksploracji na początku do eksploatacji później.
Czy PSO może obsługiwać problemy dyskretne lub kombinatoryczne?
Standardowe PSO jest zdefiniowane dla ciągłych przestrzeni poszukiwań i stosuje aktualizacje prędkości i pozycji, które zakładają współrzędne o wartościach rzeczywistych. Istnieją warianty dyskretne lub kombinatoryczne — takie jak binarne PSO — ale wymagają one nietrywialnych modyfikacji równań aktualizacji. Dla problemów czysto kombinatorycznych, takich jak trasowanie lub harmonogramowanie, optymalizacja rojem mrówek jest często bardziej naturalnym wyborem.
Skąd mam wiedzieć, czy rój zbiegł przedwcześnie?
Śledź globalnie najlepszą wartość dopasowania w kolejnych iteracjach. Jeśli krzywa spłaszcza się na długo przed wyczerpaniem budżetu iteracji, a zgłoszone rozwiązanie nie jest zadowalające, prawdopodobnie wystąpiła przedwczesna zbieżność. Powszechne środki zaradcze obejmują zwiększenie wagi inercji, ponowne uruchomienie roju z nowych losowych pozycji lub zwiększenie rozmiaru roju. Jeśli budżet obliczeniowy nie pozwala na więcej iteracji, optymalizacja bayesowska może być bardziej wydajną alternatywą.
Pokrewne metody
Źródła
Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.
Otwórz odnośnik DOISkopiowano.Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).
Otwórz odnośnik do publikacjiSkopiowano.