Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja

Boidi a kŕdle, algoritmus PSO, tri zložky rýchlosti, beh na Rastriginovej funkcii v porovnaní s evolučnou stratégiou, úloha zotrvačnosti, stabilita častice, topológia roja a veta o žiadnom obede zadarmo.

13 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 30 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Kŕdeľ škorcov nad večerným mestom sa prelieva ako jediný živý tvor — a pritom nemá vodcu. Každý vták sleduje len pár najbližších susedov. V roku 1995 si sociálny psychológ James Kennedy a elektroinžinier Russell Eberhart položili otázku: čo keby si vtáky okrem polohy susedov odovzdávali aj to, kde našli najviac potravy? Z ich simulácie sa vykľul jeden z najjednoduchších a najpoužívanejších optimalizačných algoritmov vôbec — optimalizácia rojom častíc (particle swarm optimization, PSO).

Nadväzuje na diely Evolučné stratégie a genetické programovanie a Optimalizácia mravčou kolóniou. Pustíme roj na tú istú Rastriginovu funkciu ako evolučnú stratégiu, s rovnakým štartom aj rozpočtom.

1. Kŕdle v prírode a v počítači

Už v roku 1987 ukázal Craig Reynolds, že na uveriteľný pohyb kŕdľa stačia tri miestne pravidlá. Jeho „boidi“ sa vyhýbajú zrážke s najbližšími susedmi, zarovnávajú smer letu s nimi a držia sa pri strede skupiny. Nikto neriadi celok; tvar kŕdľa sa vynorí z miestnych pravidiel. Kennedy s Eberhartom pridali štvrtú vec — pamäť dobrých miest — a z animácie sa stal optimalizátor.

Definícia — tri pravidlá boidov (zjednodušene)

Reynolds pravidlá opísal slovne; dnes sa obvykle zapisujú takto. Nech sa N ≥ 2 boidov pohybuje v ℝⁿ (n = 2 alebo 3) a boid i ∈ {1, …, N} má polohu x_i ∈ ℝⁿ a rýchlosť v_i ∈ ℝⁿ. Nech R > 0 je polomer vnímania a ‖·‖ euklidovská norma. Okolie boidu i je množina

S_i = {j ∈ {1, …, N} : j ≠ i ∧ ‖x_j − x_i‖ < R}.

Ak S_i ≠ ∅, označme priemernú rýchlosť a priemernú polohu susedov

v̄_i = 1/|S_i| ∑_{j ∈ Si} v_j,   x̄_i = 1/|S_i| ∑_{j ∈ Si} x_j.

Boid k svojej rýchlosti v_i pripočíta súčet troch vektorov vynásobených váhami k₁, k₂, k₃ ≥ 0 (pre S_i = ∅ sa rýchlosť nemení):

1. vyhýbanie a_i⁽¹⁾ = −∑_{j ∈ Si} x_j − x_i/‖x_j − x_i‖² — odpudzovanie, tým silnejšie, čím je sused bližšie;
2. zarovnávanie a_i⁽²⁾ = v̄_i − v_i — priblíženie vlastnej rýchlosti k priemernej rýchlosti susedov;
3. súdržnosť a_i⁽³⁾ = x̄_i − x_i — ťah k stredu susedov.

v_i ← v_i + k₁ a_i⁽¹⁾ + k₂ a_i⁽²⁾ + k₃ a_i⁽³⁾,   x_i ← x_i + v_i.

Každý boid teda používa len informácie zo svojho okolia. Rovnice PSO nižšie majú rovnaký tvar „rýchlosť ← rýchlosť + ťahy k cieľom“, len ciele nie sú susedia, ale najlepšie nájdené miesta.

2. Algoritmus

Definícia — optimalizácia rojom častíc

Vstup: účelová funkcia f : ℝⁿ → ℝ, ktorú minimalizujeme (n ≥ 1); počet častíc N ∈ ℕ, N ≥ 1; počet iterácií T ∈ ℕ; zotrvačnosť w ∈ ℝ a koeficienty c₁, c₂ ≥ 0; počiatočné polohy x₁, …, x_N ∈ ℝⁿ a rýchlosti v₁, …, v_N ∈ ℝⁿ (obvykle náhodné v hľadanej oblasti).

