Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna

Boidi a hejna, algoritmus PSO, tři složky rychlosti, běh na Rastriginově funkci ve srovnání s evoluční strategií, role setrvačnosti, stabilita částice, topologie hejna a věta o žádném obědu zdarma.

13 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 30 z 83

1. Mapa umělé inteligence: co je co a jak to do sebe zapadá
2. Stručná historie umělé inteligence: od Turinga po jazykové modely
3. Data, model, trénink, inference: základní pojmy na jednom příkladu
4. Jak číst matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relace: stavebnice, ze které se skládají definice v AI
6. Funkce a zobrazení: proč je každý model v AI funkce
7. Logika a důkazy: pravidla, podle kterých se v AI uvažuje
8. Grafy a stromy: struktura, na které stojí hledání i neuronové sítě
9. Lineární algebra pro strojové učení: vektory, matice a proč AI hlavně násobí
10. Derivace, gradient a řetízkové pravidlo: jak model zjistí, kterým směrem se učit
11. Gradientní sestup: jak se model učí
12. Co je pravděpodobnost: od hodu kostkou ke Kolmogorovovým axiomům
13. Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového
14. Náhodná veličina a distribuční funkce: jedna funkce, která o rozdělení řekne všechno
15. Funkce hustoty a pravděpodobnostní funkce: proč má spojitá veličina v bodě pravděpodobnost nula
16. Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí
17. Přehled pravděpodobnostních rozdělení: Bernoulli, binomické, Poisson, rovnoměrné, normální a exponenciální
18. Zákon velkých čísel a centrální limitní věta: proč se průměry chovají tak předvídatelně
19. Statistika a odhady parametrů: maximální věrohodnost, MAP a intervaly spolehlivosti
20. Teorie informace: entropie, křížová entropie a KL divergence — odkud se berou ztrátové funkce
21. Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi
22. Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search
23. Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů
24. Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy
25. Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech
26. Lokální hledání a simulované žíhání: obchodní cestující přes krajská města
27. Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet
28. Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon
29. Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu
30. Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna
31. Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT
32. Fuzzy množiny a funkce příslušnosti: jak zapsat „trochu teplo“
33. Fuzzy logika a pravděpodobnost: proč „trochu teplo“ neznamená „pravděpodobně teplo“
34. Fuzzy logika: t-normy, implikace a pravidla KDYŽ–PAK
35. Fuzzy řízení: Mamdani a Sugeno od ventilátoru po kyvadlo na vozíku
36. Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidla, která se učí z dat
38. Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank
39. Skryté Markovovy modely: Viterbiho algoritmus a nepoctivé kasino
40. Bayesovské sítě: proč je tráva mokrá a co z toho plyne pro postřikovač
41. Kalmanův filtr: jak z nepřesných měření odhadnout, kde auto je a jak rychle jede
42. Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další
43. Přeučení a regularizace: proč model, který zná data nazpaměť, selže
44. Vyhodnocení modelu: křížová validace, F1 a křivka ROC
45. Shlukování a snížení dimenze: k-means, PCA a t-SNE
46. Klasifikace a regrese: dvě úlohy učení s učitelem
47. Lineární regrese: nejmenší čtverce geometricky i maticově
48. Polynomiální a nelineární regrese: jak přímku ohnout
49. Logistická regrese: sigmoida, šance a křížová entropie
50. Vícetřídní klasifikace a softmax: od dvou tříd k mnoha
51. Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl
52. Ztrátové funkce: co přesně model minimalizuje
53. Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců
54. Ansámbly: náhodný les a gradient boosting
55. SVM a jádrový trik: nejširší hranice a jak ji ohnout
56. Signál a vzorkování: proč platí Nyquistův teorém
57. Fourierova transformace: rozklad signálu na frekvence
58. Filtry a konvoluce: vyhlazení, hrany a odstranění šumu
59. Zvuk a řeč: spektrogram, melová škála a MFCC
60. Obraz jako signál: pixely, barvy, konvoluce a hrany
61. Perceptron a umělý neuron: nejjednodušší neuronová síť a co neumí
62. Neuronová síť od nuly: zpětné šíření chyby krok za krokem
63. Aktivace, inicializace a normalizace: drobnosti, na kterých hluboká síť stojí
64. Konvoluční sítě: jak síť poznává obrázky
65. Rekurentní sítě: paměť pro posloupnosti a mizející gradient
66. LSTM a GRU: brány, které rozhodují, co si síť zapamatuje
67. Autoenkodéry: síť, která se učí data stlačit a zase rozbalit
68. Embeddingy a word2vec: jak se slovo stane vektorem
69. Mechanismus pozornosti: jak se model naučí, kam se dívat
70. Transformery a velké jazykové modely: architektura krok za krokem
71. Tokenizace: jak se text rozseká na kousky pro model
72. Předtrénování a škálování: proč větší model a víc dat funguje
73. Doladění a RLHF: jak se z doplňovače textu stane asistent
74. Prompty, kontext a RAG: jak modelu dát správné informace
75. Variační autoenkodéry (VAE): nové obrázky ze spojitého latentního prostoru
76. Generativní adversariální sítě (GAN): padělatel proti detektivovi
77. Difúzní modely: jak se z čistého šumu stane obrázek
78. Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice
79. Q-learning a DQN: učení hodnoty akcí od tabulky po neuronovou síť
80. Policy gradient a PPO: učení přímo strategie
81. Jak funguje AI agent: jazykový model ve smyčce s nástroji
82. Programování s AI agenty: zadání, testy a kontrola
83. Vyhodnocení a bezpečnost AI systémů: jak měřit a jak hlídat

