автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Многоагентные системы в моделировании социально-экономических отношений

Федеральное агентство связи Сибирский Государственный Университет Телекоммуникаций и Информатики

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

УДК 004.048/.421/.89; 330.322.7; 51-77

Зайцев Иван Дмитриевич

МНОГОАГЕНТНЫЕ СИСТЕМЫ В МОДЕЛИРОВАНИИ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ОТНОШЕНИЙ: ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ И ВЕРИФИКАЦИЯ СВОЙСТВ С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА

Специальность 05.13.10 - Управление в социальных и экономических

системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

005549359

Новосибирск 2014

п МАП

005549359

Работа выполнена в Институте систем информатики им. А.П. Ершова Сибирского отделения РАН

Научные руководители:

Мурзин Федор Александрович, кандидат физико-математических наук, зам. директора ИСИ СО РАН.

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

Официальные оппоненты:

Алгазин Геннадий Иванович, доктор физико-математических наук, профессор, зав. каф. ММСН АлтГУ.

Слуев Владимир Александрович, кандидат технических наук, научный сотрудник ИАиЭ СО РАН.

Ведущая организация:

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН).

Защита состоится «20» июня 2014 года в 15:00 часов на заседании диссертационного совета Д 219.005.03 в Сибирском государственном университете телекоммуникаций и информатики (СибГУТИ) по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

С диссертацией можно ознакомиться в читальном зале библиотеки СибГУТИ (г. Новосибирск, ул.Кирова, 86).

Автореферат разослан « »_2014 г

Ученый секретарь диссертационного совета

к.т.н., доц.

Бунцев И.А.

Общая характеристика работы

Актуальность работы

Многоагентные системы (MAC) в последнее время являются одной из важных и перспективных областей развития информационных и коммуникационных технологий. Это обусловлено всё возрастающей сложностью, пространственной распределенностью современных информационных систем, организаций, исследуемых объектов. Агентный подход находит применение всюду, где монолитное, строго иерархическое представление сталкивается с теми или иными проблемами. Например, всё более актуальным становится построение многоагентных ERP-систем для управления распределёнными производственными процессами (например, в области логистики примечательны работы Самарской научной школы мультиагентных систем, П.О. Скобелева, Г.А. Ржевского). Применяются MAC и при решении задач искусственного интеллекта (ИИ), поскольку позволяют разделить большую проблему на составные части и решить её, используя коллективный интеллект.

В экономическом моделировании ранее преобладало оптимизационное моделирование, предполагавшее жёсткое подчинение отдельных экономических субъектов общей воле, выраженной неким центром, но сейчас всё большее распространение получают децентрализованные модели, учитывающие разнонаправленность интересов экономических субъектов и эгоистичность их поведения. Это связано как с процессами либерализации экономики ряда стран, так и децентрализацией международных связей, распадом системы двух противоборствующих блоков. Построению MAC в описанных областях посвящены работы А.Б. Шабунина, H.A. Кузнецова, П.О. Скобелева, В. А. Виттиха, Katia Sycara, Uri Wilensky, Petter Holme, Andreas Grönlund.

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

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

результаты её работы. Теоретические исследования MAC, их семейств, отдельных систем представлены в работах П.Р.Коэна, Г.Дж.Левескью, В.Б. Тарасова, М.К. Валиева, М.И. Дехтяря, А.Я. Диковского, Nikos Vlassis, Junfu Zhang.

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

Цель работы.

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

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

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

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

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

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

сети, а также для анализа, визуализации и публикации результатов моделирования.

Методы исследования

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

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

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

Научная новизна

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

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

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

Основные результаты, выносимые на защиту.

1. Математическая модель поведения семейства MAC с роевым интеллектом, основанная на цепях Маркова.

2. Утверждение о взаимосвязи стационарного распределения цепи Маркова со значением характеристической функции системы.

3. Точное выражение и приближённые оценки распределения вероятности значений характеристической функции системы.

4. Альтернативные доказательства свойств различных мультиагентных моделей социально-экономических отношений и оптимизационных алгоритмов.

5. Агентная платформа, воплощающая выведенную вычислительную модель поведения MAC и предоставляющая средства для их построения и исследования.

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

Практическая значимость

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

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

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

Апробация работы

Основные результаты работы докладывались автором на ряде конференций: Международная научная конференция «Управление развитием крупномасштабных систем» (г. Москва, 2010 г., 2011 г., 2013 г.); Международная научная студенческая конференция «Студент и научно-технический прогресс» (г. Новосибирск, 2009 г., 2013 г.); Всероссийская научная конференция «Россия 2030 глазами молодых ученых» (Москва, 2011 г., 2013 г.)