Výstup: bod g ∈ ℝⁿ — najlepšia nájdená poloha — a hodnota f(g).

Roj tvorí N častíc; častica i ∈ {1, …, N} má polohu x_i, rýchlosť v_i a svoju doteraz najlepšiu polohu p_i; g je najlepšia poloha celého roja. Súradnice vektora x_i značíme x_id, d = 1, …, n.

1. Inicializácia: p_i ← x_i pre i = 1, …, N a g ← p_k, kde k = arg min_{i ∈ {1, …, N}} f(p_i).
2. Iterácia t = 1, …, T: pre každú časticu i = 1, …, N postupne
   1. pre každú súradnicu d = 1, …, n vylosuj r₁, r₂ nezávisle a rovnomerne z [0, 1) a polož v_id ← w · v_id + c₁ r₁ (p_id − x_id) + c₂ r₂ (g_d − x_id);
   2. x_i ← x_i + v_i;
   3. ak f(x_i) < f(p_i), polož p_i ← x_i; ak navyše f(p_i) < f(g), polož g ← p_i.
3. Zastavenie: po T iteráciách vráť g a f(g).

Vo vektorovom zápise (s náhodnými číslami r₁, r₂ pre každú súradnicu zvlášť) sú prvé dva podkroky iterácie

v_i ← w · v_i + c₁ r₁ (p_i − x_i) + c₂ r₂ (g − x_i),   x_i ← x_i + v_i.

Každá častica teda mení rýchlosť podľa zotrvačnosti, svojho najlepšieho miesta a najlepšieho miesta roja. Obvyklé hodnoty (Clerc a Kennedy, 2002): w = 0,7298, c₁ = c₂ = 1,49618.

v_i ← w · v_i + c₁ r₁ (p_i − x_i) + c₂ r₂ (g − x_i)

v_i vľavo

nová rýchlosť — o toľko sa častica v tomto kroku posunie (x_i ← x_i + v_i); roj neriadi polohu priamo, ale cez rýchlosť, a vďaka tomu má pohyb plynulosť

w · v_i

zotrvačnosť — časť starej rýchlosti zostane; w < 1 ju zároveň tlmí, aby sa pohyb časom upokojil

c₁ r₁, c₂ r₂

sila ťahu — c nastavuje priemernú silu, náhodné r z [0, 1) ju zakaždým inak skráti, takže častica nepristane presne v cieli a cestou ochutná aj miesta okolo

p_i − x_i

vektor od častice k jej najlepšiemu miestu — čím je ďalej, tým silnejšie ju to ťahá späť (ako pružina)

g − x_i

vektor k najlepšiemu miestu roja — jediný kanál, ktorým sa k častici dostane cudzia skúsenosť

Definícia — obmedzenie rýchlosti

Nech v_max > 0. Obmedzenie rýchlosti je úprava algoritmu PSO: v kroku iterácie sa hneď po výpočte novej rýchlosti v_i ∈ ℝⁿ (a pred posunom polohy) nahradí každá jej súradnica d = 1, …, n hodnotou

v_id ← min(v_max, max(−v_max, v_id)),

t. j. súradnica sa oreže do intervalu [−v_max, v_max] (hodnoty vnútri intervalu sa nemenia). Naša implementácia berie v_max = 5,12, teda polovicu šírky hľadaného štvorca [−5,12; 5,12]² — častica nepreletí za jeden krok viac než pol mapy.

Príklad — jeden krok jednej častice

Častica stojí v x = (4,2; −3,8) s rýchlosťou v = (0,5; 0,4). Jej najlepšie miesto je p = (4,0; −3,1), najlepšie miesto roja g = (1,1; −2,0). Padli náhodné čísla r₁ = (0,6; 0,3) a r₂ = (0,5; 0,8). Prvá súradnica (farby podľa vzorca vyššie):