Celá osnova série 83 z 83 témat hotovo

Hejno špačků nad večerním městem se přelévá jako jediný živý tvor — a přitom nemá vůdce. Každý pták sleduje jen pár nejbližších sousedů. V roce 1995 si sociální psycholog James Kennedy a elektroinženýr Russell Eberhart položili otázku: co kdyby si ptáci kromě polohy sousedů předávali i to, kde našli nejvíc potravy? Z jejich simulace se vyklubal jeden z nejjednodušších a nejpoužívanějších optimalizačních algoritmů vůbec — optimalizace hejnem částic (particle swarm optimization, PSO).

Navazuje na díly Evoluční strategie a genetické programování a Optimalizace mravenčí kolonií. Pustíme hejno na stejnou Rastriginovu funkci jako evoluční strategii, se stejným startem i rozpočtem.

1. Hejna v přírodě a v počítači

Už v roce 1987 ukázal Craig Reynolds, že k uvěřitelnému pohybu hejna stačí tři místní pravidla. Jeho „boidi“ se vyhýbají srážce s nejbližšími sousedy, srovnávají směr letu s nimi a drží se u středu skupiny. Nikdo neřídí celek; tvar hejna se vynoří z místních pravidel. Kennedy s Eberhartem přidali čtvrtou věc — paměť dobrých míst — a z animace se stal optimalizátor.

Definice — tři pravidla boidů (zjednodušeně)

Reynolds pravidla popsal slovně; dnes se obvykle zapisují takto. Nechť N ≥ 2 boidů se pohybuje v ℝⁿ (n = 2 nebo 3) a boid i ∈ {1, …, N} má polohu x_i ∈ ℝⁿ a rychlost v_i ∈ ℝⁿ. Nechť R > 0 je poloměr vnímání a ‖·‖ eukleidovská norma. Okolí boidu i je množina

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

Je-li S_i ≠ ∅, označme průměrnou rychlost a průměrnou polohu sousedů

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

Boid ke své rychlosti v_i přičte součet tří vektorů vynásobených vahami k₁, k₂, k₃ ≥ 0 (pro S_i = ∅ se rychlost nemění):

1. vyhýbání a_i⁽¹⁾ = −∑_{j ∈ Si} x_j − x_i/‖x_j − x_i‖² — odpuzování, tím silnější, čím je soused blíž;
2. srovnávání a_i⁽²⁾ = v̄_i − v_i — přiblížení vlastní rychlosti k průměrné rychlosti sousedů;
3. soudržnost a_i⁽³⁾ = x̄_i − x_i — tah ke středu sousedů.

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

Každý boid tedy používá jen informace ze svého okolí. Rovnice PSO níže mají stejný tvar „rychlost ← rychlost + tahy k cílům“, jen cíle nejsou sousedé, ale nejlepší nalezená místa.

