Neuroevolution of Augmenting Topologies: идеи и реализация

Neuroevolution of Augmenting Topologies (NEAT) представляет собой метод эволюции нейронных сетей, который позволяет одновременно развивать структуру сети и веса её связей. В отличие от классического обучения нейросетей методом обратного распространения ошибки, NEAT использует генетические алгоритмы, позволяя сети эволюционировать под задачу, адаптируя количество нейронов и топологию слоев.

Главная идея NEAT заключается в постепенном усложнении структуры сети, начиная с минимальной, что позволяет избегать переобучения и упрощает поиск оптимальных архитектур.

Генетическое представление сети

В NEAT каждая нейронная сеть кодируется как геном, состоящий из двух типов генов:

  1. Гены узлов (Node genes) — описывают нейроны сети и их тип: входные, скрытые, выходные.
  2. Гены связей (Connection genes) — описывают соединения между нейронами, их веса и включённость. Каждый ген связи имеет уникальный инновационный номер (innovation number), позволяющий отслеживать происхождение мутаций и правильно выравнивать гены при скрещивании.

Гены связи содержат информацию о:

  • источнике и цели связи,
  • значении веса,
  • включённости (enabled/disabled),
  • типе активации (в некоторых реализациях).

Преимущество инновационных номеров заключается в упрощении процесса скрещивания сетей с разной топологией — новые гены можно корректно сопоставить с генами родителей.

Мутации и развитие топологии

Мутации в NEAT делятся на две основные категории:

  1. Мутация веса связи:

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

  2. Мутация структуры:

    • Добавление связи (add connection) — создаётся новая связь между двумя случайно выбранными нейронами, если она ещё не существует.
    • Добавление нейрона (add node) — существующая связь делится на две, на месте разделения вставляется новый нейрон. Вес старой связи обычно устанавливается в 1, новой — в исходное значение старой.

Эти мутации обеспечивают пошаговое усложнение сети, что делает эволюцию более стабильной и управляемой.

Скрещивание сетей

Скрещивание (crossover) в NEAT использует инновационные номера для выравнивания генов. Схема работы следующая:

  • Гены, совпадающие по инновационным номерам, объединяются случайным образом.
  • Избыточные и уникальные гены наследуются от более приспособленного родителя.
  • Скрещивание позволяет сохранять полезные структуры, избегая случайного разрушения эффективной топологии.

Специальные механизмы NEAT

1. Специация (Speciation) Для предотвращения конкуренции между слишком различными сетями, популяция делится на виды (species) по схожести геномов. Сетям внутри одного вида начисляются скорректированные оценки приспособленности, что позволяет новым структурам развиваться без давления со стороны хорошо адаптированных старых сетей.

2. Сохранение минимальной топологии (Minimal Structure Initialization) Начало эволюции с минимально возможной сети обеспечивает:

  • меньшее количество случайных соединений,
  • более стабильное улучшение сети,
  • постепенное добавление новых нейронов только при необходимости.

3. Поддержка инноваций (Innovation Tracking) Каждая мутация фиксируется с уникальным номером. Это позволяет корректно выравнивать структуры при скрещивании, обеспечивая сохранение полезных модулей сети.

Реализация NEAT на JavaScript с Synaptic

Synaptic — это библиотека для построения и обучения нейронных сетей в JavaScript. Она предоставляет:

  • классы Neuron, Layer, Network,
  • методы для прямого распространения сигнала (activate) и обратного распространения ошибки (propagate),
  • инструменты для объединения и конфигурации сетей.

Для реализации NEAT на базе Synaptic нужно:

  1. Представление генома:

    • Использовать объекты JavaScript для хранения узлов и связей, добавляя уникальные идентификаторы для каждой связи.
    • Связи должны хранить вес и включённость.

  2. Эволюция весов:

    connection.weight += (Math.random() - 0.5) * 0.1;

    или полная замена:

    connection.weight = Math.random() * 2 - 1;

  3. Добавление нейронов и связей:

    • Для добавления нейрона можно создать новый объект Neuron, разорвать существующую связь и подключить к нему два новых соединения.
    • Для добавления связи выбирается случайная пара нейронов и создаётся объект Connection.

  4. Скрещивание сетей:

    • Сравнение инновационных номеров генов,
    • Слияние совпадающих генов с случайным выбором родителя,
    • Наследование уникальных генов более приспособленного родителя.

  5. Оценка приспособленности:

    • Каждая сеть выполняет тестовую задачу (например, XOR или управление агентом),
    • Присваивается числовая оценка, используемая для селекции.

  6. Селекция и репродукция:

    • Выбор лучших сетей в каждом виде,
    • Генерация новой популяции через мутации и скрещивание.

Реализация NEAT требует точного контроля за идентификаторами генов, чтобы не нарушить топологию сети. Synaptic предоставляет базовые структуры, но для NEAT необходимо дополнить библиотеку функциями эволюции и мутаций.

Применение NEAT

NEAT эффективен в задачах, где:

  • требуется оптимизация как структуры сети, так и весов,
  • стандартное обучение градиентным спуском не подходит,
  • возможны сложные динамические или непрерывные среды.

Типичные примеры:

  • управление агентами в симуляциях,
  • игра типа Flappy Bird или гонки на трассе,
  • прогнозирование с ограниченными данными.

Оптимизация и практические рекомендации

  • Начинать с малой популяции и минимальной сети, постепенно увеличивая сложность.
  • Использовать разделение на виды для сохранения разнообразия геномов.
  • Ограничивать максимальное количество нейронов и связей, чтобы избежать чрезмерного роста сети.
  • Вести учёт инноваций для корректного скрещивания.
Оглавление