Artificial Intelligence ( Genetic Algorithm )

» опубликован

Artificial Intelligence ( Genetic Algorithm )

Здравствуй читатель. Сейчас я расскажу тебе о построении Искусственного интеллекта с помощью Генетических алгоритмов. Интересно? Тогда слушай.
Генетические алгоритмы - это то, что мы используем на протяжении многих лет. Эволюционные процессы позволяют живым организмам развиваться и приспосабливаться к сложным законам реального мира. Но возможно ли их применение в задаче построения ИИ? Ты не поверишь, но да. Обычно процесс создания ИИ слишком не универсален, а получившиеся шаблоны довольно топорны. Поэтому для вас я приготовил ряд проверенных методов и технологий для успешного построения ИИ.
Все тесты проводились на готовом движке игры Warcraft 3 и с помощью программы kLoader.

Как мы это будем делать

На небольшом примере вы увидите все возможности ГА. Задание выбиралось простым для наглядности и сложным для оценки потенциала.
И так, на небольшой арене появляются два подопытных: герой и его противник. Конечно, наш чемпион заведомо слабее. А для победы он должен отыскать исцеляющий рудник, зелье и научиться эффективно их использовать. Враг будет беспрерывно нападать, создавая большие ограничения.

Термины и определения

Некоторые инструменты, которыми мы будем пользоваться, требуют для пояснения отдельной статьи. Поэтому я дам сжатые понятия, но такие, чтобы их описания было достаточным для понимания материала.
Нейросеть - функция, принимающая и возвращающая несколько параметров.
Однослойная нейросеть - нейросеть, которая состоит из: входного слоя/аргументов, выходного слоя/возвращаемых значений и связей/весов - параметров, изменяя которые мы меняем саму функцию.
Ген - неделимая минимальная составляющая Генома.
Геном - набор генов. Характеризует особь.
Особь, кандидат - геном, который существует в моделируемом мире, то есть, имеет местоположение, принадлежит определенной популяции и т.д.
Популяция - множество особей.
Фитнес-функция - функция пригодности особи.
Генетический алгоритм - стохастический алгоритм поиска (с элементом случайности).
Генетические операторы - методы, воздействующие на геном.
Мутация - изменение генома одной особи.
Кроссовер - скрещивание геномов нескольких особей.

Описание системы

ИИ, опираясь на некоторые сенсоры и используя заложенную логику, будет выдавать конкретное действие. Для такого механизма отлично подойдет нейросеть. В качестве аргументов мы будем подавать состояние и окружение, а на выходе принимаем желаемое действие. Тогда параметры сети будут логикой искусственного интеллекта.
Технические подробности
Для решения подобной задачи мы используем однослойную нейросеть, которая в данном случае вырождается в линейный классификатор. Посмотрите на рисунок справа.
Вход
  • особь{жизнь, угол движения, наличие зелья};
  • враг{жизнь, дистанция, угол};
  • рудник{дистанция, угол};
  • зелье{дистанция, угол};
  • нейрон смещения.
Все данные ограничены видимостью особи и принадлежат интервалу [0,1] или [-1,1].
Выход
  • ничего не делать;
  • бежать{дистанция, угол};
  • выпить зелье;
  • бить врага;
  • идти к руднику;
  • поднять зелье.
Выбирается действие с наибольшим сигналом.
В некоторых случаях я подключал предыдущие значения выходов к входам. Такие сети могут выдавать более сложное и интересное поведение.
Время отклика сети 0.2с.
Функция активации нейронов не используется.

Описание ГА

Описать работу ГА можно так:
  1. Генерация популяции.
  2. Оценка особей. Ранжирование.
  3. Применение генетических операторов. Переход в пункт 2.