Публикации

По теме диссертации автором опубликовано 13 работ, из них 3 статьи опубликованы в журналах из списка ВАК, 10 работ — в трудах и материалах международных конференций. Получено свидетельство о государственной регистрации программы для ЭВМ.

Личный вклад автора

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

Структура и объем диссертации

Диссертация состоит из оглавления, введения, 3 глав, заключения и приложения. Объем - 142 страницы. Работа содержит 18 рисунков. Общее число использованных источников: 73.

Содержание работы

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

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

Модель Алгоритм

Движение атомов при охлаждении металла Алгоритм имитации отжига

Движение муравьев в колонии Муравьиный алгоритм (англ. ant colony optimization, АСО)

Приспособление генофонда популяции к условиям среды Генетический алгоритм

Социальное поведение Метод роя частиц

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

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

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

Проведено формальное описание рассматриваемого семейства с учётом поставленной задачи, формализован процесс работы MAC, введено понятие характеристической функции на её состояниях. h(X). Для задач оптимизации (конкретно, максимизации) её можно определить как h(XJ = max(f(x,j), ..., f(Xi,n)), где Xt = <xt,i, ..., Xi,„>. В общем виде работа заключается в пошаговом процессе смены состояний

Xi+i = GifXi),

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

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

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

При условии, что

3x0.M|V*:Pj£ ><5>0 существует для всех у и не зависит от начального состояния х предел ИтР% = МУ).

t—ю

Вектор называется стационарным распределением.

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

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

Рху = ГхуНу).

При этом выполняются следующие условия:

Гху > 0,гху = гух,

Л (у) > 0.

s

А для самой ЦМ выполняются условия эргодичности. Тогда стационарное распределение будет иметь вид

//(х) = kh(x)\ 1

гдек= --—-.

Zxes^W

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

Цсу 5 0,/^, = Гух, h(y) > 0. Определим граф окрестностей

G=<V,E>, где V=S а (%,у) € Е <=> Ф 0. Пусть на данном графе

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

Ух: limP£? = kh(y);k = const

Теорема 2 (оценка распределения вероятности характеристической функции). Пусть выполнены условия Теоремы 1, то есть ц(х) = kh(x). Также предположим, что нам дана оценочная функция #(р) < ВД = |{х|Л0с) > р}|.

Тогда для вероятности того, что характеристическая функция превзойдёт заранее данное значение р0, верна формула

оэ

Р(Л(х)>р0)>А,#(р0)+ f N(p)dp.

Ро

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

Далее описана созданная в ходе исследования агентная платформа — программная система, реализующая основные идеи работа и предоставляющая инструментарий для создания MAC рассмотренного семейства, средства управления процессом их работы и исследования их

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

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

Размер поля Кол-во агентов Время моделирования в секундах

NetLogo Jade наша платформа

10x10 100 10,9 0,8 0,6

14x14 196 14,9 0,9 0,8

20x20 400 28,7 1,8 1,4

30x30 900 61,9 4,5 3,3

40x40 1600 112,7 8 6,2

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

GridRefetionship GridPanet

*paintAgentQ

Рисунок 1. Диаграмма классов пакета МАБи'агт

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

ю

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

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

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

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

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

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

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

Рисунок 2

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

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

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

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

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

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

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

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

Основные результаты работы

1. Предложено семейство многоагентных систем, в которое входят важные модели, применяемые в естественных науках; эвристические оптимизационные алгоритмы такие, как: генетические алгоритмы и алгоритмы «роя частиц»; модели типа «хищник-жертва»; модели распространения вирусов и др. Показана связь систем данного семейства с Марковскими процессами, на основании которой доказаны утверждения, характеризующие поведение таких систем.

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

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

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

Мировой хозяйственной системы, анализа и визуализации исходных

статистических данных и полученных результатов.

Публикации по теме диссертации

Публикации в журналах, входящих в перечень ВАК

1. Зайцев И.Д. Верификация мультиагентных систем с помощью цепей Маркова: оценка вероятности нахождения агентами оптимального решения // Программные продукты и системы, Тверь — том 4, 2013 г., стр. 8993.

