Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera

(1+1)-ES i reguła jednej piątej, populacja i samoadaptacja na funkcji Rastrigina, CMA-ES, programy jako drzewa, regresja symboliczna, która w danych o planetach znajduje trzecie prawo Keplera, i rozrost programów.

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

Seria Podstawy AI Część 28 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

W latach sześćdziesiątych dwaj studenci berlińskiego Uniwersytetu Technicznego, Ingo Rechenberg i Hans-Paul Schwefel, stali w tunelu aerodynamicznym nad płytą z przegubami. Chcieli znaleźć kształt o najmniejszym oporze, ale do obliczeń brakowało i równań, i komputerów. Więc losowali: losowo obracali przeguby, mierzyli opór, a gdy był mniejszy, zostawiali nowy kształt. Z tego eksperymentu powstała strategia ewolucyjna — ewolucja, która zamiast jedynek i zer stroi liczby. Ćwierć wieku później John Koza pokazał, że ewolucją można hodować także całe programy.

Ten odcinek nawiązuje do artykułu Algorytmy genetyczne. Tam osobnik był ciągiem bitów; tutaj będzie wektorem liczb rzeczywistych i drzewem programu.

1. Ewolucja liczb: (1+1)-ES

Algorytm — (1+1)-ES

Minimalizujemy f : ℝⁿ → ℝ. Osobnik to punkt x ∈ ℝⁿ, σ > 0 to rozmiar kroku. W każdym pokoleniu:

1. utwórz potomka y = x + σ · z, gdzie z ~ N(0, I) jest wektorem niezależnych liczb o rozkładzie normalnym;
2. jeśli f(y) ≤ f(x), zastąp x ← y.

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

y

potomek — nowy kandydat, którego ocenimy

x

rodzic — najlepszy dotąd znaleziony punkt; potomek powstaje w jego otoczeniu, bo blisko dobrego punktu zwykle leżą inne dobre punkty

σ

rozmiar kroku — jedna liczba, która określa, jak daleko od rodzica się szuka; szum z ma wariancję 1, dopiero σ nadaje mu skalę zadania

z ~ N(0, I)

kierunek i długość próby — średnia 0 oznacza, że żaden kierunek nie jest z góry uprzywilejowany; macierz jednostkowa I, że wszystkie współrzędne zmieniają się niezależnie i równie mocno

Definicja — rozkład normalny N(0, 1) i N(0, I)

Zmienna losowa Z ma standardowy rozkład normalny N(0, 1), jeśli ma gęstość φ(z) = e^−z²/2 / √(2π); jej wartość oczekiwana wynosi 0, a wariancja 1. Około 68 % wartości leży w przedziale [−1, 1], a 95 % w [−1,96; 1,96].

Wektor z ~ N(0, I) w ℝⁿ ma n niezależnych składowych o rozkładzie N(0, 1). Jego długość wynosi zwykle około √n (dla n = 10 około 3,2), bo E‖z‖² = n.

Nasz program wytwarza liczby normalne metodą Boxa–Mullera z dwóch liczb o rozkładzie jednostajnym u₁, u₂ ∈ (0, 1): z = √(−2 ln u₁) · cos(2πu₂).

Spróbujmy na najprostszej możliwej funkcji, sferze f(x) = x₁² + … + x₁₀² w dziesięciu wymiarach. Minimum jest oczywiście w zerze; zaczynamy w punkcie (3, …, 3), gdzie f = 90. Jak wybrać σ? Duża wartość potrafi szybko zejść ze zbocza, ale w pobliżu minimum ciągle przestrzeliwuje. Mała jest dokładna, ale do dna idzie całą wieczność.

2. Reguła jednej piątej

Definicja — reguła jednej piątej (Rechenberg, 1973)

Jeśli odsetek udanych mutacji (potomek lepszy od rodzica) jest większy niż 1/5, zwiększ σ; jeśli jest mniejszy, zmniejsz go. Jedna z możliwych postaci: po sukcesie σ ← σ · e^1/3, po porażce σ ← σ · e^−1/12. Rozmiar kroku średnio się nie zmienia dokładnie wtedy, gdy udaje się jedna piąta mutacji: (1/5) · (1/3) = (4/5) · (1/12).

Obie gałęzie reguły można zapisać jednym wzorem; s = 1 po sukcesie i 0 po porażce:

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

σ

rozmiar kroku — zmienia się przez mnożenie, nie dodawanie: pozostaje dodatni, a krok może zmaleć o wiele rzędów wielkości (z 1 aż do tysięcznych), jak tego wymaga bliskość minimum

5/12

szybkość dostosowania — po sukcesie exp(5/12 · 4/5) = e^1/3 ≈ 1,40, po porażce exp(−5/12 · 1/5) = e^−1/12 ≈ 0,92; większa liczba reagowałaby szybciej, ale σ bardziej by się wahała

s

wynik ostatniej próby (1 = potomek nie był gorszy) — jedyna informacja, jakiej reguła potrzebuje

1/5

docelowy odsetek sukcesów — gdy udaje się dokładnie jedna piąta prób, średnia s − 1/5 wynosi zero i σ średnio się nie zmienia

Reguła jednej piątej schodzi poniżej 10⁻⁶ po 587 obliczeniach — a linia na wykresie opada równomiernie, bo krok maleje równie szybko, jak zbliża się minimum. Ze stałym σ = 1 algorytm szybko trafia na „podłogę” w okolicach jedynki, poniżej której z tak dużymi skokami zejść się nie da. Z σ = 0,01 schodzi w dół, ale powoli: nawet po 5 000 obliczeniach nie jest poniżej 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)     # sukces: dodaj
        else:
            sigma *= math.exp(-1 / 12)   # porażka: ujmij
    return x, fx

Przykład — pierwsze dwanaście kroków przebiegu z wykresu

Start x = (3, …, 3), f(x) = 90, σ = 1. Kolumna σ to rozmiar kroku po aktualizacji:

krok	f(y)	sukces?	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	tak	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 porażkach: σ = e^−8/12 ≈ 0,513

9. krok się udaje (86,27 < 90): σ = 0,513 · e^1/3 ≈ 0,513 · 1,396 ≈ 0,717

Przy σ = 1 krok w dziesięciu wymiarach ma długość około √10 ≈ 3,2, a pierwszych ośmiu potomków jest gorszych od startu, więc reguła ściąga krok. Potem sukcesy przychodzą częściej i σ ustala się tam, gdzie udaje się mniej więcej co piąta próba — w całym przebiegu udało się 99 z 587 prób, czyli 17 %. W miarę jak punkt zbliża się do minimum, maleje razem z nim i krok: pod koniec przebiegu, po 580 obliczeniach, σ ≈ 0,00055.

3. Populacja i samoadaptacja

Sfera ma jedno minimum. Prawdziwe zadania mają ich często mnóstwo — i tam jeden osobnik nie wystarczy. Typową funkcją testową jest funkcja Rastrigina: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). To sfera, w której ktoś wyżłobił regularną siatkę dołków; minimum globalne 0 jest w początku układu, a wokół niego setki lokalnych.

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

10n

przesunięcie w górę — cosinus odejmuje w początku układu najwyżej 10 na każdą współrzędną, stała to oddaje, aby minimum globalne miało wartość dokładnie 0

x_i²

sfera — ogólne nachylenie ku początkowi układu; bez niej wszystkie dołki byłyby równie głębokie i żadne minimum nie byłoby globalne

10 cos 2πx_i

fale o okresie 1 i amplitudzie 10 — wydrążają dołek przy każdej liczbie całkowitej; amplituda jest dużo większa niż nachylenie sfery między sąsiednimi dołkami, więc przeszukiwanie lokalne utknie w najbliższym dołku

Przykład — start i sąsiednie dołki (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

f = 20 + (17,64 − 3,09) + (14,44 − 3,09) ≈ 45,90

dno dołków obok początku układu, przy (±1; 0) i (0; ±1): f ≈ 0,99 (w punkcie 0,995, nie dokładnie 1 — sfera ciągnie go do początku układu)

dno dołków po przekątnej przy (±1; ±1): f ≈ 1,99

Wartość 1,49 w pokoleniu 8 (zob. niżej) oznacza więc populację w sąsiednim dołku, jeszcze nie na jego dnie.

Definicja — (μ, λ)-ES i (μ + λ)-ES z samoadaptacją

Populacja ma μ rodziców; każde pokolenie tworzy λ > μ potomków. W (μ, λ) przeżywa μ najlepszych potomków, a rodzice giną; w (μ + λ) wybiera się z rodziców i potomków razem.

Samoadaptacja: każdy osobnik niesie własny rozmiar kroku σ. Potomek najpierw go mutuje, σ′ = σ · e^{τ · N(0, 1)} z τ ≈ 1/√(2n), i dopiero nim przesuwa położenie: y = x + σ′ · N(0, I).

σ′ = σ · e^{τ · N(0, 1)},   τ = 1/√(2n)

σ′

krok potomka — od razu przesuwa się nim położenie, więc przystosowanie potomka zdradzi, czy krok był dobry

σ

krok rodzica — dziedziczy się; potomek zaczyna od tego, co sprawdziło się u rodzica

τ

współczynnik uczenia kroku — jak bardzo krok może się zmienić między pokoleniami; maleje wraz z liczbą wymiarów n, bo jedna wartość przystosowania niesie wtedy mniej informacji o tym, czy krok był dobry

N(0, 1)

losowa zmiana — symetryczna wokół zera, więc zwiększenie i zmniejszenie są równie prawdopodobne; o kierunku decyduje dopiero selekcja

Przykład — mutacja kroku dla n = 2

τ = 1/√(2 · 2) = 1/2

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

Typowy potomek próbuje więc kroku mniej więcej od 40 % mniejszego do 65 % większego niż rodzic. W naszym przebiegu krok najlepszego osobnika spadł w 15 pokoleniach z 2 do 0,011 — prawie dwustukrotnie.

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)                    # losowy rodzic
            s = s * math.exp(tau * random.gauss(0, 1))      # najpierw zmutuj krok
            y = [xi + s * random.gauss(0, 1) for xi in x]   # potem nim położenie
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): przeżywają tylko najlepsi potomkowie
    return rodice[0]

Populacja startuje wokół punktu (4,2; −3,8), gdzie f ≈ 45,9. Na początku jest rozłożona na kilka dołków naraz i ściąga się ku głębszym. W pokoleniu 8 najlepszy osobnik jest jeszcze w sąsiednim dołku (f ≈ 1,49), ale rozmiar kroku spadł już z 2 do 0,27. W pokoleniu 15 populacja jest w minimum globalnym, a krok zmalał do setnej, by mogła je doszlifować.

Ze stu przebiegów z różnymi ziarnami (15, 100)-ES znalazła minimum globalne w 32 przypadkach. Dla porównania (1+1)-ES z regułą jednej piątej i tym samym budżetem 8 000 obliczeń: w jednym jedynym. Na sferach jeden osobnik jest najszybszy, w urozmaiconym terenie wygrywa populacja — i nawet ona często kończy w którymś z sąsiednich dołków.

4. CMA-ES

Samoadaptacja stroi tylko długość kroku. A jeśli minimum leży w wąskiej ukośnej dolinie, gdzie opłaca się robić długie kroki w jednym kierunku, a krótkie w innym? CMA-ES (Hansen i Ostermeier, 2001) uczy się z udanych kroków całej macierzy kowariancji mutacji — kształtu chmury, z której losuje potomków. W trakcie poszukiwań chmura obraca się i wydłuża wzdłuż doliny. Do optymalizacji funkcji ciągłych, których gradientu nie znamy, jest dziś CMA-ES jedną z najbardziej niezawodnych metod.

Definicja — mutacja z macierzą kowariancji

Dla symetrycznej dodatnio określonej macierzy C ∈ ℝ^n×n z ~ N(0, C) jest wektorem o wartości oczekiwanej 0 i kowariancjach E[z_iz_j] = C_ij. Wytwarza się go ze zwykłego szumu: z = Au, gdzie u ~ N(0, I) i AA^T = C. Potomek to y = m + σ · z, gdzie m jest środkiem populacji.

Punkty o tej samej gęstości leżą na elipsoidzie; jego osie to wektory własne C, a długości osi są proporcjonalne do pierwiastków wartości własnych. Dla C = I jest to sfera i dostajemy zwykłą strategię ewolucyjną.

W uproszczeniu (prawdziwa CMA-ES dodaje do tego jeszcze tak zwane ścieżki ewolucyjne i własne sterowanie σ, zob. N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) macierz po każdym pokoleniu przesuwa się ku udanym krokom:

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

C

macierz kowariancji mutacji — kształt chmury, z której losuje się potomków

1 − c

pamięć — stara macierz tylko trochę zbliża się do nowej informacji, bo jedno pokolenie to mała i losowa próbka

c

współczynnik uczenia macierzy, liczba między 0 a 1 — ile wagi dostają kroki ostatniego pokolenia

∑ w_i

średnia ważona po μ najlepszych potomkach; wagi są dodatnie, sumują się do 1, a lepszy potomek ma większą — uczymy się tylko z kroków, które się opłaciły

z_iz_i^T

udany krok z_i = (y_i − m)/σ jako macierz — wydłuża chmurę właśnie w jego kierunku

Przykład — jeden udany krok po przekątnej

C = I (okrągła chmura), jedyny udany krok z = (1, 1), c = 0,2:

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

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

wartości własne: 1 + 0,2 = 1,2 w kierunku (1, 1) i 1 − 0,2 = 0,8 w kierunku (1, −1)

Chmura wydłużyła się wzdłuż udanego kierunku i zwęziła w poprzek — po kilku takich pokoleniach leży wzdłuż doliny.

5. Programowanie genetyczne

Definicja — program jako drzewo

Dany jest zbiór funkcji F (z arnościami) i zbiór terminali T (zmienne i stałe). Program to drzewo z korzeniem, którego węzły wewnętrzne są funkcjami z F z tyloma dziećmi, ile wynosi ich arność, a liście terminalami z T. Wartość programu oblicza się od liści do korzenia.

Domkniętość: każda funkcja musi przyjąć wynik dowolnej innej. Dlatego używa się chronionego dzielenia (dzielenie przez zero zwraca 1) i pierwiastka z wartości bezwzględnej.

John Koza z Uniwersytetu Stanforda opisał metodę w 1992 roku w książce Genetic Programming i pokazał ją na dziesiątkach zadań, od sterowania robotem po szukanie wzorów.

Przykład — obliczenie drzewa (a ÷ 5) × √a dla Ziemi

Od liści do korzenia, a = 149,6 (milionów km):

lewa gałąź: a ÷ 5 = 149,6 / 5 = 29,92

prawa gałąź: √a = √149,6 ≈ 12,231

korzeń: 29,92 × 12,231 ≈ 365,95 dnia   (w rzeczywistości 365,26, odchylenie +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # elitaryzm: jeden najlepszy
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # krzyżowanie przez wymianę poddrzew
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # mutacja: gałąź → nowa losowa
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # zbyt głębokie dzieci odrzucamy
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # najmniejszy błąd; przy remisie mniejsze drzewo

6. Regresja symboliczna: prawo Keplera

Johannes Kepler szukał związku między odległością planety od Słońca a jej okresem obiegu przez dziesięć lat; trzecie prawo opublikował w 1619 roku. Dajmy programowaniu genetycznemu to samo zadanie. Ma do dyspozycji osiem planet — wielką półoś a w milionach kilometrów i okres obiegu T w dniach —, działania +, −, ×, ÷ i √, zmienną a i cyfry od 1 do 9. Błędem programu jest średnie względne odchylenie od rzeczywistych okresów obiegu. Populacja liczy 300 programów i 40 pokoleń.

Definicja — regresja symboliczna

Dla danych (x_i, y_i) regresja symboliczna szuka wyrażenia g z danej gramatyki (funkcji i terminali), które minimalizuje błąd ∑ ℓ(g(x_i), y_i). W odróżnieniu od zwykłej regresji kształt modelu nie jest z góry dany, tylko cegiełki.

Dokładnie błąd programu g to średnia wartości bezwzględnych różnic logarytmów:

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

(1/8) ∑

średnia po ośmiu planetach — błąd nie zależy od tego, ile mamy danych, i da się go czytać jako „typowe odchylenie na planetę”

| … |

wartość bezwzględna — przewidywanie o 1 % za duże jest tak samo złe jak o 1 % za małe, a błędy o różnych znakach się nie znoszą

ln g(a_i) − ln T_i

różnica logarytmów to ln(g/T), czyli odchylenie względne: dla małych odchyleń ln(1 + r) ≈ r. Okresy obiegu różnią się prawie tysiąckrotnie (88 dni Merkury, 60 190 Neptun); przy zwykłej różnicy o błędzie decydowałby tylko Neptun

Najlepszy program początkowej, losowej populacji odchyla się od rzeczywistych okresów obiegu średnio o 32 %. W trzecim pokoleniu ma już odchylenie 8 % i właściwy kształt a^1,5, tylko ze stałą 0,22. W piętnastym pokoleniu przychodzi to:

T = a · √a / 5 — czyli T proporcjonalne do a^3/2, albo T² proporcjonalne do a³. To trzecie prawo Keplera. Średnie odchylenie wynosi 0,30 %, a stała 1/5 jest bardzo blisko prawdziwej wartości 0,1996 dla tych jednostek. Spośród dwudziestu przebiegów z różnymi ziarnami wykładnik 1,5 znalazło osiemnaście.

Skąd 0,1996? Z prawa powszechnego ciążenia Newtona wynika dla orbity kołowej (i dla elipsy o wielkiej półosi a, gdy masa planety jest wobec Słońca zaniedbywalna) postać prawa razem ze stałą:

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

T

okres obiegu — czas jednego obiegu

2π

jeden obieg to kąt 2π; wzór powstaje z prędkości kątowej ω jako T = 2π/ω

√(GM_☉)

siła grawitacji Słońca (G stała grawitacji, M_☉ masa Słońca) — silniejsze przyciąganie oznacza szybszy obieg, dlatego jest w mianowniku

a^3/2

odległość — grawitacja słabnie z a², a droga jest dłuższa proporcjonalnie do a; z równości siły dośrodkowej i grawitacyjnej ω²a = GM_☉/a² wychodzi ω ∝ a^−3/2

Przykład — stała w milionach km i dniach

Parametr grawitacyjny Słońca GM_☉ = 1,327 124 · 10²⁰ m³/s² (wartość nominalna Międzynarodowej Unii Astronomicznej, rezolucja B3 z 2015 roku). Jednostka długości to 10⁹ m, więc a^3/2 w metrach jest (10⁹)^3/2 = √(10²⁷) razy większe:

√(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/dzień ≈ 0,1996 dnia

Program ze stałą 1/5 = 0,2 różni się więc o 0,19 % — dokładnie tyle, ile wyszło odchylenie dla Ziemi powyżej.

7. Rozrost programów

Ewolucja nie zatrzymała się jednak na pięknym wzorze. Do pokolenia 40 „poprawiła” odchylenie do 0,23 % czymś takim:

Drzewo ma zamiast sześciu węzłów szesnaście, a dodane gałęzie nie robią nic innego, niż dostrajają stałą i obchodzą zaokrąglenia w danych. Fizycznie to gorszy wzór — przeuczony na osiem planet. Średni rozmiar programu w populacji wzrósł przy tym z 9,8 węzła na początku do 23,8 w dwudziestym pokoleniu.

Definicja — rozrost i presja oszczędności

Rozrost (bloat) to wzrost rozmiaru programów w populacji, który nie odpowiada poprawie ich przystosowania. Presja oszczędności (parsimony pressure) karze za rozmiar: albo dolicza go do błędu, F′(g) = F(g) + c · |g|, albo używa go jako drugiego kryterium przy równych błędach.

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

F′(g)

skorygowany błąd, według którego się wybiera — mniejszy jest lepszy

F(g)

błąd programu na danych — nadal to główne, co chcemy obniżyć

c

cena jednego węzła — mówi, o ile musi poprawić się błąd, żeby opłacił się dodatkowy węzeł; dobiera się ją tak, by rozstrzygała tylko przy znikomych poprawach

|g|

rozmiar programu, liczba węzłów drzewa — miara złożoności, którą da się policzyć bez rozumienia programu

Przykład — jak duże c uratowałoby prawo Keplera

Drzewo z pokolenia 15: błąd 0,2986 %, 6 węzłów. Drzewo z pokolenia 40: błąd 0,2312 %, 16 węzłów. Mniejsze drzewo wygrywa, gdy

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

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

Dziesięć dodatkowych węzłów poprawiło błąd o niecałą setną procenta. Przy cenie powyżej 0,007 % za węzeł drzewo z pokolenia 40 przegrałoby w selekcji z czytelnym prawem z pokolenia 15.

8. Strategie ewolucyjne i programy dziś

• Strategie ewolucyjne zamiast uczenia ze wzmocnieniem. OpenAI w 2017 roku pokazała, że prosta strategia ewolucyjna potrafi uczyć sieci neuronowe sterowania symulowanymi robotami i grania w gry Atari podobnie dobrze jak uczenie ze wzmocnieniem — i da się ją rozłożyć na tysiące procesorów, które przesyłają sobie tylko kilka liczb.
• Odkrywanie praw z danych. Schmidt i Lipson w 2009 roku kazali regresji symbolicznej wyprowadzić prawa ruchu i prawa zachowania z pomiarów wahadeł. Dzisiejsze biblioteki, takie jak PySR, są używane w fizyce i astronomii, gdzie czytelny wzór jest cenniejszy niż czarna skrzynka.
• Ewolucja algorytmów uczenia maszynowego. Projekt AutoML-Zero (Google, 2020) pozwolił ewolucji składać algorytmy uczące z elementarnych operacji matematycznych i odkrył w ten sposób na nowo na przykład wsteczną propagację błędu.
• Programy z modelami językowymi. Systemy FunSearch i AlphaEvolve z poprzedniego odcinka to programowanie genetyczne, w którym mutację zamiast losowej gałęzi wykonuje model językowy.

9. Podsumowanie

• Strategie ewolucyjne mutują liczby rzeczywiste szumem normalnym o rozmiarze kroku σ.
• Reguła jednej piątej i samoadaptacja ustawiają σ automatycznie; CMA-ES uczy się także kształtu mutacji.
• Na sferach wystarczy jeden osobnik, w urozmaiconym terenie pomaga populacja: na funkcji Rastrigina 32 sukcesy na 100 wobec jednego.
• Programowanie genetyczne hoduje programy jako drzewa; regresja symboliczna znalazła w danych o planetach trzecie prawo Keplera.
• Programy mają skłonność do rozrastania się i przeuczania — przeciw temu pomaga presja oszczędności.

Chcesz to wypróbować na własnej skórze? Niech agent AI napisze regresję symboliczną, daj jej własne dane — na przykład okres wahadła w zależności od długości sznurka — i patrz, czy znajdzie √L.

Masz inne zdanie? Napisz na support@coden-app.com.