Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon

(1+1)-ES a pravidlo jedné pětiny, populace a sebeadaptace na Rastriginově funkci, CMA-ES, programy jako stromy, symbolická regrese, která z dat o planetách najde Keplerův třetí zákon, a nabobtnání programů.

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

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

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

Co si odnesete

Jak evoluční strategie ladí reálná čísla a jak si samy nastaví velikost kroku.
Proč na členitém terénu vyhrává populace nad jedním jedincem.
Jak genetické programování pěstuje celé vzorce — a proč mají sklon nabobtnávat.

Co se hodí znát předem: Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet

V šedesátých letech stáli dva studenti berlínské Technické univerzity, Ingo Rechenberg a Hans-Paul Schwefel, v aerodynamickém tunelu nad kloubovou deskou. Chtěli najít tvar s nejmenším odporem, jenže na výpočet chyběly rovnice i počítače. Tak losovali: náhodně pootočili klouby, změřili odpor, a když byl menší, nový tvar si nechali. Z toho pokusu vznikla evoluční strategie — evoluce, která místo jedniček a nul ladí čísla. O čtvrt století později John Koza ukázal, že evolucí lze pěstovat i celé programy.

Navazuje na díl Genetické algoritmy. Tam byl jedinec řetězec bitů; tady to bude vektor reálných čísel a strom programu.

1. Evoluce čísel: (1+1)-ES

Algoritmus — (1+1)-ES

Vstup: minimalizovaná funkce f : ℝⁿ → ℝ (n ≥ 1), počáteční bod x₀ ∈ ℝⁿ, velikost kroku σ > 0 a počet generací K ∈ ℕ. Výstup: bod x ∈ ℝⁿ a jeho hodnota f(x). Jedinec je bod x ∈ ℝⁿ.

Polož x ← x₀.
Pro k = 1, …, K opakuj:
1. vylosuj z ~ N(0, I) (vektor n nezávislých normálně rozdělených čísel, definice níže) a vytvoř potomka y = x + σ · z;
2. je-li f(y) ≤ f(x), polož x ← y; jinak x ponech.
Po K generacích skonči a vrať x a f(x). (V praxi se často končí dřív, jakmile f(x) klesne pod zvolenou mez.)

Hodnota f(x) tedy nikdy neroste. V této základní podobě je σ pevné; jak ho měnit, popisuje pravidlo jedné pětiny níže.

Laicky řečeno

Jeden rodič, jedno dítě. Dítě je rodič s trochou náhodného šumu v každém čísle; když je lepší, převezme místo. Velikost kroku σ říká, jak velký ten šum je — jestli dělá drobné úpravy, nebo velké skoky.

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

y: potomek — nový kandidát, kterého ohodnotíme
x: rodič — nejlepší dosud nalezený bod; potomek vzniká v jeho okolí, protože blízko dobrého bodu bývají jiné dobré body
σ: velikost kroku — jediné číslo, které určuje, jak daleko od rodiče se hledá; šum z má rozptyl 1, teprve σ mu dá měřítko úlohy
z ~ N(0, I): směr a délka pokusu — střed 0 znamená, že žádný směr není předem zvýhodněný; jednotková matice I, že všechny souřadnice se mění nezávisle a stejně silně

Mutace evoluční strategie: rodič plus náhodný krok, jehož délku řídí σ.

Definice — normální rozdělení N(0, 1) a N(0, I)

Nechť Z je reálná náhodná veličina. Z má standardní normální rozdělení N(0, 1), právě když má hustotu φ : ℝ → (0, ∞),

φ(z) = 1/√2π · exp(−z²/2), tj. P(a ≤ Z ≤ b) = ∫_a^b φ(z) dz pro všechna a ≤ b.

Pak EZ = 0 a var Z = 1. Asi 68 % hodnot leží v intervalu [−1, 1] a 95 % v [−1,96; 1,96].

Nechť n ≥ 1 a I ∈ ℝ^n×n je jednotková matice. Náhodný vektor z = (z₁, …, z_n) má rozdělení N(0, I), právě když jsou z₁, …, z_n nezávislé a každá má rozdělení N(0, 1). Pak E‖z‖² = ∑_i=1ⁿ Ez_i² = n, takže délka ‖z‖ je typicky kolem √n (pro n = 10 asi 3,2).