• zotrvačnosť 0,7298 · 0,5 = 0,365,
• kognitívna 1,49618 · 0,6 · (4,0 − 4,2) = −0,180,
• sociálna 1,49618 · 0,5 · (1,1 − 4,2) = −2,319,
• nová rýchlosť 0,365 − 0,180 − 2,319 = −2,134, nová poloha 4,2 − 2,134 = 2,066.

Druhá súradnica rovnako: 0,292 + 0,314 + 2,154 = 2,761, nová poloha −3,8 + 2,761 = −1,039. Obe zložky rýchlosti sú pod v_max, obmedzenie sa neuplatní. Hodnota funkcie (Rastriginovej, pozri nižšie) klesla z 45,90 na 6,51. Sociálna zložka je tu najväčšia, pretože g je ďaleko; kognitívna je malá, pretože p leží len kúsok od častice.

import random

def pso(f, n, castic=40, iteraci=200, w=0.7298, c1=1.49618, c2=1.49618):
    x = [[random.uniform(-5, 5) for _ in range(n)] for _ in range(castic)]
    v = [[0.0] * n for _ in range(castic)]
    p = [xi[:] for xi in x]                              # najlepšie miesto každej častice
    g = min(p, key=f)[:]                                 # najlepšie miesto roja
    for _ in range(iteraci):
        for i in range(castic):
            for d in range(n):
                v[i][d] = (w * v[i][d]
                           + c1 * random.random() * (p[i][d] - x[i][d])
                           + c2 * random.random() * (g[d] - x[i][d]))
                x[i][d] += v[i][d]
            if f(x[i]) < f(p[i]):
                p[i] = x[i][:]
                if f(p[i]) < f(g):
                    g = p[i][:]
    return g

Cena algoritmu sa meria počtom ohodnotení f — pri skutočných úlohách je každé drahé (simulácia, tréning modelu). Každá častica sa ohodnotí na štarte a potom raz za iteráciu, celkom N + N · T = 40 + 40 · 200 = 8 040 pre N = 40 častíc a T = 200 iterácií. (Pseudokód vyššie volá f pre prehľadnosť viackrát; skutočná implementácia si hodnoty f(p_i) pamätá.)

3. Tri sily

• Zotrvačnosť w · v — častica nechce prudko meniť smer. Vďaka nej roj preletí cez plytké jamky, namiesto aby do každej spadol.
• Kognitívna zložka c₁ r₁ (p − x) — vlastná skúsenosť: „tam mi bolo dobre“. Udržuje rozmanitosť, pretože každá častica si pamätá niečo iné.
• Sociálna zložka c₂ r₂ (g − x) — skúsenosť roja: „tam je to najlepšie, čo kto našiel“. Ťahá roj dohromady.

Na rozdiel od genetických algoritmov tu nikto neumiera a nič sa nekríži. Informácia sa šíri len tým, že častice vidia cudzí úspech. A na rozdiel od evolučných stratégií má častica rýchlosť — hybnosť, ktorá ju nesie ďalej, aj keď sa práve nedarí.

4. Roj na Rastriginovej funkcii

Rastriginova funkcia z minulého dielu: misa s pravidelnou mriežkou jamiek, globálne minimum v počiatku. 40 častíc štartuje okolo bodu (4,2; −3,8), kde f ≈ 45,9 — tam, kde štartovala evolučná stratégia:

Definícia — Rastriginova funkcia

Nech n ∈ ℕ, n ≥ 1. Rastriginova funkcia je funkcia f : [−5,12; 5,12]ⁿ → ℝ, ktorá bodu x = (x₁, …, x_n) priradí

f(x) = 10n + ∑_d=1ⁿ (x_d² − 10 cos(2πx_d)).

Je to súčet n rovnakých funkcií jednej premennej posunutý o 10n. Globálne minimum je f(0, …, 0) = 0; lokálne minimá ležia blízko každého bodu s celočíselnými súradnicami, v rozsahu štvorca ich je v dvoch rozmeroch 11 · 11 = 121.

f(x) = 10n + ∑_d (x_d² − 10 cos(2πx_d))

f(x)