2. Algoritmus

Definice — optimalizace hejnem částic

Vstup: účelová funkce f : ℝⁿ → ℝ, kterou minimalizujeme (n ≥ 1); počet částic N ∈ ℕ, N ≥ 1; počet iterací T ∈ ℕ; setrvačnost w ∈ ℝ a koeficienty c₁, c₂ ≥ 0; počáteční polohy x₁, …, x_N ∈ ℝⁿ a rychlosti v₁, …, v_N ∈ ℝⁿ (obvykle náhodné v hledané oblasti).

Výstup: bod g ∈ ℝⁿ — nejlepší nalezená poloha — a hodnota f(g).

Hejno tvoří N částic; částice i ∈ {1, …, N} má polohu x_i, rychlost v_i a svou dosud nejlepší polohu p_i; g je nejlepší poloha celého hejna. Souřadnice vektoru x_i značíme x_id, d = 1, …, n.

1. Inicializace: p_i ← x_i pro i = 1, …, N a g ← p_k, kde k = arg min_{i ∈ {1, …, N}} f(p_i).
2. Iterace t = 1, …, T: pro každou částici i = 1, …, N postupně
   1. pro každou souřadnici d = 1, …, n vylosuj r₁, r₂ nezávisle a rovnoměrně 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. je-li f(x_i) < f(p_i), polož p_i ← x_i; je-li navíc f(p_i) < f(g), polož g ← p_i.
3. Zastavení: po T iteracích vrať g a f(g).

Ve vektorovém zápisu (s náhodnými čísly r₁, r₂ pro každou souřadnici zvlášť) jsou první dva podkroky iterace

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

Každá částice tedy mění rychlost podle setrvačnosti, svého nejlepšího místa a nejlepšího místa hejna. 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 vlevo

nová rychlost — o tolik se částice v tomto kroku posune (x_i ← x_i + v_i); hejno neřídí polohu přímo, ale přes rychlost, a díky tomu má pohyb plynulost

w · v_i

setrvačnost — část staré rychlosti zůstane; w < 1 ji zároveň tlumí, aby se pohyb časem uklidnil

c₁ r₁, c₂ r₂

síla tahu — c nastavuje průměrnou sílu, náhodné r z [0, 1) ji pokaždé jinak zkrátí, takže částice nepřistane přesně v cíli a cestou ochutná i místa okolo

p_i − x_i

vektor od částice k jejímu nejlepšímu místu — čím je dál, tím silněji ji to táhne zpátky (jako pružina)

g − x_i

vektor k nejlepšímu místu hejna — jediný kanál, kterým se k částici dostane cizí zkušenost

Definice — omezení rychlosti

Nechť v_max > 0. Omezení rychlosti je úprava algoritmu PSO: v kroku iterace se hned po výpočtu nové rychlosti v_i ∈ ℝⁿ (a před posunem polohy) nahradí každá její souřadnice d = 1, …, n hodnotou

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

tj. souřadnice se ořízne do intervalu [−v_max, v_max] (hodnoty uvnitř intervalu se nemění). Naše implementace bere v_max = 5,12, tedy polovinu šířky hledaného čtverce [−5,12; 5,12]² — částice nepřeletí za jeden krok víc než půl mapy.

Příklad — jeden krok jedné částice

Částice stojí v x = (4,2; −3,8) s rychlostí v = (0,5; 0,4). Její nejlepší místo je p = (4,0; −3,1), nejlepší místo hejna g = (1,1; −2,0). Padla náhodná čísla r₁ = (0,6; 0,3) a r₂ = (0,5; 0,8). První souřadnice (barvy podle vzorce výše):

• setrvačnost 0,7298 · 0,5 = 0,365,
• kognitivní 1,49618 · 0,6 · (4,0 − 4,2) = −0,180,
• sociální 1,49618 · 0,5 · (1,1 − 4,2) = −2,319,
• nová rychlost 0,365 − 0,180 − 2,319 = −2,134, nová poloha 4,2 − 2,134 = 2,066.

