Poprzedni
Następny  

4. Particle Swarm Optimization

4.3. Schemat dzialania

Algorytm PSO opiera się na populacji cząstek poruszających się w przestrzeni rozwiązań, gdzie każda z nich aktualizuje swoją pozycję na podstawie własnego doświadczenia oraz obserwacji sąsiadów. Poszukiwanie rozwiązania odbywa się iteracyjnie, a cały proces można przedstawić jako cykl aktualizacji prędkości i położenia, z wykorzystaniem informacji lokalnej i społecznej.

Etapy działania algorytmu

  1. Inicjalizacja populacji

    • Pozycje i prędkości cząstek są losowo inicjalizowane.
    • Dla każdej cząstki oblicza się wartość funkcji celu.
    • Zapamiętywane są najlepsze pozycje własne (personal best) oraz najlepsze pozycje w sąsiedztwie (np. globalne lub lokalne optimum).

  2. Pętla optymalizacyjna (iteracje)

    • Dla każdej cząstki:

      • Aktualizowana jest prędkość na podstawie trzech komponentów: inercji, dążenia do własnego najlepszego punktu i dążenia do najlepszego punktu społecznego.
      • Obliczana jest nowa pozycja.
      • Obliczana jest wartość funkcji celu w nowej pozycji.
      • Jeżeli nowa pozycja jest lepsza niż dotychczasowy personal best – zostaje zaktualizowana.
      • Jeśli lepsza jest również od najlepszej pozycji w sąsiedztwie – sąsiedztwo jest informowane.

      Warunek zakończenia

      • Algorytm kończy działanie po osiągnięciu maksymalnej liczby iteracji lub po spełnieniu kryterium dokładności (np. brak poprawy przez N kroków).

Pseudokod algorytmu PSO

Wejście: 
    - funkcja celu f(x),
    - liczba cząstek N,
    - liczba iteracji T,
    - współczynniki: ω, c1, c2

1. Dla każdej cząstki i = 1 do N wykonaj:
    - losowo zainicjalizuj pozycję xi
    - losowo zainicjalizuj prędkość vi
    - ustaw pi ← xi      // najlepsza pozycja własna
    - oblicz f(pi)

2. Wyznacz g ← najlepsze pi w całej populacji lub w sąsiedztwie

3. Dla t = 1 do T wykonuj:
    Dla każdej cząstki i = 1 do N:
        - wylosuj r1, r2 ∈ U(0, 1)
        - zaktualizuj prędkość:
            vi ← ω * vi + c1 * r1 * (pi - xi) + c2 * r2 * (g - xi)
        - zaktualizuj pozycję:
            xi ← xi + vi
        - oblicz f(xi)
        - jeśli f(xi) < f(pi) to:
            pi ← xi
        - jeśli f(xi) < f(g) to:
            g ← xi

4. Zwróć: g jako przybliżone optimum

Ograniczenia prędkości i ich wpływ na działanie algorytmu

W praktyce działania algorytmu PSO często wprowadza się ograniczenia na maksymalną dopuszczalną prędkość cząstek (oznaczaną jako v_max). Prędkość cząstki decyduje o tym, jak duży krok wykonuje ona w przestrzeni poszukiwań – a zbyt duże kroki mogą powodować niekontrolowane skoki i pomijanie wartościowych obszarów.

Wprowadzenie ograniczenia v_max powoduje, że prędkość cząstki jest każdorazowo przycinana według wzoru:

if |v_i| > v_max then v_i ← sign(v_i) * v_max

Efekty zastosowania ograniczenia:

  • Stabilizacja algorytmu – cząstki poruszają się w sposób bardziej kontrolowany i nie „uciekają” z obszaru poszukiwań.
  • Większa precyzja – małe kroki pozwalają dokładniej zbadać obszary w pobliżu lokalnych minimów.
  • Zwiększone ryzyko utknięcia – zbyt niskie v_max może sprawić, że cząstki ugrzęzną w minimum lokalnym i nie będą w stanie się z niego wydostać.

Dobór v_max to kompromis między eksploracją (duże kroki, większe v_max) a eksploatacją (małe kroki, mniejsze v_max). Zazwyczaj wartości v_max są skalowane względem rozmiaru przestrzeni poszukiwań, np. jako 10–20% długości danego wymiaru.

  Poprzedni
Następny