Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Стохастическое моделирование является моделированием из системы , имеющей переменные , которые могут изменить стохастический (случайно) с индивидуальными вероятностями. [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]

Биномиальное распределение [ править ]

Биномиальное распределенная случайная величина У с параметрами п и р получается как сумма п независимых и одинаково Бернулли-распределенных случайных величин X 1 , X 2 , ..., Х п [4]

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

HHH, ННТ, НТН, THH , TTH, THT, HTT, ТТТ

Ответ 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 ∈ N (M, a 2 ), если плотность случайной переменной определяется по формуле [4] х ∈ R. [4]

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

Экспоненциальное распределение [ править ]

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

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

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

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

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

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

Другие дистрибутивы [ править ]

  • Обобщенное распределение экстремальных значений

Комбинированное моделирование [ править ]

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

Моделирование Монте-Карло [ править ]

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

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

Заявление [ править ]

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

  • Статистический эксперимент с генерацией случайных величин (например, игральных костей)
  • метод отбора проб
  • Математика (например, численное интегрирование, множественные интегралы)
  • Техника надежности
  • Управление проектами (SixSigma)
  • Экспериментальная физика элементарных частиц
  • Симуляции
  • Измерение риска / Управление рисками (например, оценка стоимости портфеля)
  • Экономика (например, поиск наиболее подходящей кривой спроса)
  • Моделирование процессов
  • Исследование операций

Генераторы случайных чисел [ править ]

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

Генератор случайных чисел является устройством , способным производить последовательность чисел , которые не могут быть «легко» , идентифицированными с детерминированными свойствами. Затем эта последовательность называется последовательностью стохастических чисел . [23]

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

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

См. Также [ править ]

  • Детерминированное моделирование
  • Алгоритм Гиллеспи
  • Сетевое моделирование
  • Моделирование сетевого трафика
  • Язык моделирования
  • Теория массового обслуживания
  • Дискретность
  • Гибридное стохастическое моделирование

