Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT

Нейрон і мережа коротко, еволюція регулятора для маятника на візку, чому еволюція замість градієнта, XOR і приховані нейрони, NEAT з історичними позначками й видоутворенням, що стається без видоутворення, і наступники від HyperNEAT до AmoebaNet.

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

Серія Основи ШІ Частина 31 з 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. Нейронна мережа коротко

Означення — штучний нейрон і мережа

Нейрон із входами x₁, …, x_n, вагами w₁, …, w_n і порогом (зсувом) b обчислює

y = σ(w₁x₁ + … + w_nx_n + b),

де σ — функція активації, наприклад сигмоїда σ(z) = 1 / (1 + e^−z) або проста сходинка «додатне → 1, інакше 0».

Нейронна мережа — це орієнтований граф нейронів: входи мережі ведуть до нейронів, виходи нейронів — до інших нейронів. У мережі прямого поширення граф не має циклів. Нейрони, які не є ні входом, ні виходом, називаються прихованими.

y = σ( ∑_i=1ⁿ w_i x_i + b )

x_i

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

w_i

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

b

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

σ

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

2. Еволюція ваг: маятник на візку

Класична задача керування: на візку на шарнірі стоїть жердина, і візок мусить утримувати її вертикально, роз’їжджаючи вліво й управо, — як коли балансуєте мітлою на долоні.

Означення — задача маятника на візку

Стан — це четвірка (x, v, θ, ω): положення x і швидкість v візка, кут θ жердини від вертикалі та її кутова швидкість ω. Кожні 0,02 с регулятор вибирає силу +10 Н або −10 Н, і стан змінюється за рівняннями руху (візок 1 кг, жердина 0,1 кг завдовжки 1 м). Спроба закінчується, коли |θ| > 12° або |x| > 2,4 м. Мета — протриматися 1 000 кроків (20 с).

Регулятором буде один нейрон зі сходинковою активацією: сила дорівнює +10 Н, коли w₁x + w₂v + w₃θ + w₄ω + b > 0, інакше −10 Н. Пристосованість — середня кількість кроків із трьох різних стартів.

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

Кут θ вимірюємо від вертикалі, додатна сила штовхає візок у напрямку додатного x. Позначмо M = m_v + m_t = 1 + 0,1 = 1,1 кг загальну масу візка й жердини, l = 0,5 м половину довжини жердини (відстань центра мас від шарніра) і g = 9,8 м/с². Без тертя (рівняння у формі, як їх наводять Барто, Саттон і Андерсон, 1983, і як їх досі використовує більшість реалізацій) кутове прискорення жердини ε і прискорення візка a такі:

a_F = (F + m_t l ω² sin θ) / M

ε = (g sin θ − cos θ · a_F) / (l (4/3 − m_t cos² θ / M))

a = a_F − m_t l ε cos θ / M

Симуляція йде методом Ейлера з кроком Δt = 0,02 с: нове положення — це старе плюс Δt, помножене на стару швидкість, нова швидкість — стара плюс Δt, помножене на прискорення: x ← x + Δt v, v ← v + Δt a, θ ← θ + Δt ω, ω ← ω + Δt ε.

ε = ( g sin θ − cos θ · a_F ) / l (4/3 − m_t cos² θ / M)

g sin θ

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

a_F

прискорення візка від сили регулятора (плюс мала відцентрова сила жердини) — єдиний шлях, яким регулятор діє на жердину: візок під’їжджає під жердину, і шарнір її «підштовхує» назад

cos θ

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

l (4/3 − …)

інерція жердини — 4/3 походить із моменту інерції однорідного стрижня відносно кінця, ⅓ m(2l)² = ⁴⁄₃ ml²; віднятий член виправляє те, що під час обертання жердини смикається й візок під нею

Приклад — один крок симуляції

Старт (0, 0, 0,05, 0), тобто жердина нахилена на 0,05 рад ≈ 2,9°. Знаменник: 0,5 · (4/3 − 0,1 · 0,9988² / 1,1) ≈ 0,621.

без сили (F = 0): ε = 9,8 · 0,0500 / 0,621 ≈ +0,79 рад/с² — жердина починає падати

сила +10 Н: a_F = 10 / 1,1 ≈ 9,09 м/с²,   ε = (0,490 − 0,999 · 9,09) / 0,621 ≈ −13,8 рад/с²

