Podręcznik

Wstęp historyczny i przyrodniczo-matematyczne inspiracje dla PSO

W historii nauki wiele wielkich pomysłów brało swój początek nie z głębokich analiz równań różniczkowych, ale z... obserwacji. Obserwacji życia, przyrody, zachowań społecznych. Tak właśnie było z algorytmem PSO – zrodził się nie w sali wykładowej matematyki stosowanej, ale w głowie psychologa i inżyniera, którzy próbowali opisać coś, co każdy z nas kiedyś widział: płynny, zsynchronizowany lot stada ptaków lub falującą niczym jeden organizm ławicę ryb. 

Na początku lat 90. XX wieku James Kennedy (psycholog społeczny) i Russell Eberhart (inżynier) analizowali zachowania społeczne ptaków i ryb. Zamiast skupiać się na biologicznym realizmie, postanowili wyciągnąć z obserwacji kilka prostych zasad i przełożyć je na język obliczeń. Tak w 1995 roku narodził się PSO – Particle Swarm Optimization. Zamiast pytać „jaka jest trajektoria idealnego lotu?”, Kennedy i Eberhart zapytali: „czy możemy zasymulować te zbiorowe zachowania, by rozwiązywać problemy optymalizacyjne?”.  To, co opracowali w odpowiedzi właśnie poznajecie.

Czy zastanawialiście się kiedyś dlaczego np. ptaki lecąc w wielkich stadach utrzymują spójność, zmieniają razem jako stado kierunek, czy też nie zderzają się? W sumie dzieje się tak dzięki 3 regułom: 

• separacja - nie lubię być byt blisko. Jak jestem za blisko - oddalam się.
• Wyrównanie kierunku - widzę swoich sąsiadów, i idę tam gdzie oni  - w sensie średniego kierunku ich ruchu. 
• Wyrównanie położenia - widzę sąsiadów - staram się być pośrodku między tymi najbliższymi

Te reguły wystarczą już do opisania ruchu stada ptaków. Jeśli tylko każda jednostka będzie się ich trzymać - całe stado jest w stanie zachowywać zwartą, optymalną formację i zmieniać (nawet gwałtownie) kierunek w którym się porusza. 

Zbiory bez lidera: inteligencja rozproszona

Podstawowa koncepcja PSO zakłada, że rozwiązania problemu (cząstki) poruszają się w przestrzeni poszukiwań, kierując się trzema impulsami:

1. Własną pamięcią – cząstka pamięta, gdzie wcześniej było dobrze.
2. Obserwacją sąsiadów – cząstka wie, jak poszło innym.
3. Tendencją do zmiany – ruch odbywa się z pewną inercją.

To nie są złożone algorytmy decyzyjne. To trzy wektory sił, działających jednocześnie. I właśnie ich połączenie daje efekt podobny do tego, co widzimy w naturze: adaptacyjne, grupowe, ale i rozproszone zachowanie.

Cząstki nie potrzebują centralnego koordynatora. Nie ma tu lidera ani „dyspozytora ruchu”. Całość działa na zasadzie prostych reguł lokalnych. Brzmi znajomo? Tak – to dokładnie ta sama idea, która stoi za automatem komórkowym.

Automaty komórkowe – matematyczne odbicie przyrody

Zanim jeszcze wymyślono PSO, matematycy i informatycy teoretyczni pracowali nad tzw. automatami komórkowymi (ang. cellular automata). Jeden z najsłynniejszych przykładów to „Gra w życie” Johna Conwaya. W tym modelu, każdy punkt na siatce (komórka) decyduje o swoim stanie na podstawie stanu swoich sąsiadów – i to wszystko. A jednak, z tych prostych zasad wyłaniają się niezwykle złożone zachowania.

Warto tu zwrócić uwagę na analogię: w PSO też mamy „siatkę” – tym razem nie przestrzenną, lecz abstrakcyjną przestrzeń możliwych rozwiązań problemu. Cząstki nie są przypisane do stałych komórek, ale poruszają się, dynamicznie aktualizując swoją pozycję. A ich ruch jest wynikiem prostych lokalnych reguł, działających w czasie.

Zarówno PSO, jak i automaty komórkowe korzystają z:

W obu przypadkach to, co się liczy, to interakcja – nie pojedynczy byt, ale jego relacja z sąsiedztwem.

Biologia, matematyka i emergencja

W biologii, zachowania zbiorowe to klasyczny przypadek tzw. zjawisk emergentnych – takich, które nie wynikają wprost z właściwości pojedynczych elementów, ale pojawiają się dopiero na poziomie całego układu. Przykłady?

• Mrówki, które potrafią budować z siebie mosty.
• Termity, które bez planu architektonicznego tworzą złożone kolonie.
• Pszczoły, które kolektywnie podejmują decyzje o miejscu nowego gniazda.

W PSO też występuje emergencja. Żadna cząstka nie zna najlepszego rozwiązania. Ale razem, przez dzielenie się informacją, dążą do coraz lepszych obszarów przestrzeni rozwiązań. Efekt? Często zaskakująco dobre przybliżenia globalnego optimum.

To wszystko ma swój matematyczny wymiar. Ruch każdej cząstki w PSO można modelować jako losową dynamikę różnicową z komponentą socjalną. A cały system jako złożony układ dynamiczny z lokalnymi interakcjami i pamięcią.

Dlaczego to działa?

Bo łączy w sobie:

• Eksplorację – cząstki są rozproszone po całej przestrzeni.
• Eksploatację – z czasem skupiają się wokół obiecujących rejonów.
• Pamięć i adaptację – każda cząstka wie, gdzie jej było dobrze.
• Współdzielenie wiedzy – najlepsze rozwiązania są przekazywane innym.

Takie podejście, będące mieszanką biologii, matematyki i heurystyki, okazało się wyjątkowo skuteczne – szczególnie tam, gdzie gradienty są nieznane, funkcje są nieciągłe, a przestrzeń rozwiązań ogromna.