Моделирование случайных процессов

Введение

В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации.Метод моделирования широко применяют в таких областях, как автоматизация проектирования и организации в автоматизированных системах научных исследований, в системах исследования и проектирования, в системах массового обслуживания, анализ различных сторон деятельности человека, автоматизированное управление производственными и другими процессами. Важно подчеркнуть, что моделирование используется при проектировании, создании, внедрении, эксплуатации систем, а также на различных уровнях их изучения, начиная от анализа работы элементов и кончая исследованием системы в целом при их взаимодействии с окружающей средой.1. Метод статистического моделирования системНа этапе исследования и проектирования систем при построении и реализации машинных моделей (аналитических и имитационных) широко используется метод статистического моделирования (Монте-Карло), который базируется на использовании случайных чисел, т.е. возможных значений некоторой случайной величины с заданным распределением вероятностей. Статистическое моделирование представляет собой метод получения с помощью ЭВМ статистических данных о процессах, происходящих в моделируемой системе. Для получения представляющих интерес оценки характеристик моделируемой системы S с учетом воздействий внешней среды Е статистические данные обрабатываются и классифицируются с использованием методов математической статистики,Сущность метода статистического моделирования сводится к построению для процесса функционирования исследуемой системы S некоторого моделирующего алгоритма, имитирующего поведение и взаимодействие элементов системы с учетом случайных входных воздействий и воздействий внешней среды Е, и реализации этого алгоритма с использованием программно-технических средств ЭВМ.Различают две области применения метода статистического моделирования:- для изучения стохастических систем;- для решения детерминированных задач.Основной идеей, которая используется для решения детерминированных задач методом статистического моделирования, является замена детерминированной задачи эквивалентной схемой некоторой стохастической системы, выходные характеристики последней совпадают с результатом решения детерминированной задачи. При такой замене погрешность уменьшается с увеличением числа испытаний (реализации моделирующего алгоритма) N.В результате статистического моделирования системы S получается серия частных значений искомых величин или функций, статистическая обработка которых позволяет получить сведения о поведении реального объекта или процесса в произвольные моменты времени. Если количество реализации N достаточно велико, то полученные результаты моделирования системы приобретают статистическую устойчивость и с достаточной точностью могут быть приняты в качестве оценок искомых характеристик процесса функционирования системы S.При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий. Количество случайных чисел, используемых для получения статистически устойчивой оценки характеристики процесса функционирования системы S при реализации моделирующего алгоритма на ЭВМ, колеблется в достаточно широких пределах в зависимости от класса объекта моделирования, вида оцениваемых характеристик, необходимой точности и достоверности результатов моделирования. Для метода статистического моделирования на ЭВМ характерно, что большое число операций, а соответственно большая доля машинного времени расходуются на действия со случайными числами. Кроме того, результаты статистического моделирования существенно зависят от качества исходных (базовых) последовательностей случайных чисел. Поэтому наличие простых и экономичных способов формирования последовательностей случайных чисел требуемого качества во многом определяет возможность практического использования машинного моделирования системы.Понятие “статистическое моделирование” тесно связано с понятием “метод Монте-Карло” и почти ему тождественно.Для решения задач методом Монте-Карло необходимо получать на ЭВМ последовательность выборочных значений случайной величины с заданным распределением. Такой процесс принято называть моделированием случайной величины. Случайные величины обычно моделируют с помощью преобразований одного или нескольких независимых значений случайной величины а, равномерно распределенной в интервале (0,1). Независимые случайные величины, равномерно распределенные в интервале (0,1).Можно выделить следующие этапы моделирования случайных величин:· генерирование N реализации случайной величины с требуемой функцией распределения;· преобразование полученной величины, определяемой математической моделью;· статистическая обработка реализации.Особенностью первого этапа является то, что все методы для получения заданного распределения используют преобразование равномерно распределенной величины.Конструктивно задаются случайная величина, равномерно распределенная в интервале (0,1), (0,l), далее производится отображение  и получается новая случайная величина  с распределением, определяемым решаемой задачей, в общем случае  может быть довольно сложным.Далее следует получение некоторых характеристик. При параметрических оценках вычисляется некоторая функция . При непараметрическом задании функций распределения обычно вычисляются плотности или функции распределения. Чаще всего находят оценки математической ожидания. Погрешность оценки определяется дисперсией (если она известна) по числу экспериментов N.В результате можно выделить следующие этапы (рис. 4.1):- подготовка исходных данных (блок 1),- генерирование равномерно распределенных случайных чисел (блок 2),- преобразования для получения заданного закона распределения (блок 3);- выполнение дополнительных преобразований в соответствии с проблемной областью (блок 4);- статистическая обработка (блок 5).Рис. 4.1. Технологический процесс в Монте-Карло системахгде:- ПИД - подготовка исходных данных,- ГРРСЧ - генерирование равномерно распределенных случайных чисел;- ГПЗ - генерирование произвольного (заданного) закона распределения;- ДПр - дополнительные преобразования;- СО - статистическая обработка.Имитационные системы имеют следующие функциональные блоки:- имитации входных процессов;- имитации правил переработки входной информации исследуемой системы;- накопления информации в результате моделирования;- анализа накопленной информации;- управления имитирующей системы.Традиционный подход использует все классы задач, что и в методе Монте-Карло. Рассмотрим подробнее аналитический подход задания экзогенных переменных (первый случай). Они являются выходными другой подсистемы макросистемы и сами представляют собой макромодель. В рассматриваемом случае характеристики заданы аналитически.Информационно технологическая блок-схема представлена на рис. 4.2.Рис. 4.2. Технологический процесс имитационной системыГСП - генерирование случайных (входных) процессов;ИС - имитационная система.На первом этапе находят наиболее подходящие методы и алгоритмы для описания аналитических функций распределения и проводят вычисления (блок 1) для определения исходных данных, например, при аппроксимационных методах - координаты узлов, коэффициентов и т.п.Во втором и третьем блоках производится генерирование случайных чисел с равномерным распределением x, и экзогенных случайных процессов z.Блок 4 имитирует работу исследуемой системы, результаты его работы накапливаются для последующей статистической обработки. В последнем, пятом, блоке осуществляется статистическая обработка.При моделировании систем на ЭВМ программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. В качестве базового может быть принят любой удобный в случае моделирования конкретной системы S процесс (например, пуассоновский поток при моделировании Q-схемы). Однако при дискретном моделировании базовым процессом является последовательность чисел , представляющих собой реализации независимых, равномерно распределенных на интервале (0,1) случайных величин  или – в статистических терминах- повторную выборку из равномерно распределенной на (0,1) генеральной совокупности значений величины x.Непрерывная случайная величина x имеет равномерное распределение в интервале (а,b), если ее функция плотности (рис. 4.3,а) и распределение (рис. 4.3,6) соответственно примут вид:Рис. 4.3. Равномерное распределение случайной величины2. Моделирование случайных величин и процессовПод статистическим моделированием понимается воспроизведение с помощью ЭВМ функционирования вероятностной модели некоторого объекта.Задачи статистического моделирования состоят в том, чтобы научиться воспроизводить с помощью ЭВМ поведение таких моделей, например:- с помощью специальных методов и средств вырабатывать программы реализации случайных чисел;- с помощью этих чисел получать реализацию случайных величин или случайных процессов с более сложными законами распределения;- с помощью полученных реализации вычислять значения величин, характеризующих модель, и производить обработку результатов экспериментов;Устанавливать связь алгоритмов моделирования с алгоритмами решения задач вычислительной математики с помощью метода Монте-Карло и строить так называемые “фиктивные” модели, т.е. модели, не имеющие связи с объектом моделирования, но удобные в вычислительном отношении и позволяющие вычислять нужные нам характеристики объекта.Моделирование случайных процессов строится на основе базовых распределений случайных величин.Одним из таких процессов является марковские процессы.3. Основные понятия марковских процессовМарковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений особое внимание марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.Несмотря на указанную выше простоту и наглядность, практическое применение теории марковских цепей требует знания некоторых терминов и основных положений, на которых следует остановиться перед изложением примеров.Как указывалось, марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).Случайной функцией называется функция, значение которой при любом значении аргумента является случайной величиной (СВ). По- иному, СФ можно назвать функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид.Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение СП. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.Нетрудно заметить, что если обозначить состояние  и изобразить зависимость , то такая зависимость и будет случайной функцией.СП классифицируются по видам состояний  и аргументу t. При этом СП могут быть с дискретными или непрерывными состояниями, или временем. Например, любой выборочный контроль продукции будет относиться к СП с дискретными состояниями (- годная, - негодная продукция) и дискретным временем (, - времена проверки). С другой стороны, случай отказа любой машины можно отнести к СП с дискретными состояниями, но непрерывным временем. Проверки термометра через определенное время будут относиться к СП с непрерывным состоянием и дискретным временем. В свою очередь, например, любая осциллограмма будет записью СП с непрерывными состояниями и временем.Кроме указанных выше примеров классификации СП существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями СП. Так, например, если в СП вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия (рис.1).Зависимость  называют переходной вероятностью, часто говорят, что именно процесс без последействия обладает марковским свойством, однако, строго говоря, здесь есть одна неточность. Дело в том, что можно представить себе СП, в котором вероятностная связь существует не только с предшествующими, но и более ранними () состояниями, т.е. (1)Рис. 1. Схема процесса без последействияТакие процессы также рассматривались А.А. Марковым, который предложил называть их в отличие от первого случая (простой цепи) - сложной цепью. В настоящее время теория таких цепей разработана слабо и обычно применяют так называемый процесс укрупнения состояний путем математических преобразований, объединяя предшествующие состояния в одно.Это обстоятельство должно обязательно учитываться при составлении математических моделей принятия решений.Выше мы совершили незаметный терминологический переход от понятия СП к “марковской цепи”. Теперь эту неясность следует устранить. Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.Если случайная последовательность обладает марковским свойством, то она называется цепью Маркова.С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется марковским процессом с непрерывным временем.Марковский СП называется однородным, если переходные вероятности  остаются постоянными в ходе процесса.Цепь Маркова считается заданной, если заданы два условия.1. Имеется совокупность переходных вероятностей в виде матрицы:. (2)2. Имеется вектор начальных вероятностей, ….. (3)описывающий начальное состояние системы.Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса. Переходная матрица (2) обладает следующими свойствами:a) , (3a)б) .Матрица, обладающая свойством (3a), называется стохастической. Кроме матричной формы модель марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 2).Рис. 2. Ориентированный взвешенный графВершины графа обозначают состояние , а дуги- переходные вероятности.Множество состояний системы марковской цепи, определенным образом классифицируется с учетом дальнейшего поведения системы.1. Невозвратное множество (рис. 3).Рис. 3. Невозвратное множествоВ случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.2. Возвратное множество (рис. 4).Рис. 4. Возвратное множествоВ этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.3. Эргодическое множество (рис. 5).Рис. 5. Эргодическое множествоВ случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.4. Поглощающее множество (рис. 6)Рис. 6. Поглощающее множествоПри попадании системы в это множество процесс заканчивается.Кроме описанной выше классификации множеств различают состояния системы:а) существенное состояние (рис.7): возможны переходы из  в  и обратно.Рис. 7. Существенное состояниеб) несущественное состояние (рис. 8): возможен переход из  в , но невозможен обратный.Рис. 8. Несущественное состояниеВ некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.Основным признаком дискретной марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают. Если просуммировать все вышесказанные определения, то можно дать следующую классификацию марковских процессов (рис. 9):Рис. 9. Классификация марковских процессов4. Математический аппарат дискретных марковских цепейВ дальнейшем рассматриваются простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид: (4)и называется уравнением Колмогорова-Чепмена.Уравнение Колмогорова-Чепмена относится к классу рекуррентных соотношений, позволяющих вычислить вероятность состояний марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.ЗаключениеИспользование случайных величин является наиболее универсальным и поэтому наиболее распространенным способом учета в модели случайных факторов, присущих реальным экономическим системам или процессам. Примерами случайных величин могут служить: интервал времени до появления очередного клиента, длительность проведения технического обслуживания автомобиля, объем данных, считываемых из оперативной памяти ЭВМ и т.д.Если в задаче требуется высокая точность воспроизведения законов распределения случайных величин, то целесообразно использовать алгоритмы, не обладающие методической погрешностью, погрешностью которых обычно можно пренебречь, так как она определяется лишь погрешностью выполнения на ЦВМ необходимых нелинейных преобразований и отклонением закона распределения исходных случайных чисел от равномерного (нормального). Примером систем, при моделировании которых может потребоваться высокая точность воспроизведения законов распределения случайных величин, являются системы обнаружения радиосигнала с низкой вероятностью ложной тревоги.Другим достоинством указанных алгоритмов является простота подготовительной работы, так как преобразования равномерного закона в требуемый закон распределения даются в виде готовых аналитических зависимостей. Такого вида алгоритмы, кроме того, позволяют легко изменять форму закона распределения в процессе моделирования случайных величин, закон распределения которых зависит от переменных параметров. Например, изменение в процессе моделирования функции плотности случайной величины, распределенной по закону Раиса, сводится к изменению по соответствующему закону только параметра в алгоритме.Основным недостатком этих алгоритмов является сравнительно низкое быстродействие, так как осуществление на ЦВМ нелинейных преобразований часто требует довольно большого количества элементарных операций.Согласно центральной предельной теореме теории вероятностей при сложении достаточно большого числа одинаково распределенных независимых случайных чисел получается случайная величина, имеющая нормальное распределение.На практике часто сравнение проводят с помощью вычислительных экспериментов, при решении так называемых специальных тестовых задач. Эти задачи могут быть как с малым, так и с большим числом переменных, иметь различный вид нелинейности. Они могут быть составлены специально и возникать из практических приложений, например, задача минимизации суммы квадратов, решение систем нелинейных уравнений и т.п.В работе также показано, что любые дополнительные критерии эффективности и значимости продукции или технологических способов её производства - коэффициенты функции целиК сожалению, не всегда существуют элементарные преобразования для получения случайных величин с заданным законом распределения из равномерно распределенных случайных чисел. В частности, у случайных величин с нормальным распределением функция, обратная функции распределения, не выражается в замкнутом виде через элементарные функции.Существуют различные приемы преобразования случайных чисел с равномерным распределением в случайные числа с заданным законом распределения. Так, например, в качестве нормально распределенных случайных чисел можно использовать сумму нескольких независимых случайных чисел с равномерным распределением (приближение основано на центральной предельной теореме теории вероятностей, в силу которой сумма независимых случайных величин при весьма общих условиях имеет асимптотически нормальное распределение).
Литература
Голицына, О. Л. Информационные системы и технологии: учебное пособие для студентов [СПО], обучающихся по направлениям подготовки "Прикладная информатика (по областям применения)", "Информационные системы", "Программное обеспечение вычислительной техники и автоматизированных систем" / О. Л. Голицына, Н. В. Максимов, И. И. Попов. - Москва: Форум, 2019. - 400 с. - (Среднее профессиональное образование).2. Информатика и информационные технологии 4-е изд., пер. и доп.[электронный ресурс]. - Москва: Юрайт, 2019. - 383 с.3. Гвоздева, В. А. Информатика, автоматизированные информационные технологии и системы: Учебник / В. А. Гвоздева ; Московская государственная академия водного транспорта. - Москва: НИЦ ИНФРА-М, 2019. - 542 с. - (Среднее профессиональное образование). - ISBN 9785819908563.4. Компьютерное моделирование : методические указания к практическим занятиям для студентов II курса специальности СПО 27.02.07 "Управление качеством продукции, процессов и услуг" (по отраслям) / Министерство науки и высшего образования Российской Федерации, Кузбасский государственный технический университет им. Т. Ф. Горбачева, Кафедра информационных и автоматизированных производственных систем ; составитель Г. А. Алексеева. - Кемерово: КузГТУ, 2019. - 156 с. - URL: http://library.kuzstu.ru/meto.php?n=37065. Компьютерное моделирование : методические указания к самостоятельной работе для студентов II курса специальности СПО 27.02.07 "Управление качеством продукции, процессов и услуг" (по отраслям) / Министерство науки и высшего образования Российской федерации, Кузбасский государственный технический университет им. Т. Ф. Горбачева, Кафедра информационных и автоматизированных производственных систем ; составитель Г. А. Алексеева. - Кемерово: КузГТУ, 2019. - 73 с. - URL: http://library.kuzstu.ru/meto.php?n=50916. Компьютерное моделирование : методические указания к курсовому проекту для студентов II курса специальности СПО 27.02.07 "Управление качеством продукции, процессов и услуг" (по отраслям) / Министерство науки и высшего образования Российской федерации, Кузбасский государственный технический университет им. Т. Ф. Горбачева, Кафедра информационных и автоматизированных производственных систем ; составитель Г. А. Алексеева. - Кемерово: КузГТУ, 2019. - 24 с. - URL: http://1ihrary.kn7.stti.ru/melo.php7n=5456.7. Соловьев М.Е., Соловьев М.М. Компьютерная химия. М.: СОЛОНПресс, 2005. 536 с.8. Бутырская Е. В. Компьютерная химия. Основы теории и работа с программами Gaussian и GaussView. Солон-Пресс, 2011. 224 с.9. Барановский В. И. Квантовая механика и квантовая химия. М.: Академия, 2008. 384 с