Druhá souřadnice stejně: 0,292 + 0,314 + 2,154 = 2,761, nová poloha −3,8 + 2,761 = −1,039. Obě složky rychlosti jsou pod v_max, omezení se neuplatní. Hodnota funkce (Rastriginovy, viz níže) klesla z 45,90 na 6,51. Sociální složka je tu největší, protože g je daleko; kognitivní je malá, protože p leží jen kousek od částice.

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]                              # nejlepší místo každé částice
    g = min(p, key=f)[:]                                 # nejlepší místo hejna
    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 se měří počtem ohodnocení f — u skutečných úloh je každé drahé (simulace, trénink modelu). Každá částice se ohodnotí na startu a pak jednou za iteraci, celkem N + N · T = 40 + 40 · 200 = 8 040 pro N = 40 částic a T = 200 iterací. (Pseudokód výše volá f pro přehlednost víckrát; skutečná implementace si hodnoty f(p_i) pamatuje.)

3. Tři síly

• Setrvačnost w · v — částice nechce prudce měnit směr. Díky ní hejno přelétne přes mělké důlky, místo aby do každého spadlo.
• Kognitivní složka c₁ r₁ (p − x) — vlastní zkušenost: „tam mi bylo dobře“. Udržuje rozmanitost, protože každá částice si pamatuje něco jiného.
• Sociální složka c₂ r₂ (g − x) — zkušenost hejna: „tam je to nejlepší, co kdo našel“. Táhne hejno dohromady.

Na rozdíl od genetických algoritmů tu nikdo neumírá a nic se nekříží. Informace se šíří jen tím, že částice vidí cizí úspěch. A na rozdíl od evolučních strategií má částice rychlost — hybnost, která ji nese dál, i když se zrovna nedaří.

4. Hejno na Rastriginově funkci

Rastriginova funkce z minulého dílu: koule s pravidelnou mřížkou důlků, globální minimum v počátku. 40 částic startuje kolem bodu (4,2; −3,8), kde f ≈ 45,9 — tam, kde startovala evoluční strategie:

Definice — Rastriginova funkce

Nechť n ∈ ℕ, n ≥ 1. Rastriginova funkce je funkce f : [−5,12; 5,12]ⁿ → ℝ, která bodu x = (x₁, …, x_n) přiřadí

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

Je to součet n stejných funkcí jedné proměnné posunutý o 10n. Globální minimum je f(0, …, 0) = 0; lokální minima leží poblíž každého bodu s celočíselnými souřadnicemi, v rozsahu čtverce jich je ve dvou rozměrech 11 · 11 = 121.

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

f(x)

hodnota, kterou hejno minimalizuje — testovací krajina, jejíž minimum známe, takže umíme poznat úspěch

10n

posun — v počátku je kosinus 1 a každá souřadnice dá −10; tenhle člen to vyrovná, aby minimum mělo hodnotu přesně 0

∑_d

součet přes souřadnice — každá přispívá nezávisle, takže s rozměrem počet důlků roste exponenciálně (11ⁿ)

x_d²

miska — celkový sklon k počátku; bez ní by všechny důlky byly stejně hluboké a žádné globální minimum by nebylo

− 10 cos(2πx_d)

zvlnění s periodou 1 — vyhloubí důlek u každého celého čísla a amplitudou 10 je udělá dost hlubokými, aby v nich lokální metoda uvízla

Příklad — hodnota ve startovním bodě

Pro 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. Tedy (barvy podle vzorce výše, n = 2)

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

Start leží na svahu důlku u (4; −4), kde je f = 20 + (16 − 10) + (16 − 10) = 32; skutečné dno je o chlup blíž k počátku, s hodnotou asi 31,84. Hodnota 31,9 po první iteraci (níže) tedy znamená, že hejno sjelo skoro na dno startovního důlku. Dál k minimu se dostane jen přes hřebeny mezi důlky.

Po první iteraci má hejno nejlepší místo s hodnotou 31,9. Pak se děje něco, co evoluční strategie nedělala: hejno se rozletí. Rozptyl částic vzroste z 0,7 na 1,3 v desáté iteraci — částice přestřelují svá nejlepší místa a cestou objevují nové důlky. V 25. iteraci je nejlepší místo na hodnotě 1,06, jeden důlek vedle minima, a v 50. iteraci hejno najde globální minimum. Pak se stahuje k němu.

