«Специальность 05.13.10 – Управление в социальных и экономических системах Диссертация на соискание ученой степени кандидата технических наук Научные руководители: ведущий научный сотрудник ИЭОПП СО РАН, кандидат ...»

Учреждение Российской академии наук

Институт систем информатики им. А.П. Ершова

Сибирского отделения РАН

На правах рукописи

МНОГОАГЕНТНЫЕ СИСТЕМЫ В МОДЕЛИРОВАНИИ

СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ОТНОШЕНИЙ:

ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ И ВЕРИФИКАЦИЯ

СВОЙСТВ С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА

Специальность 05.13.10 – Управление в социальных и экономических системах Диссертация на соискание ученой степени кандидата технических наук Научные руководители:

ведущий научный сотрудник ИЭОПП СО РАН, кандидат экономических наук Есикова Т.Н., заместитель директора ИСИ СО РАН, кандидат физико-математических наук Мурзин Ф.А.

Новосибирск– Оглавление ВВЕДЕНИЕ.

МУЛЬТИАГЕНТНЫЕ СИСТЕМЫ. ОБЗОР. ФОРМАЛИЗАЦИЯ.

ОСНОВНЫЕ ТЕРМИНЫ И ПРИНЦИПЫ ПОСТРОЕНИЯ

1. ОБЛАСТИ ПРИМЕНЕНИЯ И ПРИМЕРЫ.

1. МЕТОДЫ ТЕОРЕТИЧЕСКОГО АНАЛИЗА.

1. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ. АГЕНТНЫЕ ПЛАТФОРМЫ.

1. АГЕНТНОЕ МОДЕЛИРОВАНИЕ. СИСТЕМЫ С РОЕВЫМ ИНТЕЛЛЕКТОМ.

1. ФОРМАЛЬНОЕ ОПИСАНИЕ.

1. ИССЛЕДОВАНИЕ СЕМЕЙСТВА МАС С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА

ПРОВЕДЕНИЕ АНАЛОГИИ С ЦЕПЯМИ МАРКОВА.

2. НАХОЖДЕНИЕ ЭРГОДИЧЕСКОГО РАСПРЕДЕЛЕНИЯ И АНАЛИЗ ПОВЕДЕНИЯ МАС.

2. ОПИСАНИЕ СПЕЦИАЛИЗИРОВАННОЙ АГЕНТНОЙ ПЛАТФОРМЫ MASWARM.

2. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ АГЕНТНОЙ ПЛАТФОРМЫ MASWARM.

2. СРАВНЕНИЕ С ДРУГИМИ АГЕНТНЫМИ ПЛАТФОРМАМИ.

2. МОДЕЛЬ РАЗВИТИЯ МЕЖДУНАРОДНОЙ ТРАНСПОРТНОЙ СЕТИ.

ПОСТАНОВКА ЗАДАЧИ.

3. ОПИСАНИЕ МОДЕЛИ.

3. ОПИСАНИЕ ПРОГРАММНОГО КОМПЛЕКСА.

3.

ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА И ВИЗУАЛИЗАЦИИ РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ.

3. МОДЕЛИРОВАНИЕ РАЗВИТИЯ СЕВЕРНОГО МОРСКОГО ПУТИ.

3.

МОДЕЛИРОВАНИЕ РАЗВИТИЯ МЕЖДУНАРОДНЫХ ТРАНСПОРТНЫХ КОРИДОРОВ ЕВРАЗИИ.......

3. ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ 1. ДОКАЗАТЕЛЬСТВА УТВЕРЖДЕНИЙ О ПОВЕДЕНИИ НЕКОТОРЫХ

МАС.

МОДЕЛЬ ШЕЛЛИНГА

1.

ИГРА С ЛОГЛИНЕЙНЫМ ПРАВИЛОМ ВЫБОРА СТРАТЕГИИ ИГРОКАМИ.

2.

ЛОКАЛЬНЫЙ ПОИСК. АЛГОРИТМ ИМИТАЦИИ ОТЖИГА.

3.

ПРИЛОЖЕНИЕ 2. СВИДЕТЕЛЬСТВО О РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ......... ПРИЛОЖЕНИЕ 3. АКТ О ВНЕДРЕНИИ.

ЛИТЕРАТУРА

Введение.

Агентный подход к представлению и реализации крупномасштабных систем становится всё более распространен в последнее время.

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

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

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

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

Целью работы являлось:

- построение и реализация агентной модели развития транспортной сети в контексте исследования свойств мультиагентных систем и принципов их организации и функционирования;

- исследование мультиагентных систем на примере ряда экономических моделей и мультиагентных реализация алгоритмов оптимизации, их формализация;

- выделение общих методов построения и вопросов, касающихся их поведения;

- определение закономерностей, взаимосвязей между интересующими нас свойствами и параметрами, используемыми при задании МАС и их доказательство;

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

В процессе исследования было выделено семейство МАС, включающее в себя различные важные системы и доказаны взаимосвязанность связи между характеристической функцией состояния системы и её поведением, а также проведена оценка распределения характеристической функции. Эти результаты позволяют значительно упростить процесс исследования конкретных систем.

Как правило, в каждом отдельном случае такие утверждения доказываются для каждой конкретной системы. В данной же работе обоснована применимость доказанных полезных утверждений к целому множеству МАС. Использование приёмов и обобщённых утверждений, приведённых в настоящей работе, позволяет для целого ряда систем сделать процесс доказательства тривиальным. Кроме этого, становятся ясны причины того или иного поведения МАС. Это показано на примере одной реализации модели Шеллинга. А также мы получаем механизм, позволяющий строить системы, обладающие заранее известным поведением относительно заданной характеристической функции.

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

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

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

естественных процессов (в роли которых часто выступают мультиагентные системы) и эвристическими оптимизационными алгоритмами.

