Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции по моделированию - файл ГЛАВА 3.doc


Загрузка...
Лекции по моделированию
скачать (1024.9 kb.)

Доступные файлы (5):

ГЛАВА 1.doc307kb.20.02.2006 19:13скачать
ГЛАВА 2.doc615kb.20.02.2006 19:13скачать
ГЛАВА 3.doc813kb.29.03.2006 11:20скачать
ГЛАВА 4.doc731kb.20.02.2006 19:13скачать
ГЛАВА 5.doc574kb.20.02.2006 19:13скачать

ГЛАВА 3.doc

Реклама MarketGid:
Загрузка...
МЕТОДЫ МОДЕЛИРОВАНИЯ

3.1. Аналитические модели и методы

Аналитические методы исследования ВС сводятся к построению математических моделей, описывающих физические свойства элементов системы математическими объектами и отношениями между ними. При использовании аналитических методов оператор , устанавливающий зависимость между характеристиками и параметрами системы, представляется совокупностью математических выражений. В таких моделях, называемых аналитическими, зависимость между характеристиками и параметрами может быть представлена в явной аналитической форме в виде выражения , решенных относительно искомых величин, или в неявной форме в виде уравнений , связывающих характеристики и параметры.

Как правило, свойства элементов и систем удается представить в аналитической форме, если принимаются определенные допущения о свойствах и поведении описываемых объектов: независимость одних факторов от других, линейность некоторых зависимостей, мгновенность переходов между состояниями и т.д. Если допущения соответствуют реальности, модель хорошо воспроизводит зависимость между характеристиками и параметрами. Однако, во многих случаях допущения приводят к существенным отличиям модели от реального объекта, вследствие чего моделируемая зависимость существенно отличается от реальной и характеристики представляются на модели с большой погрешностью. Так, предположение о том, что процессы обладают Марковским свойством, может оказаться ошибочным, что приводит к большим погрешностям Марковских моделей и даже к неверным оценкам. Основные аналитические методы теории массового обслуживания базируются на предположении, что интервалы времени между заявками входящих потоков и длительности обслуживания распределены по экспоненциальному закону. Когда это предположение выполняется, аналитические методы позволяют точно оценивать характеристики системы. Если же потоки и длительности существенно отличаются от предполагаемых, моделируемые характеристики могут сколь угодно отличаться от реальных.

Аналитические методы и модели составляют ядро теории ВС и ценны по следующим причинам.

  1. Зависимости, полученные аналитическими методами, являются строго доказанными и их достоверность не вызывает сомнений, конечно с учетом принятых при выводе допущений. Поэтому аналитические зависимости используются в качестве своеобразных эталонов, с которыми сопоставляются результаты, получаемые другими методами.

  2. Аналитические модели имеют большую познавательную ценность. Аналитические зависимости определяют характеристики для всей области значений параметров и несут в себе информацию о поведении соответствующих систем при любых сочетаниях параметров. На основе аналитических моделей легко определяются экстремальные и предельные значения характеристик и оцениваются эффекты от изменения параметров.

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

^ 3.2. Потоки заявок

Простейший поток. При аналитическом моделировании характеристики системы вычисляются наиболее просто для потока заявок, называемого простейшим. Простейший поток – это поток заявок, который обладает следующими свойствами: 1) стационарность; 2) отсутствие последействия; 3) ординарность. Стационарность означает постоянство вероятности того, что в течение определенного временного интервала поступит одинаковое количество заявок вне зависимости от расположения интервала на оси времени. Отсутствие последействия заключается в том, что поступившие заявки не оказывают влияния на будущий поток заявок, т.е. заявки поступают в систему независимо друг от друга. Ординарность – это значит, что в каждый момент времени в систему поступает не более одной заявки. Любой поток, обладающий этими свойствами, является простейшим.

У простейшего потока интервалы времени между двумя последовательными заявками – независимые случайные величины с функцией распределения:

(3.1)

Такое распределение называется экспоненциальным (показательным) и имеет плотность

(3.2)

математическое ожидание длины интервала

(3.3)

дисперсию

(3.4)

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

Простейшие потоки заявок обладают следующими особенностями:

1. Сумма независимых, ординарных, стационарных потоков с интенсивностями сходятся к простейшему потоку с интенсивностью (3.5)