Definice — rozptyl hejna a úspěšný běh

Nechť x₁, …, x_N ∈ ℝⁿ (N ≥ 1) jsou polohy částic hejna v jedné iteraci a ‖·‖ je eukleidovská norma. Těžiště hejna je bod

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

a rozptyl hejna je číslo

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

tedy odmocnina z průměrného čtverce vzdálenosti částic od těžiště.

Nechť g je nejlepší místo hejna po poslední iteraci běhu na Rastriginově funkci f. Běh našel globální minimum, právě když f(g) < 0,01 (práh je naše volba pro tento díl). Nejbližší lokální minima mají hodnotu kolem 1 (proto 1,06 v 25. iteraci znamená „důlek vedle“), takže tenhle práh je od nich jasně odliší.

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

σ

jedno číslo pro „jak rozlétnuté je hejno“ — v jednotkách souřadnic, takže ho lze srovnat se vzdáleností důlků (1)

1/N ∑_i

průměr přes částice — výsledek nezávisí na velikosti hejna

‖x_i − x̄‖²

čtverec vzdálenosti od těžiště — měříme od středu hejna, ne od minima, protože nás zajímá tvar hejna, ne to, kde je; čtverec víc váží odlehlé průzkumníky a odmocnina pak vrátí původní jednotky

Trasování téhož běhu po iteracích:

Čtyři iterace se nejlepší hodnota nehne a hejno se mezitím stahuje do startovního důlku (ve třetí iteraci je σ jen 0,53); pak ho setrvačnost a tahy k g znovu roztáhnou a nejlepší hodnota padá po důlcích — 31,9, 25,6, 5,9, 1,06. Minimum je nalezené v 50. iteraci, ale σ je tehdy pořád 0,96: hejno se kolem minima sbaluje až potom.

Ze sta běhů s různými semínky našlo hejno globální minimum v 97 — s rozpočtem 8 040 ohodnocení. Evoluční strategie (15, 100) s 8 000 ohodnoceními stejné úlohy uspěla ve 32 případech. Když hejno místo z rohu startuje rozprostřené po celém čtverci, uspěje ve všech stovce.

5. Setrvačnost a rovnováha sil

Co se stane, když změníme jen setrvačnost? Graf ukazuje, jak daleko od sebe jsou částice (svislá osa je logaritmická):

S w = 0,4 se hejno zhroutí do jediného bodu dřív, než se stihne rozhlédnout — uvízne v důlku s hodnotou 24,9. S w = 0,9 zůstane rozlétnuté pořád: minimum najde, ale nikdy se kolem něj nesbalí a nedopiluje ho. Ze sta běhů pro každé nastavení:

Bez sociální složky je hejno jen čtyřicet osamělých horolezců, kteří o sobě nevědí — žádný se z rohu nedostane. Bez kognitivní se všichni ženou za jediným vůdcem a polovinu času uvíznou s ním. Teprve obě složky dohromady dávají rovnováhu mezi průzkumem a využíváním, kterou jsme potkali už u žíhání.

6. Proč hejno nezdivočí

Rychlost se pořád sčítá. Proč neroste do nekonečna? Odpověď dá rozbor jedné částice, když na chvíli zapomeneme na náhodu.

Věta — stabilita částice

Uvažujme jednorozměrnou částici bez náhody. Nechť p, g ∈ ℝ jsou pevná nejlepší místa (částice a hejna), w ∈ ℝ je setrvačnost a φ₁, φ₂ ∈ ℝ pevná čísla na místě c₁r₁, c₂r₂, přičemž φ = φ₁ + φ₂ ≠ 0. Označme

P = φ₁p + φ₂g/φ

(vážený průměr p a g). Nechť polohy x₀, x₁, x₂, … ∈ ℝ splňují pro každé t ≥ 1 lineární rekurenci

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

Pak lim_{t → ∞} x_t = P pro každou volbu počátečních poloh x₀, x₁ ∈ ℝ, právě když

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

Důkaz — odkud se rekurence a podmínky berou

