Optymalizacja Zaprogramowanych Ruchów: Wyjaśnienie Inteligencji Żwiarzy

Pamięć stada, przekształcona w algorytm

Współzależność Kennediego i Eberharta z 1995 roku była zaskakująco prosta: dobre rozwiązania przyciągają sąsiadów. Podobnie jak ptak dostosowuje lot, aby utrzymać się w stadzie, jednocześnie pamiętając, gdzie osobiście znalazł najlepsze jedzenie, każdy cząstek w PSO (Particle Swarm Optimization) posiada pamięć społeczną – położenie najlepiej znanego stada, gbest – oraz pamięć poznawczą, czyli własne najlepsze znane położenie, pbest. PSO należy do szerszej rodziny algorytmów oparte na inteligencji stad (obok Optymalizacji Kolonii Młódźców i Sztucnej Woski) wszystkich dzielące się właściwością emergentną: bliskooptymalne zachowanie globalne z prostych lokalnych zasad, bez scentralizowanej kontroli.

Równanie aktualizacji prędkości

Zbiór N cząstek jest inicjowany w losowych pozycjach przestrzeni poszukiwania. W każdej iteracji każda cząstka aktualizuje swoją prędkość z trzech sił – oporu inercji (zachowanie ruchu w obecnym kierunku), wpływu poznawczego w stronę jej własnej najlepszej znanej pozycji oraz wpływu społecznego w kierunku globalnej najlepszej pozycji swarzystwa, a następnie aktualizuje swoje położenie poprzez dodanie nowej prędkości. Losowe skalary r1 i r2 są próbkowane dla każdej cząstki, dla każdej wymiarowości, na każdej iteracji, co jest zasadnicze: bez tego losu cząstki w symetrycznej konfiguracji mogłyby zablokować się w identycznym ruchu, a swarzystwo upłynniają się do deterministycznego wzoru.

v(t+1) = ω·v(t) + c1·r1·(pbest − x(t)) + c2·r2·(gbest − x(t))
x(t+1) = x(t) + v(t+1)

Typical: ω 0.4→0.9 (linearly decayed), c1 = c2 = 1.5–2.0
Clerc's constriction values: ω = 0.729, c1 + c2 ≤ 4

Zbieżność, stagnacja i poprawa topologii pierścienia

Clerc i Kennedy (2002) sformalizowali warunki zbieżności PSO: bez kontroli parametrów roj swobodnie oscyluje i nigdy się nie ustabilizuje, ale przestrzeń definiowana przez trójkąt zbieżności ((ω, c1, c2)) gwarantuje stabilny tor. Najczęstszą przyczyną awarii jest wczesna konwergencja, czyli upadek całego roju na lokalny minimum zanim ma szansę zbadać przestrzeń, co zwykle wynika z dominacji współczynnika społecznego c2 lub utraty różnorodności. Rozwiązania obejmują losowe restarty dla zatrzymanych cząstek lub zmianę z pojedynczego wspólnego gbest na lokalną topologię pierścieniową (lbest), w której każda cząstka widzi tylko swoich najbliższych sąsiadów – wolniejsza konwergencja, ale znacznie bardziej odporna na utknięcie w jednym basenie.

PSO w porównaniu z algorytmami genetycznymi i symulowanym annealingiem

PSO, algorytmy genetyczne i symulowane annealing to wszystkie gradient-free, ale różnią się mechanizmem: PSO przemieszcza populację ciągle poprzez prędkość i pamięć trwałą (pbest, gbest); algorytm genetyczny stosuje krzyżowanie i mutacje z presją selekcji i bez per-indywidualnej pamięci; symulowane annealing perturbuje pojedyncze rozwiązanie pod rozkładem temperatury schładzającej się. W praktyce PSO jest często preferowane dla ciągłych, o niskich do średnich wymiarach problemów (≤100 wymiarów) ze względu na prostotę implementacji i konwergencję w kilkadziesiąt iteracji – od optymalizacji projektowania inżynierskiego i PID po układanie farm wiatrowych oraz wyszukiwanie hiperparametrów.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.