Náš program normální čísla vyrábí Boxovou–Mullerovou metodou: jsou-li u₁, u₂ nezávislé a rovnoměrně rozdělené na (0, 1), má

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

rozdělení N(0, 1).

Zkusíme to na nejjednodušší možné funkci, kouli f(x) = x₁² + … + x₁₀² v deseti rozměrech. Minimum je zjevně v nule; začneme v bodě (3, …, 3), kde f = 90. Jak zvolit σ? Velká hodnota umí rychle sejít z kopce, ale v blízkosti minima pořád přestřeluje. Malá je přesná, ale ke dnu jde věčnost.

2. Pravidlo jedné pětiny

Definice — pravidlo jedné pětiny (Rechenberg, 1973)

Nechť běží (1+1)-ES s velikostí kroku σ > 0. Mutace je úspěšná, právě když potomek není horší než rodič, f(y) ≤ f(x). Nechť p_s ∈ [0, 1] je podíl úspěšných mutací (za poslední období běhu). Pravidlo jedné pětiny mění σ takto:

je-li p_s > 1/5, σ zvětši;
je-li p_s < 1/5, σ zmenši;
je-li p_s = 1/5, σ ponech.

Podoba použitá v tomto díle mění σ po každé mutaci:

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

Uspěje-li mutace s pravděpodobností p, změní se ln σ za krok v průměru o p · 1/3 − (1 − p) · 1/12, a to je nula, právě když p = 1/5: 1/5 · 1/3 = 4/5 · 1/12. Velikost kroku se tedy v průměru nemění, právě když je úspěšná pětina mutací.

Laicky řečeno

Když se daří skoro každý pokus, jste opatrní zbytečně — přidejte. Když se nedaří skoro žádný, skáčete moc daleko — uberte. Rechenberg odvodil, že nejrychleji se postupuje, když se daří zhruba každý pátý pokus. Algoritmus si tak velikost kroku nastaví sám.

Obě větve pravidla se dají zapsat jedním vzorcem; s = 1 po úspěchu a 0 po neúspěchu:

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

σ: velikost kroku — mění se násobením, ne přičítáním: zůstane kladná a krok se umí zmenšit o mnoho řádů (z 1 až na tisíciny), jak to blízkost minima vyžaduje
5/12: rychlost přizpůsobení — po úspěchu exp(5/12 · 4/5) = exp(1/3) ≈ 1,40, po neúspěchu exp(−5/12 · 1/5) = exp(−1/12) ≈ 0,92; větší číslo by reagovalo rychleji, ale σ by víc kolísala
s: výsledek posledního pokusu (1 = potomek nebyl horší) — jediná informace, kterou pravidlo potřebuje
1/5: cílová úspěšnost — když se daří právě pětina pokusů, je průměr s − 1/5 nula a σ se v průměru nemění

Po N pokusech s S úspěchy je krok vynásoben exp(5/12 · (S − N/5)): z deseti pokusů dva úspěchy krok nezmění, čtyři ho zvětší 2,30krát, jeden zmenší na 0,66.

(1+1)-ES na kouli v deseti rozměrech pevné σ = 1σ = 0,1σ = 0,01pravidlo 1/5

Pravidlo jedné pětiny dojde pod 10⁻⁶ za 587 ohodnocení — a čára v grafu klesá rovnoměrně, protože krok se zmenšuje stejně rychle, jako se blíží minimum. S pevným σ = 1 algoritmus brzy narazí na „podlahu“ kolem jedničky, pod kterou se s tak velkými skoky dostat nedá. S σ = 0,01 jde dolů, jenže pomalu: ani po 5 000 ohodnoceních není 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)     # úspěch: přidej
        else:
            sigma *= math.exp(-1 / 12)   # neúspěch: uber
    return x, fx

Příklad — prvních dvanáct kroků běhu z grafu

Start x = (3, …, 3), f(x) = 90, σ = 1. Sloupec σ je velikost kroku po aktualizaci:

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

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

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

(Barvy podle vzorce pravidla jedné pětiny výše.)

S σ = 1 má krok v deseti rozměrech délku kolem √10 ≈ 3,2 a prvních osm potomků je horších než start, takže pravidlo krok stahuje. Úspěchy pak přicházejí častěji a σ se ustálí tam, kde se daří zhruba každý pátý pokus — za celý běh uspělo 99 z 587 pokusů, tedy 17 %. Jak se bod blíží minimu, klesá s ním i krok: na konci běhu, po 580 ohodnoceních, je σ ≈ 0,00055.