Движение атомов при охлаждении Алгоритм имитации отжига металла Приспособление генофонда Генетический алгоритм популяции к условиям среды Выделяется семейство МАС, изучение свойств которого предлагается в данной работе. Обосновывается его значимость и общность схемы построения для многих важных МАС. Формализуется схема организации МАС.

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

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

Проведено формальное описание рассматриваемого семейства с учётом поставленной задачи, формализован процесс работы МАС, введено понятие характеристической функции на её состояниях. h(X). Для задач оптимизации (конкретно, максимизации) её можно определить как h(Xi) = max(f(xi,1), …, f(xi,n)), где Xi =. В общем виде работа заключается в пошаговом процессе смены состояний где Gi – стохастическая функция с заданным распределением вероятности.

Во второй главе приведены основные теоретические результаты исследования. Для полученной формализации семейства МАС проведена аналогия с Цепями Маркова, с помощью этой аналогии доказан ряд свойств исследуемого семейства МАС.

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

Сформулирована эргодическая теорема для Цепей Маркова и эквивалентное определение её условий.

При условии, что существует для всех y и не зависит от начального состояния x предел Вектор называется стационарным распределением.

Далее вводятся и доказываются следующие утверждения.

Теорема 1 (о взаимосвязи стационарного распределения и характеристической функции). Пусть элементы матрицы перехода Цепи Маркова представимы в следующем виде:

При этом выполняются следующие условия А для самой ЦМ выполняются условия эргодичности. Тогда стационарное распределение будет иметь вид Следствие 1 (поведение МАС в зависимости от параметров, определяющих её функционирование на каждом шаге). Пусть h(x) – характеристическая функция, определённая на множестве со стояний МАС.

При этом вероятность перехода МАС из состояния x в состояние y равна выполнены условия эргодичности. Тогда вероятность попадания МАС в то или иное состояние с увеличением времени работы стремиться к величине, пропорциональной значению характеристической функции на данном состоянии. Иными словами, для вероятности попадания системы из любого состояния x в состояние y выполняется следующая формула:

Теорема 2 (оценка распределения вероятности характеристической функции). Пусть выполнены условия Теоремы 1, то есть.

Также предположим, что нам дана оценочная функция Тогда для вероятности того, что характеристическая функция превзойдёт заранее данное значение, верна формула Применение их к конкретным агентным моделям и эвристическим оптимизационным алгоритмам дано в Приложении 1.

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

В конце на основе построенных реализаций проведено сравнение нашей агентной платформы с другими существующими подобными программными системами. Произведено сравнение времени исполнения имитационной модели Шеллинга, реализованной на трёх различных агентных платформах: NetLogo, Jade и нашей.

Заметно значительное улучшение по сравнению с NetLogo. Менее явное преимущество относительно платформы Jade компенсируется тем, что трудозатраты на разработку модели на нашей платформе существенно меньше в силу того, что платформа изначально построена для работы с подобными системами.

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

Экономическая картина мира в последнее время стремительно меняется. Формируются новые экономические центры, возникают совершенно новые экономические связи. Вслед за увеличением объёмов производства идёт рост грузоперевозок по совершенно новым направлениям.

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

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

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

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

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

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

государственных и международных организаций (Всемирный Банк, МВФ, Росстат), а также журналов. Однако готовые решения не обладают необходимой для исследователей гибкостью. Они хороши для общего ознакомления со статистической информацией или как источник данных, но анализ данных с их помощью провести нельзя. Это вынуждает либо пользоваться дорогими специализированными статистическими программными пакетами (которые могут также не содержать нужных средств анализа данных), либо для каждой задачи строить отдельную программу (макрос, набор формул), обрабатывающую исходные данные. Ещё одна проблема – отсутствие отдельно работающего, удобного, автономного механизма визуализации географических данных. Всё это обусловливает необходимость создания программной системы, объединяющей 3 основные задачи: извлечение данных из файлов пользователя, их гибкий анализ с возможностью использования специализированных статистических функций и нормировок, визуализация как результатов анализа, так и произвольных исходных данных.

В рамках исследования была построена программная система, в настоящее время она используется в Институте экономики и организации промышленного производства СО РАН. Кроме этого, построены 2 вебприложения, реализующие часть функциональности программы и демонстрирующие возможности публикации результатов в интернете. Одно приложение строит различные диаграммы по фиксированному набору данных. Второе предназначено для построения картографических диаграмм (map charts) различного вида по произвольным пользовательским данным. В сгенерированные диаграммы включаются в связанные с ними статьи http://navizv.github.io/asym_web/ и http://navizv.github.io/zimm/.

проиллюстрировано на примере двух моделей. Первая посвящена исследованию перспектив Северного Морского Пути. В последнее время смягчение климата сделало возможным его более интенсивное использования, и для роста грузопотока по нему наметились два важных источника. Во-первых, это транзитный грузопоток между странами Западной Европы и Восточной Азии (в первую очередь, Китаем). Во-вторых, это транспортировка углеводородов из арктических месторождений России (в первую очередь, сжиженного газа из месторождений Ямала) к странампотребителям. Арктические области Западной Сибири переживают в настоящее время период небывалого для этих мест экономического роста, связанного в первую очередь с освоением новых месторождений природного газа. В связи с этим становится необходимым «научное обоснование долгосрочных перспектив и основных направлений развития различных видов деятельности в Арктике» (пункт 14д Стратегии развития Арктической зоны Российской Федерации). В частности, интересен вопрос о том, насколько окажутся задействованными (и при каких условиях) вновь возводимые объекты инфраструктуры.

