Содержание к диссертации
Введение
Глава 1. Обзор работ по теме диссертации 14
1.1. Обзор моделей популяционной динамики 14
1.2. Стохастические популяционные модели 23
1.3. Стохастические дифференциальные уравнения 26
1.4. Сведения по стохастическому исчислению 32
Глава 2. Метод моделирования одношаговых процессов 39
2.1. Одношаговые процессы. Уравнение Колмогорова-Чепмена. Основное кинетическое уравнение 39
2.2. Метод моделирования многомерных одношаговых процессов . 47
2.3. Численное моделирование 56
Глава 3. Применение метода моделирования одношаговых процессов 60
3.1. Стохастические модели популяционной динамики 60
3.2. Стохастические модели популяционных систем с различными меж- и внутривидовыми взаимодействиями 75
3.3. Стохастическая модель распространения сетевых червей . 92
3.4. Стохастические модели пиринговых протоколов 97
Заключение 113
Литература 116
- Стохастические дифференциальные уравнения
- Сведения по стохастическому исчислению
- Метод моделирования многомерных одношаговых процессов .
- Стохастические модели популяционных систем с различными меж- и внутривидовыми взаимодействиями
Стохастические дифференциальные уравнения
Одной из задач диссертации является задача записи стохастического дифференциального уравнения для системы так, чтобы стохастический член был связан со структурой изучаемой системы. Одно из возможных решений этой задачи — это получение стохастической и детерминистической частей из одного и тоже уравнения. Для этих целей удобно использовать основное кинетическое уравнение, которое может быть аппроксимировано уравнением Фоккера-Планка, для которого,в свою очередь, можно записать эквивалентное ему стохастическое дифференциальное уравнение в форме уравнения Ланжевена.
Раздел 1.4. содержит основные сведения, необходимые для обозначения связи между стохастическим дифференциальным уравнением и уравнением Фоккера-Планка, а также основные понятия стохастического исчисления.
Во второй главе приводятся основные сведения из теории случайных процессов и на основе этой теории формулируется метод моделирования одношаговых процессов.
В разделе 2.1 приведены основные сведения из теории случайных одношаговых процессов.
Под одношаговыми процессами понимаются марковские процессы с непрерывным временем, принимающие значения в области целых чисел, матрица перехода которых допускает только переходы между соседними участками.
Рассматривается многомерный одношаговый процесс Х() = (i(),2(), ...,n()) = { j(), = 1, } , (0.1) изменяющийся по на отрезке [0, ], т.е. Є [0, ], где - длина временного интервала, на котором задан процесс Х(). Множество G = {х , = 1, Є NQ х NQ1 — это множество дискретных значений, которые может принимать случайный процесс.
Для данного одношагового процесса вводятся вероятности переходов в единицу времени s+ и s из состояния Xj в состояние Xj__i и Xj_i соответственно. При этом считается, что вероятность перехода из состояния х на два или белее шагов за единицу времени очень мала. Поэтому можно говорить, что вектор Xj состояния системы изменяются шагами длины Г{ и тогда вместо переходов из х в Xj+i и Xj_i можно рассматривать переходы из X в X + Гі и X — Гі соответственно.
При моделировании систем, в которых временная эволюция происходит в результате взаимодействия элементов системы удобно описывать с помощью основного кинетического уравнения, (другое название управляющее уравнение [14, 15], а в англоязычной литературе носит название Master equation [16]).
Далее встает вопрос, как получить описание исследуемой системы, описываемой одношаговыми процессами, с помощью стохастического дифференциального уравнения в форме уравнения Ланжевена из основного кинетиче 11 ского уравнения. Формально к стохастическим уравнениям следует отнести лишь уравнения, содержащие стохастические функции. Таким образом, этому определению удовлетворяют лишь уравнения Ланжевена. Однако они связаны непосредственно с другими уравнениями, а именно с уравнением Фоккера-Планка и основным кинетическим уравнением. Поэтому представляется логичным рассматривать все эти уравнения в совокупности. Поэтому для решения этой задачи предлагается аппроксимировать основное кинетическое уравнение уравнением Фоккера-Планка, для которого можно записать эквивалентное ему стохастическое дифференциальное уравнение в форме уравнения Ланжевена.
В разделе 2.2 формулируется метод описания и стохастического моделирования систем, описываемых многомерными одношаговыми процессами.
Кроме того, показано, что коэффициенты для уравнения Фоккера-Планка можно получить сразу после записи для изучаемой системы схемы взаимодействия, вектора изменения состояния r и выражений для вероятностей перехода s+ и s-, т.е. при практическом применении данного метода нет необходимости записывать основное кинетическое уравнение.
В разделе 2.3. рассмотрен метод Рунге-Кутта для численного решения стохастических дифференциальных уравнений, который используется в третьей главе для иллюстрации полученных результатов.
В третьей главе представлена иллюстрация применения, описанного во второй главе метода построения стохастических моделей, на примере систем описывающих динамику роста взаимодействующих популяций, таких как «хищник-жертва», симбиоз, конкуренция и их модификации. Целью является записать их в виде стохастических дифференциальных уравнений и исследовать влияние введения стохастики на поведение системы.
В разделе 3.1. проиллюстрировано применение описанного во второй главе метода на примере модели «хищник-жертва». Системы с взаимодействием двух видов популяций типа «хищник-жертва» широко исследованы, что позволяет сравнить полученные результаты с уже хорошо известными.
Анализ полученных уравнений показал, что для исследования детерминистического поведения системы, можно использовать вектор сносов A полученного стохастического дифференциального уравнения, т.е. разработанный метод можно использовать для анализа как стохастического, так и детерминистического поведения. Кроме того сделан вывод, что стохастические модели дают более реалистичное описание поведения системы. В частности, для системы «хищник-жертва» в детерминистическом случае, решения уравнений имеют периодический вид и фазовый объем сохраняется, в то время как, введение стохаcтики в модель, дает монотонное возрастание фазового объема, что говорит о неизбежной гибели одной либо обеих популяций. В целях визуализации полученных результатов было проведено численное моделирование.
В разделе 3.2. разработанный метод применяется для получения и анализа различных стохастических моделей популяционной динамики, таких как модель «хищник–жертва» с учётом межвидовой конкуренции среди жертв, симбиоз, конкуренция и модель взаимодействия трех популяций.
Сведения по стохастическому исчислению
Развитие теории случайных процессов привело к переходу в исследования природных явлений от детерминистических представлений и моделей популяционной динамики к вероятностным и как следствие, появление большого числа работ посвященных стохастическому моделированию в математической биологии, химии, экономике и д.р.
При рассмотрении детерминистических популяционных моделей остаются не охваченными такие важные моменты, как случайные влияния различных факторов на эволюцию системы. Описывая популяционную динамику следует учитывать случайный характер размножения и выживания особей, а также случайные колебания, которые происходят в среде со временем и приводят к случайным флуктуациям параметров системы. Поэтому во всякую модель динамики популяций следует вводить вероятностные механизмы, отражающие эти моменты.
Стохастическое моделирование позволяет более полно описать изменения популяционных характеристик с учетом как всех детерминистских факторов, так и случайных эффектов, которые могут существенно изменить выводы из детерминистских моделей. С другой стороны с их помощью можно выявить качественно новые стороны поведения популяции.
Стохастические модели изменения состояний популяции можно описывать с помощью случайных процессов. При некоторых допущениях можно считать, что поведение популяции при условии ее настоящего состояния не зависит от того, каким образом это состояние было достигнуто (т.е. при фиксированном настоящем будущее не зависит от прошлого). Т.о. для моделирования процессов популяционной динамики удобно использовать марковские процессы рождения-гибели и соответствующие управляющие уравнения, которые подробно описаны во второй части работы.
Н. Н. Калинкин в своих работах [38,39] для иллюстрации процессов происходящих в системах с взаимодействующими элементами использует схемы взаимодействия и на базе этих схем строит модели этих систем используя аппарат ветвящихся марковских процессов. Применение такого подхода иллюстрируется на примере моделирования процессов в химических, популяционных, телекоммуникационных и др. системах.
В работе [22] рассматриваются вероятностные популяционные модели, для построения которых используется аппарат процессов рождения-гибели, а получившиеся системы дифференциально-разностных уравнений представляют собой динамические уравнения для случайных процессов. Также в работе рассмотрены методы нахождения решений данных уравнений.
Можно найти много статей посвященных построению стохастических моделей учитывающих различные факторы влияющие на динамику изменения численности популяций. Так,например, в статьях [5,40] построена и проанализирована модель динамики численности биологического сообщества, в котором особи потребляют пищевые ресурсы, содержащие вредные вещества. А в модели эволюции популяции в статье [6] учитывается фактор расселения представителей популяций в ареалах их обитания. Модель представляет собой систему самосогласованных уравнений Власова.
Стоит отметить работы [14,15,41], которые посвящены теории флуктуа-ций и применению стохастических методов в естественных науках, таких как физика, химия, биология и др. В частности, математическая модель изменения численности популяций, взаимодействующих по типу «хищник-жертва» строиться на базе многомерных марковских процессов рождения-гибели.
Можно рассматривать модель «хищник–жертва» как реализацию процессов рождения–гибели. В такой трактовке возможно их применение для моде 26 лей во многих областях науки. В 70-е годы М. Дои предложена методика изучения таких моделей на основе операторов рождения–уничтожения [42,43] (по аналогии со вторичным квантованием). Здесь можно отметить работы [44, 45]. Кроме того сейчас этот метод активно развивается в группе М. М. Гнатича [46–48].
Еще один подход к моделированию и изучению моделей популяцион-ной динамики связан с теорией оптимального управления. Здесь можно отметить работы [49–51].
Можно отметить, что большинство работ посвященных построению стохастических моделей популяционных процессов использует аппарат случайных процессов для получение дифференциально-разностных уравнений и последующей численной реализации. Кроме того широко применяется стохастические дифференциальные уравнения в форме Ланжевена, в которых стохастический член добавляется из общих соображений о поведении системы и призван описать случайные воздействия окружающей среды [5,6,8]. Дальнейшим исследованием модели является их качественный анализ или нахождение решений с помощью численных методов.
. Стохастические дифференциальные уравнения Определение 1. Стохастическое дифференциальное уравнение — это дифференциальное уравнение, в котором один член или более представляют собой стохастический процесс. Наиболее используемый и хорошо известный пример стохастического дифференциального уравнения (СДУ) — это уравнение с членом, который описывает белый шум и его можно рассматривать как винеровский процесс Wt, t 0.
Стохастические дифференциальные уравнения являются важным и широко используемым математическим аппаратом при изучении и моделировании динамических систем, которые подвержены различным случайным возмущениям.
Началом стохастического моделирования природных явлений принято считать описание явления броуновского движения, которое открыто Р. Броуном в 1827 году, когда он проводил исследования движения пыльцы растений в жидкости. Первое строгое объяснение этого явления независимо друг от друга дали А. Эйнштейн [52] и М. Смолуховский. Стоит отметить сборник статей [53] в котором собраны работы А. Эйнштейна и М. Смолухов-ского по броуновскому движению. Эти исследования внесли значительный вклад в развитие теории броуновского движения и ее экспериментальную проверку. А. Эйнштейном была создана молекулярно-кинетическая теория для количественного описания броуновского движения. Полученные формулы были подтверждены опытами Ж. Перрена в 1908-1909 гг.
Метод моделирования многомерных одношаговых процессов .
Для описания эволюции систем с взаимодействующими элементами существует два подхода — это построение детерминистической или стохастической моделей. В отличии от детерминистических, стохастические модели позволяют учесть вероятностный характер процессов происходящих в изучаемых системах, а также воздействия внешней среды, которые вызывают случайные флуктуации параметров модели.
Предметом изучения являются системы, процессы происходящие в которых могут быть описаны с помощью одношаговых процессов и таких, в которых переход их одного состояния в другое связан с взаимодействием элементов системы. Примером могут служить модели описывающие динамику роста взаимодействующих популяций, такие как «хищник-жертва», симбиоз, конкуренция и их модификации. Целью является записать для таких систем СДУ и исследовать влияние введения стохастической части на поведение решения уравнения, описывающего детерминистическое поведение.
Химическая кинетика
Системы уравнений, возникающие при описании систем с взаимодействующими элементами, во многом близки системам дифференциальных уравнений, описывающих кинетику химических реакций. Так, например, система Лотки-Вольтерра была первоначально выведена Лоткой как систе 48 ма, описывающая некоторую гипотетическую химическую реакцию, и лишь позже Вольтерра вывел ее как систему, описывающую модель «хищник-жертва».
Химическая кинетика описывает химические реакции с помощью, так называемых стехиометрических уравнений — уравнений отражающих количественные соотношения реагентов и продуктов химической реакции и имеющих следующий общий вид [88]: где натуральные числа ті и Щ называются стехиометрическими коэффициентами. Это символическая запись химической реакции, в которой ті молекул реагента Xi, ni2 молекул реагента Хч, ..., тр молекул реагента Хр, вступив в реакцию образуют щ молекул вещества Уї, щ молекул вещества І2, ..., nq молекул вещества Yq соответственно.
В химической кинетике полагается, что химическая реакция может происходить только при непосредственном взаимодействии реагентов, а скорость химической реакции определяется как число частиц образовавшихся в единицу времени в еденице объема.
Основным постулатом химической кинетики является закон действующих масс, который говорит о том, что скорость химической реакции прямо пропорциональна произведению концентраций реагирующих веществ в степенях их стехиометрических коэффициентов. Поэтому, если обозначить через ХІ и у І концентрации соответствующих веществ, то имеем уравнение для скорости изменения концентрации какого-либо вещества во времени в результате химической реакции [88]:
Далее предлагается использовать основные идеи химической кинетики для описания систем, эволюция во времени которых происходит в результате взаимодействия друг с другом элементов данной системы, внеся следующие основные изменения: 1. рассматриваются не скорости реакций, а вероятности переходов; 2. предлагается, что вероятность перехода из одного состояния в другое, являющегося следствием взаимодействия, пропорциональна числу возможных взаимодействий данного типа; 3. для описания системы в данном методе используется основное кинетическое уравнение; 4. детерминистические уравнения заменяются стохастическими. Подобный подход к описанию таких систем можно найти в работах [14, 38,39,89]. Для описания процессов происходящих в моделируемой системе предполагается использовать, как уже отмечалось выше, марковские одношаговые процессы.
Рассмотрим систему состоящую из типов различных элементов, которые могут взаимодействовать между собой различными способами. Обозначим через элемент -того типа, где = 1,, а через — количество элементов -того типа.
Пусть (), [0,) — одношаговый марковский процесс, описывающий количество элементов в системе в любой момент времени. Таким образом дискретное множество состояний этого процесса задается вектором x N. Кроме того считается, что в случайный момент времени в результате взаимодействия одной из возможных комбинаций элементов происходит переход системы в другое состояние, кроме того результат взаимодействия комбинации элементов не зависит от других элементов системы.
Схемы взаимодействия
Так как рассматриваются системы состоящие из элементов, которые взаимодействуют между собой и предполагается, что переход системы из одного состояния в другое происходит лишь в результате этого взаимодействия, поэтому удобно описывать процессы происходящие в таких системах с помощью схем подобных стехиометрическим уравнениям, которые будем называть схемами взаимодействия, общий вид которых представлен следующим выражением: где Xa обозначает тип элемента системы, матрицы N Є Z 0 х Z 0 и М Є Z 0 х Z 0 будем называть матрицами состояния системы, а коэффициенты к+ Є Z 0, к Є Z 0 — это коэффициенты взаимодействия в прямом и обратном направлениях соответственно. Коэффициент N есть число компонентов типа Ха в левой части уравнения, а М - соответственно в правой. Т.е. во взаимодействии вида А вступает N компонентов типа Ха и в результате этого взаимодействия в прямом направлении образуется М элементов типа Ха. Аналогично описывается взаимодействие в обратном направлении.
Т.о. схема взаимодействия это символическая запись всех возможных взаимодействий в системе между ее элементами. Т.е. такая схема показывает сколько и каких элементов вступило во взаимодействие и что получилось в результате, а также характеризует тип взаимодействия.
Также введем вектор х = (жі,Ж2, ...,жп) 0, который описысает состояние системы, т.е. количество элементов соответствующего типа присутствующих в изучаемой системе. Т.о. временную эволюцию системы будем рассматривать как изменение вектора х во времени.
Также определим для взаимодействия типа А вектор изменения состояния системы г Є Z 0 : г = М — N . (2.13) Вероятности перехода Как уже отмечалось выше, в системе, описываемой одношаговыми процессами возможны два вида перехода системы из одного состояния в другое, происходящие в результате взаимодействия элементов, в прямом направлении
Стохастические модели популяционных систем с различными меж- и внутривидовыми взаимодействиями
Сетевой червь — разновидность вредоносной программы, способной самостоятельно находить новые узлы для заражения и использовать их для распространения через локальные и глобальные компьютерные сети. Существуют различные стратегии заражения и поиска вредоносным кодом новых компьютеров для инфицирования, такие как: случайное сканирование, локальное сканирование, сканирование по топологии (использование информации о связях с другими компьютерами: адресные книги, контакт-листы) и др. 3.3.1. Описание модели
Для моделирования рассматривается система, представляющая собой компьютерную сеть из N узлов, которое могут находиться в одном из трех состояний: уязвимом, зараженном и невосприимчивом. Введем обозначения для каждого из состояний: S, I и R соответственно, а через малые буквы s, і и г обозначим число узлов каждого типа в сети(или доля узлов каждого типа). Таким образом состояние сети в каждый момент времени описывается вектором n = (s,i,r).
Предполагается, что узел для инфицирования выбирается сетевым червем случайным образом в доступном адресном пространстве и скорость поиска и заражения одного узла определяется средней скорость сканирования червем сети (ys) и размером ее адресного пространства, которое согласно спецификации протокола IP4 равна N{p = 232 [97], т.е Также предполагается, что в сети появляются новые узлы со скоростью а и новые узлы по определению считаются уязвимыми.
В модели также учитывается фактор, обеспечивающий замедление распространения сетевого червя, такой как «иммунизация», т.е. излечение зараженного узла при помощи так называемых «заплат» (сетевые черви для заражения узла чаще всего используют уязвимости ПО и т.п.) и других средств. Введем среднюю скорость иммунизации в единицу времени /І, которая определяется человеческой реакцией и необходимостью загрузки «заплат», поэтому можно считать, что скорость заражения узлов на много порядков превосходит скорость «иммунизации». Кроме того, в реальных сетях иммунизации подвергаются не только зараженные узлы, но и уязвимые, становясь невосприимчивыми к заражению.
Далее записаны все возможные переходы системы из одного состояния в другое в виде схемы взаимодействия: Первая строка схемы, представляет собой описание процесса появление нового уязвимого узла в сети в единицу времени с коэффициентом а. Вторая строка описывает процесс взаимодействия зараженного узла с уязвимым, следствии которого второй становиться зараженным с коэффициентом А. Третья и четвертая строки — это процесс иммунизации зараженных и уязвимых узлов соответственно. Т.е. узел после взаимодействия с «лекарством» А с коэффициентом /І становиться невосприимчивым.
Далее для написания уравнения Фоккера-Планка используем описанный выше метод. Для этого запишем соответствующие вектора , и .
Как показал численный анализ полученной модели, введение стохастики существенно не влияет на поведение системы, что наглядно видно на графиках (3.10) и (3.11). Однако стоит отметить, что в отличие от детерминированной модели, число уязвимых узлов в стохастической модели по прошествии некоторого времени становится равно нулю, и эволюция системы прекращается. Стохастическая модель распространение сетевых червей.
Fast Track — одноранговый (P2P) сетевой протокол для кооперативного обмена файлами через Интернет. Закачка данных осуществляется только из источников, содержащих полные файлы. FastTrack первоначально был реализован в программе KaZaA. Сеть, основанная на работе прокола FastTrack, имеет децентрализованную топологию, что делает ее работу очень надежной. В сети пользователи разделены на два класса: суперузлы и простые узлы (supernodes и ordinary nodes). Выделение суперузлов является одной из функций протокола и на эту роль выбираются узлы с быстрым подключением к сети, высокой пропускной способностью и возможностью быстрой обработки данных. При этом владельцы компьютеров не знают, что их компьютер был назначен в качестве суперузла.
Для того, чтобы загрузить файл, узел посылает запрос суперузлу, кото 98 рый в свою очередь взаимодействует с другими узлами и т.д. Таким образом запрос распространяется до определенного протоколом уровня сети и называется временем жизни запроса (Time to live). После того, как нужный файл будет найден, он передается непосредственно узлу, его запросившему, от узла, который имеет этот файл, минуя суперузел [98,99].
Сделаем предположение, что файл состоит из одной части. Таким образом за один шаг взаимодействия нового узла, желающего скачать файл, и узла, раздающего файл, новый узел скачивает весь файл и становится раздающим узлом.
Пусть — это обозначение нового узла, — это раздающий узел, а — коэффициент взаимодействия. Новые узлы могут приходить в систему с интенсивностью , а раздающие узлы уходить из нее с интенсивностью . Тогда схема взаимодействия и вектор г будет иметь вид:
Стохастическое дифференциальное уравнение в форме Ланжевена мож 100 но получить воспользовавшись соответствующей формулой (1.15). Т.к. вектор сносов A полностью описывает детермистическое поведеие системы можно получить систему обыкновеных дифференциальных уравнений, описывающих динамику численности новых клиентов и сидов:
Таким образом, в зависимости от выбора параметров особая точка может иметь разный характер. Так при /ЗА 4/І2 особая точка является устойчивым фокусом, а при обратном соотношении — устойчивый узел. В обоих случаях особая точка является устойчивой, так как выбора значений коэффициентов, изменения переменных системы может происходить по одной из двух траекторий. Если особая точка является фокусом, то в системе происходят затухающие колебания численностей новых и раздающих узлов (см. рис. 3.12). А в узловом случае приближение численностей к стационарным значениям происходит в бесколебательном режиме (см. рис. 3.13). Фазовые портреты системы для каждого из двух случаев изображены, соответственно, на графиках( 3.14) и ( 3.15).
