Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon

(1+1)-ES a pravidlo jednej pätiny, populácia a sebaadaptácia na Rastriginovej funkcii, CMA-ES, programy ako stromy, symbolická regresia, ktorá z dát o planétach nájde tretí Keplerov zákon, a nafukovanie programov.

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

Séria Základy AI Diel 28 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

V šesťdesiatych rokoch stáli dvaja študenti berlínskej Technickej univerzity, Ingo Rechenberg a Hans-Paul Schwefel, v aerodynamickom tuneli nad kĺbovou doskou. Chceli nájsť tvar s najmenším odporom, lenže na výpočet chýbali rovnice aj počítače. Tak losovali: náhodne pootočili kĺby, zmerali odpor, a keď bol menší, nový tvar si nechali. Z toho pokusu vznikla evolučná stratégia — evolúcia, ktorá namiesto jednotiek a núl ladí čísla. O štvrťstoročie neskôr John Koza ukázal, že evolúciou sa dajú pestovať aj celé programy.

Nadväzuje na diel Genetické algoritmy. Tam bol jedinec reťazec bitov; tu to bude vektor reálnych čísel a strom programu.

1. Evolúcia čísel: (1+1)-ES

Algoritmus — (1+1)-ES

Vstup: minimalizovaná funkcia f : ℝⁿ → ℝ (n ≥ 1), počiatočný bod x₀ ∈ ℝⁿ, veľkosť kroku σ > 0 a počet generácií K ∈ ℕ. Výstup: bod x ∈ ℝⁿ a jeho hodnota f(x). Jedinec je bod x ∈ ℝⁿ.

1. Polož x ← x₀.
2. Pre k = 1, …, K opakuj:
   1. vylosuj z ~ N(0, I) (vektor n nezávislých normálne rozdelených čísel, definícia nižšie) a vytvor potomka y = x + σ · z;
   2. ak f(y) ≤ f(x), polož x ← y; inak x ponechaj.
3. Po K generáciách skonči a vráť x a f(x). (V praxi sa často končí skôr, len čo f(x) klesne pod zvolenú hranicu.)

Hodnota f(x) teda nikdy nerastie. V tejto základnej podobe je σ pevné; ako ho meniť, opisuje pravidlo jednej pätiny nižšie.

y = x + σ · z,   z ~ N(0, I)

y

potomok — nový kandidát, ktorého ohodnotíme

x

rodič — najlepší doteraz nájdený bod; potomok vzniká v jeho okolí, pretože blízko dobrého bodu bývajú iné dobré body

σ

veľkosť kroku — jediné číslo, ktoré určuje, ako ďaleko od rodiča sa hľadá; šum z má rozptyl 1, až σ mu dá mierku úlohy

z ~ N(0, I)

smer a dĺžka pokusu — stred 0 znamená, že žiadny smer nie je vopred zvýhodnený; jednotková matica I, že všetky súradnice sa menia nezávisle a rovnako silno

Definícia — normálne rozdelenie N(0, 1) a N(0, I)

Nech Z je reálna náhodná premenná. Z má štandardné normálne rozdelenie N(0, 1) práve vtedy, keď má hustotu φ : ℝ → (0, ∞),

φ(z) = 1/√2π · exp(−z²/2),   t. j.   P(a ≤ Z ≤ b) = ∫_a^b φ(z) dz   pre všetky a ≤ b.

Potom EZ = 0 a var Z = 1. Asi 68 % hodnôt leží v intervale [−1, 1] a 95 % v [−1,96; 1,96].

Nech n ≥ 1 a I ∈ ℝ^n×n je jednotková matica. Náhodný vektor z = (z₁, …, z_n) má rozdelenie N(0, I) práve vtedy, keď sú z₁, …, z_n nezávislé a každá má rozdelenie N(0, 1). Potom E‖z‖² = ∑_i=1ⁿ Ez_i² = n, takže dĺžka ‖z‖ je typicky okolo √n (pre n = 10 asi 3,2).

