На правах рукописи
Гасникова Евгения Владимировна
Моделирование динамики макросистем на
основе концепции равновесия
Специальность 05.13.18 - математическое моделирование,
численные методы и комплексы программ
Автореферат
диссертации на соискание учёной степени
кандидата физико-математических наук
Москва – 2012
Работа выполнена на кафедре анализа систем и решений Московского физико-технического института (государственного университета)
Научный руководитель: кандидат физико-математических наук, доцент Меньшиков Иван Станиславович
Официальные оппоненты: Доктор физико-математических наук, профессор Бекларян Лёва Андреевич, Центральный экономико-математический институт РАН, главный научный сотрудник кандидат физико-математических наук Швецов Владимир Иванович, Институт системного анализа РАН, ведущий научный сотрудник
Ведущая организация: Институт прикладной математики им. М.В. Келдыша РАН
Защита состоится декабря 2012 года в часов на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер., д. 9, ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета).
Автореферат разослан ноября 2012 г.
Ученый секретарь диссертационного совета Федько О.С.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Работы Е.Т. Джейнса, А. Дж. Вильсона, И. Пригожина, Г. Хакена положили начало традиции использования термодинамического формализма для анализа различных макросистем, встречающихся в экономике, биологии, социальной области и т.д. В России систематические исследования в этом направлении велись Л.Н. Розоноэром, а в последнее время В.П. Масловым, Ю.С. Попковым и другими исследователями. В большинстве работ рассматривались случаи стационарных макросистем, которые уже находятся в равновесии.
В диссертации предлагается в стационарных моделях учитывать динамику, с помощью которой можно оценивать скорость сходимости макросистемы к равновесию и исследовать зависимость равновесия от различных параметров.
Вводимая динамика позволяет как более точно отражать специфику исследуемых задач, так и расширить множество моделируемых постановок.
Большой класс макросистем основывается на эволюционной динамике, приводящей к равновесию, которое может быть проинтерпретировано как равновесие Нэша. Возможность предложить и исследовать разумную динамику для той или иной стационарной макросистемы в ряде случаев позволяет также эффективно определить равновесие этой макросистемы.
Целью диссертационной работы является исследование равновесия макросистем, обладающих марковской динамикой, в основе которой лежат принципы стохастической химической кинетики.
Для этого решаются следующие задачи:
отыскание достаточных условий существования и единственности равновесия;
разработка эффективных вычислительных алгоритмов поиска равновесий макросистем путем сведения к задачам энтропийно-линейного программирования, разработка соответствующего комплекса программ;
изучение наследования свойств динамической макросистемы при различных скейлингах (изменениях масштаба), в частности, исследование перестановочности предельных переходов по времени и размерности макросистемы;
изучение теоретико-игровых аспектов концепции равновесия динамических макросистем;
оценки скорости сходимости к равновесию и плотности концентрации инвариантной меры в равновесии;
анализ конкретных макросистем, рассматриваемых при математическом моделировании транспортных потоков; при ранжировании web-страниц; в экономических и социальных моделях.
Методы исследования. В работе используются: эргодические теоремы для марковских процессов, формула Стирлинга, метод Дарвина–Фаулера, современные варианты неравенства Чигера, понятие дискретной кривизны Риччи, второй метод Ляпунова, термодинамический формализм, аппарат производящих функций, метод внутренних штрафных функций, метод стохастического квазиградиентного спуска.
Научная новизна выносимых на защиту результатов состоит в том, что впервые:
получено достаточное условие, отличное от известного ранее условия унитарности, обеспечивающее существование и единственность равновесия макросистемы, порожденной марковской динамикой, в основе которой лежат принципы стохастической химической кинетики;
выявлен характер связи функции Ляпунова макросистемы с инвариантной мерой этой макросистемы;
показано, что при достаточно естественных условиях время сходимости к равновесию оказывается малым;
приведена эволюционная интерпретация конструкции равновесия Нэша– Вардропа, отвечающая равновесному распределению потоков на графе транспортной сети, до этого использовавшаяся только стационарно. Это позволило, в том числе, усилить парадокс Браесса (1968), а также объяснить эвристический способ отбора Бар-Гира–Швецова (2010) единственного равновесия Нэша–Вардропа в случае, когда имеет место неединственность Практическая ценность работы. Диссертационная работа, в основном, носит теоретический характер, хотя во многом мотивированна конкретными приложениями.
В диссертации в рамках макросистемного подхода предложена модель, обобщающая известную на практике энтропийную модель расчета матриц корреспонденций. Эта известная модель была использована для анализа данных по транспортным потокам г. Москвы. Предложенная в диссертации модель позволила более адекватно описать имеющиеся данные. Сейчас предложенная модель тестируется в Научно-исследовательском и проектном институте четырехстадийной транспортной модели.
Диссертация выполнялась при поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании, МФТИ, грант правительства РФ договор 11G34.31.0073, а также при поддержке грантов РФФИ 11-01-00494-а, мол_а_вед 12-01-33007.
Апробация и публикации. По материалам диссертации опубликовано печатных работ, в том числе, три – в изданиях, рекомендованных ВАК РФ [6, 12, 13].
Личный вклад соискателя в работы с соавторами состоит в доказательстве теорем о сходимости динамических макросистем к равновесию; исследовании ряда свойств равновесий макросистем (скорость сходимости, плотность концентрации инвариантной меры); исследовании макросистем, имеющих практическую ценность; систематизации ранее известных алгоритмов; разработке численных алгоритмов; разработке соответствующего комплекса программ.
Результаты работы докладывались, обсуждались и получили одобрение специалистов на 16 конференциях (в том числе, пяти международных), научных семинарах по экспериментальной экономике Вычислительного центра РАН (2009семинаре-конференции РАН под рук. акад. В.В. Козлова (2010), на семинарах кафедр математических основ управления и анализа систем и решений ФУПМ МФТИ (2009-2011), на семинарах по транспортным потокам в Независимом Московском Университете (2011-2012).
Структура диссертации. Диссертация состоит из введения, трёх глав, заключения, приложения и списка использованных источников, включающего 135 наименований. Общий объём работы составляет 90 страниц.
КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
Во введении сформулированы цели работы, обосновывается её актуальность, дан обзор работ, связанных с темой диссертации, приводятся основные результаты и их предпосылки.В первой главе подробно рассматривается используемое в диссертации понятие равновесия макросистемы, приводятся известные теоремы о концепции равновесия макросистемы, даются их обобщения, приводится ряд примеров.
В начале главы разбираются задачи, имеющие прикладное значение. Приведем одну из них.
Задача 1. Обобщение энтропийной модели А.Дж. Вильсона расчета матрицы корреспонденций.
Пусть в некотором городе имеется n районов, Li 0 – число жителей i -го района, W j 0 – число работающих в j -м районе. При этом M Li W j, – общее число жителей города. Обозначим через x ij t 0 – число жителей, живущих в i-м районе и работающих в j-м в момент времени t. Со временем жители могут только меняться квартирами, поэтому во все моменты времени t Опишем имеющиеся стимулы к обмену. С одной стороны, работать далеко от дома плохо из-за транспортных издержек, но с другой, люди все-таки ездят на работу далеко. Это можно объяснить тем, что близко от дома не удается найти хорошую работу. Будем считать, что компромисс между этими двумя 0 – настраиваемые параметры модели.
Теперь опишем саму динамику. Пусть в момент времени t 0 r-й житель живет в k-м районе и работает в m-м, а s-й житель живет в p-м районе и работает в q-м.
Тогда k,m; p,q t t o t – есть вероятность того, что жители с номерами r и s ( 1 r s M ) поменяются квартирами в промежутке времени Вероятность обмена местами жительства зависит только от мест проживания и работы обменивающихся:
где коэффициент 0 характеризует интенсивность обменов.
Согласно эргодической теореме для марковских цепей:
“пуассоновской” вероятностной меры. Отметим, что стационарное распределение При M решение задачи энтропийно-линейного программирования (см. теорему 1 ниже):
Решение этой задачи можно представить как определяются из равенств системы (A). На практике мы имеем информацию о Li,Wi i1 и lij i1, j 1. Из системы ограничений (A), мы найдем Такой способ расчета матрицы корреспонденций с 0 в литературе часто называют (энтропийной) гравитационной моделью:
В классической статической энтропийной модели (второй половины 60-ых годов XX века) А.Дж. Вильсона 0. Однако по Москве наблюдается заметно лучшее соответствие реальных данных рассматриваемой модели, если допускать 0, и оптимально его подбирать.
предварительно, введем такую перестановку ij, что xij1 xij 2... xij n2, а затем введем обозначение nk t xij k t, k 1,..., n2.
Рассмотрим теперь общий подход, частным случаем которого является изложенная выше модель.
Предположим, что некоторая макросистема может находиться в различных состояниях, характеризуемых вектором n с неотрицательными целочисленными компонентами. Будем считать, что в системе происходят случайные превращения (химические реакции). Пусть n n,, J – все возможные типы интенсивность реакции:
где K 0 – константа реакции (в общем случае K n – функция, см. например, теорему 2). При этом часто считают вероятность осуществления в единицу времени перехода n n. На макроуровне все это соответствует принципам химической кинетики (закон действующих масс Гульдберга–Вааге, 1864).
Определение. Условием унитарности (условием Штюкельберга–Батищевой– Пирогова) называется следующее соотношение:
Следующая теорема уточняет результаты а) В.В. Веденяпина (1999), б) В.А.
Малышева, С.А. Пирогова, А.Н. Рыбко (2004).
тогда и только тогда, когда вектор ортогонален каждому вектору б) Пусть выполняется условие (ШБП). Тогда (ШБП), будет инвариантной относительно предложенной стохастической марковской динамики.
2. на множестве (inv) эта мера экспоненциально быстро концентрируется, с ростом M, в окрестности наиболее вероятного состояния, которое и принимается за положение равновесия макросистемы.
3. задача поиска наиболее вероятного макросостояния асимптотически (воспользовались ln (n ) ni ln ni i 1 на множестве, задаваемом условием (inv).
Теорема 2 обобщает результаты В. Вайдлиха (2000) и др. на случай, когда рассматривается более общая схема, чем модель миграции населения.
Теорема 2. Пусть Тогда справедливо утверждения п. б) теоремы 1 с Путь, по которому мы до сих пор приходили к равновесию макросистемы, состоял из следующей последовательности предельных переходов: lim и lim.
Однако для качественного понимания того как эволюционирует макросистема бывает полезно осуществить последовательность переходов в обратном порядке.
Пусть теперь dim n и число реакций J не зависят от числа агентов M, и в ci 0 lim ni 0 M 0. Тогда в произвольный момент времени t 0 для любого i существует не случайный предел ci t lim ni t M. Описанный выше предельный переход называется каноническим скейлингом.
В результате такого скейлинга приходим к «динамике квазисредних»
(терминология В. Вайдлиха):
Это технически нетривиальное утверждение следует из результатов ТроттераКуртца (1986).
Систему (ДК) можно получить и по-другому. А именно, как приближенную динамику средних ci t E ni t M. Приближенную в том смысле, что при «достаточно хороших» функций F (например, полиномов). Это верно в случае пикообразного распределения ni t.
Можно показать (следуя Батищевой–Веденяпину, 2001), что если выполняются условия (ШБП), то траектория (ДК) сходится к неподвижной точке. Какой именно, зависит, вообще говоря, от «точки старта»; но можно сказать и точнее: к той единственной неподвижной точке из семейства неподвижных точек, которая принадлежит аффинному многообразию (inv), инвариантному относительно (ДК).
Для этого, вводится (минус) энтропия:
и показывается, что она является функцией Ляпунова для системы (ДК). Обратим “породила” функцию Ляпунова H c. Подобные закономерности наблюдаются для рассматриваемых моделей и без условия (ШБП).
Теорема 3. Пусть инвариантная вероятностная мера представляется в виде:
Тогда H c – функция Ляпунова системы (ДК).
Естественно теперь задаться вопросом: А что будет, если условия (ШБП) не выполняются, однако система (ДК) имеет на внутренности пересечения неотрицательного ортанта и инвариантного аффинного многообразия (inv) единственную неподвижную точку (пример такой макросистемы имеется в докторской диссертации С.А. Пирогова)? Оказывается, имеет место Теорема 4. Если эта точка экспоненциально глобально устойчива, то 1) все инварианты (законы сохранения) системы (ДК) определяются (inv); 2) около положения равновесия инвариантная мера будет экспоненциально быстро концентрироваться (с ростом M ); 3) скорость сходимости к равновесию (mixing time) оценивается как M ln M ; 4) элементы корреляционной матрицы случайного вектора n t равномерно ограничены по времени; 5) предельные переходы lim и lim перестановочны: lim lim lim lim.
Результаты главы 1 и ряда других работ наталкивают на гипотезу: аттрактор динамической системы (ДК), который может быть сколь угодно сложным множеством (например, в приложениях типичны случаи предельных циклов, нескольких положений равновесия, и даже хаотических аттракторов), является таким множеством, в малой окрестности которого на больших временах с большой вероятностью будет пребывать рассматриваемая макросистема. Эта гипотеза для многих наиболее интересных и важных на практике случаев обоснована в диссертации с помощью техники доказательства теоремы 3.
Здесь возможны разные варианты поведения. Например, в случае двух притягивающих равновесий динамика системы “притянется” к каждому из них с вероятностями, зависящими от точки старта, и далее система может пребывать в малой окрестности равновесия длительное время, до большой флуктуации, которая сможет перебросить её в другое положение равновесия (Вентцель– (перемешиваться) по аттрактору. Возможно, конечно, и сочетание отмеченных типов поведения.
Во второй главе исследуется способы численного решения задачи энтропийнолинейного программирования. Согласно главе 1 именно к таким задачам часто сводятся задача поиска равновесия макросистемы.
Рассматривается общая задача энтропийно–линейного программирования:
Для отыскания единственного решения (ЭЛП) было предложено семейство двойственных барьерно-мультипликативных итерационных алгоритмов, которое содержит алгоритмы Брэгмана–Шелейховского, MART, GISM, Ю.С. Попкова и др.:
нуле. Например, часто выбирают Однако, как правило, разумно (с точки зрения эффективности счета) обнулять на каждом шаге большую часть случайно выбранных компонент этих векторов, причем вероятностный отбор осуществляется исходя из текущего состояния итерационного процесса, при этом после обнуления большинства компонент и соответствующего вытягивания по оставшимся (чтобы сохранить приблизительно длину) получившейся вектор должен быть достаточно близким к градиенту. То стохастический субградиентный спуск.
Глобальная сходимость итерационного процесса была установлена при следующих предположениях:
2) Строки матриц T и G линейно независимы в совокупности.
При этом было замечено, что предположение 2 не всегда выполняется в прикладных задачах (см., например, модель ранжирования web-страниц Дж.А.
Томлина). Оказывается, что от предположения 2 можно отказаться. А именно, если справедливо только предположение 1, то найдутся такие достаточно маленькие шаги (в зависимости от начального приближения), что итерационный задачи (ЭЛП). Доказательство в целом аналогично случаю регулярных ограничений. Однако, в случае зависимых ограничений решение двойственной пространстве.
Итерационные алгоритмы (ИП) особенно эффективны:
При этом время работы (число арифметических операций типа умножения двух чисел с плавающей точкой) детерминированного алгоритма (ИП) оценивается, вычислительные эксперименты, стохастические варианты, о которых говорилось выше, работают заметно быстрее.
Текст соответствующих компьютерных программ, написанных на МаtLab, имеется в приложении.
В третьей главе излагается модель Бэкмана равновесного распределения Исследование возникающих макросистем позволяет глубже понять концепцию равновесия Нэша–Вардропа.
Предварительно опишем модель Бэкмана равновесного распределения потоков на графе транспортной сети.
Пусть транспортная сеть города представлена ориентированным графом V, E, где V – узлы сети (вершины), E V V – дуги сети (рёбра графа).
Пусть W w i, j : i, j V – множество корреспонденций, т.е. возможных пар «исходный пункт» – «цель поездки»; p v1, v2,..., vm – путь из v1 в vm, если корреспонденции w W, то есть если w i, j, то Pw – множество путей, всех путей в сети ; x p [автомобилей/час] – величина потока по пути p, x x p : p P ; ye [автомобилей/час] – величина потока по дуге e :
e ye – удельные затраты на проезд по дуге e (как правило, возрастающие, выпуклые, гладкие функции).
Рассмотрим теперь G p x – затраты временные или финансовые на проезд по пути p. Естественно считать, что G p x e ye x ep, где e ye – удельные затраты на проезд по дуге e. Как правило, предполагают, что это – возрастающие, гладкие функции от ye. В приложениях часто требуется учитывать также затраты на прохождения вершин графа, которые могут зависеть от величин всех потоков через рассматриваемую вершину.
характеризующий распределение потоков, должен лежать в допустимом Это множество может иметь и более сложный вид, если дополнительно учитывать, например, конечность пропускных способностей рёбер (ограничения сверху на ye ).
Рассмотрим игру, в которой каждому элементу w W соответствует свой, достаточно большой ( d w 1), набор однотипных “игроков”, осуществляющих передвижение согласно корреспонденции w. Чистыми стратегиями игрока служат пути, а выигрышем – величина G p x. Игрок “выбирает” путь следования p Pw, при этом, делая выбор, он пренебрегает тем, что от его выбора также “немного” зависят Pw компонент вектора x и, следовательно, сам выигрыш G p x. Можно показать, что отыскание равновесия Нэша–Вардропа x * X комплементарности (принцип Вардропа): для любых w W, p Pw выполняется Заметим, что рассматриваемая нами игра принадлежит к классу, так называемых, потенциальных игр. В нашем случае это означает, что существует p P. Оказывается, что x * X – равновесие Нэша–Вардропа тогда и только тогда, когда оно доставляет минимум x на множестве X.
Введем теперь в эту статическую модель динамику. Пусть на шаге n игрок, осуществляющий перемещение согласно корреспонденции w, выбрал путь p.
Обозначим количество таких игроков через x p n. Тогда на шаге n 1 он с вероятностью 1 n выбирает тот же путь, а с вероятностью n использует смешанную стратегию: выбирает путь p Pw с вероятностью где Z nw определяется из условия нормировки. Множитель max x p n,1 n характеризует желание имитировать, т.е. использовать стратегию большинства, а также надежность использования этой стратегии (при одинаковых затратах на разных путях «надежнее» выбрать тот путь «вчерашнего дня», который «консерватизм» («ленивость»), чем меньше, тем более консервативный игрок;
«температура» T характеризует отношение к риску («горячность»), чем больше температура, тем более «горячий игрок», склонный к более рискованным действиям.
Как показали разнообразные численные эксперименты, часто вполне разумно выбирать n 1 n. При таком выборе n наблюдается сходимость к равновесию Нэша–Вардропа при наиболее общих условиях относительно T (вне зависимости от точки старта). Стоит также обратить внимание на высокую эффективность предложенной процедуры «нащупывания равновесия». Иначе говоря, на эффективный способ численного нахождения равновесия Нэша–Вардропа.
Предложенную схему можно трактовать как стохастическую динамику наилучших ответов в эволюционной (популяционной) игре, при этом имеется много общего с концепциями «quantal response equilibria» (используется похожая рандомизация) и «minority games» (наблюдаются похожие колебания около итерационному процессу является эффективный приближенный вероятностный алгоритм Григориадиса–Хачияна (см. также Фройнда–Шапире), являющийся предтечей современных вариантов метода стохастического зеркального спуска.
«