Для исследования различных вариантов развития транспортной сети рассматриваемого района была использована построенная программная система. Главным объектом исследования для нас являлись перспективы грузоперевозок по Северному морскому пути (СМП). При этом основными конкурентами СМП являются пути через Суэцкий канал и вокруг Африки (а в перспективе, возможно, ими станут Северо-Западный проход у берегов рассматривался вопрос, сможет ли СМП составить им достойную конкуренцию, и если да, то при каких условиях, выявлено, что при крупных вложениях в инфраструктуру, он сможет стать привлекательнее маршрута, проходящего вокруг Африки.

Вторая модель посвящена более подробному изучению транзитного потенциала России. Рассмотрены не только морские, но и сухопутные и мультимодальные маршруты, например, реализуемые с помощью Международных Транспортных Коридоров «Север-Юг» и «Запад-Восток», а также их альтернативы, как проходящие по территории России, так и обходящие её. В отдельное направление выделена Южная Азия. Показано, что значительная часть грузопотока может пойти по российской территории, при этом начинает наблюдаться эффект конкуренции различных путей, проходящих через Россию, между собой.

1 Мультиагентные системы. Обзор. Формализация.

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

Формализуется схема организации МАС.

1.1 Основные термины и принципы построения.

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

Пожалуй, наиболее широкое определение агента (как «любой сущности, которая находится в некоторой среде, воспринимает ее посредством сенсоров, получая данные, которые отражают события, происходящие в среде, интерпретирует эти данные и действует на среду посредством эффекторов») дано в одной из классических книг по агентам и агентным системам – «Искусственный Интеллект: современный подход» П.

Рассела и С. Норвига [23]. Тем не менее, на протяжении практически всей книги под агентам подразумевается некоторая интеллектуальная система.

Лишь мельком отмечено, что простые реактивные агенты находили применение как модель для психологических бихевиористов.

Однако существует довольно широкий класс систем, составленных из многих агентов, в которых агенты обладают весьма ограниченной интеллектуальностью. Для того, чтобы охватить и такие системы и агенты мы будем использовать концепцию, предложенную В.Б. Тарасовым в [27] (и описанную подробно в [26]). В этой статье рассмотрен целый ряд различных определений агентов, произведено их разделение на «слабые» (в которых агент практически равен любой вычислительной единице с некоторой программой, обладающей теми или иными средствами коммуникации с другими агентами) и «сильные» (согласно которым агент представляет собой антропоморфными свойствами как «убеждения», «настойчивость» и т.п.[42]).

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

Таким образом, система выстраивается не «сверху вниз», а «снизу вверх», не довлеет над интересами составляющих её агентов, но формируется с их обязательным учётом.

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

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

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

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

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

1.2 Области применения и примеры.

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

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

Известны мультиагентные системы моделирования международных отношений, торговли, военных действий.

Интересным перспективным направлением применения МАС является робототехника. Многие общие элементы, методы МАС (например, протокол взаимодействия FIPA ACL) изначально нацелены на использование физических агентов, роботов. Современные автоматизированные бытовые системы всё ещё сильно зависят от человека и покрывают лишь небольшую определённую область человеческой деятельности. Дальнейшее их усложнение чревато, как правило, понижением стабильности и надёжности их работы. В этом свете интересным представляется путь к усложнению автоматизированных систем через взаимодействие, общение составляющих их автономных участников.

Резюмируя, можно сказать, что МАС находят применение везде, где монолитное представление системы по той или иной причине сталкивается с серьёзными проблемами. А такие проблемы возникают в последнее время всё чаще. Примером могут служить всё усложняющие системы управления производством, операционные системы вычислительных устройств (где аналогом агентов являются службы (services) в Windows или процессыдемоны (daemons) в Linux), области исследования общественных наук.

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

Такой путь развития аппаратного обеспечения вычислений ставит соответствующие условия и для обеспечения программного. В программных системах всё чаще используется разделение на параллельные процессы и распределённые вычисления. Ярким примером этого могут служить ставшие популярными в последнее время облачные сервисы. В таком случае МАС можно рассматривать как дальнейшее развитие объектно-ориентированной парадигмы в условиях параллельности и распределённости вычислительных процессов.

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

Два этих типа агентов порождают два существенно отличающихся друг от друга типа МАС, два ключевых направления в исследовании агентов и составленных из них систем. Это Распределённый искусственный интеллект (РИИ) и Искусственная жизнь (ИЖ). Системы РИИ составлены, как правило, из небольшого числа интеллектуальных агентов. Системы ИЖ, напротив, составлены из большого числа реактивных агентов.

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

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

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

Вторую группу составляют системы, построенные с использованием относительно большого количества (от десятков до тысяч) агентов, имеющих простую внутреннюю структуру и не обладающие сложным поведением. Как правило, их поведение определяется простыми реактивными правилами, то есть, агенты следят за изменением определённых внешних параметров и под влиянием их изменения изменяют некоторые другие параметры среды и своё состояние. Эта реакция может иметь вероятностный характер, имитирующий контринтуитивность и сложное поведение действительно интеллектуальных агентов. Несмотря на то, что отдельные агенты не представляют собой систем искусственного интеллекта, составленная из десятков-сотен таких агентов система в целом может проявлять так называемый «роевой интеллект». Это достигается благодаря большому числу агентов и вероятностной природе их поведения.

В [26] Направление теории МАС, изучающее такие системы, называется Искусственной Жизнью (в широком смысле этого слова). Однако, как отмечается, такие системы могут находить применение не только в моделировании естественных процессов, но и в других областях, например, в эвристических алгоритмах. При этом их ключевой особенностью остаётся проявление сложного поведения в результате совместных действий большого числа простых реактивных агентов, так называемого «роевого интеллекта».

Поэтому мы также будем называть такие системы мультиагентными системами с роевым интеллектом.

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

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

Системы как первой, так и второй группы сейчас играют всё более важную роль в развитии информационных технологий и, в частности, искусственного интеллекта. Например, системы первой группы используются для решения производственных, в частности, логистических задач [31], при реализации систем дистанционного обучения [18], моделировании военных действий [20], второй – для задач оптимизации, например в мета-эвристических алгоритмах муравьиной колонии или роя частиц, при построении различных имитационных моделей в общественных науках (социологии, психологии, экономике) [33,35], естественных науках (экологии, биологии).

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

Системы второго типа применяются при моделировании общественных (например, экономических) процессов, когда нужно учитывать поведение большого числа участников (людей, продавцов, покупателей), которые формируют своей деятельностью общую картину. Ещё одна развивающаяся область применения систем второго типа – исследование операций и эвристические алгоритмы оптимизации. Действительно, различные модели естественных процессов (биологических, физических, экологических, социальных, экономических) в ходе своей работы иллюстрируют способность моделируемых систем находить всевозможные оптимальные решения, природные «ниши» и т.п. Зачастую становится возможным применение этих способностей при решении сложных оптимизационных задач, для которых не существует эффективных классических алгоритмов.

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

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

Модель муравьиной колонии иллюстрирует способность муравьёв находить кратчайший путь к цели и может быть использована для определения кратчайшего гамильтонова цикла во взвешенном графе для задачи коммивояжёра. Модель развития во времени генофонда популяции используется для нахождения оптимума сложной функции в генетическом алгоритме. Этот перечень аналогий можно продолжить и далее [40]. Таким образом, многим моделям можно поставить в соответствие эвристический оптимизационный алгоритм, основанный на тех же принципах.

Движение атомов при охлаждении Алгоритм имитации отжига металла Движение муравьёв в колонии Муравьиный алгоритм (алгоритм Приспособление генофонда Генетический алгоритм популяции к условиям среды Полученные МАС, в свою очередь, могут быть использованы при построении интеллектуальных агентов для систем РИИ (например, в [23] генетический алгоритм рассматривается не как МАС, а как возможная составная часть интеллектуального агента) Теоретическое обоснование эффективности таких алгоритмов, как правило, является отдельным и сложным вопросом, и не всегда возможно. А там, где возможно, имеет вероятностный характер, исчезающий лишь в пределе (например, доказательство эффективности алгоритма имитации отжига в [12]). Несомненно, такое обоснование является одной из важнейших проблем, которую можно представить в рамках теории мультиагентных систем.

1.3 Методы теоретического анализа.

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

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

Вообще для логического подхода к анализу МАС свойственно использование логики первого порядка дополненной средствами, характеризующими изменчивость и релятивизм определения истины. Например, в работе [30] рассматривается процесс договоров агентов между собой с логической точки зрения и используются следующие выражения:

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

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

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

состоящая из «базисных атомов» – логических выражений вида, где p – предикатный символ, а - константы, а также почтовый ящик. Текущее состояние агента это состояние его БД и почтового связи. Агенты кладут сообщения в канал и по прошествии определённого времени они попадают агентам-адресатам в почтовый ящик.

Вероятность того, что сообщение будет идти по каналу связи в течение времени t определяется как. В том числе, существует вероятность того, что сообщение вообще не дойдёт до агента-адресата. Время в данной модели считается дискретным.

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

С каждым агентом связана некая программа – последовательность параметризованных действий: добавление/удаление атомов из БД агента или пересылка сообщений другому агенту. На этой последовательности определено распределение вероятности и каждый следующий шаг выбирается в связи с текущим состоянием агента. В дальнейшем для определённого таким образом семейства проводится аналогия с Марковскими процессами и доказывается ряд свойств и оценок сложности верификации.

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

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

1.4 Программное обеспечение. Агентные платформы.

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

Существует довольно большой набор платформ, подходящих для создания мультиагентных систем, и этот набор постоянно пополняется. В него входят NetLogo, StarLogo, Repast Simphony, Eclipse AMP, JADE, Jason.

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

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

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

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

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

Однако за богатством предоставляемых средств скрывается бедность непосредственно технических возможностей системы. Во-первых, набор предоставляемых средств визуализации, хотя и широк, но строго фиксирован и регламентирован, кроме того, невозможно добавление каких-то своих приёмов. А во-вторых, система страдает именно как средство разработки программ, фактически принуждая программиста писать всю программу одним файлом, без какой-либо чёткой структуры. Кроме того, язык программирования весьма специфичен, поскольку он основан на учебном языке Logo, и вдобавок содержит многочисленные методы, предназначенные уже специально для моделирования. Язык программирования NetLogo является скриптовым языком и написанные на нём программы исполняются ощутимо медленно. В настоящее время ведутся работы по созданию его транслятора в байт-код, что обещает в перспективе существенное улучшение времени исполнения [41].

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

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

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

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

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

Однако они уже и не являются фактически автономными системами, а воплощаются в виде подключаемых модулей к существующим средствам разработки. Это довольно хорошо, поскольку позволяет совмещать богатство предназначенными исключительно для агентного моделирования средствами. К данному классу инструментов относятся системы Jason, Eclipse AMP (2009).

Ярким представителем такого класса систем является Repast Simphony – подключаемый модуль к системе разработки (IDE) Eclipse. Во-первых, такая реализация позволяет использовать существующие возможности среды, да и новых языков программирования учить не приходится. А вовторых, предоставляемые методы разработки агентных систем позволяют сконцентрироваться именно на написании агентов, причём использовать при этом весьма наглядные и интересные средства.

Главным плюсом, безусловно, является непосредственная работа с агентами и системами их взаимодействия. Так, существуют простые методы создания агента, задания его параметров, описание его поведения даже с использованием блок-схемы. Всё это делает работу с системой довольно удобной и понятной.

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

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

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

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

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

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

Итак, что касается отдельных библиотек, то они, во-первых, как правило, распространяются с исходным кодом, так что при желании в них даже можно внести изменения. Во-вторых, их использование не ограничивает нас в выборе подходов к решению задачи, заданию различных параметров. Что же касается отсутствия механизма визуализации – то тут надо отметить, что нужных нам средств визуализации нет и у решений, выполненных в виде отдельных сред разработки. Так что, вероятнее всего, всё равно придётся использовать, какие-то другие, сторонние средства. К тому же такие библиотеки весьма свободно распространяются.

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

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

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

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

Агентные модели. Первым, наиболее важным в данной работе представителем рассматриваемого семейства являются имитационные агентные модели (agent-based models), наиболее распространённые в общественных науках – социологии, экономике и т.п. Встречаются они и в естественных науках (физике, биологии), в общем, во всех случаях, когда нужно промоделировать деятельность системы, состоящей из большого количества субъектов, чья деятельность или вероятностна по своей природе, или подвержена влиянию необозримого количества различных случайных воздействий. При этом поведение системы в целом определяется не сверху, а снизу, т.е. в результате совокупности действий составляющих её агентов. В число моделируемых таким образом процессов входят, например, процесс распространения пожара в лесу.

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

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

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

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

Эвристические мета-алгоритмы для задач локального поиска.

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

Мы будем рассматривать определение задачи локального поиска данное в [13]. Для задач такого типа существуют различные общие алгоритмы (или схемы алгоритмов, называемые также мета-алгоритмами).

Возьмём, к примеру, генетический алгоритм (ГА). Описание схемы генетического алгоритма широко известно, его можно взять, например, в [48].

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

Поскольку рассматриваемая функция, как правило, имеет довольно сложный вид (для простых функций чаще всего имеются специализированные алгоритмы, работающие гораздо эффективней, чем ГА), то её вычисление занимает значительное время по сравнению с другими действиями, такими как сбор информации, определение особей для размножения и собственно размножение (формирование характеристик новой особи). Таким образом, нагрузка на систему в целом равномерно распределяется по составляющим её агентам.

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

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

Перейдём теперь к формализации интересующего нас семейства МАС, с учётом поставленного перед нами круга задач и определённого выше понятия верификации для систем данного семейства.

1.6 Формальное описание.

Итак, для основных представителей рассматриваемого нами семейства МАС характерным оказывается следующее. Процесс работы системы представляется в виде итераций, последовательно проходимых однотипных шагов. Но на каждом из этих шагов в действие вступают, как правило, несколько агентов. Далее, поведение агентов случайно, но распределение их решений зависит от вычисляемого значения некоторой определённой функции. Кроме этого, после принятия всеми агентами решения на конкретном шаге в процесс может включаться некоторый центральный агент, определяющий параметры для следующего шага. В общем случае все агенты делятся с ним информацией о принятых решениях – то есть о значении своих централизованного обмена информацией может и не быть. Например, каждого агента могут интересовать значения характеристик лишь выбранных агентов, скажем, его соседей (отношение соседства определяется на множестве агентов заранее или может меняться в процессе работы МАС).

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

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

Например, это решение о переезде агентов в рассмотренной выше модели Шеллинга. Это накладывает ограничения на использование параллельного исполнения, но всё равно не исключает выгоды, достигаемой им.

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

При этом правила перехода определяются правилами перехода, то есть алгоритмами поведения агентов, вообще говоря, вероятностными.

Определим состояние системы как совокупность состояния всех её агентов и среды. Предположим, что правила перехода агента из одного состояния в другое зависят только от его текущего состояния (и не зависит от предыдущих, уже пройденных агентом состояний). Если это не так, то в набор состояний агента можно добавить «память» агента о предыдущих состояниях, и привести правила к указанному виду. В таком случае и переход всей системы из одного состояния в другое представляется как случайная величина, чьё распределение зависит только от текущего состояния.

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

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

Пусть нам даны n агентов (A1, …, An). Целью каждого агента является нахождение максимума заданной функции f(x) (будем называть её целевой функцией) на заданной области D. Действия агентов определяются следующим алгоритмом. Изначально каждый агент получает начальное решение x0,j (j = 1, …, n). Для краткости будем обозначать совокупность значений переменной x у всего набора агентов как X =. Итак, агенты получают (или находят случайным образом) начальный набор X0 и начинают пошагово искать максимум целевой функции. Опишем алгоритм их деятельности (в общем виде) на i-м шаге.

У каждого агента имеется значение xi,j (короче говоря, задан набор Xi).

Сначала каждый агент вычисляет значение целевой функции на данном ему значении x (f(xi,j), обозначим для краткости fi,j, а набор значений f у всех агентов - Fi). Затем агенты обмениваются информацией о найденных решениях (каждый агент сообщает каждому, или передаёт в общую память, значения xi,j. fi,j). Далее, исходя из полученных решений, каждый агент определяет следующее значение xi+1,j = gi,j(Xi,Fi). Обозначим это кратко так:

Xi+1 = Gi(Xi,Fi), где функция Gi(Xi,Fi) определяет набор. Функции gi,j(Xi,Fi) в общем случае могут не быть строго детерминированы, и для многих мультиагентных моделей это действительно так.

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

Представление генетических алгоритмов в рамках полученной модели. Деятельность довольно большого круга интересующих нас МАС можно представить в предложенном нами общем виде. Интересным примером является мультиагентная реализация генетического алгоритма (ГА). Возьмём за основу описание ГА, данное в [48]. Предположим, что агенты – это селекционеры, выращивающие, отбирающие и скрещивающие лучших особей. Количество селекционеров равно количеству особей в одной популяции. Сначала селекционеры получают начальную популяцию X0.

Затем они вычисляют значение функции полезности каждый для своей особи (F(X0) = ). Затем каждый агент-селекционер выбирает сообразно значениям функции полезности случайным образом 2 особирешения и скрещивает их (алгоритм выбора и алгоритм скрещивания могут быть разными в разных реализация ГА). Таким образом определяется значение функции gi,j(Xi,Fi). Формально функцию g можно определить через умножение случайным образом составленных матриц на векторы, что например, проделано в [3].

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

Представление ГА в виде мультиагентной системы, где каждому агенту соответствует особь в популяции позволяет существенно сократить время работы ГА. Однако ещё одна выгода такого представления состоит в том, что оно позволяет применить математические методы для оценки свойств описываемой им МАС.

рассмотрели наиболее удобный для построения параллельных программных систем, когда на каждом отдельном шаге агенты действуют совершенно независимо друг от друга. Однако в более общем случае независимость действий агентов на протяжении шага нельзя гарантировать. Напротив, для более развитых моделей и методов агентам необходима коммуникация, хотя она, возможно, будет и не так сложно организована, как в МАС первой группы. Тем не менее, в действиях агентов сохраняется некоторая независимость, а круг агентов, с которыми общается данный конкретный агент для принятия решения на определённом шаге, зачастую может быть ограничен (например, заданием на множестве агентов отношения соседства).

Всё это ещё оставляет возможность для повышения эффективности работы системы по времени благодаря параллельному исполнению.

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

Итак, мы будем рассматривать состояние всей системы X. Множество всех состояний обозначим S. Поскольку в общем виде у нас может не быть заданной для всех агентов функции f, то мы будем рассматривать функцию перехода Gi как зависящую только от текущего состояния X (её можно представить в таком виде и для рассмотренного ранее более конкретного случая с независимой деятельностью агентов). Иными словами, мы получаем Xi+1 = Gi(Xi). Функция f у нас характеризовала состояние отдельных агентов.

Теперь нам нужна функция, аналогичная ей, но определённая уже на множестве состояний всей системы. Обозначим её h(X). В случае, когда нам дана f, можно, например, задать h(Xi) = max(f(xi,1), …, f(xi,n)), где Xi =.

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

2 Исследование семейства МАС с помощью цепей Маркова.

исследования. Для полученной формализации семейства МАС проведена аналогия с цепями Маркова, с помощью этой аналогии доказан ряд свойств исследуемого семейства МАС. Также приведён результат работы по созданию агентной платформы – программной системы (в данном случае реализованной как библиотека классов), которая позволяет упростить процесс построения МАС исследуемого семейства, а также содержит средства управления работой системы и наблюдения за её ключевыми свойствами, исследуемыми в данной работе.

2.1 Проведение аналогии с цепями Маркова.

Для начала введём формальное определение Марковского процесса и ряда интересующих нас свойств. Точное и полное определение Марковского процесса можно найти, например, в [4]. Говоря неформально, Марковским является такой случайный процесс, у которого при фиксированном настоящем состоянии все будущие зависят только от него (а не от прошлых).

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

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

Итак, представим себе последовательность случайных величин последовательность называется цепью Маркова (ЦМ) если иными словами, вероятность попасть в определённое состояние зависит лишь от предыдущего состояния.

Уже из определения можно увидеть способ задания ЦМ через вероятность попадания из одного состояния в другое за единицу времени, заданную для всех состояний.

Эти элементы составляют так называемую матрицу переходов.

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

Эти элементы составляют вектор, который называют начальным распределением. Как можно заметить, при заданных матрице перехода и начальном распределении можно получить распределение вероятности состояний на заданном шаге путём перемножения нужного количество матриц перехода и вектора начального распределения. Если матрица перехода постоянна и не зависит от рассматриваемого момента времени, то такая ЦМ называется однородной. В дальнейшем будем рассматривать только такие цепи. Обозначим вероятность перехода из состояния x в состояние y за n шагов как. Как видно, эти элементы так же составляют матрицу. Тогда для однородной цепи очевидно следующее соотношений для матриц перехода.

Основным интересующим нас фактом из теории Цепей Маркова является эргодическая теорема. Приведём её формулировку по [4]. При условии, что существует для всех y и не зависит от начального состояния x предел Вектор называется стационарным распределением. Очевидно, что, если текущее распределение стационарно, то оно уже не изменяется после применения матрицы перехода. Иными словами, На практике проще бывает воспользоваться эквивалентным условием эргодичности. ЦМ должна быть неразложима, возвратна и апериодична.

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

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

Для наглядности этих условий можно использовать граф переходов.

Определим для ЦМ граф переходов по заданной матрице переходов Тогда все возможные переходы из одного состояния в другое мы можем совершить, проходя по рёбрам графа.

Теперь вернёмся к введённому выше нами описанию работы МАС. Оно в нашем описание представляет Марковский процесс с дискретным временем, где множество состояний — это S, а матрица перехода определяется функцией G(X). В дальнейшем для описания состояний МАС будем употреблять строчные буквы, а если мы рассматриваем поведение и состояние отдельных агентов, оговаривать это.

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

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

Таким образом, задача верификации свойств системы, проверки и установлению утверждений о её характеристиках сводится к задаче нахождения стационарного распределения Марковской цепи, соответствующей данной МАС.

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

Теорема 1. Обозначим множество состояний цепи Маркова S.

Предположим, что S конечно. Пусть на S определена некоторая функция (будем называть её характеристической) h : S, а также дана матрица : S S. Предположим, что:

Цепь Маркова неразложимая и непериодическая;

вероятность перехода из одного состояния в другое может быть Тогда стационарное распределение имеет вид Прежде чем доказывать теоремы, рассмотрим её важное для теории МАС следствие, которое, как мы покажем в 5й главе, часто используется при доказательстве свойств поведения отдельных систем.

Следствие 1. Пусть h(x) – характеристическая функция, определённая на множестве со стояний МАС. При этом вероятность перехода МАС из состояния x в состояние y равна xyh( y), причём xy yx для всех x, y S.

Пусть на данном графе выполнены условия эргодичности (то есть для состояний ЦМ и графа переходов). Тогда вероятность попадания МАС в то или иное состояние с увеличением времени работы стремиться к величине, пропорциональной значению характеристической функции на данном состоянии. Иными словами, для вероятности попадания системы из любого состояния x в состояние y выполняется следующая формула:

Доказательство Теоремы 1. Из условий эргодичности мы получаем по эргодической теореме факт существования стационарного распределения.

Осталось лишь доказать, что оно представимо в нужном нам виде. Как известно, для стационарного распределения необходимым и достаточным условием является следующее утверждение:. Покажем, что для выбранного нами оно выполняется. Для произвольного состояния y Последнее равенство мы получили в силу исходных положений теоремы для них выполняется утверждение Заменой y на x получаем Подставив это выражение, получаем иными словами, в векторном виде. Это значит, что определённое в теореме действительно является стационарным распределением для данной ЦМ, что и следовало доказать.

Доказательство Следствия 1. Следствие 1 доказывается тривиальным образом с использованием приведённой выше аналогии между понятиями, связанными с МАС и терминами ЦМ. Действительно, с течением времени вероятность попадания системы в то или иное состояние стремится к величине стационарного распределения для этого состояния. Поскольку в Теореме 1 доказано, что стационарное распределение имеет определённый вид, то утверждение следствия становится очевидным.

Тот факт, что, позволяет нам переформулировать условие эргодичности для графа окрестностей. Действительно, переход из состояния x в состояние y возможен (иными словами, x и y – соседние состояния) тогда, Оценка распределения вероятности характеристической функции.

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

Проиллюстрируем это на предельном случае – пусть в 1000 состояний значение функции равно 1, а в одном (оптимальном) – 10. Тогда вероятность попадания в оптимальное состояние относится к вероятности непопадания в него как 10:1000, то есть, вероятность попасть в оптимальное состояние равна 1%.

Таким образом, о свойстве, доказанном в Теореме 1 можно сказать то, что сказано для его частного случая в [46].

Для исследования поведения МАС полезно было бы иметь функцию, оценивающую вероятность приближения к оптимальному состоянию.

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

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

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

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

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

2.3 Описание специализированной агентной платформы В главе 1 нами были рассмотрены некоторые агентные платформы.

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

Для создания небольших МАС с роевым интеллектом лучше всего подходит платформа NetLogo. Однако она имеет ряд существенных минусов.

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

Подытоживая, можно сказать, что система NetLogo является плохо масштабируемой, она замечательно подходит для реализации небольших и нетребовательных ко времени исполнения МАС, однако её использование для создания сложных, больших или просто требовательных ко времени МАС сопряжено с неразрешимыми трудностями.

Использование стороннего языка и среды разработки (например, C++ или Java) сняло бы все эти проблемы. Однако агентные платформы, использующие такое решение, как правило, излишне тяжеловесны для нашей задачи. Они изначально ориентированы скорее на реализацию МАС 1го типа (систем РИ, см. главу 1). Всё это делает привлекательным идею создания собственной агентной платформы, которая смогла бы соединить положительные черты как одних, так и других платформ. В общем она должна предоставлять примерно ту же функциональность, что и NetLogo, однако средой разработки должна стать некоторая независимая и достаточно хорошо развитая среда (в этом качестве была выбрана Java).

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

Действительно, проведённая в главе 1 формализация семейства МАС позволяет полностью задать работу системы с точностью до определения ключевых функций – h, G и (в случае независимости действий агентов на каждом шаге) f. Понятен простейший набор средств управления, они включают в себя рычаги запуска и остановки процесса моделирования. Ясны и значения, нуждающиеся в мониторинге – это номер текущего шага и значение характеристической функции h. Также необходимы чисто технические средства обеспечения ввода/изменения параметров системы, визуализации в различных формах (в том числе встраиваемой), выкладывания созданных моделей в интернет, сохранение результатов моделирования.

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

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

Пользователю же библиотеки предоставляется возможность определить вид визуализации, целиком определить связанную с ней структуру объектов и определить функции. После этого, с использованием стандартных средств библиотеки он получает МАС с заданными им свойствами и средства для работы с нею и её изучения.

Для реализации библиотеки было принято решение использовать Java.

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

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

Опишем реализованный нами набор классов, предоставляемые ими возможности и методы, нуждающиеся в конкретизации при создании конкретной реализации МАС на базе нашей платформы. Библиотека классов представляет собой пакет ASwarm с двумя подпакетами ASwarm.grid и ASwarm.parallel.

Основными классами для создания на их основе конкретной системы являются классы: МАС (ASwarm, «рой»), агент (Agent), отношение (Relationship). При этом класс ASwarm имеет абстрактные методы, которые необходимо определить при реализации системы. Абстрактные методы МАС – выбрать агентов для следующего шага, сделать шаг (вычислить G), вычислить характеристическую функцию (h). Библиотеки содержат:

отношение типа «шахматная доска» (grid) и соответствующее ему отображение( абстрактный метод – нарисовать 1 агента в клетке) и параллельные (независимые в течение одного шага) агенты и МАС (абстрактные методы – вычислить f (у агента) и вычислить g’ (у МАС)).

Рассмотрим классы подробнее.

Пакет ASwarm.

ASwarm – абстрактный класс «роя» (МАС). Абстрактные методы – выбрать агентов для следующего шага, сделать шаг (вычислить g), вычислить характеристическую функцию (h). Можно определить свою панель для отображения.

ASwarmFactory – вспомогательный интерфейс фабрики МАС для передачи основной панели МАС.

Agent – агент.

Globals – класс глобальных характеристик МАС, изменяемых в процессе исполнения (время, значение характеристической функции).

LineChart – вспомогательный класс (наследник JPanel) для рисования графика характеристической функции в режиме реального времени SwarmPanel – главная панель с визуализацией МАС и средствами управления ею. Включена в стандартные формы программы, содержащиеся в библиотеке (окно и апплет). Может быть включена в программу пользователя как независимый модуль.

SwarmFrame – окно, содержащее основную панель визуализации.

Может быть создано и вызвано в программе пользователя.

SwarmApplet – абстрактный класс, Java-апплет, содержащий основную панель визуализации. Может быть использован путем создания пользователем класса-наследника и определения им инициализирующего абстрактного метода init.

Params – monostate-класс с глобальными параметрами МАС.

Relationship – базовый класс для задания отношения между агентами.

Пакет ASwarm.parallel (для случая независимой работы агентов на каждом шаге, агенты-потоки, исполняемые параллельно) ParAgent – абстрактный агент, содержащий свой частный поток управления и средства синхронизации. Абстрактный метод – вычислить f.

ParSwarm – абстрактная МАС, содержащая средства синхронизации параллельных агентов в конце каждого шага. Абстрактный метод – вычислить g’ (функцию, обеспечивающую переход агентов к новому состоянию с учётом известных полученных значений функции f).

Пакет ASwarm.grid (для задания на агентах отношения соседства на основе окрестности по Муру на «шахматной доске», имеющей топологию тора).

GridPanel – абстрактный класс для отображения агентов в виде множества клеток. Абстрактный метод – нарисовать 1 агент на клетке.

GridRelationship – класс, организующий отношение между агентами.

Предоставляет возможность сопоставления агенту места, определения всех соседних агентов и является ли определённая пара агентов соседними.

Опишем в общем процесс создания модели (позже будут рассмотрены конкретные примеры). Во-первых, необходимо задать систему, определив свои классы МАС и агента, наследованные от базовых. Во-вторых, определить визуализацию МАС для того или иного состояния. В-третьих, воспользоваться тем или иным приёмом для вызова основной панели (библиотека предоставляет 3 возможных способа: окно, апплет, внедрение панели в сторонний интерфейс). Рассмотрим составные части основной панели, представленные на Рис. 6.

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

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

Секция 3 содержит основные средства управления процессом работы системы и является общей для всех систем, пользователь может лишь изменить частоту обновления информации на ней. Кнопка Refresh инициирует сброс и создание новой системы. Кнопка Play/Pause инициирует запуск/приостановку работы системы. Панели t и h выводят текущие номер шага и значение характеристической функции.График изображает изменение характеристической функции в зависимости от номера шага. Для подробного изучения работы системы можно сохранить значенияхарактеристической функции с помощью кнопки Save.

Библиотеку и примеры реализованных с её помощью систем можно найти на интернет-странице http://navizv.github.io/MASwarm/.

Модель Шеллинга. В качестве первого примера реализации МАС с роевым интеллектом была выбрана модель Шеллинга в интерпретации Ж.Чжанга (описанная в приложении).

Поскольку средой в данной системе является доска, на которой расставлены фишки-агенты, было принято решение использовать введённые в библиотеку классы, отражающие такое устройство среды (GridPanel и GridRelationship). Зависимость между агентами на каждом шаге, к сожалению, не позволяет использовать параллелизм и связанные с ним классы библиотеки при реализации модели.

У агента были заведены поля для хранения цвета агента и параметров функции полезности (Z и M). Хотя в начальной реализации функция полезности у всех агентов одинакова, их поведение при различных предпочтениях, различной функции полезности, представляет несомненный интерес. Также у класса агентов были заведены методы для вычисления количества «чужих» соседей и текущего значения функции полезности.

Для класса моделей необходимо было определить 4 метода:

конструктор, функция выбора агентов для каждого шага, вычисление функции перехода G и характеристической функции h. Конструктор просто создаёт агентов по числу клеток и расставляет их Парето-оптимальным способом (в шахматном порядке). Функция выбора агентов заключается просто в выборе пары не соседних агентов. Вычисление характеристической функции заключается в делении пополам суммы количества «чужих» соседей у каждого агента.

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

Кроме этого в классе модели определяется способ её визуализации.

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

Все эти действия определяют модель Шеллинга. Остаётся лишь ввести главный класс (или класс апплета), который будет инициировать визуальное представление модели. Пример процесса моделирования представлен на Рис.

7. Это начальное состояние модели.

Созданный с помощью библиотеки апплет можно увидеть на интернетстранице http://navizv.github.io/MASwarm/schelling.html.

Генетический алгоритм. Нахождение покрывающего кода.

Покажем, что с помощью нашей платформы можно легко создавать не только модели, но и системы, реализующие эвристические алгоритмы решения сложных задач. В качестве алгоритма выберем генетический алгоритм (ГА), а в качестве задачи – задачу нахождения оптимального покрывающего кода из [12].

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

B n {0,1}n - n-мерный куб. R – радиус шаров.

шаров (искомый набор), где d H ( x, y ) - расстояние Хемминга между точками.

Общая формула для нахождения такого числа пока что отсутствует, и может быть вообще не найдена. Некоторые наборы и их мощности найдены теоретически, некоторые практически. На Табл. 2 представлены значения для различных n и R, взятые из [12]. Границы, помеченные звёздочкой, получены с помощью эвристических алгоритмов. Для целого ряда значений характеристик существуют лишь оценочные предположения о покрывающих наборах шаров и их мощности (их текущее состояние можно найти, например, в [48]). Всё это делает рассматриваемую задачу превосходным примером для использования эвристических алгоритмов.

Она может быть представлена как задача минимизации функции [12] Её значение равно количеству непокрытых шарами точек, где C – рассматриваемый набор шаров. Перейдём к терминам генетического алгоритма. Одной отдельной особью будем считать набор шаров. Количество шаров считаем заданным изначально. Геномом особи будем считать выписанные подряд двоичные представления центров составляющих их шаров. Поскольку нас интересует не максимум, а минимум функции, видоизменим её соответствующим образом (например, возьмём обратную).

Итак, осталось лишь реализовать алгоритм с помощью нашей платформы. Поскольку агенты могут действовать независимо (вычислять реализующие параллелизм классы ParAgent и ParSwarm.

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

Затем был введён класс агента. Каждый агент имеет поле, содержащее соответствующий ему набор шаров (объект Code). Осталось определить для агента функцию f – она равна количеству точек, не покрываемых данным набором шаров.

Теперь определим класс, соответствующий МАС («рой»). Для него необходимо определить 4 метода: конструктор, функция выбора агентов для каждого шага, вычисление модифицированной функции перехода G’ и характеристической функции h. Конструктор генерирует набор случайных особей. Функция выбора агентов возвращает всех агентов, так как в естественном отборе участвуют все особи (в принципе, это может быть изменено). Характеристическая функция возвращает минимальное значение функции f среди особей текущего поколения.

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

Осталось также определить визуализацию текущего состояния модели.