2. Унтура Г.А., Есикова Т.Н., Зайцев И.Д., Морошкина О.Н. Проблемы и инструменты аналитики инновационного развития субъектов РФ. // Вестник НГУ: серия социально-экономические науки, Новосибирск — 2014 г., Т.14 №1, С.81-100.

3. Зайцев И. Д. Вероятностная оценка результатов агентного моделирования на примере модели сегрегации Шеллинга. // Журнал "Проблемы управления", Москва-№2, 2014 г., стр. 39-43.

Прочие публикации

4. Есикова Т.Н., Зайцев И.Д. Разработка агентной модели «Оценка стратегических направлений опорной транспортной сети России при разной геоэкономической архитектонике Мировой Хозяйственной Системы» // Управление развитием крупномасштабных систем (MLSD'2010): Труды Четвертой международной конференции (4-6 октября 2010 г., Москва, Россия). Москва, 2010 - Том I. С. 107-114

5. Есикова Т.Н., Зайцев И.Д. Разработка инструментария «Агентная модель прогнозирования изменений геоэкономических позиций России» // Управление развитием крупномасштабных систем (MLSD'2010): Материалы Четвертой международной конференции (4-6 октября 2010 г., Москва, Россия), Москва 2010 - Т.П. С. 59-61

6. Зайцев И.Д. Опыт разработки прототипа агентной модели «оценка стратегических направлений опорной транспортной сети России» в среде NetLogo. // Управление развитием крупномасштабных систем (MLSD'2010): Материалы Четвертой международной конференции (4-6 октября 2010 г., Москва, Россия), Москва 2010 — Т. И. С. 62-64

7. Зайцев И.Д. Разработка агентной модели «Оценка востребованности направлений опорной транспортной сети России при разных геоэкономических условиях»: построение каркаса модели с помощью технологии Java. Тезисы. // Управление развитием крупномасштабных систем MLSD'2011: материалы Пятой международной конференции (3-5 окт. 2011 г., Москва, Россия) / общ. ред. С.Н. Васильев, А.Д. Цвиркун; Ин-т проблем управления им. В.А. Трапезникова РАН. - М., 2011. - Т. II (секции 4.2 - 8). - С. 49-50.

8. Зайцев И.Д. Построение модели развития международной транспортной сети с использованием агентного подхода // Россия 2030

глазами молодых ученых. Материалы II Всероссийской научной конференции (Москва, 2011 г.) Москва, Научный эксперт 2012, ч. 1 С. 301307

9. Зайцев И.Д. Агентные модели социально-экономических систем: вероятностная оценка поведения с помощью цепей Маркова. // Управление развитием крупномасштабных систем MLSD'2013: материалы Седьмой международной конференции (30 сент.-2 окт. 2013 г., Москва, Россия)! общ. ред. С.Н. Васильев, А.Д. Цвиркун; Ин-т проблем управления им. В.А. Трапезникова РАН. - М„ 2013. - Т. I (секции 1-3). - С. 378-379.

10. Зайцев И.Д. Разработка программного комплекса для хранения, обработки и визуализации данных региональной статистики. // Управление развитием крупномасштабных систем MLSD'2013: материалы Седьмой международной конференции (30 сент.-2 окт. 2013 г., Москва, Россия) / общ. ред. С.Н. Васильев, А.Д. Цвиркун; Ин-т проблем управления им. В.А. Трапезникова РАН. - М., 2013. - Т. II (секции 4-8). - С. 229-230.

11. Зайцев И.Д. Верификация мультиагентных систем с помощью цепей Маркова // Материалы LI международной научной студенческой конференции «Студент и научно-технический прогресс», Информационные технологии. Новосибирск, 2013, С. 143.

12. Зайцев И.Д. Разработка ПО для оценки требований к транспортной сети с помощью агентного моделирования // Материалы XLVII международной научной студенческой конференции «Студент и научно-технический прогресс», Информационные технологии. Новосибирск, 2009, С. 143.

13. Береснев А.Л., Бонко A.C., Зайцев И.Д. Разработка ПО «Оценка асимметрии регионального развития» // Материалы XLVI международной научной студенческой конференции «Студент и научно-технический прогресс», Информационные технологии. Новосибирск, 2008, С. 133-134.

Зайцев И.Д.

МНОГОАГЕНТНЫЕ СИСТЕМЫ В МОДЕЛИРОВАНИИ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ОТНОШЕНИЙ: ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ И ВЕРИФИКАЦИЯ СВОЙСТВ С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА

Автореферат

Подписано в печать Объем 1 уч.-изд. л.