Náš program vyrába normálne čísla Boxovou–Mullerovou metódou: ak sú u₁, u₂ nezávislé a rovnomerne rozdelené na (0, 1), má

z = √−2 ln u₁ · cos(2πu₂)

rozdelenie N(0, 1).

Skúsime to na najjednoduchšej možnej funkcii, guli f(x) = x₁² + … + x₁₀² v desiatich rozmeroch. Minimum je zjavne v nule; začneme v bode (3, …, 3), kde f = 90. Ako zvoliť σ? Veľká hodnota vie rýchlo zísť z kopca, ale v blízkosti minima stále prestreľuje. Malá je presná, ale ku dnu ide celú večnosť.

2. Pravidlo jednej pätiny

Definícia — pravidlo jednej pätiny (Rechenberg, 1973)

Nech beží (1+1)-ES s veľkosťou kroku σ > 0. Mutácia je úspešná práve vtedy, keď potomok nie je horší ako rodič, f(y) ≤ f(x). Nech p_s ∈ [0, 1] je podiel úspešných mutácií (za posledné obdobie behu). Pravidlo jednej pätiny mení σ takto:

1. ak p_s > 1/5, σ zväčši;
2. ak p_s < 1/5, σ zmenši;
3. ak p_s = 1/5, σ ponechaj.

Podoba použitá v tomto diele mení σ po každej mutácii:

σ ← σ · exp(1/3)   po úspechu,   σ ← σ · exp(−1/12)   po neúspechu.

Ak mutácia uspeje s pravdepodobnosťou p, zmení sa ln σ za krok v priemere o p · 1/3 − (1 − p) · 1/12, a to je nula práve vtedy, keď p = 1/5: 1/5 · 1/3 = 4/5 · 1/12. Veľkosť kroku sa teda v priemere nemení práve vtedy, keď je úspešná pätina mutácií.

Obe vetvy pravidla sa dajú zapísať jedným vzorcom; s = 1 po úspechu a 0 po neúspechu:

σ ← σ · exp( 5/12 · ( s − 1/5 ) )

σ

veľkosť kroku — mení sa násobením, nie pripočítaním: zostane kladná a krok sa vie zmenšiť o mnoho rádov (z 1 až na tisíciny), ako to blízkosť minima vyžaduje

5/12

rýchlosť prispôsobenia — po úspechu exp(5/12 · 4/5) = exp(1/3) ≈ 1,40, po neúspechu exp(−5/12 · 1/5) = exp(−1/12) ≈ 0,92; väčšie číslo by reagovalo rýchlejšie, ale σ by viac kolísala

s

výsledok posledného pokusu (1 = potomok nebol horší) — jediná informácia, ktorú pravidlo potrebuje

1/5

cieľová úspešnosť — keď sa darí práve pätina pokusov, je priemer s − 1/5 nula a σ sa v priemere nemení

Pravidlo jednej pätiny sa dostane pod 10⁻⁶ za 587 ohodnotení — a čiara v grafe klesá rovnomerne, pretože krok sa zmenšuje rovnako rýchlo, ako sa blíži minimum. S pevným σ = 1 algoritmus čoskoro narazí na „podlahu“ okolo jednotky, pod ktorú sa s takými veľkými skokmi dostať nedá. S σ = 0,01 ide dole, lenže pomaly: ani po 5 000 ohodnoteniach nie je pod 10⁻⁴.

import math, random

def es_1_plus_1(f, x, sigma=1.0, kroku=1000):
    fx = f(x)
    for _ in range(kroku):
        y = [xi + sigma * random.gauss(0, 1) for xi in x]
        fy = f(y)
        if fy <= fx:
            x, fx = y, fy
            sigma *= math.exp(1 / 3)     # úspech: pridaj
        else:
            sigma *= math.exp(-1 / 12)   # neúspech: uber
    return x, fx

Príklad — prvých dvanásť krokov behu z grafu

