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

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Алгоритмизация адаптивного игрового искусственного интеллекта в мультиагентных играх

1.1 Игровой искусственный интеллект в мультиагентных играх

1.1.1 Агентно-ориентированный подход

1.1.2 Различие между игровым и классическим ИИ

1.1.3 Адаптивный игровой ИИ

1.2 Мультиагентные игры

1.3 Алгоритмы для создания адаптивного искусственного интеллекта

1.3.1 Машинное обучение и эволюционный подход

1.3.2 Нейронная сеть, обучаемая генетическим алгоритмом

1.3.3 Алгоритм искусственной пчелиной колонии (ABC)

1.3.4 Дерево принятия решений

2. Моделирование конкурентной среды интеллектуальных агентов

2.1 Характеристики модели

2.2 Архитектура программы

3. Исследование эффективности алгоритмов

3.1 Характеристики тестирования

3.2 Анализ колонии DT

3.3 Анализ колонии ABC

3.4 Анализ колонии NN+GA

3.4.1 Анализ нейронной сети в процессе обучения

3.4.2 Обученная нейронная сеть

3.5 Анализ поведения колоний в общей среде

3.5.1 Общий анализ поведения колоний при соотношении агентов к еде 1:1

3.5.2 Общий анализ поведения колоний при соотношении агентов к еде 3:1

Выводы

Список литературы

Приложения



Введение

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

Под понятием игровой искусственный интеллект (игровой ИИ) понимают набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером [1]. Игровой ИИ использует многие техники классического искусственного интеллекта, применяемые в других областях, например - машинное обучение.

Одним из самых распространенных является класс игр, в которых в качестве игроков выступают подпрограммы, называемые игровыми ботами или интеллектуальными агентами [2]. В настоящее время в разработке компьютерных игр все чаще применяются методики классического искусственного интеллекта, растет интерес академического общества к технологиям, используемым в компьютерных играх [3]. Игровой искусственный интеллект, позволяющий обучаться или адаптироваться под действия игрока или среды называется адаптивным.

Одной из основных проблем современной игровой индустрии является постоянно растущие требования игроков. Реалистичный, сложный, умный, адаптивный и возможно обучающийся игровой интеллект - одна из главных составляющих залога успешной компьютерной игры. Однако многие разработчики отдают предпочтение классическим методикам игрового ИИ, предполагающим ограниченное количество состояний игрового агента и переходов между ними [4]. Связано это с тем, что адаптивные агенты иногда могут выдавать нелогичное, или, наоборот, слишком логичное, но не нужное для игры поведение.

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

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

1. Определить основные алгоритмы исследования

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

3. Разработать средства для сбора количественной информации о поведении агентов

4. Провести исследование количественных и качественных характеристик поведения агентов

5. Сделать выводы о положительных и отрицательных сторонах алгоритмах и возможных путях использования данных алгоритмов в рамках игровой индустрии

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

1. Алгоритмизация адаптивного игрового искусственного интеллекта в мультиагентных играх

1.1 Игровой искусственный интеллект в мультиагентных играх

1.1.1 Агентно-ориентированный подход

Агентно-ориентированный подход является ведущим в разработке компьютерных игр [5]. Основополагающими его концепциями являются понятия агента и среды, в которой находится агент. Агентом является всё, что воспринимает среду с помощью датчиков и воздействует на эту среду с помощью каких-либо механизмов [6]. Под средой будем понимать пространство, заданное определенными правилами, характерными для отдельной игры, в которой взаимодействуют агенты.

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

1.1.2 Различие между игровым и классическим ИИ

Стоит понимать, что есть большая грань между понятиями "искусственный интеллект" и "игровой искусственный интеллект". Игровой ИИ на простейшем уровне заключается в моделировании или имитации поведения других игроков или объектов (то есть всех элементов игры, которые могут действовать или с которыми может действовать игрок, - от ракет до аптечек), представляемых искусственным интеллектом [7]. Основной принцип состоит в том, что это поведение имитируется. Другими словами, ИИ для игр является более "искусственным", нежели "интеллектом". Система ИИ может быть крайне проста и представлять собой набор правил или же может быть довольно сложной и выполнять роль командующего армии противника, с которой предстоит сражаться игроку.

"Искусственный интеллект" в свою очередь - это целый раздел науки, целью которого является создание настоящего интеллекта, или даже искусственного разума, хотя и искусственными средствами [8].

1.1.3 Адаптивный игровой ИИ

Для большинства игр игровой ИИ заключается в методах проектирования систем интеллекта, вписывающихся в заранее заданные игровые события. Это решение вполне применимо, если все спроектированные модели проработаны достаточно полно и существует четкое понимание целей, которые преследуют управляемые ИИ объекты. Если же в игре требуется большее разнообразие, если у игрока должен быть более сильный и динамичным противник, ИИ должен обладать способностью развиваться, приспосабливаться и адаптироваться [9].

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