hodnota, ktorú roj minimalizuje — testovacia krajina, ktorej minimum poznáme, takže vieme rozpoznať úspech

10n

posun — v počiatku je kosínus 1 a každá súradnica dá −10; tento člen to vyrovná, aby minimum malo hodnotu presne 0

∑_d

súčet cez súradnice — každá prispieva nezávisle, takže s rozmerom počet jamiek rastie exponenciálne (11ⁿ)

x_d²

misa — celkový sklon k počiatku; bez nej by všetky jamky boli rovnako hlboké a žiadne globálne minimum by nebolo

− 10 cos(2πx_d)

zvlnenie s periódou 1 — vyhĺbi jamku pri každom celom čísle a amplitúdou 10 ich urobí dosť hlbokými, aby v nich lokálna metóda uviazla

Príklad — hodnota v štartovacom bode

Pre x = (4,2; −3,8): cos(2π · 4,2) = cos(8,4π) = cos(0,4π) ≈ 0,309 a cos(2π · (−3,8)) = cos(7,6π) = cos(1,6π) ≈ 0,309. Teda (farby podľa vzorca vyššie, n = 2)

f = 20 + (17,64 − 3,090) + (14,44 − 3,090) = 20 + 14,550 + 11,350 ≈ 45,9.

Štart leží na svahu jamky pri (4; −4), kde je f = 20 + (16 − 10) + (16 − 10) = 32; skutočné dno je o chlp bližšie k počiatku, s hodnotou asi 31,84. Hodnota 31,9 po prvej iterácii (nižšie) teda znamená, že roj skĺzol skoro na dno štartovacej jamky. Ďalej k minimu sa dostane len cez hrebene medzi jamkami.

Po prvej iterácii má roj najlepšie miesto s hodnotou 31,9. Potom sa deje niečo, čo evolučná stratégia nerobila: roj sa rozletí. Rozptyl častíc vzrastie z 0,7 na 1,3 v desiatej iterácii — častice prestreľujú svoje najlepšie miesta a cestou objavujú nové jamky. V 25. iterácii je najlepšie miesto na hodnote 1,06, jednu jamku vedľa minima, a v 50. iterácii roj nájde globálne minimum. Potom sa sťahuje k nemu.

Definícia — rozptyl roja a úspešný beh

Nech x₁, …, x_N ∈ ℝⁿ (N ≥ 1) sú polohy častíc roja v jednej iterácii a ‖·‖ je euklidovská norma. Ťažisko roja je bod

x̄ = 1/N ∑_i=1^N x_i

a rozptyl roja je číslo

σ = √1/N ∑_i=1^N ‖x_i − x̄‖² ≥ 0,

teda odmocnina z priemerného štvorca vzdialenosti častíc od ťažiska.

Nech g je najlepšie miesto roja po poslednej iterácii behu na Rastriginovej funkcii f. Beh našiel globálne minimum práve vtedy, keď f(g) < 0,01 (prah je naša voľba pre tento diel). Najbližšie lokálne minimá majú hodnotu okolo 1 (preto 1,06 v 25. iterácii znamená „jamka vedľa“), takže tento prah ich od nich jasne odlíši.

σ = √1/N ∑_i ‖x_i − x̄‖²

σ

jedno číslo pre „aký rozletený je roj“ — v jednotkách súradníc, takže ho možno porovnať so vzdialenosťou jamiek (1)

1/N ∑_i

priemer cez častice — výsledok nezávisí od veľkosti roja

‖x_i − x̄‖²

štvorec vzdialenosti od ťažiska — meriame od stredu roja, nie od minima, pretože nás zaujíma tvar roja, nie to, kde je; štvorec viac váži odľahlých prieskumníkov a odmocnina potom vráti pôvodné jednotky

Trasovanie toho istého behu po iteráciách:

Štyri iterácie sa najlepšia hodnota nepohne a roj sa medzitým sťahuje do štartovacej jamky (v tretej iterácii je σ len 0,53); potom ho zotrvačnosť a ťahy k g znova roztiahnu a najlepšia hodnota padá po jamkách — 31,9, 25,6, 5,9, 1,06. Minimum je nájdené v 50. iterácii, ale σ je vtedy stále 0,96: roj sa okolo minima zbalí až potom.

