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

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

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

ЧИРКУНОВ Кирилл Сергеевич

МНОГОАГЕНТНОЕ МОДЕЛИРОВАНИЕ ПОВЕДЕНИЯ ИЕРАРХИЧЕСКИХ СИСТЕМ ЭКОНОМИЧЕСКОГО ХАРАКТЕРА

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

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

г о н:он гоїз

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

005062068

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

Научные руководители: Мурзин Федор Александрович,

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

Официальные оппоненты: Алгазин Геннадий Иванович,

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

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

РАН (ИПУ РАН).

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

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

Автореферат разослан 24 мая 2013 г.

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

к. т. н., доц. 7--Бунцев И. А.

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

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

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

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

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

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

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

Тарасов В. Б. в работе (Тарасов В. Б., 1998 [1]) говорит об агенте следующее: «элемент системы ... может пониматься как метаобъ-

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

Сама идея многоагентности подразумевает, что агенты могут действовать совместно для решения поставленных задач. Если у агента недостаточно знаний или специальных навыков для выполнения задачи, он может отправить запрос на её выполнение тем агентам, которые, по его мнению, вполне в состоянии с ней справиться. Также агенты могут кооперироваться для решения одной сложной задачи и составлять совместные планы действий с учетом намерений и возможностей друг друга (Городецкий В. И., Грушин-ский М.С., Хабалов A.B. [2]).

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

На базе обзора, выполненного Городецким В. И. и др. (Городецкий В.И., Грушинский М.С., Хабалов A.B. [2]) с некоторой долей условности можно разделить все исследования в области много-агентных систем на несколько основных направлений:

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

• Языки программирования, в число которых входят как универсальные языки программирования (Java, С#, С++), языки сценариев (Tcl/Tk), символьные языки и языки логического программирования (Oz), так и более близкие агентному подходу языки, "ориентированные на знания": языки представления знаний (KIF), языки переговоров и обмена знаниями (KQML, AgentSpeak, April), языки спецификаций агентов и др. (Telescript).

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

• Методы организации и кооперации агентов.

Рассматриваются вопросы о том, каким образом агенты могут

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

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

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

Инструментальные средства и среды разработки; это направление целиком посвящено вопросам создания инструментальных вспомогательных средств, облегчающих проектирование и реализацию агентов, и интегрированных сред разработки прикладных агентных систем (на сегодняшний день существует довольно много таких сред - JADE (X), ABLE, RePast (S), Agent Globe, но рано говорить о наиболее популярной и удобной платформе, подходящей для большинства задач).

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

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

В 1999 году была основана одна из наиболее известных в России компаний, занимающаяся построением прикладных мультиа-гентных систем — Magenta Technology, одним из руководителей которой является Скобелев Петр Олегович (доктор технических наук, профессор кафедры «Инженерия знаний» Поволжского Государственного университета телекоммуникаций и информатики, ведущий научный сотрудник Института проблем управления сложными системами РАН). В своей диссертации «Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений» в 2003 году он предложил использовать ПВ-сети ( «Потребности» - «Возможности», Иващенко А. В., Лада А. Н., Симонова Е.В., Скобелев П. О., 2011 [3]), которые нашли отражение в прикладных системах компании: логистическая система (танкеры, курьеры, такси, грузовики) с распределением заказов в реальном времени, система динамического планирования полетов, управление загрузкой производственных станков машиностроительного комплекса и др. Также в реализации проектов участвовали профессор Г. А. Ржевский (Открытый университет, Лондон) и профессор В. А. Виттих (ИПУСС СО РАН, Самара).

В работе (MacKie-Mason J.K., WellmanM.P., 2006 [4]) описано применение агентов для автоматизации процедур выбора товара на Интернет-рынке, торговли и совершения покупок. Агенты, представляя интересы своего владельца, обладают довольно сложным организационным поведением: могут договариваться с друг другом и координировать использование разделяемые ресурсы, вступать в группы, коалиции, менять стратегию в зависимости от типа задачи и пр. Это один из примеров применения агентов в экономике. Но также агенты используются для решения более масштабных задач.

Распад СССР поставил перед экономистами бывшей советской школы ряд совершенно новых задач. Раньше в ЦЭМИ успешно применялись методики расчета плана развития народного хозяйства «сверху-вниз». Однако когда значительная часть государственного имущества перешла в частные руки, такая методика перестала быть

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

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

Цель работы

— Проведение исследований, связанных с применимостью многоагентного подхода к моделированию сложных иерархических систем экономической природы;

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

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

— разработка способов оценки будущего состояния много-агентной среды, являющегося отражением состояния сложной иерархической системы экономической природы;

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

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

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

• Методы агентного моделирования, позволяющие формально описывать и программно имитировать поведение сообществ интеллектуальных агентов.

• Методы теории теории игр (принцип минимакса, игры с ненулевой суммой, принцип Парето).

• Формальные методы доказательства корректности (тотальной корректности, соответствия спецификации).

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

• В работе использовались также: нейронные сети, обучающиеся с учителем (алгоритм обратного распространения ошибки), Марковские цепи и корреляционный анализ.

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

В настоящее время с помощью мультиагентного подхода достаточно хорошо изучены вопросы, связанные с деятельностью в доменах, ориентированных на стоимость и на задачи (Дж.Розеншейн и Дж. Злоткин, 1994 [5]). Однако крайне скудно рассмотрены аспекты работы в смешанных доменах. Автор в работе развил концепции доменов переговоров, ориентированных на проекты.

Введенные концепции позволяют:

• производить согласованный выбор проектов, с учетом интересов агентов-участников;

• предсказывать изменения агентной среды.

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

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

1. Создана формальная агентная модель иерархической территориальной системы.

2. Формально описан домен переговоров, ориентированных на проекты;

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

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

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

Результаты, полученные при моделировании хода выполнения проекта «БЭМО» (Богучанское энерго-металлургическое объединение) вызвали также определенный интерес в компании «РУСАЛ».

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

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

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

Публикации

По теме диссертации автором опубликовано 14 работ, из них 4 статьи опубликованы в журналах из списка ВАК, 8 работ - в трудах и материалах международных конференций, 2 работы - в иных изданиях.

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

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

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

Диссертация состоит из оглавления, введения, заключения и 4 глав. Объем — 122 страницы. Работа содержит 16 рисунков, 21 таблицу, 2 листинга программ. Общее число использованных источников: 87.

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

Во введении обосновывается актуальность темы исследований и приводится краткое содержание работы.

В первой главе рассматриваются основные принципы агент-ного подхода, определяются понятия «агент» и «среда», их типы и разновидности. Приводится пример удачной формализации мно-гоагентной системы, предложенной Майклом Вулдриджем в книге «Introduction to MultiAgent approach».

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

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

Отдельно выделяют характеристики интеллектуальных агентов (в некоторых работах — интеллектуальных в слабом смысле):

1) реактивность (способность своевременно реагировать на воспринятые изменения среды);

