NEAT: нейроеволюція доповнюваних топологій

1. Проблема топології в нейроеволюції

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

Попередні підходи розв'язували це або еволюцією лише ваг (втрачаючи здатність нарощувати мережі), або непрямими кодуваннями й правилами розвитку, які важко аналізувати. Ключовий внесок NEAT полягав у тому, щоб дати принципове розв'язання всіх трьох викликів еволюції мереж зі змінною топологією:

1. Конкуруючі угоди: розв'язано історичними маркерами (номерами інновацій), які відстежують структурну гомологію між геномами.
2. Передчасна збіжність пошуку: розв'язано видоутворенням — захистом інновацій в окремих нішах, доки в них не буде часу на оптимізацію.
3. Керування складністю: розв'язано стартом із мінімальних мереж і нарощуванням складності лише тоді, коли це вигідно.

2. Представлення геному

Геном NEAT складається з двох списків генів:

• Гени вузлів: кожен задає унікальний ID вузла та тип (вхідний, прихований, вихідний, зсуву). Позиційної інформації немає — топологія виникає зі зв'язків, а не з шарування.
• Гени зв'язків: кожен задає вхідний вузол, вихідний вузол, вагу, біт увімкнення/вимкнення та номер інновації (глобальний історичний ID для цього конкретного структурного додавання).

Це пряме кодування: кожен ген у геномі відповідає безпосередньо одному елементу (вузлу чи зв'язку) у фенотипі мережі. Біт увімкнення/вимкнення дозволяє тимчасово заглушити зв'язок, не видаляючи його з геному — зберігаючи еволюційну історію й дозволяючи повторне ввімкнення в майбутніх поколіннях.

3. Історичні маркери та номери інновацій

Центральна ідея NEAT — відстежувати історичне походження кожного структурного гена. Щоразу, коли новий зв'язок або вузол додається до будь-якого геному в популяції протягом покоління, йому призначається глобально унікальний номер інновації — монотонно зростаючий цілочисловий лічильник.

Якщо та сама структурна мутація (та сама пара вхідного й вихідного вузла для додавання зв'язку або розщеплення того самого зв'язку для додавання вузла) трапляється у двох різних особин протягом одного покоління, вона отримує той самий номер інновації. Це створює історичне вирівнювання між геномами: гени з однаковими номерами інновацій є гомологічними — вони з'явилися в той самий еволюційний момент і представляють ту саму структурну ознаку.

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

4. Кросовер між топологіями

Кросовер NEAT працює ген за геном, використовуючи вирівнювання за номерами інновацій:

1. Збіжні гени (той самий номер інновації в обох батьків): нащадок випадково успадковує вагу від одного з батьків (підкидання монети 50/50). Якщо будь-яка копія вимкнена в одного з батьків, ген нащадка має 75% шанс також бути вимкненим.
2. Роз'єднані гени (з'являються в одного батька в межах діапазону іншого): успадковуються від більш пристосованого батька. Якщо обидва батьки мають однакову пристосованість, успадковуються випадково.
3. Надлишкові гени (за межею коротшого геному): успадковуються лише від більш пристосованого батька.

Набір вузлів нащадка визначається тим, які гени зв'язків успадковані: будь-який вузол, на який посилається успадкований зв'язок, автоматично включається. Це гарантує, що фенотип нащадка — коректна мережа попри змінну структуру його батьків.

5. Структурні мутації

NEAT використовує три типи мутацій для дослідження простору топологій:

Мутація ваги (неперервна)

Ваги зв'язків мутують додаванням гауссового шуму: w' = w + N(0, σ²), або інколи замінюються цілком новою випадковою вагою. Це найчастіший тип мутації та основний режим оптимізації в межах фіксованої топології.

Мутація додавання зв'язку (структурна)