1.2 Мультиагентные игры

В мультиагентных играх принимают участие два или более игроков-ботов (агентов), которые конкурируют за некоторый ресурс в игровой среде. Игровая среда представляет собой некое ограниченное пространство, по которому определенным образом могут быть распределены различные предметы, наносящие игрокам урон, препятствия, а также ресурсы. Задача агентов заключается в том, чтобы опередить соперника, получить ресурсы и при этом избежать урон. Как правило, агентам доступны различные действия, выбор следующего действия игроки осуществляют на основании доступной информации о конкурентах и среде, а также на основании собственной истории актов восприятия [10].

Среда, в которой существуют игровые агенты, может быть полностью или частично наблюдаемой, когда агент видит все игровое поле или не видит каких-то областей из-за препятствий или из-за ограничений собственного поля зрения. Среда может быть стохастической, т.е. ее следующее состояние не зависит от текущего состояния и действия, выполненного агентом [11], а может казаться такой из-за того, что является частично наблюдаемой. Практически все игровые среды являются, последовательными и конкурентными. Они могут быть как дискретными, так и непрерывными. Особо сложными являются частично наблюдаемые, динамические, стохастические среды, так как в условиях недостатка информации об изменяющемся мире агенту приходится поддерживать внутри себя некую внутреннюю модель игровой среды, чтобы иметь представление об ее изменениях и ее состоянии.

1.3 Алгоритмы для создания адаптивного искусственного интеллекта

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

1.3.1 Машинное обучение и эволюционный подход

Машинное обучение - обширный подраздел искусственного интеллекта, математическая дисциплина, использующая разделы математической статистики, численных методов оптимизации, теории вероятностей, дискретного анализа, и извлекающая знания из данных [12]. Основной целью машинного обучения является полная или частичная автоматизация решения сложных нелинейных профессиональных задач в различных областях человеческой деятельности.

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

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

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

Выбор пал на следующие алгоритмы:

1. Нейронная сеть, обучаемая генетическим алгоритмом

2. Алгоритм искусственной пчелиной колонии

3. Алгоритм дерева принятия решений

Рассмотрим принцип работы данных алгоритмов.

1.3.2 Нейронная сеть, обучаемая генетическим алгоритмом

Устройство нейронной сети. Искусственная нейронная сеть (artificial neural network, ANN) - математическая модель, построенная по образу и подобию нервных клеток живого организма, а в частности, человеческого мозга [13].

Основным прототипом искусственной нейронной сети является биологическая нейронная сеть - совокупность нейронов (структурно-функциональная единица нервной системы, которая обрабатывает и передает информацию посредством химических и электрических сигналов.) головного и спинного мозга центральной нервной системы (ЦНС) и ганглия периферической нервной системы (ПНС). Связанные или функционально объединенные в нервной системе, они выполняют специфичные физиологические функции [14].

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

В биологической нейронной сети нейрон имеет отростки нервных волокон двух типов - дендриты, принимающие импульсы, и аксон, по которому нейрон может передавать импульс. Аксон контактирует с дендритами других нейронов через специальные образования - синапсы, влияющие на силу импульса. При прохождении синапса сила импульса меняется в определенное число раз, называемое весом синапса. Импульсы, поступившие к нейрону одновременно по нескольким дендритам, суммируются. Если суммарный импульс превышает некий порог, нейрон возбуждается, формирует собственный импульс и передает его далее по аксону. Стоит отметить, что веса синапсов могут меняться со временем, то есть будет меняться и поведение соответствующего нейрона.

Искусственный нейрон, в отличие от нейрона биологического, представляет собой более простой элемент-процессор, получающий на вход сигналы в виде каких-либо параметров для оптимизации или выходные сигналы других нейронов ИНН через некоторое количество входных каналов. Каждый входной сигнал проходит через связь, имеющую определенную интенсивность или вес. Каждый нейрон имеет некое пороговое значение. При поступлении сигнала вычисляется взвешенная сумма входов, из нее вычитается пороговое значение и в результате получается величина активации нейрона (постсинаптический потенциал нейрона, PSP). Сигнал активации преобразуется с помощью функции активации (передаточной функции) в выходной сигнал нейрона [15].

Рис. 1

Математическая модель данного процесса можно описать следующим образом (рис. 1). Каждый вход нейрона (дендрит) имеет синапсы, чьи веса равны w₁, w₂, w_3. К синапсам поступают импульсы силы x₁, x₂, x₃ соответственно. Тогда при прохождении через синапсы к нейрону поступают импульсы равные:

,

V = w_{1 *} x_{1 +} w_{2 *} x_{2 +} w_{3 *} x_3.

Нейрон преобразует полученный суммарный импульс V в соответствии с функцией активации F(x). В итоге на выходе получается величина равная:

y = F(w_{1 *} x_{1 +} w_{2 *} x_{2 +} w_{3 *} x₃).

Выбор функции активации для нейрона практически ничем не ограничен, но наиболее распространенными являются следующие виды функций:

· Линейная функция: Выходной сигнал нейрона равен его постсинаптическому потенциалу

· Пороговая функция: Нейрон выбирает решение из вариантов активен/неактивен

· Многопороговая: выходной сигнал может принимать одно из q значений, определяемых (q-1) порогом внутри предельных значений

· Сигмовидная: выходной сигнал может быть двух вариантов:

- с выходными значениями в промежутке [0,1]:

,

- С выходными значениями в промежутке [-1;1]

,

где коэффициент b определяет крутизну сигмоида.



Рис. 2

Нейроны, соединенные между собой, образуют искусственную нейронную сеть (рис. 2). Как правило, функции активации всех нейронов фиксированы, а веса могут меняться и являются параметрами нейронной сети. Некоторые входы нейронов помечены как внешние входы нейронной сети, а некоторые выходы - как внешние выходы. Подавая любые числа на входы нейронной сети, мы получаем какой-то набор чисел на выходе. Таким образом, работа нейронной сети состоит в преобразовании входного вектора в выходной вектор, задаваемое весами нейронной сети.

В зависимости от количества скрытых слоев, способов связи и методик обучения формируются различные типы нейронных сетей. Одним из наиболее часто реализуемых типов нейронных сетей является многослойный персептрон [16]. Многослойный персептрон имеет входной, выходной слой, а также n-ное количество скрытых слоев, представляющих собой нейроны, не имеющие непосредственных входов исходных данных, а связанных только с выходами входного слоя и с входом выходного. Данные слои дополнительно преобразуют информацию и добавляют модели нелинейности. Многослойный персептрон с сигмовидными решающими функциями способен аппроксимировать любую функциональную зависимость. Однако до сих пор не существует оптимального набора слоев или количества скрытых нейронов, являющимися универсальными показателями для решения любой задачи [17].

Генетический алгоритм как метод обучения нейронной сети. Генетический алгоритм - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе [18]. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссовер.

Генетический алгоритм часто используется в задачах оптимизации как самостоятельное решение, но в рамках данной работы особенный интерес представляет связка "генетический алгоритм + нейронная сеть".

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

1. Оптимизация весов внутри нейронной сети.

2. Оптимизация топологии нейронной сети (отбор среди различных вариаций нейронных сетей с разным количеством нейронов и скрытых слоев).

Наиболее интересным в данной ситуации является оптимизация внутри нейронной сети с ограниченной топологией, т.е. именно оптимизация весов, а не самой нейронной сети. Веса кодируются в виде двоичных последовательностей (хромосом). Каждая особь популяции характеризуется полным множеством весов нейронной сети. Оценка приспособленности особей определяется функцией приспособленности, задаваемой в виде суммы квадратов погрешностей, т.е. разностей между эталонными (ожидаемыми) и получаемыми значениями на выходе сети для различных входных данных [19].

Алгоритм обучения нейронной сети генетическим алгоритмом можно представить следующим образом (рис. 3).



Рис. 3

1.3.3 Алгоритм искусственной пчелиной колонии (ABC)

Данный алгоритм относится к подсемейству алгоритмов эволюционного подхода, именуемых как "роевой интеллект" (РИ). Данные алгоритмы, как и все класса эволюционных, берут за основу оптимизации происходящие в природе явления. Системы роевого интеллекта, как правило, состоят из множества агентов (боидов) локально взаимодействующих друг с другом и с окружающей средой [20]. Идеи поведения, как правило, исходят от природы, а в частности, от биологических систем. Каждый боид следует простым правилам и, несмотря на то, что нет какой-то централизованной системы управления поведения, которая бы указывала каждому из них, что ему следует делать, локальные и случайные взаимодействия приводят к возникновению интеллектуального глобального поведения, неконтролируемого отдельными боидами. В целом, РИ должен представлять собой мультиагентную систему, которая бы обладала самоорганизующимся поведением, которое, суммарно, должно проявлять некоторое разумное поведение [21]. Наиболее известными алгоритмами являются: метод роя частиц, муравьиный алгоритм, пчелиный алгоритм, алгоритм серых волков, алгоритм летучих мышей и т.д.

Алгоритм искусственной пчелиной колонии является относительно новым способом оптимизации, придуманным в 2005 году Дервисом Карабога. Данный алгоритм основан на поведении диких пчел в природе при добыче нектара. Основной целью работы пчелиной колонии в природе является разведка пространства вокруг улья с целью поиска и сбора нектара. Для этого в составе колонии существуют различные типы пчел, такие как пчелы-разведчики, рабочие пчелы-фуражиры, пчелы-наблюдатели. Разведчики ведут исследование окружающего улей пространства и сообщают информацию о перспективных местах, в которых было обнаружено наибольшее количество нектара (для обмена информацией в улье существует специальный механизм, именуемый танцем пчелы). Далее по наиболее перспективным направлениям вылетают рабочие пчёлы, которые занимаются сбором нектара, попутно проводя уточнение информации разведчиков о количестве нектара в некоторой окрестности от указанной разведчиком области. Работа указанных типов пчел в улье обеспечивает эффективную разведку окружающего пространства и сбор нектара [22].