після кроку: ω = 0 + 0,02 · (−13,8) ≈ −0,28 рад/с,   v ≈ 0 + 0,02 · 9,72 ≈ 0,19 м/с

Сила ±10 Н порівняно з тяжінням величезна — один-єдиний поштовх змінює напрямок падіння. Отже, задача не в силі, а в часі: коли перестати штовхати, щоб жердина не перехилилася на інший бік.

Скільки дає випадок? Із тисячі регуляторів із випадковими вагами всі 20 секунд протримався лише один; медіана — 9 кроків: жердина падає менш ніж за п’яту частину секунди. Прямолінійний регулятор, який просто їде туди, куди нахиляється жердина, протримується 39 кроків: жердину він ловить, але розгойдує. Еволюційна стратегія (5, 20) із частини про еволюційні стратегії знайшла регулятор, який тримається всі 20 секунд з усіх трьох стартів, у 15-му поколінні — приблизно після трьохсот випробуваних регуляторів:

Виведений регулятор надає найбільшої ваги кутовій швидкості — він ловить жердину не тоді, коли вона вже падає, а коли тільки починає розганятися до падіння. Чималі ваги мають і кут та швидкість візка, тож візок не розгойдується й не з’їжджає з колії. Такого «правила» ніхто не писав; воно випало з еволюції.

Означення — пристосованість регулятора та еволюція ваг

Для ваг w = (w₁, …, w₄, b) величина T_k(w) ∈ {1, …, 1 000} — це кількість кроків, доки зі старту k жердина не впаде або візок не з’їде (щонайбільше 1 000). Пристосованість дорівнює

Z(w) = ⅓ (T₁(w) + T₂(w) + T₃(w)),

зі стартами (0, 0, 0,05, 0), (0, 0, −0,08, 0) і (0,5, 0, 0,02, 0,1). Три старти замість одного не дають еволюції знайти регулятор, який уміє лише одне початкове положення. Z кусково-стала — мала зміна ваг здебільшого взагалі не змінює кількість кроків, тож градієнт майже всюди нульовий. Тому еволюція.

Еволюційна стратегія (5, 20): п’ять батьків із вагами, випадково взятими з [−1, 1]; у кожному поколінні двадцять нащадків, кожен виникає з випадкового батька додаванням 0,5 · N(0, 1) до кожної ваги; наступними батьками стають п’ять найкращих нащадків.

import random

def regulator(w, s):                 # s = (x, v, θ, ω)
    u = w[0]*s[0] + w[1]*s[1] + w[2]*s[2] + w[3]*s[3] + w[4]
    return 10 if u > 0 else -10       # сходинкова активація: сила ±10 Н

def zdatnost(w):                     # simuluj(): кроки до падіння, щонайбільше 1000
    return sum(simuluj(regulator, w, start) for start in STARTY) / 3

rodice = [[random.uniform(-1, 1) for _ in range(5)] for _ in range(5)]
for generace in range(30):
    deti = [[wi + 0.5 * random.gauss(0, 1) for wi in random.choice(rodice)]
            for _ in range(20)]
    deti.sort(key=zdatnost, reverse=True)
    rodice = deti[:5]                # (5, 20): виживають лише нащадки

Приклад — як вирішує виведений регулятор

Ваги, знайдені еволюцією (заокруглено): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 для (x, v, θ, ω).

жердина нахилена й нерухома: (0, 0, 0,05, 0) → u = 1,37 · 0,05 + 0,09 ≈ +0,16 → +10 Н, візок під’їжджає під жердину

жердина нахилена, але вже повертається: (0, 0, 0,05, −0,1) → u = 0,07 − 0,42 + 0,09 ≈ −0,26 → −10 Н, візок гальмує

У другому випадку жердина нахилена так само, але регулятор штовхає в протилежний бік: кутова швидкість −0,1 рад/с із вагою 4,23 важить більше, ніж кут 0,05 рад із вагою 1,37. Жердина повертається сама, і якби візок далі штовхав, вона перехилилася б. Прямолінійний регулятор «лише за кутом» в обох станах штовхав би однаково — тому він жердину розгойдує.

3. Чому еволюція, а не градієнт

• Рідкісна винагорода. У маятника, гри чи робота якість видно лише після цілого епізоду. Еволюції достатньо одного числа наприкінці.
• Недиференційовні частини. Сходинкова активація, фізичний симулятор, правила гри — еволюції не потрібно їх диференціювати.
• Паралельність. Кожну особину можна незалежно оцінити на іншому комп’ютері.
• Структура. Градієнт уміє налаштовувати ваги, але не додати нейрон. Еволюція може змінювати й те, як мережа виглядає.

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