Технические подробности
Одной из важных характеристик ГА является мощность. Мощность - это количество особей. Мы будем использовать 13. В обычных ГА их количество значительно больше.
Естественный отбор - один из принципов эволюционных процессов, суть которого в увеличении количества более хороших кандидатов и уменьшении менее хороших. Для исполнения этого принципа будем заменять 33% или 4 особи.
Выбор уничтожаемых кандидатов - самые худшие. Другие стохастические способы могут вывести ключевое решение из популяции, что недопустимо при их малом количестве.
Выбор кандидатов для генетических операторов проходит с помощью метода рулетки.
Метод рулетки - один из простейших методов отбора. Суть его в том, что шанс выбора у более значимой особи больше, у менее значимой - меньше. Использовать будем тот вариант, который учитывает лишь положение особей в отсортированном виде. Предварительные тесты показали, что эта методика показывает результаты лучше, чем любые ручные значения.
Используемая комбинация генетических операторов:
1. Кроссовер.
2. Мутация.
3. Мутация.
4. Перегенерация.
Практика показала, что количество отбрасываемых кандидатов, а также выбор комбинации генетических операторов существенно влияет на скорость сходимости ГА при небольшой мощности.
Количество мутировавших генов 5%-40%.
Использовался двухточечный кроссовер.
Веса сети генерировались в промежутке [-1,1].
Но как именно эти операторы помогают ГА осуществлять поиск? Такой вопрос я бы назвал интересным. Для прозрачности раскрою эту информацию.
Мутация. Обычно заменяется/смещается от одного до нескольких генов. Таким способом происходит стохастический поиск вокруг уже существующего решения - мы сместимся куда-то и посмотрим, что будет дальше.
Скрещивание. Комбинирование генов двух хороших особей в некоторое новое решение. Хорошие они, исходя из того, что до сих пор живы. Логику оператора можно описать так: человеку нравится быть с друзьями, пить алкоголь, ездить на машине. Как видно, парная комбинация может дать как хороший результат, так и не очень. Именно этот оператор чаще всего вызывает взрывной рост пригодности популяции.
Генерация.
  1. Если сгенерировать качественное решение не возможно или очень маловероятно, то алгоритм может не сойтись.
  2. Если нужное решение находится далеко от области генерации, то алгоритм будет сходиться долго.

Фитнес-функция

Фитнесс-функция полностью определяет то, как ГА будет воспринимать пригодность особи и, следовательно, то, к каким решениям нужно стремиться.
Технические подробности
Если функция будет выглядеть как F = Bdeath, где Bdeath {0,1} - событие смерти противника. То алгоритм может никогда не найти решения. В нашем примере случайная особь имеет ~0.001 шанс победить в силу стечения оптимальной генерации генов и окружения.
Вспомним, что вначале мы желали победы нашему герою, для которой он должен найти рудник и зелье. Следовательно, результат функции можно представить в виде суммы задач.
Примеры удачных формул:
F = (Bflask + Bmine + Bdamage + Bdeath) * k
F = (Bflask + Bmine + Bdeath) * ki + (Bflask + Bmine + Bdeath) * kl * Bdamage * ki
Где B[0.,1.] - некоторое задание, (в нашем случае: взять зелье, подойти к руднику, нанести урон, победить.) а k - коэффициент нормировки.
Обратите внимание на вторую функцию. Это использование априорных знаний - невозможно победить, не умея поднимать зелье или вставать рядом с фонтаном. В первом же случае они сразу учатся всему.
Можно выделить два типа реализации заданий: дискретный и непрерывный. Дискретный подход актуален для задания - поднять и использовать - зелье с состояниями {0, 0.5, 1}. Непрерывный подход можно использовать в задаче Bdamage, как ( 1 - (оставшееся здоровье врага)/максимальное )
Наша задача включает в себя несколько локальных оптимумов. Балансируя, алгоритму необходимо найти наилучшее решение. Для повышения эффективности я опишу для тебя несколько приемов:
Усреднение результатов.
При усреднении значений пригодности особи за все раунды мы нивелируем влияние случайных побед, оставляя наиболее качественные и стабильные решения.
Правильное нормирование.
В примере с Bdamage мы использовали абсолютную нормировку. Она проста, понятна, доступна при моделировании, но не учитывает текущий уровень развития популяции. Поэтому мы заменим её более продвинутым вариантом:
damagei / maxdamage, где damagei - урон текущей особи, maxdamage - максимальный урон в текущем раунде.
Такой подход позволяет передвигаться по кривой точек Парето - члены популяции будут стараться сохранять многообразие и максимальный баланс между задачами. А при попадании в некий оптимум в не лидирующих позициях появляется потенциал для новых решений. В то же время, нахождение еще не открытых оптимумов поощряется.
Много малых или один большой.
Посмотрим на следующий пример:
(0.1 + 0.2 + 0.9)/3 = 0.4
(0.4 + 0.4 + 0.4)/3 = 0.4
Две особи решили задачи по-разному, но фитнес-функция и наш алгоритм видит их одинаково. Хорошо это или плохо? Если мы хотим научить алгоритм одновременно решать как можно больше задач, то второй пример явно ценнее. Тогда мы можем взять из каждой задачи[0,1] квадратный корень, для получения нужного эффекта.
(0.1^0.5 + 0.2^0.5 + 0.9^0.5)/3 = 0.57
(0.4^0.5 + 0.4^0.5 + 0.4^0.5)/3 = 0.63

