Стохастическое моделирование - Stochastic simulation

А стохастическое моделирование это симуляция из система который имеет переменные, которые могут изменяться стохастически (случайно) с индивидуальными вероятностями.[1]

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

Часто случайные переменные, вставленные в модель, создаются на компьютере с генератор случайных чисел (ГСЧ). U (0,1) равномерное распределение затем выходные данные генератора случайных чисел преобразуются в случайные величины с распределениями вероятностей, которые используются в модели системы.[2]

Этимология

Стохастик первоначально означало «относящийся к предположению»; от греч. стокхастикос "уметь угадывать, догадываться": от стокхазестай "догадываться"; от стокоса «угадай, прицелься, прицелись, отметь». Смысл «случайно определенного» впервые был зафиксирован в 1934 году немецким издательством Stochastik.[3]

Дискретно-событийное моделирование

Чтобы определить следующее событие в стохастическом моделировании, вычисляются скорости всех возможных изменений состояния модели, а затем они упорядочиваются в массиве. Затем берется совокупная сумма массива, и последняя ячейка содержит число R, где R - общая частота событий. Этот совокупный массив теперь представляет собой дискретное совокупное распределение, и его можно использовать для выбора следующего события путем выбора случайного числа z ~ U (0, R) и выбора первого события, так что z меньше скорости, связанной с этим событием. .

Распределения вероятностей

Распределение вероятностей используется для описания потенциального результата случайной величины.

Ограничивает результаты, когда переменная может принимать только дискретные значения.[4]

Распределение Бернулли

Случайная величина X равна Распределенный по Бернулли с параметром p, если он имеет два возможных результата, обычно кодируемых 1 (успех или по умолчанию) или 0 (неудача или выживание)[5] где вероятности успеха и неудачи и куда .

Чтобы получить случайную величину X с распределением Бернулли из равномерного распределения U (0,1), созданного генератором случайных чисел, мы определяем

такая, что вероятностьи .[2]

Пример: подбрасывание монеты

Определять

X = 1, если поднимается голова, и X = 0, если поднимается хвост

Для честной монеты обе реализации одинаково вероятны. Мы можем генерировать реализации этой случайной величины X из равномерное распределение, обеспечиваемое генератором случайных чисел (ГСЧ) за счет наличия если ГСЧ выдает значение от 0 до 0,5 и если ГСЧ выдает значение от 0,5 до 1.

P (X = 1) = P (0 ≤ U <1/2) = 1/2
P (X = 0) = P (1 ≥ U ≥ 1/2) = 1/2

Конечно, оба исхода не могут быть одинаково вероятными (например, успех лечения).[6]

Биномиальное распределение

А биномиально распределенный случайная величина Y с параметрами п и п получается как сумма п независимый и идентичный Распределенный по Бернулли случайный переменные X1, ИКС2, ..., ИКСп[4]

Пример: монета подбрасывается трижды. Найдите вероятность получить ровно две головы. Эту проблему можно решить, посмотрев на пробное пространство. Есть три способа получить две головы.

HHH, HHT, HTH, THH, TTH, THT, HTT, TTT

Ответ - 3/8 (= 0,375).[7]

распределение Пуассона

Пуассоновский процесс - это процесс, в котором события происходят случайным образом в интервале времени или пространства.[2][8] Распределение вероятностей для пуассоновских процессов с постоянной скоростью λ за интервал времени задается следующим уравнением.[4]

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

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

куда является равномерно распределенная случайная величина.[2]

Моделирование пуассоновского процесса с постоянной скоростью по количеству событий которые происходят в интервале можно осуществить по следующему алгоритму.[9]

  1. Начинать с и
  2. Сгенерировать случайную величину из равномерное распределение
  3. Обновите время с помощью
  4. Если , затем остановись. В противном случае перейдите к шагу 5.
  5. Перейти к шагу 2

Методы

Методы прямой и первой реакции

Опубликовано Дэн Гиллеспи в 1977 году, и представляет собой линейный поиск по кумулятивному массиву. Видеть Алгоритм Гиллеспи.

Алгоритм стохастического моделирования (SSA) Гиллеспи - это, по сути, точная процедура для численного моделирования временной эволюции хорошо перемешиваемой химически реагирующей системы с должным учетом случайности, присущей такой системе.[10]

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

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

Следующий метод реакции