4. Коли ваг недостатньо: XOR

Функція XOR повертає 1, коли рівно один із двох входів дорівнює 1. Як показала частина Логіка й доведення, один нейрон її не вміє: його вихід ділить площину входів прямою, а точки (0, 1), (1, 0) від (0, 0), (1, 1) жодна пряма не відділить. Для XOR потрібен принаймні один прихований нейрон. І тут постає питання, яке сама еволюція ваг не розв’яже: скільки нейронів і як їх з’єднати?

Теорема — XOR не є лінійно роздільною

Не існує чисел w₁, w₂, b таких, щоб w₁x₁ + w₂x₂ + b > 0 виконувалося рівно для тих точок, де XOR дорівнює 1.

Доведення. Якби такі числа існували, виконувалося б

(0, 0): b ≤ 0    (1, 1): w₁ + w₂ + b ≤ 0

(1, 0): w₁ + b > 0    (0, 1): w₂ + b > 0

Додавши перший рядок, дістанемо w₁ + w₂ + 2b ≤ 0, додавши другий — w₁ + w₂ + 2b > 0. Суперечність. ∎

Доведення не використовує вигляд функції активації — воно справджується для будь-якого одиничного нейрона, вихід якого залежить лише від знака зваженої суми (сходинка і сигмоїда з порогом 0,5).

Відповісти можна вручну — спроєктувати архітектуру, а еволюцією налаштовувати лише ваги. Але у складніших задачах ми не знаємо, яка архітектура правильна. Чому б не дати виростити й її?

5. NEAT: еволюція мереж, що ростуть

Спроби еволюціонувати структуру мереж наштовхувалися на три проблеми. Як схрещувати дві мережі різної форми? Як дати шанс новій структурі, яка спочатку гірша, бо її нові ваги ще не налаштовані? І як не дати мережам безпідставно розростатися? Кеннет Стенлі та Ристо Мііккулайнен 2002 року відповіли алгоритмом NEAT (NeuroEvolution of Augmenting Topologies) із трьома ідеями.

Означення — геном NEAT та історичні позначки

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

Мутації: зміна ваг; додавання зв’язку між двома досі не з’єднаними нейронами; додавання нейрона — наявний зв’язок a → b із вагою w вимикається і замінюється парою a → h із вагою 1 та h → b із вагою w.

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

Приклад — додавання нейрона на зв’язок із вагою 2

Наш NEAT, так само як оригінальна стаття, використовує крутішу сигмоїду σ(z) = 1 / (1 + e^−4,9z). Зв’язок x₁ → y із вагою 2 додавав до виходу 2x₁. Після розділення веде x₁ → h із вагою 1 та h → y із вагою 2:

x₁ = 1:   2 · σ(1) = 2 · 0,993 ≈ 1,985   (раніше 2)

x₁ = 0:   2 · σ(0) = 2 · 0,5 = 1   (раніше 0)

Отже, «приблизно те саме» тут справджується лише частково: для входу 1 зміна мізерна, для входу 0 до суми додається одиниця, бо сигмоїда в нулі повертає половину. Мережа від цього трохи псується — і саме тому нова структура потребує захисту, про який ітиметься далі.

Означення — видоутворення і розподіл пристосованості

Відстань сумісності двох геномів дорівнює

δ = c₁ E / N + c₂ D / N + c₃ W̄,

де E — кількість надлишкових генів (із номерами за кінцем коротшого генома), D — кількість диз’юнктних (тих, що бракує посередині), W̄ — середня різниця ваг спільних генів, а N — розмір більшого генома (для малих геномів 1). Геноми з δ нижче порогу належать до одного виду. Пристосованість особини ділиться на розмір її виду, а нащадки розподіляються між видами відповідно до їхньої середньої пристосованості.

δ = c₁ E / N + c₂ D / N + c₃ W̄

c₁ E

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

c₂ D

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

N

розмір більшого генома — щоб два великі геноми, які відрізняються кількома генами з багатьох, не виявилися так само віддаленими, як два малі, що відрізняються майже всім; для геномів менш ніж із 20 генів береться N = 1

c₃ W̄

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

Приклад — відстань після додавання нейрона