Štart x = (3, …, 3), f(x) = 90, σ = 1. Stĺpec σ je veľkosť kroku po aktualizácii:

krok	f(y)	úspech?	f(x)	σ
1	115,31	nie	90,00	0,920
2	95,78	nie	90,00	0,846
3	123,94	nie	90,00	0,779
4	107,86	nie	90,00	0,717
5	101,54	nie	90,00	0,659
6	113,11	nie	90,00	0,607
7	94,03	nie	90,00	0,558
8	95,09	nie	90,00	0,513
9	86,27	áno	86,27	0,717
10	114,52	nie	86,27	0,659
11	97,72	nie	86,27	0,607
12	102,44	nie	86,27	0,558

po 8 neúspechoch (s = 0): σ = 1 · [exp(5/12 · (0 − 1/5))]⁸ = exp(−8/12) ≈ 0,513

9. krok uspeje (86,27 < 90, s = 1): σ = 0,513 · exp(5/12 · (1 − 1/5)) = 0,513 · exp(1/3) ≈ 0,513 · 1,396 ≈ 0,717

(Farby podľa vzorca pravidla jednej pätiny vyššie.)

S σ = 1 má krok v desiatich rozmeroch dĺžku okolo √10 ≈ 3,2 a prvých osem potomkov je horších ako štart, takže pravidlo krok sťahuje. Úspechy potom prichádzajú častejšie a σ sa ustáli tam, kde sa darí zhruba každý piaty pokus — za celý beh uspelo 99 z 587 pokusov, teda 17 %. Ako sa bod blíži k minimu, klesá s ním aj krok: na konci behu, po 580 ohodnoteniach, je σ ≈ 0,00055.

3. Populácia a sebaadaptácia

Guľa má jediné minimum. Skutočné úlohy ich mávajú kopu — a tam jeden jedinec nestačí. Typická skúšobná funkcia je Rastriginova: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). Je to guľa, do ktorej niekto nasekal pravidelnú mriežku jamiek; globálne minimum 0 je v počiatku a okolo neho stovky lokálnych.

f(x) = 10n + ∑_i=1ⁿ ( x_i² − 10 cos 2πx_i )

10n

posun nahor — kosínus odčíta v počiatku najviac 10 na každú súradnicu, konštanta to vráti, aby globálne minimum malo hodnotu presne 0

x_i²

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

10 cos 2πx_i

vlnky s periódou 1 a amplitúdou 10 — vyhĺbia jamku pri každom celom čísle; amplitúda je oveľa väčšia ako sklon gule medzi susednými jamkami, takže lokálne hľadanie v najbližšej jamke uviazne

Príklad — štart a susedné jamky (n = 2)

štart (4,2; −3,8): x₁² = 17,64,   10 cos(2π · 4,2) = 10 cos(0,4π) ≈ 3,09

x₂² = 14,44,   10 cos(2π · (−3,8)) = 10 cos(0,4π) ≈ 3,09,   10n = 20

f = 20 + (17,64 − 3,09) + (14,44 − 3,09) ≈ 45,90   (farby podľa vzorca vyššie)

dno jamiek vedľa počiatku, pri (±1; 0) a (0; ±1): f ≈ 0,99 (v bode 0,995, nie presne 1 — guľa ho ťahá k počiatku)

dno diagonálnych jamiek pri (±1; ±1): f ≈ 1,99

Hodnota 1,49 v generácii 8 (pozri nižšie) teda znamená populáciu v susednej jamke, ešte nie na jej dne.

Definícia — (μ, λ)-ES a (μ + λ)-ES so sebaadaptáciou

Nech f : ℝⁿ → ℝ je minimalizovaná funkcia a μ, λ ∈ ℕ. Jedinec je dvojica (x, σ) ∈ ℝⁿ × (0, ∞) — bod a jeho vlastná veľkosť kroku. Populácia je μ-tica jedincov (rodičov). Nech τ > 0 je učiaca rýchlosť kroku, zvyčajne τ ≈ 1/√2n. Jedna generácia:

1. Sebaadaptácia a mutácia: pre j = 1, …, λ vyber rovnomerne náhodného rodiča (x, σ), vylosuj nezávisle ξ_j ~ N(0, 1) a z_j ~ N(0, I) a vytvor potomka (y_j, σ′_j), kde σ′_j = σ · exp(τ · ξ_j),   y_j = x + σ′_j · z_j. Potomok teda najprv zmutuje krok a až s novým krokom posunie polohu.
2. Výber:
   • pri (μ, λ)-ES (vyžaduje λ > μ) tvorí novú populáciu μ potomkov s najmenšími hodnotami f(y_j) a rodičia zahynú;
   • pri (μ + λ)-ES tvorí novú populáciu μ jedincov s najmenšou hodnotou f zo všetkých μ + λ rodičov a potomkov dohromady.

Generácie sa opakujú do vyčerpania zvoleného počtu generácií (alebo ohodnotení).

σ′ = σ · exp(τ · N(0, 1)),   τ = 1/√2n

σ′

krok potomka — s ním sa hneď posunie poloha, takže zdatnosť potomka prezradí, či bol krok dobrý

σ

krok rodiča — dedí sa; potomok začína od toho, čo sa rodičovi osvedčilo

τ

učiaca rýchlosť kroku — ako veľmi sa smie krok medzi generáciami zmeniť; s rastúcim počtom rozmerov n sa zmenšuje, pretože jedna zdatnosť potom nesie menej informácie o tom, či bol krok dobrý

N(0, 1)

náhodná zmena — symetrická okolo nuly, takže zväčšenie aj zmenšenie sú rovnako pravdepodobné; o smere rozhodne až výber

Príklad — mutácia kroku pre n = 2

τ = 1/√2 · 2 = 1/2

N(0, 1) = +1:   σ′ = σ · exp(0,5 · 1) ≈ 1,65 σ;   N(0, 1) = −1:   σ′ = σ · exp(0,5 · (−1)) ≈ 0,61 σ

(Farby podľa vzorca vyššie.)

Typický potomok teda skúša krok zhruba o 40 % menší až o 65 % väčší ako rodič. V našom behu klesol krok najlepšieho jedinca za 15 generácií z 2 na 0,011 — skoro dvestokrát.

import math, random

def es_mi_lambda(f, start, mi=15, lam=100, sigma=2.0, generaci=80):
    n = len(start)
    tau = 1 / math.sqrt(2 * n)
    rodice = [(start, sigma)] * mi
    for _ in range(generaci):
        deti = []
        for _ in range(lam):
            x, s = random.choice(rodice)                    # náhodný rodič
            s = s * math.exp(tau * random.gauss(0, 1))      # najprv zmutuj krok
            y = [xi + s * random.gauss(0, 1) for xi in x]   # potom s ním polohu
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): prežijú len najlepší potomkovia
    return rodice[0]

Populácia štartuje okolo bodu (4,2; −3,8), kde f ≈ 45,9. Na začiatku je rozprestretá cez niekoľko jamiek naraz a sťahuje sa k tým hlbším. V generácii 8 je najlepší jedinec ešte v susednej jamke (f ≈ 1,49), ale veľkosť kroku už klesla z 2 na 0,27. V generácii 15 je populácia v globálnom minime a krok sa zmenšil na stotinu, aby ho mohla dopilovať.

Zo sto behov s rôznymi semienkami našla (15, 100)-ES globálne minimum v 32 prípadoch. Pre porovnanie (1+1)-ES s pravidlom jednej pätiny a rovnakým rozpočtom 8 000 ohodnotení: v jedinom. Na guliach je jeden jedinec najrýchlejší, na členitom teréne vyhráva populácia — a aj tá často skončí v niektorej zo susedných jamiek.

4. CMA-ES