Zo sto behov s rôznymi semienkami našiel roj globálne minimum v 97 — s rozpočtom 8 040 ohodnotení. Evolučná stratégia (15, 100) s 8 000 ohodnoteniami tej istej úlohy uspela v 32 prípadoch. Keď roj namiesto z rohu štartuje rozprestretý po celom štvorci, uspeje vo všetkých sto.

5. Zotrvačnosť a rovnováha síl

Čo sa stane, keď zmeníme len zotrvačnosť? Graf ukazuje, ako ďaleko od seba sú častice (zvislá os je logaritmická):

S w = 0,4 sa roj zrúti do jediného bodu skôr, než sa stihne rozhliadnuť — uviazne v jamke s hodnotou 24,9. S w = 0,9 zostane rozletený stále: minimum nájde, ale nikdy sa okolo neho nezbalí a nedopiluje ho. Zo sto behov pre každé nastavenie:

Bez sociálnej zložky je roj len štyridsať osamelých horolezcov, ktorí o sebe nevedia — žiadny sa z rohu nedostane. Bez kognitívnej sa všetci ženú za jediným vodcom a polovicu času uviaznu s ním. Až obe zložky dohromady dávajú rovnováhu medzi prieskumom a využívaním, ktorú sme stretli už pri žíhaní.

6. Prečo roj nezdivie

Rýchlosť sa stále sčítava. Prečo nerastie do nekonečna? Odpoveď dá rozbor jednej častice, keď na chvíľu zabudneme na náhodu.

Veta — stabilita častice

Uvažujme jednorozmernú časticu bez náhody. Nech p, g ∈ ℝ sú pevné najlepšie miesta (častice a roja), w ∈ ℝ je zotrvačnosť a φ₁, φ₂ ∈ ℝ pevné čísla na mieste c₁r₁, c₂r₂, pričom φ = φ₁ + φ₂ ≠ 0. Označme

P = φ₁p + φ₂g/φ

(vážený priemer p a g). Nech polohy x₀, x₁, x₂, … ∈ ℝ spĺňajú pre každé t ≥ 1 lineárnu rekurenciu

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP.

Potom lim_{t → ∞} x_t = P pre každú voľbu počiatočných polôh x₀, x₁ ∈ ℝ práve vtedy, keď

1. |w| < 1   a
2. 0 < φ < 2(1 + w).

Dôkaz — odkiaľ sa rekurencia a podmienky berú

Bez náhody je jednorozmerný krok v_t+1 = wv_t + φ₁(p − x_t) + φ₂(g − x_t) a x_t+1 = x_t + v_t+1. S φ = φ₁ + φ₂ a P = φ₁p + φ₂g/φ z vety je φ₁(p − x) + φ₂(g − x) = φ(P − x) a po dosadení v_t = x_t − x_t−1:

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP.

Odchýlka e_t = x_t − P spĺňa tú istú rekurenciu bez konštanty, takže e_t = C₁λ₁^t + C₂λ₂^t, kde λ_1,2 sú korene charakteristickej rovnice λ² − (1 + w − φ)λ + w = 0 (pri dvojnásobnom koreni e_t = (C₁ + C₂t)λ₁^t) a konštanty C₁, C₂ možno voľbou x₀, x₁ nastaviť ľubovoľne. Preto e_t → 0 pre všetky počiatočné polohy práve vtedy, keď |λ₁| < 1 a |λ₂| < 1. Pre kvadratickú rovnicu λ² + aλ + b = 0 s reálnymi a, b to nastane práve vtedy, keď |b| < 1 a 1 ± a + b > 0 (Juryho kritérium). Tu b = w, a = −(1 + w − φ):

• |w| < 1,
• 1 − (1 + w − φ) + w = φ > 0,
• 1 + (1 + w − φ) + w = 2(1 + w) − φ > 0. ∎

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP

x_t+1