2) проективность (проявление инициативы для достижения своих целей);

3) сог^альные навыки (способность к взаимодействию с другими агентами «ради дела»).

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

Популяция взаимодействующих агентов совместно со средой образует многоагентную систему (МАС).

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

Задачи, с которыми имеет дело агент, условно можно разделить на два класса:

1) задачи достижения состояния;

2) задачи поддержания состояния.

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

Джефри Розеншейн и Гилад Злоткин сделали важный вклад в разработку теоретических основ переговоров между агентами. Они разделили все множество переговоров на два типа: переговоры, ориентированные на выполнение задач; и переговоры, связанные с распределением материальных благ.

В работе выделяется еще один тип переговоров - переговоры, ориентированные на совместную реализацию (выбор) проекта или группы проектов.

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

Такая область характеризуется следующим:

- конфликтность достижения целей при вынужденном сотрудничестве;

- различная оценка привлекательности проекта с точки зрения каждого из участников;

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

Одна из наиболее известных и комплексных работ, посвященных описанию когнитивной деятельности агента в терминах логики, была написана П. Р. Коэном и Г.Дж. Левескью в 1990 г. [6].

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

Таблица 1

Типы модальности

Оператор Описание

(Ве11 ф) Агент / считает факт ф истинным

(Соа1/ ф) Агент / имеет цель ф

(НаррепБ а) Действие а случится в следующий момент времени

(Бопе «) Действие а только что произошло

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

(1) Распознавание побудительной силы высказывания является необязательным.

(2) Побудительные речевые акты являются комплексными типами событий и не являются примитивными.

Вторая глава посвящена построению новой децентрализованной и многоагентной модели согласованного развития экономических районов.

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

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

Каждый экономический район может иметь несколько возможных наборов собственных специализаций:

{ /т,\' • • • > /т,п)т } ' {}

(1)

где /тп -производственная специализация с индексом для набора с номером т. Тогда все множество сделок А описывается декартовым произведением множеств возможных наборов собственных специализаций экономических районов ег е ЕЯ0:

А -

{./и'-"'Аи, )

{/2,1 > Л,л . I У2,1

и пи ,1' "* > ^ т, ,п ■ I

г у-М ^|£Л| 1 1.71,1 '"->71 ,„ / у1,1

I Г№\ ЛЕВ\ 1 1У2.1 I

у2,1

< АЕЯ\ ЛЕВ.

}

(2)

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

специализаций для района и размеры предлагаемого набора специализаций невелики: 3 и 2 соответственно. Также мы учитываем то, что состав специализаций района может иметь переменную длину от 0 до 2 (т.е. множество предложений может содержать пустое множество). Однако полное число возможных специализаций для территориальной системы может быть и больше.

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

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

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

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

Определение. Территориально-производственный комплекс (ТПК) - совокупность расположенных рядом друг с другом взаимосвязанных производств (Колосовский H.H.).

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

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

Формула оценки проекта (функция полезности) для агента «Государство» имеет вид взвешенной суммы нормированных значений критериев Сц, помноженных на удельные весар:

а - Рсв СВ, N + Рс„ ' CPV, N + Рс„ ' СВТ, N + Рсвс ' СВС, N + Pcs ' CS. N>

(3)

где св - величина денежных поступлений в бюджет;

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

Свс— объем затрат на строительство дорог и производственных

сооружений; cs - объем заработной платы рабочих.

Веса же имеют следующие значения (полученные с помощью ранжирования по важности):

Рсв =0.25, рСвт =0.2, рСвс =0.15, pCs =0.1, сумма

которых равна 1.

Оценка проекта (функция полезности) для агента «Государство» а е[0,1].

Формально оценка проекта (функция полезности) для агента «Инвестор» записывается так:

ß=Pc,-CI.N + Pct-Ct,n + Pcr-Cr,n + Pcrr-Crr,n> (4)

где cN — нормированная величина критерия и ß е [0,1].

Чем больше проект сулит итоговой чистой прибыли, тем он более предпочтителен для агента «Инвестор» при прочих равных условиях. Это критерий с,. Также критериями выступают сроки окупаемости проекта, коэффициент рентабельности, внутренняя ставка доходности проекта. Обозначим их соответственно cT,cR,... Значения критериев нормируются по формуле:

х - min

XN=--. (5)

max - min

Заинтересованность государства в проекте выражается как:

in, = а, + 1, (6)

а заинтересованность инвестора:

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

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

Утверждение: Если алгоритм (протокол) поэтапного компромисса возвращает решение, то оно является индивидуально-рациональным.

Утверждение: Алгоритм (протокол) поэтапного компромисса завершается.

Теорема: Алгоритм (протокол) поэтапного компромисса строит Парето-оптимальное решение.

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

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

ционными свойствами. В конце главы описывается созданная автором программная оснастка модулей аМоБе (объем кода — 1,5 МБ) для качественного моделирования процесса реализации проекта БЭМО и специфицируется формат хранения данных о постановке исходной задачи моделирования.

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

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

• На основе многоагентного подхода предложены: алгоритм (протокол) согласованного выбора проектов (алгоритм поэтапного компромисса) при заданных критериях оценок проекта для различных участников; доказана теорема о Парето-оптимальности итогового решения (проекта).

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

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

• Разработан программный комплекс аМо8е для планирования и моделирования хода выполнения государственно-частных проектов с участием ТНК.

Цитируемая литература

1. Тарасов В. Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте // Новости искусственного интеллекта — 1998-№2.

2. Городецкий В.И., Грушинский М.С., Хабалов А. В. Многоагентные системы (обзор) // Новости искусственного интеллекта — 1998 —№ 2 — С. 64-116.

3. Иващенко А.В., Лада А. Н., Симонова Е. В., Скобелев П. О. Мультиагентная технология управления мобильными ресурсами, — Поволжский государственный университет телекоммуникаций и информатики. Самара, 2011. — 177 с.

4. MacKie-Mason J.K., Wellman М. P. Automated Markets and Trading Agents // Handbook of computational economics. — Volume 2, North-Holland. - 2006.

5. Rosenschein J.S., ZIotkin G. Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT Press, Cambridge, MA, 1994.

6. Cohen P. R., Levesque H.J. Intention is choice with commitment. Artificial Intelligence, 42- 1990.-pp. 213-261.

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

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

1. Кадников В.Е., Лескин О. В., Чиркунов К. С. Имитационное моделирование логистических цепочек на примере задачи доставки продукции Богучанского алюминиевого завода на китайский рынок //Лизинг,-2011,-№ 10.

2. Чиркунов К. С. Агентное моделирование развития территориальной системы // Информатика и ее применения — 2011 — Т. 5 — Вып. 1.-С. 58-64.

3. Чиркунов К.С. Совокупность инвестиционных проектов: экономическое обоснование // Проблемы теории и практики управления.-2011-№ 10.

4. Чиркунов К. С. Агентный протокол переговоров государства и частного сектора на примере задачи выбора концессионного транспортного проекта // В мире научных открытий — 2011 — № 8 (20)-С. 118-129.

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

5. Есикова Т.Н., Чиркунов К. С. Разработка агентной модели «Оценка реализуемости программ формирования и развития ИПТЗ (на примере Нижнего Приангарья — проект БЭМО) » // "Управление развитием крупномасштабных систем" (МЬ80'2011): Материалы Пятой междунар. конф — М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2011.

6. Кадников В.Е., Лескин О. В., Чиркунов К. С. Доставка продукции Богучанского алюминиевого завода на китайский рынок как задача имитационного моделирования // Имитационное моделирование: Теория и практика" (ИММОД'2011): Сборник докладов конференции, Санкт-Петербург, 2011.

7. Кадников В.Е., Лескин О. В., Чиркунов К. С. Имитационное моделирование логистических цепочек на примере задачи доставки продукции Богучанского алюминиевого завода на китайский рынок // Прикладная логистика — 2011.— № 10.

8. Чиркунов К. С. Разработка ПО для деловой игры «Концессии в крупных транспортных проектах» // Материалы Х1ЛУ Международной научной студенческой конференции «Студент и научно-

технический прогресс»: Информационные технологии / Новосиб. гос. университет. Новосибирск, 2006-С. 100-101.

9. Чиркунов К. С. Агентный протокол переговоров государства и частного сектора на примере задачи выбора концессионного транспортного проекта // Управление развитием крупномасштабных систем (MLSD'2010): Материалы Четвертой междунар. конф.— М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2010.

10. Чиркунов К. С. Компьютерная деловая игра «Концессия: способ реализации крупных транспортных проектов» // Материалы XLV Международной научной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии / Новосиб. гос. университет-Новосибирск, 2007-С. 152-153.

11. Чиркунов К. С. Компьютерное моделирование реализации транспортных проектов федерального уровня // Управление развитием крупномасштабных систем (MLSD'2009): Материалы Третьей междунар. конф. (5—7 окт. 2009 г., Москва, Россия).—М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2009 - Т. 2 - С. 182-184.

12. Чиркунов К. С. Моделирование развития территориальной системы на базе агентного подхода: основные понятия // Управление развитием крупномасштабных систем (MLSD'2010): Труды Четвертой междунар. конф — М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2010.

13. Чиркунов К.С. Моделирование развития территориальной системы при низком уровне общих расходов на базе агентного подхода // Управление развитием крупномасштабных систем (MLSD'2010): Материалы Четвертой междунар. конф- М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2010.

14. Чиркунов К. С. Разработка инструментария для прогнозирования мирового спроса с использованием аппарата нейронных сетей и марковских процессов (на примере алюминия). // "Управление развитием крупномасштабных систем" (MLSD'2011): Материалы Пятой междунар. конф—М.: Ин-т проблем управления им. В. А. Трапезникова РАН, 2011.

ЧИРКУНОВ Кирилл Сергеевич

МНОГОАГЕНТНОЕ МОДЕЛИРОВАНИЕ ПОВЕДЕНИЯ ИЕРАРХИЧЕСКИХ СИСТЕМ ЭКОНОМИЧЕСКОГО ХАРАКТЕРА

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

системах

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

Компьютерная вёрстка Т. А. Измайлова

Подписано в печать 23.05.2013. Объем 1 уч.-изд. л. Формат бумаги 60 х 84 Ч16. Тираж 120 экз.

Отпечатано в ИЦ СибГУТИ 630128, г. Новосибирск, ул. Кирова, д. 86. Заказ № 50

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

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

0420135^628

ЧИРКУНОВ КИРИЛЛ СЕРГЕЕВИЧ

МНОГОАГЕНТНОЕ МОДЕЛИРОВАНИЕ ПОВЕДЕНИЯ ИЕРАРХИЧЕСКИХ СИСТЕМ ЭКОНОМИЧЕСКОГО

ХАРАКТЕРА

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

системах

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

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

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

Мурзин Ф.А.

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

ОГЛАВЛЕНИЕ

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

ГЛАВА 1.АГЕНТНЫЙ ПОДХОД КАК НОВАЯ ПАРАДИГМА МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ................................................................................................................21

1.1. Агенты и среды.................................................................................................................21

1.2. Основные термины и понятия агентного подхода. Формальная модель Вулдриджа23

1.3. Функция пользы................................................................................................................27

1.4. Проблемные среды...........................................................................................................32

1.5. Взаимодействие агентов..................................................................................................34

1.6. Переговоры и достижение соглашений..........................................................................36

1.7. Интенциональная логика Коэна - Левескью.................................................................44

1.8. Выводы..............................................................................................................................49

ГЛАВА 2. РАЗВИВАЮЩАЯСЯ ТЕРРИТОРИАЛЬНАЯ СИСТЕМА ЭКОНОМИЧЕСКИХ РАЙОНОВ....................................................................................................................................50

2.1. Территориальная система как совокупность агентов ЕР..............................................51

2.2. Математическое и алгоритмическое описание задачи развития территориальной системы.....................................................................................................................................54

2.3. Переговоры о специализации..........................................................................................55

2.4. Функции развития и алгоритм выбора специализаций района....................................62

2.5. Отыскание необходимых ресурсов для развития..........................................................64

2.6. Выводы..............................................................................................................................65

ГЛАВА 3. АГЕНТНЫЙ ПРОТОКОЛ ПЕРЕГОВОРОВ ГОСУДАРСТВА И ЧАСТНОГО

СЕКТОРА НА ПРИМЕРЕ ЗАДАЧИ ВЫБОРА СОВМЕСТНОГО ПРОЕКТА.....................67

3.1. Основные сведения о задаче............................................................................................68

3.2. Описание алгоритмов переговоров между частным инвестором и представителем государственной власти..........................................................................................................69

3.3. Машинная реализация......................................................................................................78

3.4. Выводы..............................................................................................................................82

ГЛАВА 4. РАЗРАБОТКА МОДЕЛИ ДЛЯ ОЦЕНКИ РАЗВИТИЯ ТЕРРИТОРИАЛЬНЫХ

СИСТЕМ НА ПРИНЦИПАХ ГОСУДАРСТВЕННО-ЧАСТНОГО ПАРТНЕРСТВА

(ПРОЕКТ «БЭМО») НА БАЗЕ АГЕНТОВ..............................................................................84

4.1 Построение прогнозов для будущего состояния среды.................................................85

4.2. аМоБе - программный инструментарий для интерактивного описания проектных ситуаций.................................................................................................................................104

4.3. Формат описания проектов аМоБе...............................................................................107

4.4. Выводы............................................................................................................................111

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ................................................................................................115

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

ВВЕДЕНИЕ

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

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

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

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

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

Тарасов В.Б. в работе [45] говорит об агенте следующее: «элемент системы ... может пониматься как метаобъект, наделенный некоторой долей субъектности...». Это значит, что такой метаобъект способен самостоятельно действовать в некоторой среде и манипулировать другими объектами (в том числе влиять на из жизненный цикл), принимать на вход сенсорную информацию об окружающей обстановке и, при необходимости, устанавливать коммуникации с себе подобными. Теория агентов использует существующий аппарат объектно-ориентированного подхода, но при этом стоит на более высоком уровне сложности.

Сама идея многоагентности подразумевает, что агенты могут действовать совместно для решения поставленных задач. Если у агента недостаточно знаний или специальных навыков для выполнения задачи, он может отправить запрос на её выполнение тем агентам, которые, по его мнению, вполне в состоянии с ней справиться. Также агенты могут кооперироваться для решения одной сложной задачи и составлять совместные планы действий с учетом намерений и возможностей друг друга (Городецкий В.И., Грушинский М.С., Хабалов A.B., 1998 [12]).

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

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

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

На базе обзора, выполненного Городецким В.И. и др. [12] с некоторой долей условности можно разделить все исследования в области многоагентных систем на несколько основных направлений (см. рис.1).

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

• Языки программирования, в число которых входят как универсальные языки программирования (Java, С#, С++), языки сценариев (Tcl/Tk), символьные языки и языки логического программирования (Oz), так и более близкие агентному подходу языки, "ориентированные на знания": языки представления знаний (KIF), языки переговоров и обмена знаниями (KQML, AgentSpeak, April), языки спецификаций агентов и др. (Telescript).

• Мобильные агенты. Свое название эти сущности получили из-за способности передавать свой исполняемый код на расстояния. Такие

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

• Методы организации и кооперации агентов.

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

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

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

Инструментальные средства и среды разработки; это направление целиком посвящено вопросам создания инструментальных вспомогательных средств, облегчающих проектирование и реализацию агентов, и интегрированных сред разработки прикладных агентных систем (на сегодняшний день существует довольно много таких сред - JADE (X), ABLE, RePast (S), Agent Globe, но рано говорить о наиболее популярной и удобной платформе, подходящей для большинства задач).

В настоящее время агентно-ориентированный подход оказался востребован в таких областях, как имитационное моделирование экономических систем и электронная торговля (где в качестве самозаинтересованного агента выступает субъект экономических отношений

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

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

- Magenta Technology, одним из руководителей которой является Скобелев Петр Олегович (доктор технических наук, профессор кафедры «Инженерия знаний» Поволжского Государственного университета телекоммуникаций и информатики, ведущий научный сотрудник Института проблем управления сложными системами РАН). В своей диссертации «Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений» в 2003 году он предложил использовать ПВ-сети ( «Потребности» - «Возможности» [19]), которые нашли отражение в прикладных системах компании: логистическая система (танкеры, курьеры, такси, грузовики) с распределением заказов в реальном времени, система динамического планирования полетов, управление загрузкой производственных станков машиностроительного комплекса и др. Также в реализации проектов участвовали профессор Г.А.Ржевский (Открытый университет, Лондон) и профессор В.А.Виттих (ИПУСС СО РАН, Самара).

В работе [61] описано применение агентов для автоматизации процедур выбора товара на Интернет-рынке, торговли и совершения покупок. Агенты, представляя интересы своего владельца, обладают довольно сложным организационным поведением: могут договариваться с друг другом и координировать использование разделяемые ресурсы, вступать в группы, коалиции, менять стратегию в зависимости от типа задачи и пр.

Это один из примеров применения агентов в экономике. Но также агенты

используются для решения более масштабных задач.

Распад СССР поставил перед экономистами бывшей советской школы

ряд совершенно новых задач. Раньше в ЦЭМИ успешно применялись

методики расчета плана развития народного хозяйства «сверху-вниз».

Однако когда значительная часть государственного имущества перешла в

частные руки, такая методика перестала быть эффективной. Потребовалась

разработка совершенно нового класса моделей, которые бы отражали

рыночный характер экономики, ее децентрализованность. Все чаще стало

упоминаться экономико-математическое моделирование в терминах

«экономических агентов», т.е. самозаинтересованных активных участников

экономических отношений. Экономическими агентами могут выступать

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

В это же время в мире активно развивалась парадигма агентного

моделирования, которая наделяет объекты такими чертами, как

«активность», «целеустремленность», «коммуникативные навыки».

На сегодняшний день многоагентное моделирование кажется уже

достаточно изученной дисциплиной. Тем не менее в ней существуют «белые

пятна», которые заполняются по мере решения практических задач.

Совершенствуются алгоритмы переговоров между агентами, усложняются

алгоритмы планирования последовательности действий для достижения

целей, вводятся новые типы агентов.

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

проведение исследований, связанных с применимостью

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

экономической природы;

- создание и апробирование методик многоагентного подхода,

основанных на проектной деятельности, с целью развития аппарата

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

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

8

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

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

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

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

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

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

Актуальность использования и развития этого инструментария для исследования и прогнозирования иерархических систем обусловливается следующим

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

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

• адаптации системы к изменению поведения отдельных агентов зависит от своевременно прогнозирования последствий от всего многообразия принимаемых в ней решений;

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

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

Джефри Розеншейн и Гил ад Злоткин в 1994 г. предложили использовать две основные разновидности агентных доменов, которые получили дальнейшее развитие - домен, ориентированный на задачи, и домен, ор