Новий ген зв'язку додається між двома раніше непов'язаними вузлами (з дотриманням топологічного впорядкування, щоб уникнути циклів лише вперед, якщо рекурентні зв'язки не ввімкнено). Новий зв'язок має випадкову початкову вагу й отримує наступний доступний номер інновації. Якщо той самий зв'язок було додано деінде в тому самому поколінні, вони мають спільний номер інновації.

Мутація додавання вузла (структурна)

Наявний увімкнений зв'язок розщеплюється шляхом його вимкнення та вставлення нового прихованого вузла H між його кінцями. Додаються два нові зв'язки: IN → H з вагою 1.0 (зберігаючи наявну поведінку мережі) та H → OUT з вихідною вагою. Це гарантує, що нова структура спершу обчислює ту саму функцію, що й раніше, захищаючи пристосованість особини, водночас дозволяючи згодом уточнити ваги нового вузла.

Початкові ваги (IN→H = 1.0, H→OUT = вихідна вага) обираються так, щоб новий вузол не порушував одразу поточну поведінку мережі — форма мінімально руйнівної структурної інновації.

6. Видоутворення та відстань сумісності

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

Два геноми належать до одного виду, якщо їхня відстань сумісності δ нижча за поріг δ_t:

Кожен геном призначається до першого виду, чий представницький геном (випадково обраний на початку кожного покоління) має δ < δ_t щодо нього. Якщо жоден наявний вид не підходить, створюється новий вид. Представники видів замінюються щопокоління, запобігаючи тому, щоб види ставали «статичними».

Розподіл пристосованості та розподіл розмноження

У межах кожного виду сира пристосованість кожного геному ділиться на розмір виду — форма розподілу пристосованості (fitness sharing), що карає великі види й захищає малі:

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

7. Мінімальність та ускладнення

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

Цей принцип мінімальності має дві переваги:

• Ефективний пошук: алгоритм спершу використовує найпростіші можливі розв'язки (які часто достатньо хороші для простих задач), перш ніж досліджувати складніші топології.
• Економність: розв'язки, які можна знайти з меншою кількістю нейронів і зв'язків, є кращими, що веде до компактних, інтерпретовних мереж. NEAT не додає складності без обґрунтування пристосованістю.

Це називається ускладненням (complexification): популяція в цілому схильна зростати в структурній складності з поколіннями, але лише в напрямках, що покращують пристосованість. Різні види можуть досліджувати дуже різні топологічні стратегії одночасно.

8. Демонстрація NEAT XOR на JavaScript

Симуляція нижче запускає спрощений NEAT на задачі XOR — класичному еталоні, бо вона не є лінійно роздільною й вимагає щонайменше одного прихованого вузла. Популяція еволюціонує з поколіннями, а мережа найкращого геному відмальовується праворуч. Вузли розташовані за шарами (входи ліворуч, вихід праворуч, приховані вузли між ними), а ваги зв'язків показані як товщина ліній. Спостерігайте, як приховані вузли поступово додаються для розв'язання XOR.

Повний NEAT із сотнями особин обчислювально важкий для браузера; це демо використовує полегшену реалізацію зі спрощеним видоутворенням і структурною мутацією, щоб проілюструвати концепції. Ліва панель показує пристосованість за поколіннями; права панель показує граф мережі найкращого геному з вагами зв'язків як прозорість ліній.

// Спрощена структура геному NEAT
class Genome {
  constructor() {
    this.nodes = new Map();   // id → { type: 'in'|'hid'|'out'|'bias' }
    this.conns = new Map();   // innov → { in, out, weight, enabled }
    this.fitness = 0;
    this.species  = -1;
  }

  activate(inputs) {
    // Топологічне сортування, потім прямий прохід
    const values = new Map();
    for (const [id, n] of this.nodes) {
      if (n.type === 'in')   values.set(id, inputs[n.idx]);
      if (n.type === 'bias') values.set(id, 1.0);
      if (n.type === 'hid' || n.type === 'out') values.set(id, 0);
    }
    for (const [, g] of this.conns) {
      if (!g.enabled) continue;
      const v = (values.get(g.out) ?? 0) + values.get(g.in) * g.weight;
      values.set(g.out, v);
    }
    return sigmoid(values.get(outputNodeId));
  }
}

function compatibility(g1, g2) {
  let E = 0, D = 0, W = 0, M = 0;
  for (const [innov, c1] of g1.conns) {
    if (g2.conns.has(innov)) { W += Math.abs(c1.weight - g2.conns.get(innov).weight); M++; }
    else D++;
  }
  for (const [innov] of g2.conns) if (!g1.conns.has(innov)) E++;
  const N = Math.max(g1.conns.size, g2.conns.size, 1);
  return C1 * E / N + C2 * D / N + C3 * (M > 0 ? W / M : 0);
}