Заключение

Уверен, что многие захотят испытать эти технологии. Ведь ГА преодолевает большие трудности. Естественное поведение нашего ИИ связано с естественным обучением и, в некотором смысле, самообучением. А простота и прозрачность методов поможет в дальнейшем вам изобрести свой ИИ.
Похожие материалы:
ГА на Unity
Естественный отбор


Просмотров: 1 772

» Лучшие комментарии


Bergi_Bear #1 - 5 месяцев назад 0
С удовольствие прочитал, но понят только до середины, дико много терминов, но очень инетерсно... надо как-то статью перестроить немного... и разместить видео с конечным результатом в начало, таким образом это заинтригует читателя "А как же он это сделал"
И не понятно:
  1. как в итоге сохранено конечное поведение, в каком виде?
  2. как в конечном итоге и в последующие разы вызывать сразу алгоритм до которого додумалась нейросеть?
PT153 #2 - 5 месяцев назад 0
А зачем нейросеть, если большая часть функций нейросети не используется?
Vlod #3 - 5 месяцев назад 1   
Bergi_Bear, осуществляет поиск ГА, нейросеть и есть алгоритм.
PT153, что вы имеете ввиду?
PT153 #4 - 5 месяцев назад 0
1 слой, нет функции активации. Лучше просто использовать логистический классификатор, суть та же, но меньше терминов и громкого слова "нейросеть".
Я также совсем не понял, зачем классификатор, если есть ГА. И наоборот, если есть классификатор, то зачем ГА?
bifurcated #5 - 5 месяцев назад 0
Vlod, Вы будите выкладывать сам алгоритм с картой для Warcraft 3, который показан в видео? Недавно по этой теме ролик смотрел youtu.be/SFEZSYVBJ2W Я так понимаю алгоритм после удовлетворяющего результата можно остановить и использовать в конечной карте? Как этот процесс будет выглядеть? В следующей статье расскажите?
Raised #6 - 5 месяцев назад 0
В каком виде хранится результат тренировки нейросетки? Хранится ли вообще? Кст. может кто подсказать в чем была суть AMAI? Была ли это нейронка, появившаяся до того как это стало мейнстримом или какой-то аналитический алгоритм или что еще?
Sergarr #7 - 5 месяцев назад 3   
Raised:
Кст. может кто подсказать в чем была суть AMAI? Была ли это нейронка, появившаяся до того как это стало мейнстримом или какой-то аналитический алгоритм или что еще?
Обычные АИ скрипты, просто лучше, чем стандартные. Обучить нейронную сеть в варике для сколько-нибудь сложной ситуации с помощью ресурсов, имеющихся у обычных людей (т.е. исключая мегакорпорации типа Google) нереально, а для простых случаев - проще руками написать.
DarkLigthing #8 - 5 месяцев назад (отредактировано ) 0
Sergarr:
Обучить нейронную сеть в варике для сколько-нибудь сложной ситуации с помощью ресурсов, имеющихся у обычных людей (т.е. исключая мегакорпорации типа Google) нереально, а для простых случаев - проще руками написать.
Смотря что подразумевать под сложной задачей и каким методом её решать. Не обязательно ведь целиком отдавать нейронной сети задачу научиться играть в Melee стратегию, а например обучить её использовать опыт и угадывать исходя из разведки во что играет противник и прочие ключевые аспекты, в которых слаба типичная архитектура AI.
МрачныйВорон #9 - 5 месяцев назад 0
DarkLigthing, если сделать что то нестандартное. То ИИ начнет тупить
ScorpioT1000 #10 - 5 месяцев назад 0
  1. Амаи не использует обучаемые алгоритмы.
  2. НА jass вполне реально написать различные типы ИНС, но это медленный язык с oplimit
  3. Чтобы быстрее влиться в тему предлагаю поиграть в Evolution, есть даже браузерная версия (но она тормознутее)