Bez náhody je jednorozměrný 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 věty je φ₁(p − x) + φ₂(g − x) = φ(P − x) a po dosazení v_t = x_t − x_t−1:

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

Odchylka e_t = x_t − P splňuje tutéž rekurenci bez konstanty, takže e_t = C₁λ₁^t + C₂λ₂^t, kde λ_1,2 jsou kořeny charakteristické rovnice λ² − (1 + w − φ)λ + w = 0 (při dvojnásobném kořeni e_t = (C₁ + C₂t)λ₁^t) a konstanty C₁, C₂ lze volbou x₀, x₁ nastavit libovolně. Proto e_t → 0 pro všechny počáteční polohy, právě když |λ₁| < 1 a |λ₂| < 1. Pro kvadratickou rovnici λ² + aλ + b = 0 s reálnými a, b to nastane, právě když |b| < 1 a 1 ± a + b > 0 (Juryho kritérium). Tady 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

příští poloha — závisí na dvou předchozích, protože rychlost je rozdíl dvou poloh; proto se částice chová jako kmitající těleso, ne jako koule kutálející se po svahu

(1 + w − φ) x_t

současná poloha posunutá setrvačností (+w) a stažená přitažlivostí (−φ) — souboj „letět dál“ proti „vrátit se“

− w x_t−1

paměť minulého kroku — tenhle člen přináší hybnost; jeho koeficient w je součin kořenů, a proto tlumení určuje právě setrvačnost

φP

kotva — přitažlivost váženého průměru p a g; kolem něj částice kmitá a do něj se usadí

Jak rychle se usadí? Pro obvyklé φ vycházejí oba kořeny komplexní (částice kmitá) a mají stejnou absolutní hodnotu √w, protože jejich součin je w. Amplituda odchylky se tedy každou iterací vynásobí číslem √w a na polovinu klesne za ln 2/−ln √w iterací. S průměrným φ = c₁ + c₂/2 = 1,49618 (náhodné r má průměr 1/2):

To přesně odpovídá grafu rozptylu výše: s w = 0,4 se hejno sbalí za pár iterací, s w = 0,9 kmity doznívají desítky iterací. Jde o zjednodušení — skutečné r se losují v každém kroku a p, g se mění —, ale řád sedí. A pozor: s w = 0,4 je mez 2(1 + w) = 2,8 menší než největší možné φ = c₁ + c₂ ≈ 2,99, takže výjimečně silný náhodný tah částici na jeden krok rozhoupe (útlum 1,280 > 1).

7. Kdo koho slyší: topologie

Definice — topologie hejna

Nechť hejno tvoří N ≥ 3 částic očíslovaných 1, …, N, s dosud nejlepšími polohami p₁, …, p_N, a f je minimalizovaná funkce. Topologie hejna je neorientovaný graf G = ({1, …, N}, E) na množině částic; určuje, čí nejlepší místa částice vidí. Okolí částice i je množina

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

a nejlepší místo okolí je g_i = p_k, kde k = arg min_{j ∈ S(i)} f(p_j). V pravidle rychlosti částice i se místo g použije g_i. Dvě běžné topologie:

1. globální (gbest): G je úplný graf, tj. S(i) = {1, …, N} pro každé i; pak g_i = g je společné všem;
2. kruhová (lbest): E = {{i, i + 1} : i = 1, …, N} s indexy modulo N (N + 1 ≡ 1), tj. S(i) = {i − 1, i, i + 1} (0 ≡ N).

V globální topologii tedy každá částice vidí všechny, v kruhové jen své dva sousedy v kruhu.

Formálně má každá částice i okolí S(i) a v pravidle rychlosti místo společného g používá g_i = p_k, kde k = arg min_{j ∈ S(i)} f(p_j). Globální topologie má S(i) = {1, …, N}, kruhová S(i) = {i − 1, i, i + 1} (indexy modulo N). Kolik iterací trvá, než se zpráva o novém nálezu dostane ke všem? V globální topologii jedna. V kruhu postoupí za iteraci nejvýš o jednoho souseda na každou stranu, a nejvzdálenější částice v kruhu 40 částic je 20 míst daleko — zpráva k ní dorazí nejdřív za 20 iterací. Tak dlouho mohou vzdálené části hejna zkoumat po svém.