при условии, что складываемые потоки оказывают примерно одинаковое малое влияние на суммарный поток.

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

3. Интервал времени между произвольным моментом времени и моментом поступления очередной заявки имеет экспоненциальное распределение с таким же математическим ожиданием , что и интервал времени между двумя последовательными заявками.

4. Простейший поток создает тяжелый режим функционирования системы, поскольку, во-первых, большое число (63%) промежутков времени между заявками имеет длину меньшую, чем ее математическое ожидание , и, во-вторых, коэффициент вариации, равный отношению среднеквадратического отклонения к математическому ожиданию:

и характеризующий степень нерегулярности потока, равен единице, в то время как у детерминированного потока коэффициент вариации , а для большинства законов распределения /

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

^ Пуассоновский поток. Пуассоновским потоком называется ординарный поток заявок с отсутствием последействия, у которого число заявок, поступивших в систему за промежуток времени , распределено по закону Пуассона:

(3.6)

где - вероятность того, что за время

в систему поступит точно заявок; - интенсивность потока заявок.

Математическое ожидание и дисперсия распределения Пуассона равны .

Следует подчеркнуть, что распределение Пуассона дискретно. Стационарный пуассоновский поток является простейшим. Если нестационарный поток, интенсивность которого представляет собой функцию времени , описывается законом распределения Пуассона, то такой поток называется пуассоновским, но не простейшим. В распределении Пуассона длительности интервалов между двумя последовательными заявками – это случайные величины с экспоненциальным распределением.

^ 3.3. Вероятностные модели процессов

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

Случайные величины, соответствующие параметрам, характеристикам и другим элементам моделей, могут представляться в виде:

  • статистической выборки , определяющей случайную величину набором значений, имевших место в некоторой реализации случайного процесса;

  • закона распределения случайной величины;

  • математического ожидания и дисперсии.

^ Марковские модели.

Общие сведения. В теории массового обслуживания к наиболее изученным и исследованным относятся модели, у которых случайный процесс функционирования относится к классу Марковских процессов, т.е. Марковские модели.

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

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



Рис. 3.1. Пример графа состояний

Описание Марковской модели. Для описания поведения системы в виде Марковской модели следует определить понятие состояния системы; выявить все состояния, в которых может находиться система; указать, в каком состоянии находится система в начальный момент; построить граф состояний, т.е. изобразить все состояния, например, кружками и возможные переходы из состояния в состояние – стрелками, соединяющими состояния (на рис. 3.1. выделено пять состояний); разметить граф, т.е. для каждого перехода указать интенсивность потока событий, переводящих систему из состояния в состояние :

(3.7)

где - вероятность перехода из состояния в состояние за время от до .

Для стационарных Марковских процессов интенсивности переходов не зависят от времени: , тогда .

Понятие состояния зависит от целей моделирования. В одном случае, например, оно может быть определено по состояниям элементов, каждый из которых может быть «свободен» или «занят»; в другом случае состояние системы определяется числом заявок, находящихся на обслуживании и в очередях.

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

Дискретная марковская цепь определяется:

  • множеством состояний ;

  • матрицей вероятностей переходов , , , элементы которой характеризуют вероятности перехода процесса из состояния в состояние ;

  • вектором начальных вероятностей , определяющим вероятности того, что в начальный момент времени процесс находится в состоянии .

Марковская цепь может быть представлена графом, вершины которого соответствуют состояниям цепи, а дуги ненулевым вероятностям переходов. На рис. 3.2 (а) представлен граф марковской цепи, имеющей 5 состояний и вектор начальных вероятностей . Вероятности переходов показаны на дугах графа.



Рис. 3.2. Графы марковских цепей: а – дискретная, б – непрерывная

Марковская цепь порождает множество реализаций случайного процесса , который представляется последовательностью состояний соответствующих моментам времени . В зависимости от возможности перехода из одних состояний в другие марковские цепи делятся на поглощающие и эргодические цепи.

Поглощающая марковская цепь содержит поглощающее состояние, достигнув которого, процесс прекращается. Признаком поглощающей цепи является наличие в матрице диагонального элемента . Так, марковская цепь, представленная на рис. 3.2, является поглощающей, так как содержит поглощающее состояние . Для поглощающей цепи любой процесс в результате шагов при с вероятностью 1 попадает в поглощающее состояние.

