Давайте рассмотрим среду: в ней могут существовать частицы «еды» и агенты. С помощью сенсоров агенты могут получать информацию о среде. Если агент находится достаточно близко к частице пищи, то она считается «съеденной» и исчезает, а в тот же самый момент в случайном месте среды появляется новая частица еды. Задача группы агентов — собирать пищу. Эффективность рассматривается исходя из суммарного количества собранной пищи.
Давайте смоделируем конкурентную среду для автоматического поиска оптимального поведения группы агентов. Алгоритм поведения агентов будем конструировать в виде нейронной сети.
Для моделирования конкурентной среды можно воспользоваться генетическим алгоритмом и проводить турниры: всем агентам присваивается нейронная сеть определенной конфигурации («мозг») и через некоторый промежуток времени фиксируется количество съеденных частиц пищи. Выигрывают те нейронные сети, под управлением которых агенты смогли собрать больше еды — на их основе формируется новая популяция нейронных сетей и т.д.
Конечно, существуют специализированные алгоритмы обучения нейронных сетей, но я использовал именно генетический алгоритм, поскольку:
- не хотел ограничиваться конкретной топологией нейронной сети (если более объективно, то это по причине отсутствия теоретических предпосылок относительно того, какую топологию сети и количество нейронов лучше использовать в данном случае)
- хотелось проверить возможность применения генетического алгоритма для обучения нейронной сети
- переиспользовал реализацию генетического алгоритма, которую создал для решения еще одной задачи
Давайте рассмотрим детали нашей модели
Среда характеризуется размерами (шириной и высотой), а также количеством агентов и частиц еды. Среда является замкнутой — агенты не могут выйти за её пределы.
Частицы пищи характеризуются координатами (х, у).
Каждый агент характеризуется положением (х, у) и вектором направления.
Сенсоры агентов получают от среды следующие показатели: сигнал о наличии пищи поблизости, расстояние до частицы пищи, косинус угла между вектором направления агента и вектором направленным на еду, сигнал о наличии других агентов поблизости (и соответственно — расстояние и косинус угла между направлением нашего агента и вектором направленным к другому агенту). Способность агента получать информацию о среде ограничивается «областью видимости» — грубо говоря, агент может видеть только впереди себя.
Агент взаимодействует со средой путем изменения собственного положения и направления. То есть, на вход нейронной сети подаются показатели сенсоров, а на выходе — считывается значение угла, на который нужно повернуть, а также значение величины, на которую следует изменить скорость движения агента.
Генетические операции над нейронной сетью
Для удобства, нейронную сеть можно трансформировать в линейный вид. Для этого достаточно все параметры нейронной сети записать в одномерный массив. К параметрам относятся веса связей, а также тип и параметры переходных функций нейронов. Операции скрещивания и мутации линейных хромосом реализуется достаточно просто.
Модель в действии
Наблюдать за агентами будем в среде с размерами 600 х 400, но для ускорения расчётов, турнирные соревнования проводятся в среде с более компактными параметрами: размеры среды 200 х 200, количество агентов — 10, количество частиц еды — 5.
Нейронная сеть оптимальной конфигурации получается достаточно быстро. На видео можно наблюдать за тем, как меняется поведение агентов, в результате проведения турнирных отборов (если смотреть на ютубе, то изображение будет выглядеть немного чётче):
Интересные наблюдения
- Среду можно усложнить тем, что дать возможность частичкам пищи двигаться. Интересно, что нейронные сети полученные для среды со статическими частицами еды — показывают неплохие результаты и в среде, где пища может двигаться (в конце видеоролика я продемонстрировал двигающиеся частицы еды).
- Среда, в которой функционируют агенты, является частично наблюдаемой (агенты могут видеть только впереди себя, и не могут видеть положение одновременно всех объектов среды).
Также, среда является недетерминированной (частицы еды могут появляться в случайных местах и двигаться в разных направлениях).Но в результате «эволюции» довольно часто образуются такие конфигурации нейронных сетей, которые во время движения к цели «заставляют» агента «поворачиваться по сторонам» (это тоже можно заметить на видео). Такое поведение является эффективным, поскольку всегда есть вероятность, что, пока агент приближается к цели, то какой-нибудь другой агент может съесть эту частицу еды, или на пути к цели появится новый кусочек еды, который можно съесть быстрее.
Если обобщить — более эффективными оказываются те нейронные сети, которые помогают бороться с ограничениями среды.
- Вообще говоря, наблюдая за поведением агентов, иногда складывается впечатление, что они ведут себя достаточно «натурально» — словно группа каких-нибудь жучков или рыб.
Я реализовал возможность сохранять конфигурацию нейронной сети в файл, и следующее видео является демонстрацией различных стратегий поведения, которые я наблюдал:
Если есть желание поэкспериментировать
- У вас должна быть установлена среда выполнения Java
- Эмулятор можно скачать отсюда
- Запук эмулятора:
java -jar simulator.jar
Здесь находятся файлы с мозгами агентов конфигурациями нейронных сетей, которые я использовал в демонстрационных видеороликах.
Эмулятор оснащен простым графическим интерфейсом. Нажатием левой кнопки мыши можно добавлять пищу, а нажатием правой кнопки — новых агентов.
Технические подробности
Архитектура основных компонентов приложения выглядит следующим образом:
Генетический алгоритм выполняется в отдельном потоке, а по его окончании всем агентам устанавливается новая конфигурация нейронной сети, что влечет за собой изменение в поведении агентов на экране. Конфигурацию нейронной сети можно сохранить — достаточно удобным для этого является формат xml.
Вместо заключения
Работая над такой крошечной задачей получаешь массу удовольствия, ты будто создаешь мирок, и наблюдаешь за его развитием. Его можно усложнять, добавляя новые объекты, взаимодействия и ограничения. Возможно, когда-нибудь, для этого найдется более практическое применение :-)
Ссылки
- В этой можно почитать про агентный подход для создания интеллектуальных систем, про различные варианты окружающей среды и стратегии принятия решений:
Stuart J. Russell, Peter Norvig, Artificial Intelligence: A Modern Approach (есть в переводе) - Исходники проекта на гитхабе
- Обобщённая реализация генетического алгоритма — исходники
Ещё один небольшой ролик напоследок:
Автор: stemm