Ссылки [ править ]

  1. ^ a b c d DLOUHÝ, M .; FÁBRY, J .; КУНЦОВА, М .. Simulace pro ekonomy. Прага: VŠE, 2005.
  2. ^ a b c d Деккинг, FM (Фредерик Мишель), 1946- (2005). Современное введение в вероятность и статистику: понимание, почему и как . Springer. ISBN 1-85233-896-2. OCLC  783259968 .CS1 maint: multiple names: authors list (link)
  3. ^ стохастический. (nd). Интернет-словарь этимологии. Получено 23 января 2014 г. с веб-сайта Dictionary.com: http://dictionary.reference.com/browse/stochastic.
  4. ^ a b c d e f g Рачев, Светлозар Т. Стоянов, Стоян В. Фабоцци, Фрэнк Дж. «Концепции вероятности в главе 1» в продвинутых стохастических моделях, оценке рисков и оптимизации портфеля: идеальный риск, неопределенность и Показатели эффективности, Хобокен, Нью-Джерси, США: Wiley, 2008
  5. ^ Рачев, Светлозар Т .; Стоянов, Стоян В .; Фабоцци, Фрэнк Дж. (14 апреля 2011 г.). Подход на основе вероятностных показателей к мерам финансового риска . DOI : 10.1002 / 9781444392715 . ISBN 9781444392715.
  6. ^ Распределение Бернулли, Чикагский университет - Статистический факультет, [онлайн] доступно по адресу http://galton.uchicago.edu/~eichler/stat22000/Handouts/l12.pdf
  7. ^ "Архивная копия" . Архивировано из оригинала на 2014-02-26 . Проверено 25 января 2014 .CS1 maint: archived copy as title (link)
  8. ^ Хейт, Фрэнк А. (1967). Справочник по распределению Пуассона . Вайли. OCLC 422367440 . 
  9. ^ Сигман, Карл. «Пуассоновские процессы и Составные (пакетные) Пуассоновские процессы» (PDF) .
  10. ^ a b Стивен Гилмор, Введение в стохастическое моделирование - алгоритмы стохастического моделирования, Эдинбургский университет, [онлайн] доступно по адресу http://www.doc.ic.ac.uk/~jb/conferences/pasta2006/slides/stochastic- Simulation-Introduction.pdf
  11. ^ М.А. Гибсон и Дж. Брук, Эффективное точное стохастическое моделирование химических систем со многими видами и многими каналами , J. Comp Phys., 104: 1876–1899, 2000.
  12. Y. Cao, H. Li, and L. Petzold. Эффективная формулировка алгоритма стохастического моделирования для химически реагирующих систем , J. Chem. Phys. 121 (9): 4059–4067, 2004.
  13. Перейти ↑ Gillespie, DT (1976). «Общий метод численного моделирования стохастической временной эволюции связанных химических реакций». Журнал вычислительной физики . 22 (4): 403–434. Bibcode : 1976JCoPh..22..403G . DOI : 10.1016 / 0021-9991 (76) 90041-3 .
  14. ^ HT Бэнкс, Анна Бройдо, Брэнди Кантер, Кейтлин Гайверт, Шухуа Ху, Мишель Джойнер, Кэтрин Линк, Симуляционные алгоритмы для моделей цепей Маркова с непрерывным временем, [онлайн] доступно по адресу http://www.ncsu.edu/crsc/reports/ ftp / pdf / crsc-tr11-17.pdf
  15. ^ Разлив, F; Майни, ПК; Бирн, HM (2016). «Оптимизация моделирования случайных процессов путем устранения противоположных реакций». Журнал химической физики . 144 (8): 084105. arXiv : 1602.02655 . Bibcode : 2016JChPh.144h4105S . DOI : 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 . DOI : 10.1016 / j.jcp.2015.07.002 . PMC 4554296 . PMID 26478601 .  
  22. ^ a b Cosma Rohilla Shalizi, Монте-Карло и другие виды стохастического моделирования, [онлайн] доступно на http://bactra.org/notebooks/monte-carlo.html
  23. ^ a b Дональд Э. Кнут, Искусство компьютерного программирования, Том 2: Получисленные алгоритмы - глава 3: Случайные числа (Аддисон-Уэсли, Бостон, 1998).
  24. ^ Андреас Хелландер, Стохастическое моделирование и методы Монте-Карло, [онлайн] доступно по адресу http://www.it.uu.se/edu/course/homepage/bervet2/MCkompendium/mc.pdf
  • (Слепой, 2008): Слепой, А; Томпсон, AP; Плимптон, SJ (2008). «Кинетический алгоритм Монте-Карло с постоянным временем для моделирования крупных сетей биохимических реакций». Журнал химической физики . 128 (20): 205101. Bibcode : 2008JChPh.128t5101S . DOI : 10.1063 / 1.2919546 . PMID 18513044 . 
  • (Брацун 2005): Д. Брацун; Д. Вольфсон; Дж. Хэсти; Л. Цимринг (2005). «Стохастические колебания, вызванные задержкой в ​​регуляции генов» . PNAS . 102 (41): 14593–8. Bibcode : 2005PNAS..10214593B . DOI : 10.1073 / pnas.0503858102 . PMC 1253555 . PMID 16199522 .  
  • (Cai 2007): X. Cai (2007). «Точное стохастическое моделирование сопряженных химических реакций с запаздыванием». J. Chem. Phys . 126 (12): 124108. Bibcode : 2007JChPh.126l4108C . DOI : 10.1063 / 1.2710253 . PMID 17411109 . 
  • Хартманн, АК (2009). Практическое руководство по компьютерному моделированию . World Scientific. ISBN 978-981-283-415-7. Архивировано из оригинала на 2009-02-11 . Проверено 3 мая 2012 .
  • Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 17.7. Стохастическое моделирование сетей химических реакций» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
  • (Рамасвами 2009): Р. Рамасвами; Н. Гонсалес-Сегредо; И.Ф. Сбальзарини (2009). «Новый класс высокоэффективных алгоритмов точного стохастического моделирования для сетей химических реакций». J. Chem. Phys . 130 (24): 244104. arXiv : 0906.1992 . Bibcode : 2009JChPh.130x4104R . DOI : 10.1063 / 1.3154624 . PMID 19566139 . 
  • (Рамасвами 2010): Р. Рамасвами; И.Ф. Сбальзарини (2010). «Вариант с частичной склонностью алгоритма стохастического моделирования отклонения состава для сетей химических реакций» (PDF) . J. Chem. Phys . 132 (4): 044102. Bibcode : 2010JChPh.132d4102R . DOI : 10.1063 / 1.3297948 . PMID 20113014 .  
  • (Рамасвами 2011): Р. Рамасвами; И.Ф. Сбальзарини (2011). "Формулировка частичной склонности алгоритма стохастического моделирования для сетей химических реакций с задержками" (PDF) . J. Chem. Phys . 134 (1): 014106. Bibcode : 2011JChPh.134a4106R . DOI : 10.1063 / 1.3521496 . PMID 21218996 .  

Внешние ссылки [ править ]

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