Поглощающие марковские цепи широко используются в качестве временных моделей программ и вычислительных процессов. При моделировании программы состояния цепи отождествляются с модулями (операторами) программ, а матрица переходных вероятностей определяет порядок переходов между модулями, зависящий от структуры программы и исходных данных, значения которых определяют развитие вычислительного процесса. На такой модели можно вычислить число обращений к модулям программы и время выполнения программы, оцениваемой средними значениями, дисперсиями и при необходимости – распределениями. Аналогично вычислительный процесс, сводящийся к последовательности обращений к ресурсам системы в порядке, определяемом программой, можно представить поглощающей марковской цепью, состояния которой соответствуют использованию ресурсов системы – процессора и периферийных устройств, а переходные вероятности отображают порядок обращения к различным ресурсам.

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

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

Непрерывная марковская цепь, поведение которой в любой момент времени подчиняется одному и тому же закону, называется однородной. Такая цепь задается матрицей интенсивностей переходов , . Интенсивность переходов определяется следующим образом:

, ,

где - вероятность перехода из состояния в состояние за время .

Это означает, что если процесс находится в состоянии , то вероятность перехода в течение промежутка времени в состояние , отличное от равно . Аналогично вероятность перехода процесса из состояния в состояние равно .

Интенсивность переходов должна удовлетворять условию , (1)

На рис. 3.2 (б) представлен граф непрерывной Марковской цепи с тремя состояниями и дугами, нагруженными интенсивностями переходов. Матрица для данного графа, составленная с учетом условия (1) имеет вид:



Основной характеристикой непрерывной Марковской цепи является стационарное (финальное) распределение вероятностей состояний , где - вероятности пребывания процесса в состояниях соответственно. Значение вероятностей определяется решением системы уравнений:

,

(2)

Систему уравнений (2) называют уравнениями равновесия. Они составляются по графу Марковской цепи с учетом того, что в каждом состоянии входящий поток должен равняться исходящему потоку. Например, для цепи на рис. 3.2 (б) имеем:

Состояние

Интенсивность входящего потока

Интенсивность исходящего потока



















Система уравнений равновесия получается из условия равенства интенсивности входящего и исходящего потока

;

;

.

В соответствии с Марковским свойством вся предыстория процесса сказывается на его поведении в будущем только через текущее состояние, которое и определяет дальнейший ход процесса. Таким образом, нет необходимости знать, как долго процесс находится в текущем состоянии. Отсюда следует, что распределение остающегося времени пребывания процесса в состоянии должно зависеть только от самого состояния, а не от времени пребывания в нем. Этим свойством обладает только одно распределение – экспоненциальное, функция плотности вероятности которого имеет следующий вид: , где - параметр распределения, определяющий математическое ожидание случайной величины . Таким образом, непременное свойство непрерывного Марковского процесса – экспоненциальность распределения времени пребывания в каждом из состояний.

^ Уравнения Колмогорова для вероятностей состояний. Исчерпывающей количественной характеристикой Марковского процесса является совокупность вероятностей состояний, т.е. вероятностей того, что в момент процесс будет находиться в состоянии .

Рассмотрим, как определяются вероятности состояний по приведенному на рис. 3.3 графу состояний, считая все потоки простейшими. В случайный момент времени система может находиться в одном из состояний с вероятностью . Придадим малое приращение и найдем, например, - вероятность того, что в момент система будет в состоянии . Это может произойти, во-первых, если система в момент была в состоянии и за время не вышла из него; во-вторых, если в момент система была в состоянии или и за время перешла в состояние .

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

.

Найдем вероятность перехода в состояние . Если в момент система находилась в состоянии с вероятностью , то вероятность перехода в состояние за время равна

.

Аналогично для состояния

.

Складывая вероятности , и , получим

.

Раскроем квадратные скобки, перенесем в левую часть и разделим обе части на :

.

Если устремить к нулю, то слева получим производную функции :

.

Аналогичные уравнения можно вывести для всех остальных состояний. Получается система дифференциальных уравнений:



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

Представим уравнения Колмогорова в общем виде:

, (3.8)

Здесь учтено, что для состояний, не имеющих непосредственных переходов, можно считать .