Формат бумаги 60 х 90 1/16_Тираж 100 экз._

Отпечатано в ООО «Инкпрессо»

630128, г. Новосибирск, ул. Кутателадзе, 4г, 310., +7 (383) 330-72-02 Заказ № 139

Учреждение Российской академии наук Институт систем информатики им. А.П. Ершова Сибирского отделения РАН

04201458753

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

МНОГОАГЕНТНЫЕ СИСТЕМЫ В МОДЕЛИРОВАНИИ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ОТНОШЕНИЙ: ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ И ВЕРИФИКАЦИЯ СВОЙСТВ С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА

Специальность 05.13.10 — Управление в социальных и экономических

системах

Диссертация на соискание ученой степени кандидата технических наук

Научные руководители:

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

Мурзин Ф.А.

Новосибирск-2014

Оглавление

ВВЕДЕНИЕ...................................................................................................................................................3

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

1.1 основный термины и при! 1ципы построе11ия.......................................................................15

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

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

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

1.5 Аге1 1thoe моделирование. Системы с роевым интеллектом...........................................36

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

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

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

2.2 Нахождение эргодического распределения и анализ поведения MAC........................49

2.3 Описание специализированной агентной платформы MASwarm.................................55

2.4 Примеры использования агентной платформы MASwarm..............................................61

2.5 Сравнение с другими агентными платформами................................................................67

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

3.1 Постановка задачи..................................................................................................................71

3.2 Описание модели.....................................................................................................................74

3.3 Описание программного комплекса...................................................................................84

3.4 Программный комплекс для анализа и визуализации результатов моделирования.90

3.5 Моделирование развития Северного морского пути........................................................98

3.6 Моделирование развития Между! сродных Транспорт! 1ых коридоров Евразии.......106

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

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

1. Модель Шеллш 1га...................................................................................................................115

2. Игра с логлипейным правилом выбора стратегии игроками........................................123

3. Локальный поиск. Алгоритм имита1 щи отжига..............................................................129

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

ПРИЛОЖЕНИЕ 3. АКТ О ВНЕДРЕНИИ...........................................................................................133

ЛИТЕРАТУРА.........................................................................................................................................134

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модель

Алгоритм

Движение атомов при охлаждении металла Алгоритм имитации отжига

Движение Муравьёв в колонии Муравьиный алгоритм (англ. ant colony optimization, АСО)

Приспособление генофонда популяции к условиям среды Генетический алгоритм

Социальное поведение Метод роя частиц

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

MAC.

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

Проведено формальное описание рассматриваемого семейства с учётом поставленной задачи, формализован процесс работы MAC, введено понятие характеристической функции на её состояниях. h(X). Для задач оптимизации (конкретно, максимизации) её можно определить как h(Xi) = max(f(xu\), f(xiM)), где Xi = <Xjj, ..., x/,„>. В общем виде работа заключается в пошаговом процессе смены состояний

Xi+i = Gi(Xi),

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

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

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

При условии, что 3Ха,К8\Ух:Р™ > 6 > О существует для всех у и не зависит от начального состояния х предел limP® = fi(y).

t—tco J

Вектор fi(y} называется стационарным распределением.

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

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

Рху = Гхук^у).

При этом выполняются следующие условия: Г > О Г = г

Xу — I ху 1 ух>

h(y) > 0.

А для самой ЦМ выполняются условия эргодичности. Тогда стационарное распределение будет иметь вид

/¿(х) = kh(x);

1

гдек= --—

Lxes h(x)

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

ГхуЬ-(у),тДе Г"ху ? ®>Гху = Гух> h(y) > 0- Определим граф окрестностей

G=<V,E>, где V=S а (кх,у)ЕЕ&ГхуФ 0. Пусть на данном графе

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

Vx: limP,= fefr(y); к = const.

t—* oo

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

Также предположим, что нам дана оценочная функция N(p) < iV(p) = |{x|/l(x) > р}\.

Тогда для вероятности того, что характеристическая функция превзойдёт заранее данное значение pQ, верна формула

P(h(x) > Pq) > PqNQjq) + J N(p} dp.

Po

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

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

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

Размер поля Кол-во агентов Время моделирования в секундах

NetLogo Jade наша платформа

10x10 100 10,9 0,8 0,6

14x14 196 14,9 0,9 0,8

20x20 400 28,7 1,8 1,4

30x30 900 61,9 4,5 3,3

40x40 1600 112,7 8 6,2

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

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

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

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

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

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

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

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

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