Na naší dvourozměrné úloze našel kruh minimum ve všech 100 bězích, globální topologie v 97. Rozdíl je zřetelnější v deseti rozměrech, kde je důlků astronomicky mnoho: po 2 000 iteracích skončila globální topologie v průměru na hodnotě 5,84, kruhová na 4,57. Globální minimum nenašla ani jedna — desetirozměrná Rastriginova funkce je pro 40 částic opravdu těžká.

8. Pozor na metafory

Věta — žádný oběd zdarma (Wolpert a Macready, 1997)

Zprůměrováno přes všechny možné účelové funkce na konečné množině mají všechny algoritmy, které nevyhodnocují tentýž bod dvakrát, stejný očekávaný výkon.

Přesněji: nechť X a Y jsou konečné neprázdné množiny a 𝓕 = Y^X množina všech funkcí f : X → Y (je jich |Y|^|X|). Algoritmus a v každém kroku na základě dosud viděných dvojic (x, f(x)) zvolí bod x ∈ X, který ještě nevyhodnotil, a zjistí f(x). Nechť m ∈ {1, …, |X|} a d_m^y = (y₁, …, y_m) ∈ Y^m je posloupnost hodnot, které algoritmus uvidí během prvních m ohodnocení. Pak pro libovolné dva takové algoritmy a₁, a₂ a každou posloupnost 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 pravděpodobnost, že algoritmus a na funkci f uvidí právě posloupnost d_m^y (u deterministického algoritmu 0, nebo 1).

Sčítá se tedy přes všech |Y|^|X| funkcí. Každé měřítko výkonu, které závisí jen na viděných hodnotách (třeba nejlepší nalezená), má tedy přes všechny funkce stejný průměr.

Po úspěchu mravenců a hejna se roztrhl pytel s algoritmy „inspirovanými přírodou“: světlušky, kukačky, netopýři, šedí vlci, harmonie v jazzové kapele. Kenneth Sörensen v roce 2015 upozornil, že mnohé z nich jsou staré myšlenky v novém kostýmu — metafora nahradila matematický popis a ztížila srovnání. Dobrá otázka u každého nového algoritmu proto nezní „čím je inspirovaný“, ale „co dělá jinak než ty známé a na čem je to vidět“.

9. Hejna v praxi

• Ladění parametrů. PSO je oblíbené tam, kde je parametrů málo, gradient neznáme a jedno ohodnocení je simulace: nastavení regulátorů, tvar antén, řízení energetických sítí nebo hyperparametry modelů strojového učení.
• Roboti v hejnu. Na Harvardu v roce 2014 složilo 1 024 malých robotů Kilobot podle místních pravidel zadané tvary — bez centrálního řízení, jen komunikací se sousedy.
• A co drony na ohňostrojích? Světelné show s tisíci drony nejsou inteligence hejna: každý dron letí po předem spočítané dráze z centrálního plánu. Hejno v pravém smyslu se rozhoduje samo, podle sousedů.

10. Shrnutí

• Částice v PSO mění rychlost podle setrvačnosti, vlastního nejlepšího místa a nejlepšího místa hejna.
• Na Rastriginově funkci našlo hejno minimum v 97 ze 100 běhů — evoluční strategie se stejným startem a rozpočtem ve 32.
• Setrvačnost řídí, jak dlouho hejno zkoumá: malá ho zhroutí předčasně, velká ho nenechá dopilovat výsledek. Bez sociální i bez kognitivní složky hejno selhává.
• Částice je jako tlumená pružina; pro |w| < 1 a 0 < φ < 2(1 + w) se usadí.
• Kruhová topologie šíří informaci pomaleji a na těžkých úlohách bývá robustnější; a podle věty o žádném obědu zdarma neexistuje optimalizátor nejlepší na všechno.

Chcete si to osahat? Nechte AI agenta napsat PSO s vizualizací hejna a zkuste mu dát vlastní krajinu — třeba funkci se dvěma vzdálenými údolími — a sledujte, jestli se hejno rozdělí.

Máte na to jiný názor? Napište na support@coden-app.com.