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
Естественный отбор
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
32
4 года назад
0
С удовольствие прочитал, но понят только до середины, дико много терминов, но очень инетерсно... надо как-то статью перестроить немного... и разместить видео с конечным результатом в начало, таким образом это заинтригует читателя "А как же он это сделал"
И не понятно:
  1. как в итоге сохранено конечное поведение, в каком виде?
  2. как в конечном итоге и в последующие разы вызывать сразу алгоритм до которого додумалась нейросеть?
0
28
4 года назад
0
А зачем нейросеть, если большая часть функций нейросети не используется?
3
17
4 года назад
3
Bergi_Bear, осуществляет поиск ГА, нейросеть и есть алгоритм.
PT153, что вы имеете ввиду?
0
28
4 года назад
0
1 слой, нет функции активации. Лучше просто использовать логистический классификатор, суть та же, но меньше терминов и громкого слова "нейросеть".
Я также совсем не понял, зачем классификатор, если есть ГА. И наоборот, если есть классификатор, то зачем ГА?
0
15
4 года назад
0
Vlod, Вы будите выкладывать сам алгоритм с картой для Warcraft 3, который показан в видео? Недавно по этой теме ролик смотрел youtu.be/SFEZSYVBJ2W Я так понимаю алгоритм после удовлетворяющего результата можно остановить и использовать в конечной карте? Как этот процесс будет выглядеть? В следующей статье расскажите?
0
21
4 года назад
0
В каком виде хранится результат тренировки нейросетки? Хранится ли вообще? Кст. может кто подсказать в чем была суть AMAI? Была ли это нейронка, появившаяся до того как это стало мейнстримом или какой-то аналитический алгоритм или что еще?
5
12
4 года назад
5
Raised:
Кст. может кто подсказать в чем была суть AMAI? Была ли это нейронка, появившаяся до того как это стало мейнстримом или какой-то аналитический алгоритм или что еще?
Обычные АИ скрипты, просто лучше, чем стандартные. Обучить нейронную сеть в варике для сколько-нибудь сложной ситуации с помощью ресурсов, имеющихся у обычных людей (т.е. исключая мегакорпорации типа Google) нереально, а для простых случаев - проще руками написать.
0
15
4 года назад
Отредактирован DarkLigthing
0
Sergarr:
Обучить нейронную сеть в варике для сколько-нибудь сложной ситуации с помощью ресурсов, имеющихся у обычных людей (т.е. исключая мегакорпорации типа Google) нереально, а для простых случаев - проще руками написать.
Смотря что подразумевать под сложной задачей и каким методом её решать. Не обязательно ведь целиком отдавать нейронной сети задачу научиться играть в Melee стратегию, а например обучить её использовать опыт и угадывать исходя из разведки во что играет противник и прочие ключевые аспекты, в которых слаба типичная архитектура AI.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.