Геном A має гени 1–5. Геном B виник зі схожого предка: він теж має гени 1–5 (ген 3 вимкнений, бо його розділив новий нейрон) і додатково гени 6 і 7 від додавання нейрона. Ваги спільних генів відрізняються на 0,2; 0,6; 0; 0,9 і 0,8.

спільні: 1–5 → W̄ = (0,2 + 0,6 + 0 + 0,9 + 0,8) / 5 = 0,5

надлишкові: 6, 7 (за кінцем коротшого генома, який закінчується геном 5) → E = 2;   диз’юнктні: немає → D = 0

δ = 1 · 2 / 1 + 1 · 0 / 1 + 0,4 · 0,5 = 2,2 < 3 → той самий вид

Якби B набув ще одного зв’язку (ген 8), вийшло б E = 3 і δ = 3,2 ≥ 3 — B заснував би новий вид. Отже, один новий нейрон мережу з виду не виключає, а новий нейрон із новим зв’язком — уже так.

n_k = P · F̄_k / ∑_j F̄_j,   F̄_k = ∑_{i ∈ Sk} f_i / |S_k|

n_k

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

P

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

|S_k|

кількість членів виду — розподіл пристосованості: пристосованість кожного члена ділиться на розмір його виду, f′_i = f_i / |S_k|; тож великий вид не може отримати більше лише тому, що він великий

F̄_k

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

∑_j F̄_j

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

Приклад — чому розподіл захищає новий вид

Популяція 150: усталений вид A має 120 мереж із середньою пристосованістю 9,0, новий вид B із прихованим нейроном — 30 мереж із середньою пристосованістю 7,5.

із розподілом: n_A = 150 · 9,0 / 16,5 ≈ 81,8 → 81 (+1 залишок) = 82,   n_B = 150 · 7,5 / 16,5 ≈ 68,2 → 68

без розподілу (за сумою пристосованостей 1 080 і 225): A ≈ 150 · 1 080 / 1 305 ≈ 124,   B ≈ 26

Без розподілу новий вид за кілька поколінь вимер би, бо він гірший і менший. Із розподілом він отримує більше нащадків, ніж має членів, і має час налаштувати ваги.

Третя ідея найпростіша: почати з мінімуму. Усі мережі на початку не мають жодного прихованого нейрона — входи ведуть прямо до виходу. Структура додається лише тоді, коли це окупається. Тому підсумкові мережі зазвичай малі.

Усе разом — одне покоління нашого спрощеного NEAT (імовірності — ті, з якими працює програма для XOR):

популяція ← 150 мінімальних мереж (x₁, x₂ і поріг прямо до y, ваги випадково з [−2, 2])
для покоління g = 0, 1, …, 100:
    оціни кожну мережу пристосованістю f
    якщо якась мережа розв’язує задачу: кінець
    розподіли мережі на види: мережа належить до першого виду, з представником якого
                              має δ < 3,
                              інакше засновує новий
    вилучи види, які 15 поколінь не покращувалися (крім виду з найкращою мережею)
    виду k признач n_k = 150 · F̄_k / ∑ F̄_j нащадків
    у кожному виді:
        батьки ← найкращі 20 % членів
        якщо вид має понад 5 членів, його найкраща мережа переходить без змін
        кожен наступний нащадок:
            з імовірністю 0,75 схрещування двох батьків, інакше копія одного
            з імовірністю 0,8 зміни ваги (90 %: w ← w + N(0, 1), 10 %: нова випадкова)
            з імовірністю 0,1 додай зв’язок
            з імовірністю 0,03 додай нейрон (розділи випадковий увімкнений зв’язок)

6. NEAT на XOR

Наш спрощений NEAT має популяцію зі 150 мереж і щонайбільше 100 поколінь. У запуску з рисунка він розв’язав XOR у поколінні 27 мережею з одним прихованим нейроном і сімома зв’язками — а це найменший можливий розв’язок:

f = ( 4 − ∑ |y − t| )²

∑ |y − t|

похибка — сума відхилень виходу y від правильного значення t за всіма чотирма входами; абсолютне значення — щоб похибки вгору і вниз не скасовували одна одну

4

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

²

піднесення до квадрата — підсилює різниці поблизу розв’язку: мережа з похибкою 0,5 має пристосованість 12,25, мережа з похибкою 1 — лише 9, тож добір більше винагороджує останні кілька відсотків