Sebaadaptácia ladí len dĺžku kroku. Čo ak je minimum v úzkom šikmom údolí, kde sa oplatí robiť dlhé kroky jedným smerom a krátke iným? CMA-ES (Hansen a Ostermeier, 2001) sa z úspešných krokov učí celú kovariančnú maticu mutácie — tvar oblaku, z ktorého potomkov losuje. Oblak sa počas hľadania natáča a naťahuje pozdĺž údolia. Na optimalizáciu spojitých funkcií, pri ktorých nepoznáme gradient, je dnes CMA-ES jednou z najspoľahlivejších metód.

Definícia — mutácia s kovariančnou maticou

Nech n ≥ 1 a C ∈ ℝ^n×n je symetrická (C = C^T) pozitívne definitná matica (v^TCv > 0 pre všetky v ∈ ℝⁿ, v ≠ 0). Náhodný vektor z má rozdelenie N(0, C) práve vtedy, keď má rovnaké rozdelenie ako

Au,   kde u ~ N(0, I) a A ∈ ℝ^n×n je ľubovoľná matica s AA^T = C

(rozdelenie od voľby A nezávisí; také A vždy existuje, napr. Choleského rozklad). Potom Ez = 0 a E[z_iz_j] = C_ij pre všetky i, j = 1, …, n; C je teda kovariančná matica vektora z.

Nech m ∈ ℝⁿ je stred populácie a σ > 0 veľkosť kroku. Mutácia s kovariančnou maticou C vytvorí potomka

y = m + σ · z,   z ~ N(0, C).

Body s rovnakou hustotou ležia na elipsoide; jeho osi sú vlastné vektory C a dĺžky osí úmerné odmocninám vlastných čísel. Pre C = I je to guľa a dostaneme obyčajnú evolučnú stratégiu.

Zjednodušene (skutočná CMA-ES k tomu pridáva ešte takzvané evolučné cesty a vlastné riadenie σ, pozri N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) sa matica po každej generácii posunie k úspešným krokom:

C ← (1 − c) C + c ∑_i=1^μ w_i z_iz_i^T

C

kovariančná matica mutácie — tvar oblaku, z ktorého sa losujú potomkovia

1 − c

pamäť — stará matica sa len trochu priblíži novej informácii, pretože jedna generácia je malá a náhodná vzorka

c

učiaca rýchlosť matice, číslo medzi 0 a 1 — koľko váhy dostanú kroky poslednej generácie

∑ w_i

vážený priemer cez μ najlepších potomkov; váhy sú kladné, sčítajú sa na 1 a lepší potomok má väčšiu — učíme sa len z krokov, ktoré sa oplatili

z_iz_i^T

úspešný krok z_i = y_i − m/σ ako matica — natiahne oblak práve v jeho smere

Príklad — jeden úspešný krok po diagonále

C = I (kruhový oblak), jediný úspešný krok z = (1, 1), teda μ = 1 a w₁ = 1, c = 0,2 (farby podľa vzorca vyššie):

zz^T = [[1, 1], [1, 1]]

C ← 0,8 · [[1, 0], [0, 1]] + 0,2 · 1 · [[1, 1], [1, 1]] = [[1; 0,2], [0,2; 1]]

vlastné čísla: 1 + 0,2 = 1,2 v smere (1, 1) a 1 − 0,2 = 0,8 v smere (1, −1)

Oblak sa natiahol pozdĺž úspešného smeru a zúžil naprieč — po pár takých generáciách leží pozdĺž údolia.

5. Genetické programovanie

Definícia — program ako strom

Nech 𝓕 je konečná množina funkcií, kde každá h ∈ 𝓕 má aritu ar(h) ∈ ℕ, ar(h) ≥ 1 (počet argumentov), a 𝓣 konečná množina terminálov (premenné a konštanty). Množina programov nad 𝓕 a 𝓣 je najmenšia množina koreňových stromov, pre ktorú platí:

1. každý terminál t ∈ 𝓣 je program — strom s jediným uzlom t;
2. ak sú h ∈ 𝓕, k = ar(h) a g₁, …, g_k programy, je programom aj strom h(g₁, …, g_k) s koreňom h a podstromami g₁, …, g_k v tomto poradí.