budúca poloha — závisí od dvoch predchádzajúcich, pretože rýchlosť je rozdiel dvoch polôh; preto sa častica správa ako kmitajúce teleso, nie ako guľa kotúľajúca sa po svahu

(1 + w − φ) x_t

súčasná poloha posunutá zotrvačnosťou (+w) a stiahnutá príťažlivosťou (−φ) — súboj „letieť ďalej“ proti „vrátiť sa“

− w x_t−1

pamäť minulého kroku — tento člen prináša hybnosť; jeho koeficient w je súčin koreňov, a preto tlmenie určuje práve zotrvačnosť

φP

kotva — príťažlivosť váženého priemeru p a g; okolo neho častica kmitá a do neho sa usadí

Ako rýchlo sa usadí? Pre obvyklé φ vychádzajú oba korene komplexné (častica kmitá) a majú rovnakú absolútnu hodnotu √w, pretože ich súčin je w. Amplitúda odchýlky sa teda každou iteráciou vynásobí číslom √w a na polovicu klesne za ln 2/−ln √w iterácií. S priemerným φ = c₁ + c₂/2 = 1,49618 (náhodné r má priemer 1/2):

To presne zodpovedá grafu rozptylu vyššie: s w = 0,4 sa roj zbalí za pár iterácií, s w = 0,9 kmity doznievajú desiatky iterácií. Ide o zjednodušenie — skutočné r sa losujú v každom kroku a p, g sa menia —, ale rád sedí. A pozor: s w = 0,4 je hranica 2(1 + w) = 2,8 menšia než najväčšie možné φ = c₁ + c₂ ≈ 2,99, takže výnimočne silný náhodný ťah časticu na jeden krok rozhojdá (útlm 1,280 > 1).

7. Kto koho počuje: topológia

Definícia — topológia roja

Nech roj tvorí N ≥ 3 častíc očíslovaných 1, …, N, s doteraz najlepšími polohami p₁, …, p_N, a f je minimalizovaná funkcia. Topológia roja je neorientovaný graf G = ({1, …, N}, E) na množine častíc; určuje, čie najlepšie miesta častica vidí. Okolie častice i je množina

S(i) = {i} ∪ {j : {i, j} ∈ E}

a najlepšie miesto okolia je g_i = p_k, kde k = arg min_{j ∈ S(i)} f(p_j). V pravidle rýchlosti častice i sa namiesto g použije g_i. Dve bežné topológie:

1. globálna (gbest): G je úplný graf, t. j. S(i) = {1, …, N} pre každé i; potom g_i = g je spoločné všetkým;
2. kruhová (lbest): E = {{i, i + 1} : i = 1, …, N} s indexmi modulo N (N + 1 ≡ 1), t. j. S(i) = {i − 1, i, i + 1} (0 ≡ N).

V globálnej topológii teda každá častica vidí všetky, v kruhovej len svojich dvoch susedov v kruhu.

Formálne má každá častica i okolie S(i) a v pravidle rýchlosti namiesto spoločného g používa g_i = p_k, kde k = arg min_{j ∈ S(i)} f(p_j). Globálna topológia má S(i) = {1, …, N}, kruhová S(i) = {i − 1, i, i + 1} (indexy modulo N). Koľko iterácií trvá, kým sa správa o novom náleze dostane ku všetkým? V globálnej topológii jedna. V kruhu postúpi za iteráciu najviac o jedného suseda na každú stranu, a najvzdialenejšia častica v kruhu 40 častíc je 20 miest ďaleko — správa k nej dorazí najskôr za 20 iterácií. Tak dlho môžu vzdialené časti roja skúmať po svojom.

Na našej dvojrozmernej úlohe našiel kruh minimum vo všetkých 100 behoch, globálna topológia v 97. Rozdiel je zreteľnejší v desiatich rozmeroch, kde je jamiek astronomicky veľa: po 2 000 iteráciách skončila globálna topológia v priemere na hodnote 5,84, kruhová na 4,57. Globálne minimum nenašla ani jedna — desaťrozmerná Rastriginova funkcia je pre 40 častíc naozaj ťažká.