Опубликовано Гибсоном и Бруком в 2000 г.[11]. Это улучшение по сравнению с первым методом реакции, при котором повторно используется неиспользованное время реакции. Чтобы сделать выборку реакций более эффективной, для хранения времени реакции используется очередь с индексированным приоритетом. С другой стороны, чтобы сделать пересчет склонностей более эффективным, используется граф зависимостей. Этот график зависимостей показывает, какие склонности к реакции обновляются после того, как сработала конкретная реакция.

Оптимизированные и прямые методы сортировки

Опубликовано в 2004 г.[12] и 2005. Эти методы сортируют совокупный массив, чтобы уменьшить среднюю глубину поиска алгоритма. Первый запускает предварительное моделирование для оценки частоты срабатывания реакций, тогда как второй сортирует совокупный массив на лету.

Логарифмический прямой метод

Опубликовано в 2006 году. Это бинарный поиск по кумулятивному массиву, что снижает временную сложность выборки реакции в наихудшем случае до O (log M).

Методы частичной склонности

Опубликовано в 2009, 2010 и 2011 годах (Рамасвами 2009, 2010, 2011). Используйте факторизованные частичные склонности к реакциям, чтобы уменьшить вычислительные затраты и масштабировать с учетом количества разновидностей в сети, а не (большего) количества реакций. Существуют четыре варианта:

  • PDM, прямой метод частичной склонности. Имеет вычислительные затраты, которые линейно масштабируются с количеством различных частиц в реакционной сети, независимо от класса связи сети (Ramaswamy 2009).
  • SPDM, прямой метод сортировки с частичной склонностью. Использует динамическую пузырьковую сортировку, чтобы уменьшить предварительный фактор вычислительных затрат в многомасштабных реакционных сетях, где скорость реакции составляет несколько порядков (Ramaswamy 2009).
  • PSSA-CR, SSA с частичной склонностью с отбором отбраковки состава. Снижает вычислительные затраты до постоянного времени (т.е.не зависит от размера сети) для слабосвязанных сетей (Ramaswamy, 2010) с использованием выборки с отклонением состава (Slepoy, 2008).
  • dPDM, прямой метод частичной склонности к задержке. Распространяет PDM на сети реагирования, которые несут временные задержки (Ramaswamy 2011), обеспечивая вариант частичной склонности метода SSA задержки (Bratsun 2005, Cai 2007).

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

Примерные методы

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

τ прыжковый метод

Поскольку метод SSA отслеживает каждый переход, было бы непрактично реализовать его для определенных приложений из-за высокой временной сложности. Гиллеспи предложил процедура аппроксимации, то тау-прыжковый метод что сокращает время вычислений с минимальной потерей точности.[13]Вместо того, чтобы делать последовательные шаги во времени, отслеживая X (t) на каждом временном шаге, как в методе SSA, тау-прыжковый метод перескакивает с одного подынтервала на другой, приблизительно определяя, сколько переходов происходит за данный подинтервал. Предполагается, что величина скачка τ достаточно мала, чтобы не было значительного изменения значения скоростей переходов на подынтервале [t, t + τ]. Это состояние известно как условие прыжка. В тау-прыжковый метод таким образом, имеет то преимущество, что имитирует множество переходов за один прыжок, не теряя при этом значительной точности, что приводит к ускорению времени вычислений.[14]

Метод условной разности

Этот метод аппроксимирует обратимые процессы (включая процессы случайного блуждания / распространения), принимая во внимание только чистые скорости противоположных событий обратимого процесса. Основное преимущество этого метода состоит в том, что он может быть реализован с помощью простого оператора if, заменяющего предыдущие скорости перехода модели на новые эффективные скорости. Таким образом, модель с замененными скоростями перехода может быть решена, например, с помощью обычного SSA.[15]

Непрерывное моделирование

В то время как в дискретном пространство состояний четко различать отдельные состояния (ценности) в непрерывном пространстве невозможно в силу определенной непрерывности. В системе обычно со временем меняются переменные модели, а затем также изменяются непрерывно. Непрерывное моделирование тем самым моделирует систему во времени, учитывая дифференциальные уравнения определение скорости изменения переменных состояния.[16]Пример непрерывной системы модель хищник / жертва[17] или балансировка полюсов тележки [18]

Распределения вероятностей

Нормальное распределение

В случайный переменная X называется нормально распределенный с параметрами μ и σ, сокращенно X ∈ N (μ, σ2), если плотность случайный переменная задается формулой [4]x ∈ R.[4]

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

Экспоненциальное распределение

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

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

Распределение Стьюдента