3. Populace a sebeadaptace

Koule má jediné minimum. Skutečné úlohy jich mívají spoustu — a tam jeden jedinec nestačí. Typická zkušební funkce je Rastriginova: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). Je to koule, do které někdo nasekal pravidelnou mřížku důlků; globální minimum 0 je v počátku a kolem něj stovky lokálních.

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

10n: posun nahoru — kosinus odečte v počátku nejvýš 10 na každou souřadnici, konstanta to vrátí, aby globální minimum mělo hodnotu přesně 0
x_i²: koule — celkový sklon k počátku; bez ní by všechny důlky byly stejně hluboké a žádné minimum by nebylo globální
10 cos 2πx_i: vlnky s periodou 1 a amplitudou 10 — vyhloubí důlek u každého celého čísla; amplituda je mnohem větší než sklon koule mezi sousedními důlky, takže lokální hledání v nejbližším důlku uvízne

Rastriginova funkce: hladká koule s pravidelně zvlněným povrchem.

Příklad — start a sousední důlky (n = 2)

start (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 (barvy podle vzorce výše)

dno důlků vedle počátku, u (±1; 0) a (0; ±1): f ≈ 0,99 (v bodě 0,995, ne přesně 1 — koule ho táhne k počátku)

dno diagonálních důlků u (±1; ±1): f ≈ 1,99

Hodnota 1,49 v generaci 8 (viz níže) tedy znamená populaci v sousedním důlku, ještě ne na jeho dně.

Definice — (μ, λ)-ES a (μ + λ)-ES se sebeadaptací

Nechť f : ℝⁿ → ℝ je minimalizovaná funkce a μ, λ ∈ ℕ. Jedinec je dvojice (x, σ) ∈ ℝⁿ × (0, ∞) — bod a jeho vlastní velikost kroku. Populace je μ-tice jedinců (rodičů). Nechť τ > 0 je učící rychlost kroku, obvykle τ ≈ 1/√2n. Jedna generace:

Sebeadaptace a mutace: pro j = 1, …, λ vyber rovnoměrně náhodného rodiče (x, σ), vylosuj nezávisle ξ_j ~ N(0, 1) a z_j ~ N(0, I) a vytvoř potomka (y_j, σ′_j), kde σ′_j = σ · exp(τ · ξ_j), y_j = x + σ′_j · z_j. Potomek tedy nejdřív zmutuje krok a teprve s novým krokem posune polohu.
Výběr:
- u (μ, λ)-ES (vyžaduje λ > μ) tvoří novou populaci μ potomků s nejmenšími hodnotami f(y_j) a rodiče zahynou;
- u (μ + λ)-ES tvoří novou populaci μ jedinců s nejmenší hodnotou f ze všech μ + λ rodičů a potomků dohromady.

Generace se opakují do vyčerpání zvoleného počtu generací (nebo ohodnocení).

Laicky řečeno

Velikost kroku se dědí jako každá jiná vlastnost. Kdo má dobře nastavený krok, má lepší děti — a tím se prosadí i jeho krok. Nikdo nemusí počítat úspěšnost, evoluce vyladí sama sebe. Varianta (μ, λ), ve které rodiče nepřežijí, se navíc nenechá zablokovat jedním jedincem, který měl štěstí: každá generace začíná znovu.

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

σ′: krok potomka — s ním se hned posune poloha, takže zdatnost potomka prozradí, jestli byl krok dobrý
σ: krok rodiče — dědí se; potomek začíná od toho, co se rodiči osvědčilo
τ: učící rychlost kroku — jak moc se smí krok mezi generacemi změnit; s rostoucím počtem rozměrů n se zmenšuje, protože jedna zdatnost pak nese méně informace o tom, zda byl krok dobrý
N(0, 1): náhodná změna — symetrická kolem nuly, takže zvětšení i zmenšení jsou stejně pravděpodobné; o směru rozhodne až výběr

Krok se mění násobením exponenciálou: zůstane kladný a zdvojnásobení je stejně pravděpodobné jako zpolovičení.

Příklad — mutace kroku pro 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 σ

(Barvy podle vzorce výše.)

Typický potomek tedy zkouší krok zhruba o 40 % menší až o 65 % větší než rodič. V našem běhu klesl krok nejlepšího jedince za 15 generací z 2 na 0,011 — skoro dvousetkrá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))      # nejdřív zmutuj krok
            y = [xi + s * random.gauss(0, 1) for xi in x]   # pak s ním polohu
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): přežijí jen nejlepší potomci
    return rodice[0]

(15, 100)-ES na Rastriginově funkci; křížek je globální minimum

Populace startuje kolem bodu (4,2; −3,8), kde f ≈ 45,9. Na začátku je rozprostřená přes několik důlků najednou a stahuje se k těm hlubším. V generaci 8 je nejlepší jedinec ještě v sousedním důlku (f ≈ 1,49), ale velikost kroku už klesla z 2 na 0,27. V generaci 15 je populace v globálním minimu a krok se zmenšil na setinu, aby ho mohla dopilovat.

Ze sta běhů s různými semínky našla (15, 100)-ES globální minimum v 32 případech. Pro srovnání (1+1)-ES s pravidlem jedné pětiny a stejným rozpočtem 8 000 ohodnocení: v jednom jediném. Na koulích je jeden jedinec nejrychlejší, na členitém terénu vyhrává populace — a i ta často skončí v některém ze sousedních důlků.

4. CMA-ES

Sebeadaptace ladí jen délku kroku. Co když je minimum v úzkém šikmém údolí, kde se vyplatí dělat dlouhé kroky jedním směrem a krátké jiným? CMA-ES (Hansen a Ostermeier, 2001) se z úspěšných kroků učí celou kovarianční matici mutace — tvar oblaku, ze kterého potomky losuje. Oblak se během hledání natáčí a protahuje podél údolí. Pro optimalizaci spojitých funkcí, u kterých neznáme gradient, je dnes CMA-ES jednou z nejspolehlivějších metod.

Definice — mutace s kovarianční maticí

Nechť n ≥ 1 a C ∈ ℝ^n×n je symetrická (C = C^T) pozitivně definitní matice (v^TCv > 0 pro všechna v ∈ ℝⁿ, v ≠ 0). Náhodný vektor z má rozdělení N(0, C), právě když má stejné rozdělení jako

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

(rozdělení na volbě A nezávisí; takové A vždy existuje, např. Choleského rozklad). Pak Ez = 0 a E[z_iz_j] = C_ij pro všechna i, j = 1, …, n; C je tedy kovarianční matice vektoru z.

Nechť m ∈ ℝⁿ je střed populace a σ > 0 velikost kroku. Mutace s kovarianční maticí C vytvoří potomka

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

Body se stejnou hustotou leží na elipsoidu; jeho osy jsou vlastní vektory C a délky os úměrné odmocninám vlastních čísel. Pro C = I je to koule a dostaneme obyčejnou evoluční strategii.

Zjednodušeně (skutečná CMA-ES k tomu přidává ještě takzvané evoluční cesty a vlastní řízení σ, viz N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) se matice po každé generaci posune k úspěšným krokům:

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

C: kovarianční matice mutace — tvar oblaku, ze kterého se losují potomci
1 − c: paměť — stará matice se jen trochu přiblíží nové informaci, protože jedna generace je malý a náhodný vzorek
c: učící rychlost matice, číslo mezi 0 a 1 — kolik váhy dostanou kroky poslední generace
∑ w_i: vážený průměr přes μ nejlepších potomků; váhy jsou kladné, sečtou se na 1 a lepší potomek má větší — učíme se jen z kroků, které se vyplatily
z_iz_i^T: úspěšný krok z_i = y_i − m/σ jako matice — protáhne oblak právě v jeho směru

Směry, ve kterých se dařilo, dostanou v příští generaci větší rozptyl.

Příklad — jeden úspěšný krok po diagonále

C = I (kruhový oblak), jediný úspěšný krok z = (1, 1), tedy μ = 1 a w₁ = 1, c = 0,2 (barvy podle vzorce výše):

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 ve směru (1, 1) a 1 − 0,2 = 0,8 ve směru (1, −1)

Oblak se protáhl podél úspěšného směru a zúžil napříč — po pár takových generacích leží podél údolí.

5. Genetické programování

Definice — program jako strom

Nechť 𝓕 je konečná množina funkcí, kde každá h ∈ 𝓕 má aritu ar(h) ∈ ℕ, ar(h) ≥ 1 (počet argumentů), a 𝓣 konečná množina terminálů (proměnné a konstanty). Množina programů nad 𝓕 a 𝓣 je nejmenší množina kořenových stromů, pro kterou platí:

každý terminál t ∈ 𝓣 je program — strom s jediným uzlem t;
jsou-li h ∈ 𝓕, k = ar(h) a g₁, …, g_k programy, je program i strom h(g₁, …, g_k) s kořenem h a podstromy g₁, …, g_k v tomto pořadí.

Vnitřní uzly jsou tedy funkce s tolika dětmi, kolik je jejich arita, a listy jsou terminály. Velikost programu |g| je počet jeho uzlů. Při daných hodnotách proměnných je hodnota programu definována rekurzivně od listů ke kořeni: hodnota terminálu je jeho hodnota a hodnota h(g₁, …, g_k) je h použitá na hodnoty g₁, …, g_k.

Uzavřenost: nechť D je množina hodnot (zde ℝ). Množina 𝓕 je uzavřená, právě když každá h ∈ 𝓕 je definovaná pro všechny vstupy, tj. je to funkce h : D^ar(h) → D; pak má hodnotu každý program. Proto se používá chráněné dělení, a ÷ b = a/b pro |b| ≥ 10⁻⁹ a a ÷ b = 1 jinak, a odmocnina z absolutní hodnoty, √|a|.

Laicky řečeno

Vzorec a/5 · √a je strom: nahoře násobení, pod ním dělení a odmocnina, dole a a pětka. Genetické programování křižuje programy tak, že jednomu odstřihne větev a na její místo přiroubuje větev z druhého. Mutace nahradí větev náhodně vyrostlou novou. Chráněné operace zajistí, že žádný program nespadne, jen může dávat nesmysly — a ty výběr vyřadí.

John Koza z Univerzity ve Stanfordu sepsal metodu v roce 1992 v knize Genetic Programming a ukázal ji na desítkách úloh, od řízení robota po hledání vzorců.

Příklad — vyhodnocení stromu programu pro Zemi

Strom programu a/5 · √a má v kořeni násobení, vlevo dělení a ÷ 5, vpravo √a. Od listů ke kořeni, a = 149,6 (milionů km):

levá větev: a/5 = 149,6/5 = 29,92

pravá větev: √a = √149,6 ≈ 12,231

