Вероятностное моделирование

Московский технический университет связи и информатики МЕТОДЫ МОДЕЛИРОВАНИЯ УСТРОЙСТВ И СИСТЕМ ЛЕКЦИЯ 4 ТЕМА ЛЕКЦИИ: ВЕРОЯТНОСТНОЕ МОДЕЛИРОВАНИЕ ВОПРОСЫ ЛЕКЦИИ: • Понятие о стохастическом (вероятностном) моделировании • Этапы осуществления вероятностного моделирования • Пример вероятностного моделирования – исследование СМО методом Монте-Карло • Оценка результатов вероятностного моделирования 2 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ • В большинстве имитационных моделей в качестве входных данных используются случайные величины, поэтому выходные данные (отклики), также носят случайный характер. 3 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ В связи с этим необходимо осторожно делать выводы относительно действительных характеристик модели (например, ожидаемой точности, надежности, вероятности ошибки и т.п.). Правильное проведение анализа выходных данных невозможно без ознакомления со стохастическими процессами. 4 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Стохастический процесс ‒ совокупность однородных случайных величин, которые упорядочены во времени и определены в общем (выборочном) пространстве. Множество всех возможных значений, которые могут принимать эти случайные величины, называется пространством состояний. 5 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Результаты моделирования стохастической системы являются реализациями случайных величин (процессов). Следовательно, для нахождения характеристик системы требуется многократное повторение и последующая статистическая обработка (усреднение) данных. 6 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Численный анализ вероятностных систем с применением имитационного моделирования называется прямым вероятностным моделированием. По результатам вероятностного моделирования определяются оценки вероятностных критериев качества, характеризующих работу системы. 7 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Достоинства вероятностного моделирования: Метод анализа систем прямым вероятностным моделированием является универсальным. Он позволяет получить желаемый результат во всех случаях, если только удается построить каким-либо способом математическую модель системы. 8 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Позволяет решать широкий круг задач, относящихся к анализу данной системы. При достаточной полноте модели вероятностное моделирование позволяет оценивать показатели работы системы с высокой надежностью. 9 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ Недостатки вероятностного моделирования:  для выявления необходимых закономерностей при изучении стохастических систем необходима постановка статистического эксперимента, требующего значительных затрат, усилий и времени; 10 ПОНЯТИЕ О ВЕРОЯТНОСТНОМ МОДЕЛИРОВАНИИ • кроме того, статистические критерии не могут ни доказать, ни опровергнуть ни одной гипотезы: они лишь могут доказать отсутствие опровержения или показать, с какой вероятностью данная гипотеза выполняется. 11 ЭТАПЫ ОСУЩЕСТВЛЕНИЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ Для осуществления вероятностного моделирования необходимо иметь: набор генераторов случайных чисел и процессов, имитирующих входные воздействия, начальные условия, а также функции изменения параметров системы; 12 ЭТАПЫ ОСУЩЕСТВЛЕНИЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ реализованную математическую модель системы (на специализированном программном обеспечении или универсальных языках программирования), позволяющую получить выходные отклики в виде случайных функций времени; алгоритм, обеспечивающий обработку полученных реализаций. 13 ЭТАПЫ ОСУЩЕСТВЛЕНИЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ 14 ЭТАПЫ ОСУЩЕСТВЛЕНИЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Частная задача ‒ задача моделирования сигналов и помех. Формулируется как задача нахождения алгоритмов (по возможности, наиболее простых), позволяющих получить дискретные реализации (выборочные функции) моделируемых процессов. 15 ЭТАПЫ ОСУЩЕСТВЛЕНИЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ  Это самостоятельная задача синтеза дискретных случайных процессов, имитирующих непрерывные процессы с заданными статистическими характеристиками.  Она решается путем отыскания удобных для реализации на компьютере линейных и нелинейных преобразований, с помощью которых можно превратить независимые равномерно или нормально распределенные случайные числа, вырабатываемые датчиком случайных чисел, в случайные последовательности с требуемыми 16 статистическими характеристиками. ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • В сложных системах не всегда получается выразить модель аналитически. В этом случае прибегают к методу статистического имитационного моделирования, получившему название метод Монте-Карло. • Методика этого вида моделирования состоит из следующих этапов: 17 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • 1. Моделирование на ЭВМ псевдослучайных последовательностей с заданной корреляцией и законом распределения вероятностей, имитирующих случайные значения параметров при каждом испытании; • 2. Использование полученных числовых последовательностей в имитационных математических моделях. 18 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • 3. Статистическая обработка результатов моделирования. • Рассмотрим простейшую систему массового обслуживания (СМО), которая состоит из n линий (каналов) обслуживания. • В случайные моменты времени в систему поступают заявки. 19 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Каждая заявка поступает на линию № 1. Если в момент поступления заявки Тk эта линия свободна, заявка обслуживается за время tз (время занятости линии). Если линия занята, заявка мгновенно передается на линию № 2 и т. д. 20 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Если все n линий в данный момент заняты, то система выдает отказ. Естественной является задача определения характеристик данной системы, по которым можно оценить ее эффективность: среднее время ожидания обслуживания, доля времени простоя системы, среднюю длину очереди и т. д. 21 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • В этом случае каждой линии ставится в соответствие ячейка памяти (переменная), в которую записывается момент освобождения линии. • Пусть в момент времени t = Т1, который мы примем за начало отсчета, все линии свободны. За время окончания расчета примем Т=Тк . 22 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Первая заявка поступает на линию 1 и тут же обслуживается, поскольку линия свободна. • Следовательно, в течение времени τ1 эта линия будет занята. • Поэтому заменяем текущее время t на новое значение Т1 + τ1 и добавляем 1 к счетчику выполненных заявок. • Затем переходим к рассмотрению следующей заявки. 23 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Для этого генерируем значение γ, равномерно распределенное на интервале [0, 1], и по формуле τ=(‒1/λ) ln(1-γ) вычисляем очередное значение τ = τ2. • В этом случае для генерирования, экспоненциально распределенной, случайной величины был применен метод обратных функций. • Вычисляем момент поступления второй заявки: t2=T1+ τ2. 24 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Проверяем, свободна ли в этот момент первая линия, т.е. выполнено ли условие t1≤t2. • Если это условие выполнено, линия свободна и приступает к обслуживанию второй заявки. Заменяем t1 на t2 + tз, добавляем 1 к счетчику выполненных заявок и переходим к рассмотрению следующей заявки. 25 ПРИМЕР ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ – ИССЛЕДОВАНИЕ СМО МЕТОДОМ МОНТЕ-КАРЛО • Если линия занята, то проверяем, свободна ли вторая линия, и т. д. • Если в какой-то момент времени заняты все линии, добавляем 1 в счетчик отказов и переходим к выполнению следующей заявки. • После каждого вычисления tk проверяем условие окончания опыта: tk>Tк. • Если это условие выполнено, опыт заканчивается. Такой опыт повторяется N раз, и результаты всех опытов усредняются. 26 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Заключительный этап статистического моделирования ‒ математическая обработка полученных результатов. • Здесь используются методы математической статистики: параметрическое и непараметрическое оценивание, проверка гипотез. 27 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Пример параметрического оценивания ‒ выборочное среднее. • Непараметрическое оценивание ‒ метод гистограмм. • Задача проверки гипотез ‒ проверка соответствия распределения заданному закону. 28 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Предположим, что y1 y2.....yn являются независимыми и одинаково распределенными величинами (наблюдениями) с конечным математическим ожиданием my и конечной дисперсией генеральной совокупности σy2. • В этом случае выборочное среднее несмещенной (точечной) оценкой my; • это означает, что при очень большом количестве независимых экспериментов, каждый из которых дает результат в значение y(n) , среднее значение y(n) будет равно my. • Аналогично выборочная дисперсия представляет собой несмещенную оценку σy2.   y  y ( n ) n D( n )  i 1 y ( n)  1 n  yi n i 1 является 2 i n 1 29 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Сложность использования y(n) в качестве оценки my без какой-либо дополнительной информации состоит в том, что невозможно определить, насколько близко значение y(n) к my. • Поскольку y(n) является случайной величиной с дисперсией Var[y (n)], в одном эксперименте y (n) может быть близко к my, а в другом их значения могут существенно отличаться. 30 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Обычно, чтобы оценить точность y(n), как оценки my, необходимо построить доверительный интервал для my. • Первым шагом в построении доверительного интервала является оценка дисперсии Var[y(n) ]. • Очевидно, что чем больше объем выборки n, тем ближе выборочное среднее будет к my. 31 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Как свидетельствует опыт, выходные данные моделирования практически всегда являются коррелированными. • Следовательно, вышеприведенные сведения о независимых и одинаково распределенных наблюдениях не могут быть непосредственно применены к анализу выходных данных моделирования. 32 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Поскольку выходные данные моделирования являются коррелированными, то формулы классической статистики, в основе которых лежат независимые и одинаково распределенные наблюдения, не могут непосредственно использоваться для оценки дисперсий. 33 ОЦЕНКА РЕЗУЛЬТАТОВ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ • Но часто выходные данные моделирования группируют в новые наблюдения, к которым можно применять формулы, основанные на независимых одинаково распределенных наблюдениях. • Следовательно, формулы, в основе которых лежат независимые одинаково распределенные наблюдения, могут косвенно применяться при анализе выходных данных моделирования. 34 СПАСИБО ЗА ВНИМАНИЕ! 35