Machine Learning, Нейронные сети

NEAT алгоритм или как обыграть кактусы

Время прочтения: 5 мин.

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

Ген, геном, поколение – наборы нейронов и их связей, которые использует генетический алгоритм

Нейрон – узел нейронной сети, является упрощенной моделью естественного нейрона. Вычисляет выходной сигнал по особым правилам на основе полученных входных сигналов

Связи – сумма входных сигналов нейрона может быть описана с помощью трех факторов: элемент, от которого исходит связь, элемент, к которому связь направлена, и вес связи.

Мутация – бывают двух видов: появляется новая связь между существующими, создается новый нейрон на месте уже существующей связи.

Нейронная сеть представляет собой совокупность нейронов, соединенных друг с другом определенным образом.

NEAT алгоритм (NeuroEvolutionofAugmentingTopology) – алгоритм для создания развивающихся искусственных нейронных сетей, созданный Кеном Стенли в 2002 году. Он изменяет весовые параметры и структуру сетей, чтобы найти баланс между пригодностью разработанных решений и их разнообразием. Он включает три основных метода: отслеживание генов с помощью маркеров истории, позволяющих пересечение топологий, эволюция видов и постепенное разнообразие топологий из простых исходных структур.

Мы будем исследовать NEAT алгоритм на примере обучения искусственного интеллекта играть в игру. Мой выбор пал на Dinosaur Game (доступен через Google chrome по ссылке chrome://dino). Цель этой игры состоит в том, чтобы игрок набрал как можно больше очков, уклоняясь от препятствий в виде кактусов и летающих птиц. Для упрощения встраивания алгоритма нейронных сетей напишем собственную версию игры.

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

Далее была разработана логика алгоритма искусственных нейронных сетей. Всего в поколении за раз используются 500 особей. Цель каждого динозаврика пробежать как можно дальше, счетчиком этого будут очки, отображаемые снизу слева. В каждом поколении динозаврики разделяются на небольшие группы – виды, по схожести развития и действий особей, например, одни динозаврики прыгают не переставая с самого начала, а вторые бегут, сразу пригнувшись. В процессе забега изучаются действия динозавриков, которые приводят к наилучшему результату. Когда все динозаврики умирают, они располагаются в рейтинге по убыванию набранных очков. На этом этапе происходит искусственный “естественный отбор”:

    speciate();//разделяем популяцию на виды
    calculateFitness();//вычисляем приспособленность каждого игрока
    sortSpecies();//сортируем виды для ранжирования в порядке пригодности, сначала лучшие
    if (massExtinctionEvent) { 
      massExtinction();
      massExtinctionEvent = false;
    }
    cullSpecies();//убиваем нижнюю половину каждого вида
    setBestPlayer();//сохраняем лучшего игрока этого поколения
    killStaleSpecies();//удаляем виды, которые не улучшились за последние 15 (ish) поколений
    killBadSpecies();//убиваем виды, которые настолько плохи, что не могут эволюционировать

Далее идет создание следующего поколения. Лучшие особи предыдущего поколения становятся родителями для следующего с небольшими мутациями.

  ArrayList<Player> children = new ArrayList<Player>(); //новое поколение
    println("Species:");               
    for (int j = 0; j < species.size(); j++) { //for каждого вида

      println("best unadjusted fitness:", species.get(j).bestFitness);
      for (int i = 0; i < species.get(j).players.size(); i++) {
        print("player " + i, "fitness: " +  species.get(j).players.get(i).fitness, "score " + species.get(j).players.get(i).score, ' ');
      }
      println();
      children.add(species.get(j).champ.clone()); //добавить чемпиона  без каких-либо мутаций

      int NoOfChildren = floor(species.get(j).averageFitness/averageSum * pop.size()) -1; //допустимое количество детей этого вида, примечание -1, потому что чемпион уже добавлен
      for (int i = 0; i< NoOfChildren; i++) { //получаем рассчитанное количество детей от этого вида
        children.add(species.get(j).giveMeBaby(innovationHistory));
      }
    }
    while (children.size() < pop.size()) { //если не хватает кол-во детей для популяции
      children.add(species.get(0).giveMeBaby(innovationHistory));//получить детей от лучших видов
    }
    pop.clear();
    pop = (ArrayList)children.clone(); //установить детей как текущее поколение
    gen+=1;
    for (int i = 0; i< pop.size(); i++) { //генерировать сети для каждого из детей
      pop.get(i).brain.generateNetwork();
    }
    
    populationLife = 0; 

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

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

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

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

У искусственного интеллекта вырабатывается нечеловеческая реакция, и эта характеристика может очень сильно помочь человеку. После обучения такой нейронной сети ее можно встроить, например, в автопилот для автомобиля. Искусственный интеллект во время поездки сканирует все находящиеся вокруг препятствия, так же, как и динозаврик смотрит на кактусы, и выбирает наиболее лучшее и безопасное направление движения автомобиля. Для применения в Data science большую роль сыграет изменения весов связей и выявление наиболее важных признаков (или их совокупности) поиска информации, в случае динозаврика он большое внимание обращал на расстояние до препятствия, но ему было все равно на ширину препятствия и его собственную скорость.

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

Советуем почитать