Vnútorné uzly sú teda funkcie s toľkými deťmi, aká je ich arita, a listy sú terminály. Veľkosť programu |g| je počet jeho uzlov. Pri daných hodnotách premenných je hodnota programu definovaná rekurzívne od listov ku koreňu: hodnota terminálu je jeho hodnota a hodnota h(g₁, …, g_k) je h použitá na hodnoty g₁, …, g_k.

Uzavretosť: nech D je množina hodnôt (tu ℝ). Množina 𝓕 je uzavretá práve vtedy, keď každá h ∈ 𝓕 je definovaná pre všetky vstupy, t. j. je to funkcia h : D^ar(h) → D; potom má hodnotu každý program. Preto sa používa chránené delenie, a ÷ b = a/b pre |b| ≥ 10⁻⁹ a a ÷ b = 1 inak, a odmocnina z absolútnej hodnoty, √|a|.

John Koza zo Stanfordovej univerzity spísal metódu v roku 1992 v knihe Genetic Programming a ukázal ju na desiatkach úloh, od riadenia robota po hľadanie vzorcov.

Príklad — vyhodnotenie stromu programu pre Zem

Strom programu a/5 · √a má v koreni násobenie, vľavo delenie a ÷ 5, vpravo √a. Od listov ku koreňu, a = 149,6 (miliónov km):

ľavá vetva: a/5 = 149,6/5 = 29,92

pravá vetva: √a = √149,6 ≈ 12,231