Автору предлагаю прям в статью зафигачить - эта игруха реально хорошо вводит в индустрию
Vlod #11 - 5 месяцев назад 2   
bifurcated, я подумаю. Конечно можно сохранить результат
Raised, логика ИИ находится в весах сети
Bergi_Bear #12 - 5 месяцев назад 1   
Vlod, код покеж
PT153 #13 - 5 месяцев назад 0
PT153:
1 слой, нет функции активации. Лучше просто использовать логистический классификатор, суть та же, но меньше терминов и громкого слова "нейросеть".
Я также совсем не понял, зачем классификатор, если есть ГА. И наоборот, если есть классификатор, то зачем ГА?
bifurcated #14 - 5 месяцев назад 0
PT153, Классификатор служит для создания определённого генетического алгоритма, который с течением времени будет развиваться, то есть решения находиться будут с каждым разом лучше, а просто классификатор без ГА это алгоритм с одним поведением.
Raised #15 - 5 месяцев назад 0
Vlod, если весы генерятся во время и на время сессии, то это не слишком полезно.
PT153 #16 - 5 месяцев назад 0
bifurcated, можно сделать несколько заведомо верных начальных данных и действий, натренировать классификатор, и дело в шляпе. Вообще неясно, каким образом тут взаимодействует ГА и классификатор.

Или ГА как раз используется для генерации таких данных, а после мы тренируем на них классификатор? Тогда в этом есть смысл.
ScorpioT1000 #17 - 5 месяцев назад 0
А preload exploit всё ещё работает? Можно с ним это всё сейвить и ресторить
Clamp #18 - 5 месяцев назад 2   
А preload exploit всё ещё работает?
Нет =(

Можно с ним это всё сейвить и ресторить
Эта мысль ещё в описании Data Editor'а была высказана, кстати.

По теме треда считаю, что делать самообучающийся ИИ для Варкрафта — оверкил, хотя идея забавная.
ScorpioT1000 #19 - 5 месяцев назад (отредактировано ) 0
Значит, делать сейв гейм (записав между бинарных меток) и потом запилить конвертер в lua массивы)
PT153 #20 - 5 месяцев назад 0
Вообще неясно, каким образом тут взаимодействует ГА и классификатор.
Vlod, будет ответ на этот вопрос?
Vlod #21 - 5 месяцев назад 2   
Clamp, для тестирования я запускал по 20 копий игры, много ли таких.
PT153, ГА осуществляет поиск оптимальной особи -> генома -> весов сети.
Editor #22 - 5 месяцев назад 0
Надо какое-то наглядное пособие для ламера, как начать тренировать нейросеть на эмуляторе денди например)
Bergi_Bear #23 - 5 месяцев назад 0
Editor, у нас тут варкрафт основная тема, какую эмулятор, пусть кампанию проходит
Editor #24 - 5 месяцев назад 1   
Bergi_Bear:
Editor, у нас тут варкрафт основная тема, какую эмулятор, пусть кампанию проходит
высокопроизводительного кластера нету для варкрафта))