Мережу можна прочитати. Прихований нейрон h спалахує лише тоді, коли обидва входи дорівнюють 0 (обидва мають велику від’ємну вагу, поріг додатний). Прямі зв’язки до виходу самі обчислювали б «не обидва одночасно» — вихід 1 для всього, крім (1, 1), — але сильно від’ємна вага від h вимикає його для (0, 0). Виходи 0,000; 0,855; 1,000 і 0,005 після заокруглення — це точно XOR. Кількість видів тим часом зросла з одного приблизно до двадцяти.

Приклад — обчислення мережі для всіх чотирьох входів

Ваги (заокруглено): до h від x₁, x₂ і порогу −3,37; −3,67; 0,95; до y від x₁, x₂, порогу та h −1,42; −2,96; 3,32; −5,69. Активація — σ(z) = 1 / (1 + e^−4,9z). Спершу обчислюється h, потім y (таблиця рахує з незаокругленими вагами, тож ручний перерахунок може відрізнятися в останній цифрі):

(x1, x2)	zh	h	zy	y	|y − t|
(0, 0)	0,95	0,990	3,32 − 5,69 · 0,990 = −2,32	0,000	0,000
(0, 1)	−2,72	0,000	−2,96 + 3,32 = 0,36	0,855	0,145
(1, 0)	−2,43	0,000	−1,42 + 3,32 = 1,89	1,000	0,000
(1, 1)	−6,09	0,000	−1,42 − 2,96 + 3,32 = −1,06	0,005	0,005

Похибка становить 0,150, а пристосованість — (4 − 0,150)² ≈ 14,82 із 16. Найгірше мережа відповідає для (0, 1): вихід 0,855 правильно лежить вище половини, але не біля одиниці — для розв’язку цього досить, подальше налаштування ваг підняло б пристосованість ще вище.

Із п’ятдесяти запусків із різними зернами NEAT розв’язав XOR у 47, у середньому за 31 покоління, з 2,6 прихованого нейрона, які справді щось роблять. Оригінальна стаття наводить 32 покоління і 2,35 прихованого нейрона — тож наш спрощений NEAT близький до неї.

7. На чому тримається NEAT

Ті самі 50 запусків із вимкненою частиною алгоритму:

Без видоутворення NEAT майже не працює. Мережа з прихованим нейроном після появи гірша за усталені мережі без нього, бо її нові ваги випадкові, — і в одному спільному змаганні добір одразу її вилучає. Видоутворення захищає її, доки вона не дозріє. Без схрещування XOR теж розв’язується, лише повільніше і з більшими мережами (3,1 активного прихованого нейрона): схрещування допомагає складати докупи часткові відкриття різних особин.

8. Наступники NEAT

• HyperNEAT (Стенлі та ін., 2009) еволюціонує малу мережу, яка лише генерує ваги великої мережі відповідно до геометрії задачі, — як геном, що описує не кожну клітину, а правила росту.
• Пошук новизни (Леман і Стенлі, 2011) винагороджує не пристосованість, а нову поведінку. У лабіринті з оманливими глухими кутами він знаходив ціль частіше, ніж пошук, керований пристосованістю.
• Глибока нейроеволюція. 2017 року команда Uber AI показала, що простий генетичний алгоритм здатен навчати мережі з мільйонами ваг на іграх Atari порівнянно з навчанням із підкріпленням.
• Еволюційний пошук архітектур. Мережа AmoebaNet (Google, 2019) виникла еволюцією будівельних блоків і в розпізнаванні зображень на ImageNet належала тоді до найкращих. Сьогодні архітектури частіше проєктують люди або інші методи, але еволюція лишається однією з можливостей.

9. Підсумок

• Нейроеволюція вирощує нейронні мережі еволюційними алгоритмами — вона доречна там, де градієнт неможливо обчислити або де винагорода надходить лише наприкінці.
• Еволюція ваг одного нейрона утримує маятник на візку 20 секунд приблизно після трьохсот спроб; випадкові ваги дають у медіані 9 кроків.
• Для XOR одного нейрона недостатньо — потрібно змінити структуру мережі.
• NEAT еволюціонує і ваги, і структуру: історичні позначки уможливлюють схрещування, видоутворення захищає нові структури, а мережі ростуть від мінімуму.
• Без видоутворення NEAT розв’язав XOR в 1 із 50 запусків, із видоутворенням — у 47, і найкращий розв’язок мав один-єдиний прихований нейрон.

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

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