Предельные вероятности состояний. В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого состояния можно перейти в любое другое за конечное число шагов, то существуют предельные (финальные) вероятности состояний: , (3.9)

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

Для вычисления предельных вероятностей нужно все левые части в уравнениях Колмогорова (3.8) положить равными нулю и решить полученную систему линейных алгебраических уравнений:

, (3.10)

В связи с тем, что эти уравнения однородные, т.е. не имеют свободного члена и, значит, позволяют определить неизвестные только с точностью до произвольного множителя, следует воспользоваться нормировочным условием (3.11)

и с его помощью решить систему уравнений.

^ Модель размножения и гибели. Разновидностью Марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели. Она характерна тем, что ее граф состояний имеет вид цепи (рис.3.2). Особенность этого графа состоит в том, что каждое из средних состояний связано прямой и обратной стрелками с каждым из соседних состояний – правым и левым, а крайние состояния и - только с одним соседним состоянием.



Рис. 3.2. Граф состояний модели размножения и гибели

В этой модели формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова, имеют вид:

(3.12)

(3.13)

Эти формулы часто используют при решении задач теории массового обслуживания.

^ 3.4. Статистические модели

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

Математическая статистика предлагает обширный набор моделей и методов установления статистических закономерностей, присущих исследуемым объектам. Наиболее широкое применение получил регрессионный анализ.

Регрессионный анализ состоит в построении функций , связывающих характеристики (зависимые переменные) с параметрами (независимыми переменными), на основе статистической выборки, содержащей статистически независимые данные. Статистическая независимость данных состоит в том, что значения признаков разных наблюдений статистической выборки не должны зависеть друг от друга. Чтобы проявились статистические зависимости, число наблюдений должно превосходить число признаков в 6–8 раз. Выборка должна быть однородной, то есть относиться к объектам одного класса.

Зависимость характеристики от параметров представляется в виде линейного полинома



а при необходимости – в виде полинома более высокого порядка

Параметры называются коэффициентами регрессии. Если число признаков , то имеет место уравнение парной регрессии, при – уравнение множественной регрессии. Переменная рассматривается как случайная величина, которая распределена в окрестности среднего значения , зависящего от то есть считается, что переменные влияют лишь на среднее значение . Коэффициенты регрессии оцениваются по методу наименьших квадратов минимизацией дисперсии отклонения уравнения регрессии от наблюдаемых значений , .

При построении регрессионной модели основными являются два момента:

  • выбор числа независимых признаков ;

  • выбор формы полинома, посредством которого представляется зависимость .

Процедуры оценки качества и улучшения моделей реализованы в пакетах прикладных программ статистического анализа.

Регрессионные модели обладают следующими особенностями:

  • они применимы для прогноза значений только при аргументах , принадлежащих области определения переменных, для которой построено уравнение регрессии;

  • уравнения регрессии принципиально необратимы, то есть недопустимо путем тождественных преобразований из уравнения строить уравнение ,поскольку это две совершенно различные регрессии, каждая из которых должна строиться самостоятельно;

  • регрессионные модели не раскрывают механизм взаимосвязи характеристик и параметров и фиксируют лишь количественную взаимосвязь величин.

Регрессионные и другие статистические модели наиболее широко используются для описания рабочей нагрузки, создаваемой прикладными задачами, а также системными процессами (управление заданиями, задачами, данными, ввод–вывод и др.). Применение статистических методов для этого класса объектов объясняется тем, что хотя рабочая нагрузка, как правило, хорошо наблюдаема, однако по своей природе – это чрезвычайно сложный объект. В нем совмещены свойства прикладных задач, технология обработки данных, организация операционной системы и даже конфигурация ЭВМ, для которой разрабатывается программное обеспечение. Поэтому рабочую нагрузку приходится рассматривать как черный ящик и описывать количественные взаимосвязи статистическими методами.

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

^ 3.5. Имитационные модели и методы

Методы имитационного моделирования основаны на представлении порядка функционирования системы в виде алгоритма, который называется имитационной (алгоритмической) моделью. Программа, реализующая модель, содержит процедуры, регистрирующие состояния имитационной модели и обрабатывающие зарегистрированные данные для оценки требуемых характеристик процессов и моделируемой системы.