Распределение Стьюдента используются в финансах как вероятностные модели доходности активов. В функция плотности t-распределения определяется следующим уравнением:[4]

куда это количество степени свободы и это гамма-функция.

Для больших значений п, то t-распределение существенно не отличается от стандартного нормальное распределение. Обычно для значений п > 30 лет t-распределение считается равным стандарту нормальное распределение.

Другие дистрибутивы

Комбинированное моделирование

Часто можно смоделировать одну и ту же систему, используя совершенно разные мировоззрения. Дискретное моделирование событий проблемы, а также непрерывное моделирование событий его (непрерывное моделирование с дискретными событиями, которые нарушают непрерывный поток) может в конечном итоге привести к тем же ответам. Однако иногда эти методы могут дать ответ на разные вопросы о системе. Если нам обязательно нужно ответить на все вопросы, или если мы не знаем, для каких целей будет использоваться модель, удобно применять комбинированный непрерывный / дискретный методология.[20] Подобные методы могут измениться от дискретного стохастического описания к детерминированному континуальному описанию в зависимости от времени и пространства.[21] Использование этого метода позволяет улавливать шум из-за малого количества копий, при этом его моделирование намного быстрее, чем у обычного алгоритма Гиллеспи. Кроме того, использование детерминированного континуального описания позволяет моделировать сколь угодно большие системы.

Моделирование Монте-Карло

Монте-Карло это процедура оценки. Основная идея заключается в том, что если необходимо знать среднее значение какого-либо случайный переменная и ее распределение не могут быть указаны, и если можно взять выборки из распределения, мы можем оценить ее, взяв выборки независимо и усреднив их. Если выборок достаточно, то закон больших чисел гласит, что среднее значение должно быть близко к истинному значению. Центральная предельная теорема утверждает, что среднее имеет Гауссово распределение вокруг истинного значения.[22]

В качестве простого примера предположим, что нам нужно измерить площадь фигуры со сложным неправильным контуром. Подход Монте-Карло заключается в том, чтобы нарисовать квадрат вокруг формы и измерить квадрат. Затем мы бросаем дротики в квадрат как можно более равномерно. Доля дротиков, падающих на фигуру, дает отношение площади фигуры к площади квадрата. Фактически, в эту форму можно представить практически любую интегральную задачу или любую задачу усреднения. Необходимо иметь хороший способ определить, находитесь ли вы внутри контура, и научиться определять, сколько дротиков бросить. И последнее, но не менее важное: нам нужно метать дротики равномерно, т.е. генератор случайных чисел.[22]

Заявление

Существуют широкие возможности использования метода Монте-Карло:[1]