8. Pozor na metafory

Veta — žiadny obed zadarmo (Wolpert a Macready, 1997)

Spriemerované cez všetky možné účelové funkcie na konečnej množine majú všetky algoritmy, ktoré nevyhodnocujú ten istý bod dvakrát, rovnaký očakávaný výkon.

Presnejšie: nech X a Y sú konečné neprázdne množiny a 𝓕 = Y^X množina všetkých funkcií f : X → Y (je ich |Y|^|X|). Algoritmus a v každom kroku na základe doteraz videných dvojíc (x, f(x)) zvolí bod x ∈ X, ktorý ešte nevyhodnotil, a zistí f(x). Nech m ∈ {1, …, |X|} a d_m^y = (y₁, …, y_m) ∈ Y^m je postupnosť hodnôt, ktoré algoritmus uvidí počas prvých m ohodnotení. Potom pre ľubovoľné dva také algoritmy a₁, a₂ a každú postupnosť d_m^y ∈ Y^m platí

∑_{f ∈ 𝓕} P(d_m^y | f, m, a₁) = ∑_{f ∈ 𝓕} P(d_m^y | f, m, a₂),

kde P(d_m^y | f, m, a) je pravdepodobnosť, že algoritmus a na funkcii f uvidí práve postupnosť d_m^y (pri deterministickom algoritme 0 alebo 1).

Sčítava sa teda cez všetkých |Y|^|X| funkcií. Každá miera výkonu, ktorá závisí len od videných hodnôt (napríklad najlepšia nájdená), má teda cez všetky funkcie rovnaký priemer.

Po úspechu mravcov a roja sa roztrhlo vrece s algoritmami „inšpirovanými prírodou“: svätojánske mušky, kukučky, netopiere, sivé vlky, harmónia v jazzovej kapele. Kenneth Sörensen v roku 2015 upozornil, že mnohé z nich sú staré myšlienky v novom kostýme — metafora nahradila matematický opis a sťažila porovnanie. Dobrá otázka pri každom novom algoritme preto neznie „čím je inšpirovaný“, ale „čo robí inak než tie známe a na čom je to vidieť“.

9. Roje v praxi

• Ladenie parametrov. PSO je obľúbené tam, kde je parametrov málo, gradient nepoznáme a jedno ohodnotenie je simulácia: nastavenie regulátorov, tvar antén, riadenie energetických sietí alebo hyperparametre modelov strojového učenia.
• Roboty v roji. Na Harvarde v roku 2014 zložilo 1 024 malých robotov Kilobot podľa miestnych pravidiel zadané tvary — bez centrálneho riadenia, len komunikáciou so susedmi.
• A čo drony na ohňostrojoch? Svetelné show s tisíckami dronov nie sú inteligencia roja: každý dron letí po vopred vypočítanej dráhe z centrálneho plánu. Roj v pravom zmysle sa rozhoduje sám, podľa susedov.

10. Zhrnutie

• Častica v PSO mení rýchlosť podľa zotrvačnosti, vlastného najlepšieho miesta a najlepšieho miesta roja.
• Na Rastriginovej funkcii našiel roj minimum v 97 zo 100 behov — evolučná stratégia s rovnakým štartom a rozpočtom v 32.
• Zotrvačnosť riadi, ako dlho roj skúma: malá ho zrúti predčasne, veľká mu nedovolí doladiť výsledok. Bez sociálnej aj bez kognitívnej zložky roj zlyháva.
• Častica je ako tlmená pružina; pre |w| < 1 a 0 < φ < 2(1 + w) sa usadí.
• Kruhová topológia šíri informáciu pomalšie a na ťažkých úlohách býva robustnejšia; a podľa vety o žiadnom obede zadarmo neexistuje optimalizátor najlepší na všetko.

Chcete si to vyskúšať? Nechajte AI agenta napísať PSO s vizualizáciou roja a skúste mu dať vlastnú krajinu — napríklad funkciu s dvoma vzdialenými údoliami — a sledujte, či sa roj rozdelí.

Máte na to iný názor? Napíšte na support@coden-app.com.