При построении имитационных моделей широко используется агрегатный подход. Для моделирования заданного класса систем создается набор агрегатов – модулей модели. Агрегаты могут соответствовать элементам систем, например, процессорам, ОЗУ, каналам ввода–вывода, каналам передачи данных и другим элементам, воспроизводя определенные аспекты их функционирования. В качестве агрегатов могут выступать математические объекты, с помощью которых генерируются и преобразуются необходимые процессы. Так, для моделирования систем на основе сетей массового обслуживания в качестве агрегатов представляются источники потоков заявок, систем массового обслуживания, узлы, управляющие распределением заявок по нескольким направлениям, и т.д. По существу агрегат является описанием функции некоторого объекта в аспектах, соответствующих цели моделирования – оценке производительности, надежности и т.д. Функции агрегатов представляются в параметрической форме, то есть в записи функций используются параметры, характеризующие конкретный объект. Так, параметром процессора является производительность (быстродействие), оперативной памяти – емкость, системы массового обслуживания – дисциплина обслуживания, число каналов и распределение длительности обслуживания. Функция агрегата , представляется в алгоритмической форме – в виде процедуры , где параметры – определяют состояние входов агрегата, а – режим его функционирования, – состояние выходов агрегата. В модели агрегат выглядит как модуль (рис. 3.3 (а)), настраиваемый на заданный режим функционирования множеством параметров и преобразующий входные воздействия в выходные состояния в соответствии с функцией агрегата и значениями параметров . Множество агрегатов разного типа составляет базис имитационных моделей заданного класса систем.



Рис. 3.3 Структура агрегатной модели

Имитационная модель собирается путем соединения выходов агрегатов с входами других агрегатов (рис. 3.3 (б)). На рисунке агрегаты обозначены , где тип и – порядковый номер агрегата в модели. Агрегаты и генераторы, формирующие воздействия в соответствии с параметрами и . Состав агрегатов, структура связей между ними и наборы параметров агрегатов определяют модель. Процесс моделирования состоит в реализации процедур в необходимом порядке. При этом значения, формируемые на выходах агрегатов, переносятся на входы, связанных с ними агрегатов, в результате чего вычисляются значения и . Путем обработки данных, наблюдаемых в характерных точках модели (на выходах модулей), получают оценки качества функционирования любого из агрегатов и системы в целом.

Имитационные модели воспроизводят процесс функционирования и свойства исследуемых систем, исходя из априорно известных свойств элементов системы за счет объединения соответствующих модулей в структуру, отображающую исследуемую систему, и имитации функционирования элементов в их взаимодействии.

Исследование ВС имитационными методами включает несколько этапов.

1. ^ Определение принципов построения модели.

Цель этого этапа – сформировать общий замысел модели (состав характеристик и параметров, подлежащих отображению, область определения модели, требования к точности результатов моделирования, тип математической модели, программные и технические средства для описания и реализации модели). На этом этапе выдвигаются гипотезы о свойствах моделируемой системы, принимаются допущения для использования соответствующих математических методов и конкретизируются эксперименты, проводимые на модели.

2. ^ Разработка модели.

Цель этого этапа – создание программы моделирования для ЭВМ. При этом общий замысел модели преобразуется в конкретное алгоритмическое описание. Этап завершается проверкой работоспособности и адекватности модели.

3. ^ Моделирование на ЭВМ.

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

Важнейшее свойство метода имитационного моделирования – универсальность, проявляющаяся в следующем:

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

2. Метод имитации не ограничивает уровень детализации в моделях. С помощью алгоритмов можно воспроизводить любые, сколь угодно своеобразные взаимосвязи между элементами системы и процессы функционирования. Более детальное представление организации и функционирования системы сказывается только на объеме алгоритмического описания модели (программы) и затратах времени на моделирование. Особенности организации и функционирования, препятствующие использованию аналитических методов, легко воспроизводятся в имитационных моделях.

3. Имитационная модель является неограниченным источником данных о поведении исследуемой системы – новые эксперименты на модели позволяют получать дополнительные данные о системе. За счет этого гарантируется детальная оценка характеристик функционирования как системы в целом, так и ее составляющих. Как правило, увеличивая длительность экспериментов на моделях или число экспериментов, то есть время моделирования, можно добиться высокой точности результатов моделирования.