В модели ABC, колония состоит из трех групп пчел: рабочих пчел, наблюдателей и разведчиков. Число рабочих пчел в колонии равно количеству источников пищи вокруг улья. Алгоритм можно описать следующим образом:

1. Каждой еде (параметру оптимизации) назначается своя рабочая пчела (в цикле)

2. Каждая рабочая пчела отправляется к своей еде и определяет соседа, оценивает его нектар и танцует в улье

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

4. Заброшенные источники пищи заменяются на те новые, которые находят пчелы-разведчики

5. Наилучший вариант еды сохраняется

(Пока не выполнится требование).

Отходя от понятия пчел и меда, ABC алгоритм определяет источник пищи как возможное решение к проблеме оптимизации, тогда как количество нектара соответствует фитнесс-функции данного решения. Количество пчел равно количеству возможных решений.

1.3.4 Дерево принятия решений

Согласно наиболее общему определению, дерево принятия решений - это средство поддержки принятия решений при прогнозировании, широко применяющееся в статистике и анализе данных [23].

Рис. 4

Дерево решений, подобно его прототипу из живой природы, состоит из "ветвей" и "листьев" (рис. 4). Ветви (ребра графа) хранят в себе значения атрибутов, от которых зависит целевая функция; на листьях же записывается значение целевой функции. Существуют также и другие узлы - родительские и потомки - по которым происходит разветвление, и можно различить случаи. Цель всего процесса построения дерева принятия решений - создать модель, по которой можно было бы классифицировать случаи и решать, какие значения может принимать целевая функция, имея на входе несколько переменных.

Общий алгоритм построения дерева принятия решений выглядит следующим образом:

Выбрать атрибут Q и поместить его в корневой узел.

Из тестовых примеров (или набора данных) для каждого значения атрибута i выбираем только те, для которых Q=i.

Далее, рекурсивно строим дерево принятия решений в этом потомке.

Основная проблема данного алгоритма кроется в первом шаге - на каком основании выбирается каждый следующий атрибут Q? На этот вопрос существует несколько ответов в виде частных алгоритмов принятия решений - главными из которых являются алгоритмы ID3, C4.5 и CART. Именно данные алгоритмы превращают дерево из простой структуры данных в алгоритм, способный анализировать информацию и обучаться на примерах.

Алгоритм построения дерева решений ID3. ID3, разработанный Джоном Р. Квинланом, является одним из самых известных и наиболее популярных алгоритмов построения дерева принятия решений [24].

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

Алгоритм можно описать следующим образом:

1. Если все примеры положительны, то возвратить узел с меткой "+".

2. Если все примеры отрицательны, то возвратить узел с меткой "-".

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

4. Иначе:

1. A - признак, который лучше всего классифицирует примеры (с максимальной информационной выгодой).

2. Создать корень дерева решения; признаком в корне будет являться .

3. Для каждого возможного значения ():

1. Добавить новую ветвь дерева ниже корня с узлом со значением

2. Выделить подмножество примеров, у которых .

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

4. Иначе, ниже этой новой ветви добавить поддерево, вызывая рекурсивно ID3(, Целевой признак, Признаки)

5. Возвратить корень.

Общий принцип работы дерева принятия решений таков:

1. Дерево принятия решений строится по примерам, содержащим в себе конечное решение

2. В построенное дерево можно направлять n-ное количество атрибутов (атрибуты должны быть того же типа что и данные на этапе обучения)

3. На основе уже изученной информации, дерево будет возвращать, к какой ветке принадлежит тот или иной набор атрибутов

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



2. Моделирование конкурентной среды интеллектуальных агентов

2.1 Характеристики модели

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

Смоделируем конкурентную, замкнутую среду, характеризующуюся следующими параметрами:

· Размеры. Среда создается с заранее заданными параметрами (200х 300).

· Агенты. Количество агентов - настраиваемый параметр, для проведения тестирования важно лишь, чтобы количество агентов было больше 0. Положение агента характеризуется координатами (x, y) и вектором направления.

· Пища. Количество частиц пищи также является настраиваемым параметром. Для тестирования важно чтобы количество пищи было больше 0.

Положение частиц пищи характеризуется координатами (x, y).

Рис. 5

