Ta symulacja uruchamia prawdziwy algorytm optymalizacji rojem cząstek (PSO) przeciwko symulowanemu problemowi lokalizacji pokrycia komórkowego. Każda cząstka w roju to cały kandydujący układ — pozycja (x, y) każdego proponowanego przez nią masztu — a w każdej iteracji prędkość każdej cząstki jest aktualizowana prawdziwą regułą PSO v ← w·v + c₁·r₁·(pbest − x) + c₂·r₂·(gbest − x), a następnie jej pozycja wzorem x ← x + v, z nowymi losowymi wartościami r₁, r₂ w każdym kroku. Dopasowanie to prawdziwy cel jakości pokrycia: ważone popytem pokrycie sygnału na obszarze usługowym, z kwadratowym spadkiem w zależności od odległości i karą za maszty redundantnie pokrywające ten sam teren.
🔬 Co pokazuje
Widok obszaru usługowego z góry w 3D: punkty popytu o rozmiarze i kolorze zależnym od wagi populacji, delikatne różowe kropki pokazujące pozycje kandydujących masztów każdej cząstki w ruchu oraz jasno świecące maszty z przezroczystymi pierścieniami pokrycia oznaczającymi bieżący najlepszy znany (gbest) układ masztów roju. Poniżej wykres na żywo śledzi najlepsze dotychczasowe i bieżące średnie dopasowanie roju — prawdziwa krzywa zbieżności, a nie zaskryptowana animacja.
🎮 Jak korzystać
Dostosuj rozmiar roju (10-60 cząstek), wagę bezwładności w (0,2-0,9) oraz liczbę masztów do rozmieszczenia (3-8). Wybierz układ punktów popytu — losowy, skupiony ("miasta") lub siatkowy — i dostosuj promień pokrycia na maszt. Przeciągnij widok 3D, aby obrócić kamerę, i użyj Restartu, aby zresetować nowy przebieg z nowym polem popytu i rojem.
💡 Czy wiesz, że?
PSO zostało zainspirowane skoordynowanym, bezprzywódczym ruchem stad ptaków i ławic ryb — żadna pojedyncza cząstka nie „zna” odpowiedzi, jednak rój jako całość niezawodnie zbiega, ponieważ każda cząstka jest popychana zarówno przez własną pamięć, jak i wspólne najlepsze odkrycie grupy. Nie potrzebuje pochodnej funkcji celu, co jest właśnie powodem, dla którego tak dobrze sprawdza się w problemach lokalizacyjnych, gdzie pokrycie nie jest gładką, różniczkowalną powierzchnią.
Czym jest optymalizacja rojem cząstek (PSO)?
Optymalizacja rojem cząstek to metaheurystyka populacyjna, w której rój rozwiązań kandydujących („cząstek”) porusza się w przestrzeni przeszukiwania, przyciągany zarówno do najlepszej pozycji, jaką osobiście odnalazł (pbest), jak i najlepszej pozycji odnalezionej przez cały rój (gbest). W przeciwieństwie do metod gradientowych, PSO nie wymaga pochodnej funkcji celu — jedynie możliwości oceny wyniku dopasowania dla dowolnego kandydata — co czyni ją dobrze dostosowaną do kombinatorycznych problemów lokalizacyjnych, takich jak rozmieszczenie anten, gdzie funkcja pokrycia nie jest gładka ani różniczkowalna w żadnej prostej postaci zamkniętej.
Jak faktycznie działa reguła aktualizacji prędkości?
W każdej iteracji każda cząstka aktualizuje swoją prędkość wzorem v ← w·v + c₁·r₁·(pbest − x) + c₂·r₂·(gbest − x), a następnie przemieszcza się według x ← x + v. Człon bezwładności w·v przenosi dotychczasowy pęd cząstki; człon poznawczy c₁·r₁·(pbest − x) przyciąga ją z powrotem do jej własnej najlepszej dotychczasowej pozycji; człon społeczny c₂·r₂·(gbest − x) przyciąga ją do najlepszej dotychczasowej pozycji roju. r₁ i r₂ to nowe, niezależne liczby losowe losowane dla każdego wymiaru, w każdej iteracji, więc żadne dwie cząstki nie podążają identycznymi trajektoriami, nawet gdy dzielą te same cele pbest i gbest. Ta symulacja używa c₁ = c₂ = 1,6, standardowych wartości z literatury PSO.
Jaka funkcja celu ocenia jakość rozmieszczenia anten?
Każdy kandydujący układ jest oceniany przez zsumowanie, dla każdego punktu popytu na obszarze usługowym, wagi popytu tego punktu pomnożonej przez najsilniejszy sygnał, jaki odbiera z dowolnego masztu — modelowany jako kwadratowy spadek z odległością, który osiąga zero na promieniu pokrycia (uproszczony model tłumienia trasy najlepszego serwera). Następnie odejmowany jest człon kary za punkty popytu redundantnie pokryte przez więcej niż jeden maszt powyżej minimalnego progu sygnału, ponieważ rzeczywiste wdrożenia chcą, aby maszty były rozłożone, by pokryć więcej terenu, a nie skupione na tych samych klientach. Jest to prawdziwa, deterministyczna funkcja współrzędnych masztów — nic w niej nie jest zaskryptowane ani z góry ustalone.
Dlaczego krzywe najlepszego i średniego dopasowania zachowują się inaczej?
Krzywa najlepsza (gbest) może jedynie rosnąć lub pozostać płaska, ponieważ rój pamięta najlepszy układ, jaki kiedykolwiek znalazł, i nigdy go nie odrzuca — to strukturalna gwarancja sposobu śledzenia pbest i gbest, a nie zaskryptowana animacja. Krzywa średnia odzwierciedla bieżącą pozycję każdej cząstki w każdej iteracji, która może się obniżać, gdy cząstki wychodzą poza cel podczas eksploracji, a następnie odbudowywać się, gdy rój ponownie się zbiega. Obserwowanie obu razem pokazuje rzeczywisty kompromis eksploracja/eksploatacja: średnie dopasowanie jest bardziej zaszumione na wczesnym etapie, gdy cząstki są rozproszone, a obie krzywe zbliżają się do siebie, gdy rój zbiega do wspólnego regionu przestrzeni przeszukiwania.
Co zmieniają regulatory wagi bezwładności i rozmiaru roju?
Waga bezwładności w skaluje, jaka część poprzedniej prędkości cząstki przenosi się do następnego kroku: wysokie w (blisko 0,9) utrzymuje cząstki w szerokim ruchu i dłuższej eksploracji przed ustabilizowaniem się, podczas gdy niskie w (blisko 0,2) szybko tłumi pęd, więc cząstki szybciej zbliżają się do pbest i gbest, ale ryzykują osiedlenie się w przeciętnym lokalnym układzie. Rozmiar roju kontroluje, ile niezależnych kandydujących układów przeszukuje równolegle w każdej iteracji — większy rój próbkuje więcej przestrzeni rozmieszczenia na iterację i zwykle znajduje lepszy gbest szybciej, kosztem większej liczby ocen dopasowania na krok.
Jak PSO wypada w porównaniu z przeszukiwaniem siłowym lub spadkiem gradientu przy lokalizacji masztów?
Przeszukiwanie siłowe wszystkich możliwych kombinacji współrzędnych masztów jest obliczeniowo niewykonalne, gdy masztów jest więcej niż jeden lub dwa, ponieważ przestrzeń przeszukiwania rośnie wykładniczo wraz z liczbą masztów. Spadek gradientu wymaga różniczkowalnej funkcji celu, ale używana tu funkcja pokrycia najlepszego serwera ma załamania w każdym miejscu zmiany najbliższego masztu, a wybory kombinatoryczne, takie jak „który maszt pokrywa który punkt popytu”, w ogóle nie są naturalnie różniczkowalne. PSO omija oba problemy: potrzebuje jedynie oceny dopasowania dla kandydującego układu, a nie jego różniczkowania, a jego rój równoległych kandydatów przeszukuje wiele regionów przestrzeni rozmieszczenia jednocześnie, co czyni go standardowym praktycznym wyborem dla rzeczywistej optymalizacji rozmieszczenia anten i obiektów.