Недостатки имитационных методов – большие затраты времени на моделирование и частный характер получаемых результатов. В имитационной модели процесс функционирования системы воспроизводится во всех, существенных для исследования, деталях за счет последовательного выполнения на ЭВМ операций над величинами. Поэтому для одного прогона модели требуются минуты и часы процессорного времени. При этом оцениваются характеристики системы только в одной точке, соответствующей значениям параметров, введенных в модель перед началом моделирования. Чтобы определить зависимость между характеристиками и параметрами, необходимы многократные прогоны модели, в результате которых значения характеристик определяются для многих наборов параметров. Возможности методов оптимизации параметров на имитационных моделях ограничиваются большими затратами времени на моделирование системы в одной точке.

Несмотря на указанные недостатки, методы имитационного моделирования в силу их универсальности широко используются при теоретических исследованиях и проектировании ВС. Имитационные модели позволяют исследователю и разработчику формировать представления о свойствах системы и, познавая систему через ее модель, принимать обоснованные проектные решения.

^ МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ.

МЕТОД МОНТЕ-КАРЛО.

Возникновение метода относится к 1949 г. и связано с именами американских ученых Д. Неймана и С. Улама.

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

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

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



Будем считать, что и . Ограничение на функцию , изображенную на рис. 1, несущественно, так как можно использовать масштабирование. Необходимо найти площадь области , ограниченной кривой осью и ординатами .



Пусть в квадрат случайно вбрасывается точка, координаты которой независимо и равномерно распределены в интервале . Какова вероятность того, что точка попадает в область под кривой? Очевидно, что вероятность этого события численно равна площади . Для первой точки генерируем пару величин (координат) и проверяем условие

(1)

Если условие (1) выполняется, то выбранная случайная точка с координатами попала в область под кривой. Далее берется еще пара случайных величин , и для всех этих пар проверяется условие (1). Затем число пар , для которых выполнилось условие (1), делится на число всех взятых пар . Если число достаточно велико, то в силу закона больших чисел получаем величину близкую к вероятности попадания точки в область . Величина является, следовательно, приближенным значением искомого интеграла.

Метод Монте-Карло обладает следующими особенностями:

  • является приближенным, точность повышается с увеличением числа реализаций;

  • обладает малой связностью, что сокращает объем данных для хранения в памяти, особенно для многомерных задач;

  • устойчив по отношению к случайным сбоям, так как одиночная ошибка мало сказывается на окончательном результате;

  • результаты, получаемые этим методом, также как и оценки их точности носят вероятностный характер;

  • не существует общей теории перехода от конкретной задачи к вероятностной схеме, позволяющей применить метод.

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

Датчики равномерно распределенных случайных чисел


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

,

где - константы; - большое положительное целое число.

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

^ Моделирование случайных событий и дискретных величи

Для моделирования случайного события , наступающего с вероятностью , берется значение случайного числа, равномерно распределенного на интервале , и сравнивается с . Если , то считается, что произошло событие .

Предположим, что дискретная случайная величина может принимать значения с вероятностями . При этом ; .

Тогда берется значение случайного числа, распределенного равномерно на интервале , и определяется такое , принадлежащее совокупности , при котором удовлетворяется неравенство

.

Тогда случайная величина принимает значение .

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

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

Для определения одного конкретного значения случайной величины берется значение случайного числа, равномерно распределенного на интервале . Затем находится такое , при котором .

Тогда искомое случайное число равно (рис. 2б). Это же правило применимо и при задании случайной непрерывной величины интегральной функцией распределения , как показано на рис. 2в. Оно вытекает из теоремы: если случайная величина имеет плотность распределения , то ее распределение (2)

является равномерным на интервале .

Для некоторых законов распределения (экспоненциальный, Эрланга) получены простые аналитические зависимости . Так, для получения конкретного значения случайного числа с экспоненциальным законом распределения подставим в формулу (2) и плотность распределения:

.

После интегрирования получается .

Отсюда .

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

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




Рис. 2. Графики для определения значения случайного числа

по дискретной и интегральной функции распределения

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

Имитационное моделирование систем по принципу особых состояний проводится с постоянным использованием датчиков случайных чисел для формирования всех управляющих последовательностей.


Скачать файл (1024.9 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru