Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера

(1+1)-ES і правило однієї п’ятої, популяція і самоадаптація на функції Растригіна, CMA-ES, програми як дерева, символьна регресія, яка в даних про планети знаходить третій закон Кеплера, і розбухання програм.

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 28 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

У шістдесятих роках двоє студентів Берлінського технічного університету, Інго Рехенберг і Ганс-Пауль Швефель, стояли в аеродинамічній трубі над шарнірною пластиною. Вони хотіли знайти форму з найменшим опором, але для розрахунку бракувало і рівнянь, і комп’ютерів. Тож вони кидали жереб: навмання повертали шарніри, вимірювали опір, і коли він був меншим, залишали нову форму. З того досліду постала еволюційна стратегія — еволюція, яка замість одиниць і нулів налаштовує числа. Через чверть століття Джон Коза показав, що еволюцією можна вирощувати й цілі програми.

Ця частина продовжує статтю Генетичні алгоритми. Там особина була рядком бітів; тут це буде вектор дійсних чисел і дерево програми.

1. Еволюція чисел: (1+1)-ES

Алгоритм — (1+1)-ES

Мінімізуємо f : ℝⁿ → ℝ. Особина — це точка x ∈ ℝⁿ, σ > 0 — розмір кроку. У кожному поколінні:

1. створи нащадка y = x + σ · z, де z ~ N(0, I) — вектор незалежних нормально розподілених чисел;
2. якщо f(y) ≤ f(x), заміни x ← y.

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

y

нащадок — новий кандидат, якого ми оцінимо

x

батько — найкраща досі знайдена точка; нащадок виникає в її околі, бо поблизу доброї точки зазвичай лежать інші добрі точки

σ

розмір кроку — одне-єдине число, яке визначає, як далеко від батька шукати; шум z має дисперсію 1, і лише σ надає йому масштаб задачі

z ~ N(0, I)

напрям і довжина спроби — середнє 0 означає, що жоден напрям не має переваги наперед; одинична матриця I — що всі координати змінюються незалежно й однаково сильно

Означення — нормальний розподіл N(0, 1) і N(0, I)

Випадкова величина Z має стандартний нормальний розподіл N(0, 1), якщо її густина φ(z) = e^−z²/2 / √(2π); її математичне сподівання 0, а дисперсія 1. Приблизно 68 % значень лежать в інтервалі [−1, 1], а 95 % — у [−1,96; 1,96].

Вектор z ~ N(0, I) у ℝⁿ має n незалежних компонент із розподілом N(0, 1). Його довжина зазвичай близька до √n (для n = 10 близько 3,2), бо E‖z‖² = n.

Наша програма отримує нормальні числа методом Бокса–Мюллера з двох рівномірних чисел u₁, u₂ ∈ (0, 1): z = √(−2 ln u₁) · cos(2πu₂).

Спробуймо на найпростішій можливій функції — сфері f(x) = x₁² + … + x₁₀² у десяти вимірах. Мінімум, очевидно, в нулі; почнемо в точці (3, …, 3), де f = 90. Як вибрати σ? Велике значення вміє швидко спуститися з гори, але поблизу мінімуму постійно перелітає. Мале точне, але до дна йде цілу вічність.

2. Правило однієї п’ятої

Означення — правило однієї п’ятої (Рехенберг, 1973)

Якщо частка вдалих мутацій (нащадок кращий за батька) більша за 1/5, збільш σ; якщо менша — зменш. Одна з можливих форм: після успіху σ ← σ · e^1/3, після невдачі σ ← σ · e^−1/12. Розмір кроку в середньому не змінюється саме тоді, коли вдається п’ята частина мутацій: (1/5) · (1/3) = (4/5) · (1/12).

Обидві гілки правила можна записати однією формулою; s = 1 після успіху і 0 після невдачі:

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

σ

розмір кроку — змінюється множенням, а не додаванням: лишається додатним, і крок може зменшитися на багато порядків (від 1 до тисячних), як того вимагає близькість мінімуму

5/12

швидкість пристосування — після успіху exp(5/12 · 4/5) = e^1/3 ≈ 1,40, після невдачі exp(−5/12 · 1/5) = e^−1/12 ≈ 0,92; більше число реагувало б швидше, але σ коливалася б сильніше

s

результат останньої спроби (1 = нащадок не був гіршим) — єдина інформація, яка потрібна правилу

1/5

цільова частка успіхів — коли вдається рівно п’ята частина спроб, середнє s − 1/5 дорівнює нулю і σ у середньому не змінюється

Правило однієї п’ятої опускається нижче 10⁻⁶ за 587 обчислень — і лінія на графіку спадає рівномірно, бо крок зменшується так само швидко, як наближається мінімум. Зі сталим σ = 1 алгоритм скоро натрапляє на «підлогу» близько одиниці, нижче якої з такими великими стрибками не дістатися. З σ = 0,01 він іде вниз, але повільно: навіть після 5 000 обчислень він не нижче 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)     # успіх: додай
        else:
            sigma *= math.exp(-1 / 12)   # невдача: зменш
    return x, fx

Приклад — перші дванадцять кроків запуску з графіка

Старт x = (3, …, 3), f(x) = 90, σ = 1. Стовпець σ — це розмір кроку після оновлення:

крок	f(y)	успіх?	f(x)	σ
1	115,31	ні	90,00	0,920
2	95,78	ні	90,00	0,846
3	123,94	ні	90,00	0,779
4	107,86	ні	90,00	0,717
5	101,54	ні	90,00	0,659
6	113,11	ні	90,00	0,607
7	94,03	ні	90,00	0,558
8	95,09	ні	90,00	0,513
9	86,27	так	86,27	0,717
10	114,52	ні	86,27	0,659
11	97,72	ні	86,27	0,607
12	102,44	ні	86,27	0,558

після 8 невдач: σ = e^−8/12 ≈ 0,513

9-й крок вдається (86,27 < 90): σ = 0,513 · e^1/3 ≈ 0,513 · 1,396 ≈ 0,717

При σ = 1 крок у десяти вимірах має довжину близько √10 ≈ 3,2, і перші вісім нащадків гірші за старт, тож правило стягує крок. Потім успіхи приходять частіше, і σ усталюється там, де вдається приблизно кожна п’ята спроба — за весь запуск вдалися 99 з 587 спроб, тобто 17 %. У міру того як точка наближається до мінімуму, разом із нею зменшується й крок: наприкінці запуску, після 580 обчислень, σ ≈ 0,00055.

3. Популяція і самоадаптація

Сфера має єдиний мінімум. Справжні задачі часто мають їх безліч — і там однієї особини замало. Типова тестова функція — функція Растригіна: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). Це сфера, у якій хтось вибив правильну сітку ямок; глобальний мінімум 0 лежить у початку координат, а навколо нього — сотні локальних.

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

10n

зсув угору — косинус у початку координат віднімає щонайбільше 10 на кожну координату, стала це повертає, щоб глобальний мінімум мав значення рівно 0

x_i²

сфера — загальний нахил до початку координат; без неї всі ямки були б однаково глибокі і жоден мінімум не був би глобальним

10 cos 2πx_i

хвилі з періодом 1 і амплітудою 10 — вони видовбують ямку біля кожного цілого числа; амплітуда значно більша за нахил сфери між сусідніми ямками, тож локальний пошук застрягне в найближчій ямці

Приклад — старт і сусідні ямки (n = 2)

старт (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

дно ямок поруч із початком координат, біля (±1; 0) і (0; ±1): f ≈ 0,99 (у точці 0,995, не рівно 1 — сфера тягне її до початку координат)

дно діагональних ямок біля (±1; ±1): f ≈ 1,99

Значення 1,49 у поколінні 8 (див. нижче) отже означає популяцію в сусідній ямці, ще не на її дні.

Означення — (μ, λ)-ES і (μ + λ)-ES із самоадаптацією

Популяція має μ батьків; кожне покоління створює λ > μ нащадків. У (μ, λ) виживає μ найкращих нащадків, а батьки гинуть; у (μ + λ) вибирають із батьків і нащадків разом.

Самоадаптація: кожна особина несе власний розмір кроку σ. Нащадок спершу його мутує, σ′ = σ · e^{τ · N(0, 1)} з τ ≈ 1/√(2n), і лише з ним зсуває положення: y = x + σ′ · N(0, I).

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

σ′

крок нащадка — ним одразу зсувається положення, тож пристосованість нащадка видасть, чи був крок добрим

σ

крок батька — успадковується; нащадок починає з того, що спрацювало в батька

τ

швидкість навчання кроку — наскільки крок може змінитися між поколіннями; зі зростанням кількості вимірів n вона зменшується, бо одне значення пристосованості тоді несе менше інформації про те, чи був крок добрим

N(0, 1)

випадкова зміна — симетрична відносно нуля, тож збільшення і зменшення однаково ймовірні; про напрям вирішить лише відбір

Приклад — мутація кроку для 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 σ

Типовий нащадок, отже, пробує крок приблизно від на 40 % меншого до на 65 % більшого, ніж у батька. У нашому запуску крок найкращої особини за 15 поколінь упав з 2 до 0,011 — майже вдвісті разів.

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)                    # випадковий батько
            s = s * math.exp(tau * random.gauss(0, 1))      # спершу мутуй крок
            y = [xi + s * random.gauss(0, 1) for xi in x]   # потім ним положення
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): виживають лише найкращі нащадки
    return rodice[0]

Популяція стартує навколо точки (4,2; −3,8), де f ≈ 45,9. Спочатку вона розкидана по кількох ямках одразу і стягується до глибших. У поколінні 8 найкраща особина ще в сусідній ямці (f ≈ 1,49), але розмір кроку вже впав з 2 до 0,27. У поколінні 15 популяція в глобальному мінімумі, а крок зменшився до сотої, щоб вона могла його доточити.

Зі ста запусків із різними зернами (15, 100)-ES знайшла глобальний мінімум у 32 випадках. Для порівняння (1+1)-ES із правилом однієї п’ятої і тим самим бюджетом 8 000 обчислень: в одному-єдиному. На сферах одна особина найшвидша, на пересіченій місцевості перемагає популяція — і навіть вона часто опиняється в одній із сусідніх ямок.

4. CMA-ES

Самоадаптація налаштовує лише довжину кроку. А що, як мінімум лежить у вузькій похилій долині, де вигідно робити довгі кроки в одному напрямку і короткі в іншому? CMA-ES (Гансен і Остермаєр, 2001) вчиться з вдалих кроків цілої коваріаційної матриці мутації — форми хмари, з якої вона витягає нащадків. Під час пошуку хмара повертається і витягується вздовж долини. Для оптимізації неперервних функцій, градієнта яких ми не знаємо, CMA-ES сьогодні — один із найнадійніших методів.

Означення — мутація з коваріаційною матрицею

Для симетричної додатно визначеної матриці C ∈ ℝ^n×n z ~ N(0, C) — це вектор із математичним сподіванням 0 і коваріаціями E[z_iz_j] = C_ij. Його отримують зі звичайного шуму: z = Au, де u ~ N(0, I) і AA^T = C. Нащадок — це y = m + σ · z, де m — центр популяції.

Точки з однаковою густиною лежать на еліпсоїді; його осі — власні вектори C, а довжини осей пропорційні квадратним кореням власних значень. Для C = I це сфера, і ми отримуємо звичайну еволюційну стратегію.

Спрощено (справжня CMA-ES додає до цього ще так звані еволюційні шляхи і власне керування σ, див. N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) матриця після кожного покоління зсувається до вдалих кроків:

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

C

коваріаційна матриця мутації — форма хмари, з якої витягають нащадків

1 − c

пам’ять — стара матриця лише трохи наближається до нової інформації, бо одне покоління — мала і випадкова вибірка

c

швидкість навчання матриці, число між 0 і 1 — скільки ваги отримують кроки останнього покоління

∑ w_i

зважене середнє за μ найкращими нащадками; ваги додатні, у сумі дають 1, і кращий нащадок має більшу — ми вчимося лише з кроків, які окупилися

z_iz_i^T

вдалий крок z_i = (y_i − m)/σ як матриця — витягує хмару саме в його напрямку

Приклад — один вдалий крок по діагоналі

C = I (кругла хмара), єдиний вдалий крок 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]]

власні значення: 1 + 0,2 = 1,2 у напрямку (1, 1) і 1 − 0,2 = 0,8 у напрямку (1, −1)

Хмара витягнулася вздовж вдалого напрямку і звузилася впоперек — після кількох таких поколінь вона лежить уздовж долини.

5. Генетичне програмування

Означення — програма як дерево

Задано множину функцій F (з арностями) і множину терміналів T (змінні та сталі). Програма — це кореневе дерево, внутрішні вузли якого — функції з F із такою кількістю дітей, яка їхня арність, а листки — термінали з T. Значення програми обчислюють від листків до кореня.

Замкненість: кожна функція мусить приймати вихід будь-якої іншої. Тому використовують захищене ділення (ділення на нуль повертає 1) і корінь з абсолютного значення.

Джон Коза зі Стенфордського університету описав метод 1992 року в книжці Genetic Programming і показав його на десятках задач, від керування роботом до пошуку формул.

Приклад — обчислення дерева (a ÷ 5) × √a для Землі

Від листків до кореня, a = 149,6 (мільйона км):

ліва гілка: a ÷ 5 = 149,6 / 5 = 29,92

права гілка: √a = √149,6 ≈ 12,231

корінь: 29,92 × 12,231 ≈ 365,95 доби   (насправді 365,26, відхилення +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # елітизм: одна найкраща
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # схрещування обміном піддерев
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # мутація: гілка → нова випадкова
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # надто глибоких дітей відкидаємо
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # найменша похибка; за рівності менше дерево

6. Символьна регресія: закон Кеплера

Йоганн Кеплер десять років шукав зв’язок між відстанню планети від Сонця та її періодом обертання; третій закон він опублікував 1619 року. Дамо генетичному програмуванню ту саму задачу. У нього є вісім планет — велика піввісь a у мільйонах кілометрів і період обертання T у добах —, операції +, −, ×, ÷ і √, змінна a і цифри від 1 до 9. Похибка програми — це середнє відносне відхилення від справжніх періодів обертання. Популяція має 300 програм і 40 поколінь.

Означення — символьна регресія

Для даних (x_i, y_i) символьна регресія шукає вираз g із заданої граматики (функцій і терміналів), який мінімізує похибку ∑ ℓ(g(x_i), y_i). На відміну від звичайної регресії, форма моделі не задана наперед, лише будівельні цеглинки.

Точніше, похибка програми g — це середнє абсолютних різниць логарифмів:

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

(1/8) ∑

середнє за вісьмома планетами — похибка не залежить від того, скільки в нас даних, і її можна читати як «типове відхилення на планету»

| … |

абсолютне значення — передбачення на 1 % більше і на 1 % менше однаково погані, і похибки різних знаків не взаємознищуються

ln g(a_i) − ln T_i

різниця логарифмів — це ln(g/T), тобто відносне відхилення: для малих відхилень ln(1 + r) ≈ r. Періоди обертання відрізняються майже втисячу разів (88 діб Меркурій, 60 190 Нептун); зі звичайною різницею про похибку вирішував би лише Нептун

Найкраща програма початкової, випадкової популяції відхиляється від справжніх періодів обертання в середньому на 32 %. У третьому поколінні вона вже має відхилення 8 % і правильну форму a^1,5, лише зі сталою 0,22. У п’ятнадцятому поколінні з’являється ось що:

T = a · √a / 5 — тобто T пропорційне a^3/2, або T² пропорційне a³. Це третій закон Кеплера. Середнє відхилення становить 0,30 %, а стала 1/5 дуже близька до справжнього значення 0,1996 для цих одиниць. З двадцяти запусків із різними зернами показник 1,5 знайшли вісімнадцять.

Звідки 0,1996? З Ньютонового закону всесвітнього тяжіння для колової орбіти (і для еліпса з великою піввіссю a, коли маса планети порівняно з Сонцем нехтовно мала) випливає форма закону разом зі сталою:

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

T

період обертання — час одного оберту

2π

один оберт — це кут 2π; формула виникає з кутової швидкості ω як T = 2π/ω

√(GM_☉)

сила тяжіння Сонця (G — гравітаційна стала, M_☉ — маса Сонця) — сильніше притягання означає швидший оберт, тому вона в знаменнику

a^3/2

відстань — тяжіння слабне з a², а шлях довший пропорційно a; з рівності доцентрової і гравітаційної сил ω²a = GM_☉/a² виходить ω ∝ a^−3/2

Приклад — стала в мільйонах км і добах

Гравітаційний параметр Сонця GM_☉ = 1,327 124 · 10²⁰ м³/с² (номінальне значення Міжнародного астрономічного союзу, резолюція B3 2015 року). Одиниця довжини — 10⁹ м, тож a^3/2 у метрах у (10⁹)^3/2 = √(10²⁷) разів більше:

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

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

17 247 с / 86 400 с/добу ≈ 0,1996 доби

Програма зі сталою 1/5 = 0,2 відрізняється, отже, на 0,19 % — рівно стільки, скільки вийшло відхилення для Землі вище.

7. Розбухання

Проте еволюція на гарній формулі не зупинилася. До покоління 40 вона «покращила» відхилення до 0,23 % ось цим:

Дерево має замість шести вузлів шістнадцять, і додані гілки не роблять нічого іншого, як підганяють сталу й обходять заокруглення в даних. Фізично це гірша формула — перенавчена на вісім планет. Середній розмір програми в популяції при цьому зріс із 9,8 вузла на початку до 23,8 у двадцятому поколінні.

Означення — розбухання і тиск економності

Розбухання (bloat) — це зростання розміру програм у популяції, якому не відповідає покращення їхньої пристосованості. Тиск економності (parsimony pressure) штрафує за розмір: або додає його до похибки, F′(g) = F(g) + c · |g|, або використовує як другий критерій за рівних похибок.

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

F′(g)

скоригована похибка, за якою відбирають — менша краща

F(g)

похибка програми на даних — і далі головне, що ми хочемо знизити

c

ціна одного вузла — каже, наскільки має покращитися похибка, щоб додатковий вузол окупився; її вибирають так, щоб вона вирішувала лише за мізерних покращень

|g|

розмір програми, кількість вузлів дерева — міра складності, яку можна порахувати, не розуміючи програми

Приклад — яке c врятувало б закон Кеплера

Дерево з покоління 15: похибка 0,2986 %, 6 вузлів. Дерево з покоління 40: похибка 0,2312 %, 16 вузлів. Менше дерево перемагає, коли

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

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

Десять додаткових вузлів покращили похибку менш ніж на соту відсотка. З ціною понад 0,007 % за вузол дерево з покоління 40 програло б у відборі читабельному закону з покоління 15.

8. Еволюційні стратегії і програми сьогодні

• Еволюційні стратегії замість навчання з підкріпленням. OpenAI 2017 року показала, що проста еволюційна стратегія здатна навчати нейронні мережі керувати симульованими роботами і грати в ігри Atari приблизно так само добре, як навчання з підкріпленням, — і її можна розподілити на тисячі процесорів, які пересилають одне одному лише кілька чисел.
• Відкриття законів із даних. Шмідт і Ліпсон 2009 року доручили символьній регресії вивести закони руху і закони збереження з вимірювань маятників. Сучасні бібліотеки, як-от PySR, використовують у фізиці й астрономії, де читабельна формула цінніша за чорну скриньку.
• Еволюція алгоритмів машинного навчання. Проєкт AutoML-Zero (Google, 2020) дав еволюції складати алгоритми навчання з елементарних математичних операцій і так заново відкрив, наприклад, зворотне поширення помилки.
• Програми з мовними моделями. Системи FunSearch і AlphaEvolve з попередньої частини — це генетичне програмування, у якому мутацію замість випадкової гілки виконує мовна модель.

9. Підсумок

• Еволюційні стратегії мутують дійсні числа нормальним шумом із розміром кроку σ.
• Правило однієї п’ятої і самоадаптація налаштовують σ автоматично; CMA-ES вчиться ще й форми мутацій.
• На сферах досить однієї особини, на пересіченій місцевості допомагає популяція: на функції Растригіна 32 успіхи зі 100 проти одного.
• Генетичне програмування вирощує програми як дерева; символьна регресія знайшла в даних про планети третій закон Кеплера.
• Програми схильні розбухати й перенавчатися — проти цього допомагає тиск економності.

Хочете спробувати самі? Попросіть ШІ-агента написати символьну регресію і дайте їй власні дані — скажімо, період коливань маятника залежно від довжини нитки, — і подивіться, чи знайде вона √L.

Маєте іншу думку? Напишіть на support@coden-app.com.