kořen: 29,92 × 12,231 ≈ 365,95 dne (skutečnost 365,26, odchylka +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # elitismus: jeden nejlepší
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # křížení výměnou podstromů
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # mutace: větev → nová náhodná
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # příliš hluboké děti zahodíme
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # nejmenší chyba; při shodě menší strom

6. Symbolická regrese: Keplerův zákon

Johannes Kepler hledal vztah mezi vzdáleností planety od Slunce a její oběžnou dobou deset let; třetí zákon publikoval v roce 1619. Dáme genetickému programování stejnou úlohu. Má k dispozici osm planet — velkou poloosu a v milionech kilometrů a oběžnou dobu T ve dnech —, operace +, −, ×, ÷ a √, proměnnou a a číslice 1 až 9. Chybou programu je průměrná relativní odchylka od skutečných oběžných dob. Populace má 300 programů a 40 generací.

Definice — symbolická regrese

Nechť (x₁, y₁), …, (x_N, y_N) ∈ X × ℝ jsou data (X množina vstupů, např. ℝ^d), 𝓟 množina programů nad zvolenými funkcemi 𝓕 a terminály 𝓣 (definice výše; proměnné odpovídají složkám vstupu) a ℓ : ℝ × ℝ → [0, ∞] ztrátová funkce. Symbolická regrese je optimalizační úloha najít

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

kde g(x_i) je hodnota programu g pro vstup x_i. Na rozdíl od běžné regrese tedy není předem dán tvar modelu s neznámými parametry — hledá se sám výraz, jen ze zadaných stavebních kamenů.

Laicky řečeno

Lineární regrese z dílu o statistice hledá nejlepší přímku. Symbolická regrese nehledá čísla ve známém vzorci, ale vzorec sám — a výsledek si může přečíst člověk.

Přesně je chyba programu g průměr absolutních rozdílů logaritmů:

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

1/8 ∑: průměr přes osm planet — chyba nezávisí na tom, kolik dat máme, a dá se číst jako „typická odchylka na planetu“
| … |: absolutní hodnota — předpověď o 1 % větší i menší je stejně špatná a chyby různých znamének se nevyruší
ln g(a_i) − ln T_i: rozdíl logaritmů je ln g(a_i)/T_i, tedy relativní odchylka: pro malé odchylky ln(1 + r) ≈ r. Oběžné doby se liší skoro tisíckrát (88 dní Merkur, 60 190 Neptun); s obyčejným rozdílem by o chybě rozhodoval jen Neptun

Průměrná relativní odchylka, ve které má Merkur stejnou váhu jako Neptun. Program se záporným nebo nekonečným výsledkem dostane chybu ∞.

Nejlepší program počáteční, náhodné populace se od skutečných oběžných dob odchyluje v průměru o 32 %. Ve třetí generaci už má odchylku 8 % a správný tvar a^1,5, jen s konstantou 0,22. V patnácté generaci přijde tohle:

Nejlepší program v generaci 15 ((a ÷ 5) × √(a))

T = a · √a/5 — tedy T úměrné a^3/2, neboli T² úměrné a³. To je Keplerův třetí zákon. Průměrná odchylka je 0,30 % a konstanta 1/5 je velmi blízko skutečné hodnotě 0,1996 pro tyto jednotky. Ze dvaceti běhů s různými semínky našlo exponent 1,5 osmnáct.

Odkud je 0,1996? Z Newtonova gravitačního zákona plyne pro kruhovou dráhu (a pro elipsu s velkou poloosou a, když je hmotnost planety proti Slunci zanedbatelná) tvar zákona i s konstantou:

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

T: oběžná doba — čas jednoho oběhu
2π: jeden oběh je úhel 2π; vzorec vznikne z úhlové rychlosti ω jako T = 2π/ω
√GM_☉: síla gravitace Slunce (G gravitační konstanta, M_☉ hmotnost Slunce) — silnější přitažlivost znamená rychlejší oběh, proto je ve jmenovateli
a^3/2: vzdálenost — gravitace slábne s a² a dráha je delší úměrně a; z rovnosti dostředivé a gravitační síly ω²a = GM_☉/a² vyjde ω ∝ a^−3/2

Keplerův třetí zákon odvozený z Newtonovy gravitace; genetické programování našlo tvar a^3/2 i konstantu jen z osmi dvojic čísel.

Příklad — konstanta v milionech km a dnech

Gravitační parametr Slunce GM_☉ = 1,327 124 · 10²⁰ m³/s² (nominální hodnota Mezinárodní astronomické unie, rezoluce B3 z roku 2015). Jednotka délky je 10⁹ m, takže a^3/2 v metrech je (10⁹)^3/2 = √10²⁷ krát víc. Konstanta v sekundách je 2π/√GM_☉ · √10²⁷ (barvy podle vzorce výše):

√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/den ≈ 0,1996 dne

Program s konstantou 1/5 = 0,2 se tedy liší o 0,19 % — přesně tolik, kolik vyšla odchylka u Země výše.

7. Nabobtnání

Evoluce ale u krásného vzorce nezůstala. Do generace 40 „zlepšila“ odchylku na 0,23 % tímhle:

Nejlepší program v generaci 40 (((a + ((((2 × 8) − a) ÷ 5) ÷ a)) ÷ 5) × √(a))

Strom má místo šesti uzlů šestnáct a přidané větve nedělají nic jiného, než že doladí konstantu a obejdou zaokrouhlení v datech. Fyzikálně je to horší vzorec — přeučený na osm planet. Průměrná velikost programu v populaci přitom vzrostla z 9,8 uzlu na začátku na 23,8 ve dvacáté generaci.

Definice — nabobtnání a tlak na úspornost

Nechť P₀, P₁, … jsou populace programů v po sobě jdoucích generacích, |g| velikost programu g (počet uzlů stromu) a F(g) ≥ 0 jeho chyba na datech (menší je lepší). Označme s̄_t průměrnou velikost programů v P_t.

Nabobtnání (bloat) je jev, kdy s̄_t s rostoucím t výrazně roste, aniž by tomu odpovídal pokles chyby F — programy přibývají uzly, které chybu nesnižují vůbec nebo jen nepatrně. (Jde o pozorovaný jev, ne o pojem s jedinou přesnou mezí, kdy růst ještě je a kdy už není „odpovídající“.)

Tlak na úspornost (parsimony pressure) je úprava výběru, která zvýhodní menší programy. Nechť c > 0. Používají se dvě podoby:

trest za velikost: výběr porovnává programy podle upravené chyby F′(g) = F(g) + c · |g|;
lexikografické porovnání: program g je lepší než h, právě když F(g) < F(h), nebo F(g) = F(h) ∧ |g| < |h| — velikost rozhoduje jen při shodě chyb.

Laicky řečeno

Programy obrůstají kódem, který nic nedělá nebo dělá nepatrnou korekci — podobně jako se v genomech živých organismů hromadí úseky bez funkce. Velký strom navíc hůř rozbije křížení, takže se množí snáz. Náš algoritmus dává při stejné chybě přednost menšímu stromu, ale když větší strom chybu o chlup sníží, vyhraje. Stejné dilema jako u přeučení modelu: přesnost na datech, nebo jednoduchost, která zobecňuje?

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

F′(g): upravená chyba, podle které se vybírá — menší je lepší
F(g): chyba programu na datech — pořád to hlavní, co chceme snížit
c: cena jednoho uzlu — říká, o kolik se musí chyba zlepšit, aby se vyplatil uzel navíc; volí se tak, aby rozhodovala jen u zanedbatelných zlepšení
|g|: velikost programu, počet uzlů stromu — měřítko složitosti, které se dá spočítat bez porozumění programu

Uzel navíc musí zaplatit tím, že chybu sníží aspoň o c.

Příklad — jak velké c by zachránilo Keplerův zákon

Strom z generace 15: chyba 0,2986 %, 6 uzlů. Strom z generace 40: chyba 0,2312 %, 16 uzlů. Menší strom vyhraje, když

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

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

(Barvy podle vzorce výše: obě strany nerovnosti jsou upravené chyby F′.)

Deset uzlů navíc zlepšilo chybu o necelou setinu procenta. S cenou nad 0,007 % za uzel by ve výběru strom z generace 40 prohrál s čitelným zákonem z generace 15.

8. Evoluční strategie a programy dnes

Evoluční strategie místo zpětnovazebního učení. OpenAI v roce 2017 ukázala, že jednoduchá evoluční strategie zvládne učit neuronové sítě ovládat simulované roboty a hrát hry Atari podobně dobře jako zpětnovazební učení — a dá se rozložit na tisíce procesorů, které si posílají jen pár čísel.
Objevování zákonů z dat. Schmidt a Lipson v roce 2009 nechali symbolickou regresi odvodit pohybové zákony a zákony zachování z měření kyvadel. Dnešní knihovny jako PySR se používají ve fyzice a astronomii, kde je čitelný vzorec cennější než černá skříňka.
Evoluce algoritmů strojového učení. Projekt AutoML-Zero (Google, 2020) nechal evoluci sestavovat učicí algoritmy z elementárních matematických operací a znovu tak objevil například zpětné šíření chyby.
Programy s jazykovými modely. Systémy FunSearch a AlphaEvolve z minulého dílu jsou genetické programování, ve kterém mutaci místo náhodné větve dělá jazykový model.

9. Shrnutí

Evoluční strategie mutují reálná čísla normálním šumem s velikostí kroku σ.
Pravidlo jedné pětiny a sebeadaptace nastavují σ automaticky; CMA-ES se učí i tvar mutací.
Na koulích stačí jeden jedinec, na členitém terénu pomáhá populace: na Rastriginově funkci 32 úspěchů ze 100 proti jednomu.
Genetické programování pěstuje programy jako stromy; symbolická regrese z dat o planetách našla Keplerův třetí zákon.
Programy mají sklon nabobtnávat a přeučovat se — proti tomu pomáhá tlak na úspornost.

Chcete si to osahat? Nechte AI agenta napsat symbolickou regresi a dejte jí vlastní data — třeba dobu kmitu kyvadla podle délky provázku — a sledujte, jestli najde √L.

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

Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon

1. Evoluce čísel: (1+1)-ES

2. Pravidlo jedné pětiny

3. Populace a sebeadaptace

4. CMA-ES

5. Genetické programování

6. Symbolická regrese: Keplerův zákon

7. Nabobtnání

8. Evoluční strategie a programy dnes

9. Shrnutí

Agent na vašem počítači, ovládaný z telefonu