koreň: 29,92 × 12,231 ≈ 365,95 dňa   (skutočnosť 365,26, odchýlka +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # elitizmus: jeden najlepší
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # kríženie výmenou podstromov
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # mutácia: vetva → nová náhodná
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # príliš hlboké deti zahodíme
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # najmenšia chyba; pri zhode menší strom

6. Symbolická regresia: Keplerov zákon

Johannes Kepler hľadal vzťah medzi vzdialenosťou planéty od Slnka a jej obežnou dobou desať rokov; tretí zákon publikoval v roku 1619. Dáme genetickému programovaniu rovnakú úlohu. Má k dispozícii osem planét — veľkú polos a v miliónoch kilometrov a obežnú dobu T v dňoch —, operácie +, −, ×, ÷ a √, premennú a a číslice 1 až 9. Chybou programu je priemerná relatívna odchýlka od skutočných obežných dôb. Populácia má 300 programov a 40 generácií.

Definícia — symbolická regresia

Nech (x₁, y₁), …, (x_N, y_N) ∈ X × ℝ sú dáta (X množina vstupov, napr. ℝ^d), 𝓟 množina programov nad zvolenými funkciami 𝓕 a terminálmi 𝓣 (definícia vyššie; premenné zodpovedajú zložkám vstupu) a ℓ : ℝ × ℝ → [0, ∞] stratová funkcia. Symbolická regresia je optimalizačná úloha nájsť

g* ∈ argmin_{g ∈ 𝓟} ∑_i=1^N ℓ(g(x_i), y_i),

kde g(x_i) je hodnota programu g pre vstup x_i. Na rozdiel od bežnej regresie teda nie je vopred daný tvar modelu s neznámymi parametrami — hľadá sa samotný výraz, len zo zadaných stavebných kameňov.

Presne je chyba programu g priemer absolútnych rozdielov logaritmov:

E(g) = 1/8 ∑_i=1⁸ | ln g(a_i) − ln T_i |

1/8 ∑

priemer cez osem planét — chyba nezávisí od toho, koľko dát máme, a dá sa čítať ako „typická odchýlka na planétu“

| … |

absolútna hodnota — predpoveď o 1 % väčšia aj menšia je rovnako zlá a chyby rôznych znamienok sa nevyrušia

ln g(a_i) − ln T_i

rozdiel logaritmov je ln g(a_i)/T_i, teda relatívna odchýlka: pre malé odchýlky ln(1 + r) ≈ r. Obežné doby sa líšia skoro tisíckrát (88 dní Merkúr, 60 190 Neptún); s obyčajným rozdielom by o chybe rozhodoval len Neptún

Najlepší program počiatočnej, náhodnej populácie sa od skutočných obežných dôb odchyľuje v priemere o 32 %. V tretej generácii už má odchýlku 8 % a správny tvar a^1,5, len s konštantou 0,22. V pätnástej generácii príde toto:

T = a · √a/5 — teda T úmerné a^3/2, čiže T² úmerné a³. To je tretí Keplerov zákon. Priemerná odchýlka je 0,30 % a konštanta 1/5 je veľmi blízko skutočnej hodnote 0,1996 pre tieto jednotky. Z dvadsiatich behov s rôznymi semienkami našlo exponent 1,5 osemnásť.

Odkiaľ je 0,1996? Z Newtonovho gravitačného zákona vyplýva pre kruhovú dráhu (a pre elipsu s veľkou polosou a, keď je hmotnosť planéty oproti Slnku zanedbateľná) tvar zákona aj s konštantou:

T = 2π/√GM_☉ ·a^3/2

T

obežná doba — čas jedného obehu

2π

jeden obeh je uhol 2π; vzorec vznikne z uhlovej rýchlosti ω ako T = 2π/ω

√GM_☉

sila gravitácie Slnka (G gravitačná konštanta, M_☉ hmotnosť Slnka) — silnejšia príťažlivosť znamená rýchlejší obeh, preto je v menovateli

a^3/2

vzdialenosť — gravitácia slabne s a² a dráha je dlhšia úmerne a; z rovnosti dostredivej a gravitačnej sily ω²a = GM_☉/a² vyjde ω ∝ a^−3/2

Príklad — konštanta v miliónoch km a dňoch

Gravitačný parameter Slnka GM_☉ = 1,327 124 · 10²⁰ m³/s² (nominálna hodnota Medzinárodnej astronomickej únie, rezolúcia B3 z roku 2015). Jednotka dĺžky je 10⁹ m, takže a^3/2 v metroch je (10⁹)^3/2 = √10²⁷-krát viac. Konštanta v sekundách je 2π/√GM_☉ · √10²⁷ (farby podľa vzorca vyššie):

√10²⁷/1,327 124 · 10²⁰ = √7,535 · 10⁶ ≈ 2 745,0 s

2π · 2 745,0 s ≈ 17 247 s

17 247 s/86 400 s/deň ≈ 0,1996 dňa

Program s konštantou 1/5 = 0,2 sa teda líši o 0,19 % — presne toľko, koľko vyšla odchýlka pri Zemi vyššie.

7. Nafukovanie

Evolúcia však pri krásnom vzorci nezostala. Do generácie 40 „zlepšila“ odchýlku na 0,23 % týmto:

Strom má namiesto šiestich uzlov šestnásť a pridané vetvy nerobia nič iné, než že doladia konštantu a obídu zaokrúhlenie v dátach. Fyzikálne je to horší vzorec — preučený na osem planét. Priemerná veľkosť programu v populácii pritom vzrástla z 9,8 uzla na začiatku na 23,8 v dvadsiatej generácii.

Definícia — nafukovanie a tlak na úspornosť

Nech P₀, P₁, … sú populácie programov v po sebe idúcich generáciách, |g| veľkosť programu g (počet uzlov stromu) a F(g) ≥ 0 jeho chyba na dátach (menšia je lepšia). Označme s̄_t priemernú veľkosť programov v P_t.

Nafukovanie (bloat) je jav, keď s̄_t s rastúcim t výrazne rastie bez toho, aby tomu zodpovedal pokles chyby F — programom pribúdajú uzly, ktoré chybu neznižujú vôbec alebo len nepatrne. (Ide o pozorovaný jav, nie o pojem s jedinou presnou hranicou, kedy rast ešte je a kedy už nie je „zodpovedajúci“.)

Tlak na úspornosť (parsimony pressure) je úprava výberu, ktorá zvýhodní menšie programy. Nech c > 0. Používajú sa dve podoby:

1. trest za veľkosť: výber porovnáva programy podľa upravenej chyby F′(g) = F(g) + c · |g|;
2. lexikografické porovnanie: program g je lepší ako h práve vtedy, keď F(g) < F(h), alebo F(g) = F(h) ∧ |g| < |h| — veľkosť rozhoduje len pri zhode chýb.

F′(g) = F(g) + c · |g|

F′(g)

upravená chyba, podľa ktorej sa vyberá — menšia je lepšia

F(g)

chyba programu na dátach — stále to hlavné, čo chceme znížiť

c

cena jedného uzla — hovorí, o koľko sa musí chyba zlepšiť, aby sa uzol navyše oplatil; volí sa tak, aby rozhodovala len pri zanedbateľných zlepšeniach

|g|

veľkosť programu, počet uzlov stromu — miera zložitosti, ktorá sa dá spočítať bez porozumenia programu

Príklad — aké veľké c by zachránilo Keplerov zákon

Strom z generácie 15: chyba 0,2986 %, 6 uzlov. Strom z generácie 40: chyba 0,2312 %, 16 uzlov. Menší strom vyhrá, keď

0,002 986 + 6c < 0,002 312 + 16c

10c > 0,000 674  ⇒  c > 0,000 674/10 ≈ 6,7 · 10⁻⁵

(Farby podľa vzorca vyššie: obe strany nerovnosti sú upravené chyby F′.)

Desať uzlov navyše zlepšilo chybu o necelú stotinu percenta. S cenou nad 0,007 % za uzol by vo výbere strom z generácie 40 prehral s čitateľným zákonom z generácie 15.

8. Evolučné stratégie a programy dnes

• Evolučné stratégie namiesto učenia posilňovaním. OpenAI v roku 2017 ukázala, že jednoduchá evolučná stratégia zvládne učiť neurónové siete ovládať simulované roboty a hrať hry Atari podobne dobre ako učenie posilňovaním — a dá sa rozložiť na tisíce procesorov, ktoré si posielajú len pár čísel.
• Objavovanie zákonov z dát. Schmidt a Lipson v roku 2009 nechali symbolickú regresiu odvodiť pohybové zákony a zákony zachovania z meraní kyvadiel. Dnešné knižnice ako PySR sa používajú vo fyzike a astronómii, kde je čitateľný vzorec cennejší ako čierna skrinka.
• Evolúcia algoritmov strojového učenia. Projekt AutoML-Zero (Google, 2020) nechal evolúciu zostavovať učiace algoritmy z elementárnych matematických operácií a znova tak objavil napríklad spätné šírenie chyby.
• Programy s jazykovými modelmi. Systémy FunSearch a AlphaEvolve z minulého dielu sú genetické programovanie, v ktorom mutáciu namiesto náhodnej vetvy robí jazykový model.

9. Zhrnutie

• Evolučné stratégie mutujú reálne čísla normálnym šumom s veľkosťou kroku σ.
• Pravidlo jednej pätiny a sebaadaptácia nastavujú σ automaticky; CMA-ES sa učí aj tvar mutácií.
• Na guliach stačí jeden jedinec, na členitom teréne pomáha populácia: na Rastriginovej funkcii 32 úspechov zo 100 proti jednému.
• Genetické programovanie pestuje programy ako stromy; symbolická regresia z dát o planétach našla tretí Keplerov zákon.
• Programy majú sklon nafukovať sa a preučovať sa — proti tomu pomáha tlak na úspornosť.

Chcete si to vyskúšať? Nechajte AI agenta napísať symbolickú regresiu a dajte jej vlastné dáta — napríklad dobu kmitu kyvadla podľa dĺžky špagátu — a sledujte, či nájde √L.

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