Генераторы случайных чисел

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c d DLOUHÝ, M .; FÁBRY, J .; КУНЦОВА, М .. Simulace pro ekonomy. Прага: VŠE, 2005.
  2. ^ а б c d Деккинг, Ф. (Фредерик Мишель), 1946- (2005). Современное введение в вероятность и статистику: понимание, почему и как. Springer. ISBN  1-85233-896-2. OCLC  783259968.CS1 maint: несколько имен: список авторов (связь)
  3. ^ стохастический. (нет данных). Интернет-словарь этимологии. Получено 23 января 2014 г. с сайта Dictionary.com: http://dictionary.reference.com/browse/stochastic
  4. ^ а б c d е ж грамм Рачев, Светлозар Т. Стоянов, Стоян В. Фабоцци, Фрэнк Дж., «Концепции вероятности в главе 1» в продвинутых стохастических моделях, оценка риска и оптимизация портфеля: идеальный риск, неопределенность и показатели эффективности, Хобокен, Нью-Джерси, США : Wiley, 2008 г.
  5. ^ Рачев, Светлозар Т .; Стоянов, Стоян В .; Фабоцци, Фрэнк Дж. (14 апреля 2011 г.). Подход на основе вероятностных показателей к мерам финансового риска. Дои:10.1002/9781444392715. ISBN  9781444392715.
  6. ^ Bernoulli Distribution, Чикагский университет - Департамент статистики, [онлайн] доступно по адресу http://galton.uchicago.edu/~eichler/stat22000/Handouts/l12.pdf
  7. ^ «Архивная копия». Архивировано из оригинал на 2014-02-26. Получено 2014-01-25.CS1 maint: заархивированная копия как заголовок (связь)
  8. ^ Хейт, Фрэнк А. (1967). Справочник по распределению Пуассона. Вайли. OCLC  422367440.
  9. ^ Зигман, Карл. «Пуассоновские процессы, и Составные (периодические) Пуассоновские процессы» (PDF).
  10. ^ а б Стивен Гилмор, Введение в стохастическое моделирование - алгоритмы стохастического моделирования, Эдинбургский университет, [онлайн] доступно по адресу http://www.doc.ic.ac.uk/~jb/conferences/pasta2006/slides/stochastic-simulation-introduction.pdf
  11. ^ М. А. Гибсон и Дж. Брук, Эффективное точное стохастическое моделирование химических систем с множеством видов и множеством каналов, J. Comp Phys., 104: 1876–1899, 2000.
  12. ^ Ю. Цао, Х. Ли, Л. Петцольд. Эффективная формулировка алгоритма стохастического моделирования химически реагирующих систем, J. Chem. Phys. 121 (9): 4059–4067, 2004.
  13. ^ Гиллеспи, Д.Т. (1976). «Общий метод численного моделирования стохастической временной эволюции связанных химических реакций». Журнал вычислительной физики. 22 (4): 403–434. Bibcode:1976JCoPh..22..403G. Дои:10.1016/0021-9991(76)90041-3.
  14. ^ H.T. Бэнкс, Анна Бройдо, Брэнди Кантер, Кейтлин Гайверт, Шухуа Ху, Мишель Джойнер, Кэтрин Линк, Simulation Algorithms for Continuous Time Markov Chain Models, [онлайн] доступно по адресу http://www.ncsu.edu/crsc/reports/ftp/pdf/crsc-tr11-17.pdf
  15. ^ Разлив, F; Майни, ПК; Бирн, HM (2016). «Оптимизация моделирования случайных процессов путем устранения противоположных реакций». Журнал химической физики. 144 (8): 084105. arXiv:1602.02655. Bibcode:2016ЖЧФ.144х4105С. Дои:10.1063/1.4942413. PMID  26931679.
  16. ^ Креспо-Маркес, А., Р. Р. Усано и Р. Д. Аснар, 1993, "Непрерывное и дискретное моделирование в системе планирования производства. Сравнительное исследование"
  17. ^ Луи Дж. Бирта, Гилберт Арбез (2007). Моделирование и имитация, стр. 255. Springer.
  18. ^ "Учебник по балансировке полюсов".
  19. ^ Университет Нотр-Дам, Нормальное распределение, [онлайн] доступно по адресу http://www3.nd.edu/~rwilliam/stats1/x21.pdf
  20. ^ Франсуа Э. Селье, Приложения, методы и инструменты для комбинированного непрерывного / дискретного моделирования
  21. ^ Разлив, F .; и другие. (2015). «Гибридные подходы для многовидовых стохастических реакционно-диффузионных моделей». Журнал вычислительной физики. 299: 429–445. arXiv:1507.07992. Bibcode:2015JCoPh.299..429S. Дои:10.1016 / j.jcp.2015.07.002. ЧВК  4554296. PMID  26478601.
  22. ^ а б Cosma Rohilla Shalizi, Монте-Карло и другие виды стохастического моделирования, [онлайн] доступно по адресу http://bactra.org/notebooks/monte-carlo.html
  23. ^ а б Дональд Э. Кнут, Искусство компьютерного программирования, Том 2: Получисловые алгоритмы - глава 3: Случайные числа (Аддисон-Уэсли, Бостон, 1998).
  24. ^ Андреас Хелландер, Стохастическое моделирование и методы Монте-Карло, [онлайн] доступно по адресу http://www.it.uu.se/edu/course/homepage/bervet2/MCkompendium/mc.pdf

внешняя ссылка

Программного обеспечения
  • кайенский перец - Быстрый и простой в использовании пакет Python для стохастического моделирования. Реализации прямого, тау-прыжкового и тау-адаптивного алгоритмов.
  • StochSS - StochSS: служба стохастического моделирования - среда облачных вычислений для моделирования и моделирования стохастических биохимических систем.
  • ResAssure - Программное обеспечение для стохастического моделирования коллектора - решает полностью неявные, динамические уравнения трехфазного потока жидкости для каждой геологической реализации.
  • Каин - Стохастическое моделирование химической кинетики. Прямая, следующая реакция, тау-прыжок, гибрид и т. Д.
  • pSSAlib - C ++ реализации всех методов частичной склонности.
  • StochPy - Стохастическое моделирование на Python
  • ШАГИ - STochastic Engine для моделирования пути с использованием swig для создания интерфейса Python для кода C / C ++