Сенсоры агентов получают от среды следующие показатели: сигнал о наличии пищи поблизости, расстояние до частицы пищи, косинус угла между вектором направления агента и вектором, направленным на еду, сигнал о наличии других агентов поблизости (рис. 5). Способность агента получать информацию о среде ограничивается "областью видимости" - грубо говоря, агент может видеть только впереди себя. Агент взаимодействует со средой путем изменения собственного положения и направления. Агент поглощает пищу при пересечении с ней.

Среда является конкурентной, основная цель агента - собрать как можно больше пищи, основываясь на области видимости, расположении других агентов и расстояния до пищи.

2.2 Архитектура программы

Рис. 6

Готовую программу для исследования алгоритмов можно наблюдать на рис. 6. Она состоит из (1) - конкурентная мультиагентная среда, (2) - панели настроек среды, включающую себя настройки количества еды, агентов, типы агентов, (3) - панели настроек тестирования с возможностью задания времени тестирования и опций вывода, (4) - поля вывода тестовой информации - динамическое (слева) и поминутное (справа).

Рис. 7

Типы агентов наследуются от общего класса Agent (рис. 7). Каждый из дочерних классов представляет собой реализацию одного из алгоритмов для управления адаптивным поведением агента.

· Агент, управляемый нейронной сетью (NetworkDrivenAgent)

Рис. 8

· Агент, управляемый искусственной пчелиной колонией (ABCDrivenAgent)

Рис. 9

· Агент, управляемый деревом принятия решений (TreeDrivenAgent)

Рис. 10



3. Исследование эффективности алгоритмов

3.1 Характеристики тестирования

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

В рамках данного исследования представлено 3 колонии:

1. Колония DT - агенты, управляемые алгоритмом дерева решений DT

2. Колония ABC - агенты, управляемые алгоритмом искусственной пчелиной колонии ABC

3. Колония NN+GA - агенты, управляемые искусственной нейронной сетью, обучаемой генетическим алгоритмом

Для чистоты тестирования будут введены следующие ограничения:

1. Количество агентов в каждой колонии должно быть одинаково

2. Количество агентов в среде всегда фиксировано в рамках одного эксперимента

3. Количество еды всегда фиксировано (при "поедании" агентом еда регенерируется)

Основными критериями оценки каждой из колонии будут служить следующие факторы:

1. Скорость поедания пищи - количество съеденной еды в рамках одной колонии

2. Средняя скорость передвижения агента

3. Качественная оценка поведения агента

В рамках данного исследования будут произведены следующие тесты:

1. Одиночное тестирование каждой колонии

2. Тестирование всех колоний в общей среде в соотношении агентов к еде 1:1

3. Тестирование всех колоний в общей среде с более конкурентными условиями, где соотношение агентов к еде 3:1

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

Для точности результата одиночный тест проводится 3 раза со следующими параметрами:

- количество агентов - 10

- количество еды - 10

- время тестирование - 5 минут

3.2 Анализ колонии DT

Ниже представлена сводная таблица полученных данных (таб.1) и графическое отображение полученной информации в ходе тестирований (рис. 11, 12, 13).

Таблица 1

№ теста	Кол-во съеденной еды	Среднее на агента	Средняя V
1	557	55,7	2,2020339317773225
2	530	53	2,212439712
3	575	57,5	1,79476311474912

Рис. 11

Рис. 12

Рис. 13

Анализ данных:

На сводном графике (рис. 11) видно, что общее количество еды и среднее количество на одного агента приблизительно одинаково для всех результатов тестирования. Количество еды, потребляемой агентом в течение одной минуты (рис. 12) варьируется, хотя средняя цифра остается около 100 еды в минуту. В то же время скорость агентов (рис. 13) примерно одинакова для всех результатов тестирования и составляет в среднем 2, при максимально разрешенной скорости 4.

Анализ поведения:

Поведение колонии схоже во время всех тестирований. Можно выделить следующие основные особенности:

· Агенты движутся со средней скоростью. При максимальной разрешенной скорости 4, агенты движутся со значением ровно половина от максимальной, лишь иногда ускоряясь, чтобы опередить соперника.

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

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

3.3 Анализ колонии ABC

Ниже представлена сводная таблица полученных данных (таб.2) и графическое отображение полученной информации в ходе тестирований (рис. 14, 15, 16).

Таблица 2

№ теста	Кол-во съеденной еды	Среднее на агента	Средняя V
1	329	32,9	2,245798603
2	350	35	1,912978738
3	322	32,2	2,255829392

Рис. 14



Рис. 15

Рис. 16

Анализ данных:

Среднее и общее количество еды (рис. 14) колония ABC потребляет около 300, при том, что количество еды, потребленной в течение одной минуты стабильно и колеблется от 60 до 70 штук (рис. 15). Скорость агента в среднем показывает значение около 2.2, однако сильно колеблется и в течение 5 минут может как достигать отметки 3, так и падать до отметки 1.5 (рис. 16).

Анализ поведения:

Поведение колонии схоже во время всех тестирований. Можно выделить следующие основные особенности:

· При приближении к еде агенты ускоряются.

· Поведение агентов не всегда "адекватно" - практически достигнув цели, агент может развернуться к другой еде или метаться между двумя целями одинакового приоритета.

· В среднем агенты движутся со скоростью 2, однако отдельные особи могут развивать скорость до 3.5.

3.4 Анализ колонии NN+GA

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

- в процессе обучения;

- уже обученной.

3.4.1 Анализ нейронной сети в процессе обучения

Ниже представлена сводная таблица полученных данных (таб.3) и графическое отображение полученной информации в ходе тестирований (рис. 17, 18, 19).

Таблица 3

№ теста	Кол-во съеденной еды	Среднее на агента	Средняя V
1	390	39	2,112095466016364
2	398	39,8	1,784617526
3	404	40,4	1,994474208

Рис. 17



Рис. 18

Рис. 19

Анализ данных:

Несмотря на то, что нейронная сеть обучается в режиме реального времени (первоначально необученная нейронная сеть не может практически ничего), показатели ее довольно высоки. Количество еды, собранной за 5 минут в среднем остановилось на цифре 400 при средней скорости за все время меньше 2пкс/с (рис. 17). Также можно наблюдать драматический скачок в количестве собранной еды между первой и последующими минутами (рис. 18). При этом средняя скорость остается примерно одинаковой во всех тестах, колеблясь от 1.5 до 2.5 (рис. 19). Из этого можно сделать вывод, что в среднем колонии NN+GA требуется около 1-2 минут для обучения сети.

Анализ поведения:

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

В целом можно вывести следующие интересные аспекты поведения:

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

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

· Логичность действий. Нейронная сеть в процессе обучения может показывать крайне нелогичное поведение агента. Однако уже обученная нейронная сеть выглядит наиболее логичным и естественным образом, имитируя поведение каких-либо организмов: при отсутствии еды агенты делают полный оборот вокруг себя, при наблюдении больших стай отправляющихся в одном направлении некоторые особи делают разворот в другую сторону, чтобы искать пищу отдельно ото всех.

3.4.2 Обученная нейронная сеть

Для сравнения результатов возьмем средние показатели по нейронной сети в процессе обучения и сравним их с данными, полученными по уже обученной нейронной сети (таб.4).



Таблица 4

	ИНН в процессе обучения	Обученная ИНН
Количество еды	397	554
Среднее на агента	39,7	55,4
Скорость	1,963729	2,184567

Рис. 20

Как видно из полученных данных, эффективность работы обученной нейронной сети возрастает в 1.4 раза по сравнению с нейронной сетью, обучающейся в процессе тестирования (рис. 20). Также обученная нейронная сеть имеет более высокую скорость (таб.4).

3.5 Анализ поведения колоний в общей среде

Для проведения общего анализа проведем тесты с двумя вариантами параметров:

· Соотношение еды 1:1

Количество агентов на одну колонию: 10

Количество еды: 30

· Соотношение еды 3:1

Количество агентов на одну колонию: 10

Количество еды:10

Различные параметры нужны для создания соревновательного элемента. При соотношении 1:1 получается, что на одного агента в среднем приходится 1 еда и практически нет конкуренции. Соотношение же 3:1 показывает не только умение определенной колонии собирать еду лучше других, но и их адаптацию при большом количестве конкурентов. Для чистоты эксперимента каждый тест будет выполняться 3 раза.

3.5.1 Общий анализ поведения колоний при соотношении агентов к еде 1:1

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

Таблица 5

Данные	Тест 1	Тест 2	Тест 3	Среднее
ABC еда	254	283	281	272,6666667
NN+GA еда	684	893	608	728,3333333
DT еда	1145	1119	1010	1091,333333
ABC Vср.	1,600138656	2,00155501	2,355600397	1,985764688
NN+GA Vср.	2,09380452	2,620171146	1,686636182	2,133537283
DT Vср.	2,322556198	2,085812257	1,883345829	2,097238095
ABC %	12	12	14	12,66666667
NN+GA %	32	38	32	34
DT %	54	48	53	51,66666667

Рис. 21

Рис. 22

Рис. 23

Анализ данных:

Из полученных результатов можно сделать вывод, что в среде, где на каждого агента приходится минимум по 1 еде, лидирует колония DT. Не смотря на среднюю скорость ниже, чем у колонии NN+GA, в среднем колония DT потребляет 52 % всей пищи (рис. 22). Колония NN+GA показывает средний результат, но стоит учитывать, что в данной ситуации мы рассматриваем нейронную сеть в процессе обучения, что означает, что всегда возможны погрешности в ее развитии. В отдельных тестах данная колония может показывать себя как намного лучше полученного значения, так и намного хуже.

Анализ поведения:

При тестировании колоний в общей среде, выводы относительно поведения остаются схожими:

· После минуты обучения колония NN+GA ведет себя наиболее реалистично и логично, хотя модель поведения рознится. Из-за большого количества еды часто развивается "ленивая" модель поведения - агенты медленно крутятся вокруг своей оси на месте до тех пор, пока поблизости не окажется еда - тогда они быстро двигаются к ней и продолжают медленно кружиться на месте в поисках другой еды.

· Колония ABC при большом количестве еды показывает наихудшие результаты, как по сбору еды, так и по поведению - агенты часто мечутся из стороны в сторону, двигаются стаей, редко ускоряются.

· Колония DT показывает наиболее оптимальные результаты по количественным характеристикам, но в реалистичности поведения проигрывают агентам колонии NN+GA.

3.5.2 Общий анализ поведения колоний при соотношении агентов к еде 3:1

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

Таблица 6

Данные	Тест 1	Тест 2	Тест 3	Среднее
ABC еда	192	185	183	186,6666667
NN+GA еда	504	351	391	415,3333333
DT еда	424	467	447	446
ABC Vср.	1,592228329	1,435430556	2,360383435	1,796014107
NN+GA Vср.	1,556694799	2,15812726	2,586313851	2,100378637
DT Vср.	1,831733764	1,916742027	1,961091984	1,903189258
ABC %	17	18	17	17,33333333
NN+GA %	45	34	38	39
DT %	37	46	43	42

Рис. 24

Рис. 25

Рис. 26

Анализ данных:

В более конкурентной среде ситуация немного меняется. Колония NN+GA практически сравнивает свои результаты с колонией DT с результатами 40 % против 43 %. При этом общий показатель колонии ABC тоже улучшается и становится 17 %. При всем при этом можно заметить, что скорость колонии NN+GA значительно выше скоростей других колоний, превышая их в 1.5 раза.

Анализ поведения:

· В конкурентной среде алгоритм NN+GA показывает наиболее оптимальные результаты в плане поведения благодаря лучшему приспособлению к среде. Двигаясь со значительно большей скоростью, чем другие колонии, агенты колонии NN+GA успевают собирать значительно большее количество еды, чем все остальные.

· Алгоритм ABC при меньшем количестве пищи показывает лучшие результаты. Причина в том, что проблемы равности вариантов движения наступает реже.

Исходя из полученных результатов, можно предположить, что уже обученная колония NN+GA выиграет по всем показателям у остальных колоний. Проведем небольшой тест, чтобы проверить эту теорию.

Обученная нейронная сеть.

Таблица 7

Данные	Тест 1	Тест 2	Тест 3	Среднее
ABC еда	163	219	162	181,3333333
NN+GA еда	520	373	511	468
DT еда	435	430	473	446
ABC Vср.	2,17126179	1,999667448	2,115696355	2,095541865
NN+GA Vср.	2,178332266	1,950570128	2,313130189	2,147344194
DT Vср.	2,113636481	2,510369331	2,1527696	2,258925137
ABC %	14	21	14	16,33333333
NN+GA %	46	36	44	42
DT %	38	42	41	40,33333333

Рис. 27

Рис. 28

Анализ данных:

Как видно из полученных данных, действительно, обученная нейронная сеть показывает лучшие результаты среди всех колоний. Исходя из графика (рис. 27) колония NN+GA поедает 43 % от общего количества еды, опережая как колонию DT, так и колонию ABC. При этом средняя скорость колонии DT значительно выше (рис. 28), но эффективность ниже.

Анализ поведения:

Низкий уровень средней скорости колонии NN+GA объясняется их стратегией поведения: агенты либо практически не двигаются, лишь поворачиваясь в поисках пищи, либо стремительно несутся к ней.

Выводы

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

Алгоритм искусственной пчелиной колонии.

Общая характеристика: Агенты, движимые данным алгоритмом, показывают близкие к низким показания скорости и худший результат в эффективности потребления пищи. Поведение агентов нелогично, они часто совершают нерациональные поступки, при большом количестве вариантов еды с равной степенью доступности агенты мечутся между ними. Часто наблюдается такое явление, что практически достигнув пищи, агент направляется в противоположную сторону.

Положительные стороны:

· Эффективно работает при малом количестве параметров оптимизации (малом количестве пищи)

· Нелинейность поведения (в случае, когда требуется создание нелинейной модели поведения)

Отрицательные стороны:

· Поведение не логично и не эффективно при больших количествах параметров оптимизации

Возможные области применения:

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

Алгоритм искусственной нейронной сети, обучаемой генетическим алгоритмом.

Общая характеристика: Агенты, управляемые данным алгоритмом, показывают отличные результаты в тестированиях и лучшие отзывы в качественных характеристиках, таких как логичность и рациональность. С помощью одного алгоритма можно получить огромное количество различных вариантов поведения, и, если брать алгоритм на том этапе, когда он уже обучен, он будет показывать наилучшие результаты среди всех представленных.

Положительные стороны:

· Эффективен при различных уровнях конкурентности среды

· При добавлении дополнительных параметров (какие-либо новые условия или ограничения) модификация алгоритма - минимальна

· Может генерировать огромное количество различных стратегий поведения

Отрицательные стороны:

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

· Подбор наилучшего "мозга" может занять большое количество времени

Возможные области применения:

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

Алгоритм дерева принятия решений.

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

Положительные стороны:

· Результаты оптимальны вне зависимости от размеров среды, количества агентов, врагов или еды

· Легко вводить модификации в зависимости от желаемого результата

· Линейность поведения (в тех случаях, когда оно необходимо)

Отрицательные стороны:

· Может использоваться только в случаях с четко-заданным и продуманным деревом решений (если существует большое количество не зависимых друг от друга вариантов, алгоритм не будет показывать оптимальных результатов).

Возможные области применения:

Любая игра, в которой требуется конечное количество действий, но не требуется проявления "интеллекта" врага. Вариации выбора пути, принятия решения, выбор методики боя.

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

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



Список литературы

1. Алимов А.А., Шабалина О.А. Искусственный интеллект в компьютерных играх. Многоуровневое планирование и реактивное поведение агентов [Электронный ресурс]. Режим доступа: http://masters.donntu.edu.ua/2013/fknt/ilkun/library/ii.htm.

2. Сотников. И.Ю., Григорьева И.В. Адаптивное поведение программных агентов в мультиагентной компьютерной игре [Электронный ресурс]. - Режим доступа: http://cyberleninka.ru/article/n/iskusstvennyy-intellekt-v-kompyuternyh-igrah-mnogourovnevoe-planirovanie-i-reaktivnoe-povedenie-agentov.

3. Редько, В.Г. От моделей поведения к искусственному интеллекту / В.Г. Редько. - М.: КомКнига, 2010. - 456 с.

4. Дональд Кихо, Создание искусственного интеллекта для игр (часть 1) [Электронный ресурс]. - Режим доступа: https://software.intel.com/ru-ru/articles/1.

5. Рассел С., Норвиг П. Искусственный интеллект: современный подход. 2-е изд. / пер. с анг. М.: Вильямс, 2006. 1408 с.

6. Сотников И. Мультиагентные компьютерные игры и обучающийся агент // Образование, наука, инновации: вклад молодых исследователей - материалы IX (XLI) Международной научно-практической конференции / сост. В.В. Поддубиков; под общ. ред. В.А. Волчека. Кемеровский государственный университет. Кемерово, 2014. Вып. 15. 1626 с.

7. Millington (2005). Artificial Intelligence for Games. Morgan Kaufman. ISBN 0-12-497782-0.* Schwab (2004). AI Game Engine Programming. Charles River Media. ISBN 1-58450-344-0.

8. Искусственный интеллект [Электронный ресурс]. - Режим доступа: https://ru.wikipedia.org/wiki/Искусственный_интеллект.

9. Сотников И. Конкурентные мультиагентные игры для софтботов // Материалы 52-й Международной научной студенческой конференции МНСК-2014: Информационные технологии. Новосиб. гос. ун-т. Новосибирск, 2014. 265 с.

10. Гуревич Л.А., Вахитов А.Н. Мультиагентные системы // Введение в Computer Science. - 2005.

11. Свойства среды [Электронный ресурс]. - Режим доступа: http://chernykh.net/content/view/273/472/.

12. Mitchell T. Machine Learning. - McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.

13. Каллан Р. Основные концепции нейронных сетей / Пер. с англ. М.: Вильямс, 2001. 287 с.

14. Уоссермен Ф. Нейрокомпьютерная техника / пер. с англ. Ю.А. Зуев, В.А. Точенов. Режим доступа: http://www.codenet.ru/progr/alg/nks/.

15. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. - М.: Горячая линия - Телеком, 2001. - 382 с. - ISBN 5-93517-031-0.

16. Розенблатт Ф. Принципы нейродинамики: Перцептроны и теория механизмов мозга = Principles of Neurodynamic: Perceptrons and the Theory of Brain Mechanisms. - М.: Мир, 1965. - 480 с.

17. Нейронные сети и их устройство [Электронный ресурс]. - Режим доступа: http://kond-mariya.narod.ru/nauka.html.

18. Генетический алгоритм. Режим доступа: - http://www.aiportal.ru/articles/ genetic-algorithms/1/.

19. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / Пер. с польск. И.Д. Рудинского. М.: Горячая линия-Телеком, 2006. 452 c.

20. Роевой интеллект [элекстронный ресурс]. - Режим доступа: https://ru.wikipedia.org/wiki/Роевой_интеллект.

21. Миллер, П. Роевой интеллект: Муравьи, пчелы и птицы способны многому нас научить// National Geographic Россия. - 2007. - № 8. - С. 88-107.

22. D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.

...