ИПиС. Литература по теме Тема Информационная система как сложная система
 Скачать 2.5 Mb.
|
|
Тема 7. Имитационное моделирование информационных процессов и систем Цели изучения темы: изучить сущность подхода на основе методологии имитационного моделирования к анализу и синтезу информационных процессов и систем. Задачи изучения темы: изучить сущность и границы применимости метода статистических испытаний; изучить основные принципы компьютерной имитации стохастических процессов; понять возможности моделирующих комплексов для создания и применения имитационных моделей. Успешно изучив тему, Вы: Получите представление о: когда применяется и как практически реализуется модель на основе метода статистических испытаний; принципах построения и механизме программной имитации стохастических процессов. Будете знать: как можно создавать модели с помощью систем имитационного моделирования; из чего состоят и как следует анализировать результаты прогонов программной модели. Вопросы темы: 1. Метод статистических испытаний. 2. Концепции имитационного моделирования. 3. Создание имитационных моделей с помощью систем моделирования. 4. Примеры имитационных моделей. 113 Вопрос 13. Метод статистических испытаний. Аналитические модели, рассмотренные ранее, могут с успехом применяться на этапе системного анализа и для решения ряда задач этапа проектирования, когда требования к точности результата не являются слишком строгими. Такими задачами могут быть задачи выбора конфигурации или модели сервера, где требуется определить только класс выбираемого устройства или подсистемы. Однако в ряде практических ситуаций применение аналитических моделей приводит к большой потере точности получаемого результата из-за того, что модели строятся на слишком приблизительном описании реальных процессов. В этих случаях можно использовать подход на основе имитационного моделирования процессов, который позволяет практически с любой степенью точности описать исследуемые процессы и отличается универсальностью применения. Рассмотрение имитационных моделей начнем с метода статистических испытаний. Статистическое моделирование является разновидностью имитационного моделирования и состоит в обработке данных о системе (модели) с целью получения статистических характеристик системы. Чаще всего оно применяется как способ исследования процессов поведения систем в условиях, когда внутренние взаимодействия в системах неизвестны, и построение аналитической модели явления затруднено или вовсе неосуществимо. Метод может применяться и на этапе системного анализа информационных систем, но основными для его применения являются задачи исследования операций, массового обслуживания и многие другие, связанные со случайными процессами. Эти задачи возникают в основном на этапах системного проектирования и разработки. Смысл метода Монте-Карло состоит в том, что исследуемый процесс моделируется путем многократных повторений его случайных реализаций (Рис. 30). 114 n=0 Провести испытание n=n+1 n Да Нет Найти итоги 1 2 3 4 5 Рис. 30. Схема метода Монте-Карло Единичные реализации называются статистическими испытаниями, в силу чего метод называется также методом статистических испытаний. Поясним применение метода Монте-Карло к решению задачи оценивания величины критического пути сетевой модели, показанной на Рис. 28. На примере этой модели рассматривался метод нахождения величины критического пути при детерминированных условиях. Будем теперь предполагать, что длительности работ не являются неизменными, а варьируются в зависимости от случайных факторов, что, как уже отмечалось, встречается на практике значительно чаще. Каждое испытание (блок 2 на Рис. 30) будет включать два шага: 1) генерацию значений длительностей всех работ t(i,j) на графе сетевой модели; 2) расчет на основе применения описанного ранее метода критического пути величины критического пути Ткр для данной совокупности значений длительностей работ. Шаг 1 выполняется на основе наблюдений за случайными величинами, представляющими собой длительности работ графа. Результат этих наблюдений выражается некоторым законом распределения вероятностей. Генерация случайных величин для каждой их реализации проводится с помощью программных средств. Эти средства строятся на основе специальных алгоритмов получения псевдослучайных чисел, т.е., не являющихся, строго говоря, результатом 115 измерения характеристик каких-то физических явлений, а достаточно точно их имитирующих. К настоящему времени предложено и реализовано большое количество этих алгоритмов, которые позволяют, с одно стороны, получить достаточно хорошие выборки значений и, с другой стороны, весьма сводят к минимуму потребности в вычислительных ресурсах, которые необходимы для выполнения программ. Шаг 2 в данном случае состоит в обработке данных, полученных в результате выполнения шага 1, а именно, массива N значений кр T . Если задача ставится, как задача нахождения только среднего значения кр T , то обработка сведется к выполнению лишь одной операции: 1 N i кр i кр T T N , где i кр T - значение кр T , полученное в i-ом испытании. Однако данные, собранные в результате моделирования, содержат в себе более полную информацию относительно исследуемого показателя. Поэтому целесообразно использовать результат для построения гистограммы частот значений кр T . Например, моделирование методом Монте-Карло графа Рис. 28, в котором длительности работ распределены по равномерному закону со средними значениями, показанными на рисунке, и величиной полуинтервалов изменений равными 1/3 средних значений, даст следующие результаты: Гистограмма распределения длины критического пути MIN MAX N % <<< 14 1032 0.1032 14 15 1551 0.1551 15 16 2133 0.2133 16 17 2166 0.2166 17 18 1712 0.1712 18 19 956 0.0956 19 20 365 0.0365 20 >>> 85 0.0085 Tкр.ср=16.1486. 116 Представление гистограммы частот в графическом виде дано на Рис. 31. 0,00 0,05 0,10 0,15 0,20 0,25 <14 15 16 17 18 19 20 >20 О тн о си тель н ая час то та Ткр Гистограмма частот Ткр Рис. 31. Пример гистограммы частот кр T По этой гистограмме можно оценить величину вероятности выполнения совокупности работ в течение заданного времени ( ) кр пл P T T Например, если нужно оценить, с какой вероятностью может быть выдержан срок пл T =18, то находим: ( ) 0,1032+0,1551+0, 2133+0, 2166+0,1712=0,8594 кр пл P T T что можно считать очень большой величиной. Ниже приводится текст программы на языке С++ для выполнения на ее основе практического задания. 117 // // Нахождение распределения величины критического пути сетевого графа методом Монте-Карло // // Заголовочные файлы --------------------------------------------------------------------------------------------------- #include «stdafx.h» //стандартные заголовки #include //функции работы с системным временем (time) #include //математические функции (log()) #include //для функции creat() #include //потоковый класс #include //значения параметров amode #include //манипуляторы ввода-вывода #include //константы предельных значений // Функции -------------------------------------------------------------------------------------------------------------------- // Равномерное распределение [0,1] (конгруэнтный алгоритм) float rundum(void) { long static bx = (long)time(NULL); unsigned long m =2<<31 - 1; if (bx % 2 == 0) bx++; bx = (16807 * bx) % m; return((long double) bx / (long double)m); } //Нормальное распределение float normal(float m, float s) { float a; int i; for (i=0,a=0.0; i<12;i++) a+=rundum(); return(m+(a-6.0)*s); } //Экспоненциальное распределение (метод обратной функции) float expont(float m) { return(m*(-log(rundum()))); } //Равномерное распределение на произвольном интервале [m-s,m+s] float unifrm (float m, float s) { return (m-s + 2*s*rundum()); } //Треугольное распределение float triplex(float a, float m, float b) { float x,r; r=rundum(); if (r<=(m-a)/(b-a)) x=a+sqrt(r*(m-a)*(b-a)); else x=b-sqrt((1.0-r)*(b-m)*(b-a)); return(x); } 118 //Длительность работы для текущего испытания float duration (int flag, float parm_1, float parm_2, float parm_3) { if (flag == 1) return(parm_1); if (flag == 2) return(normal(parm_1,parm_2)); if (flag == 3) return(expont(parm_1)); if (flag == 4) return(unifrm(parm_1,parm_2)); if (flag == 5) return(triplex(parm_1,parm_2, parm_3)); } //Вывод гистограммы распределения void printhist(char hdr[],int fileNumb,int dim,float bounds[],int counts[]) {ofstream fileOut; int i; float sum; fileOut.attach (fileNumb); fileOut << hdr << setprecision(4); fileOut << «\n---------------------------------------------» <<«\n»< << « « << static_cast } fileOut << «\n---------------------------------------------»; } int APIENTRY WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance, LPSTR lpCmdLine,int nCmdShow) { //Параметры моделирования ========================================================== int Nexp=10000; //число испытаний метода Монте-Карло int stock=5; //номер конечной вершины (стока) графа работ int distr=4; //вид распределения длительностей работ: // 1-постоянное, // 2-нормальное, // 3-экспоненциальное // 4-равномерное // 5-треугольное 119 //Параметры распределения длительности работ:::::::::::::::::::::::::::::::::::::::::::::::::::: float t_1[100][100]={FLT_MA X}; //средние(distr=1-3),минимальные(distr=4) t_1[0][1]=1; t_1[0][2]=5; t_1[1][2]=3; t_1[1][3]=2; t_1[2][3]=6; t_1[2][4]=5; t_1[3][4]=0; t_1[3][5]=5; t_1[4][5]=3; float t_2[100][100]={FLT_MA X}; //ст.откл.(distr=2),полуинтервалы(distr=4),наиб.вероятн.(dis tr=5) t_2[0][1]=t_1[0][1]/3; t_2[0][2]=t_1[0][2]/3; t_2[1][2]=t_1[1][2]/3; t_2[1][3]=t_1[1][3]/3; t_2[2][3]=t_1[2][3]/3; t_2[2][4]=t_1[2][4]/3; t_2[3][4]=t_1[3][4]/3; t_2[3][5]=t_1[3][5]/3; t_2[4][5]=t_1[4][5]/3 float t_3[100][100]={FLT_MA X}; //максимальные(distr=5) float bounds[]={FLT_MIN,14.0f,15.0f,16.0f,17.0f,18.0f,19.0f,20.0f,FLT_MAX}; //границы интервалов //Организация вывода результатов ----------------------------------------------------------------------------------------- -- int reportfile=creat («D:\\MyResults.txt», S_IWRITE); //создание файла ofstream fileOut; //выводной файл fileOut.attach (reportfile); //включение в поток //Переменные ===================================================================== long i,j,k; int const dim = sizeof bounds / sizeof (float)-1; //число интервалов int counts [dim]={ 0 }; //счетчики float task[100][100]; //длительности работ в конкретном испытании float times[50]; //моменты наступления событий float Tsum=0; //накопитель Ткр 120 //Испытания ======================================================================= for (k = 1; k <= Nexp; k++) //повторение испытаний { //Генерация длительностей работ для текущего испытания for(i = 0; i <99; i++) for (j = 0; j <99; j++) if (t_1[i][j] //Сбор статистики for(i=0;i Tsum+=times[stock]; } //Итоги::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: printhist(«Гистограмма распределения длины критического пути», reportfile, dim, bounds, counts); fileOut << «\nTкр.ср=« << Tsum / Nexp; //============================================================================== = return(0); } Значения параметров моделирования задаются в разделе с заголовком (строкой комментария) «Параметры моделирования» (выделен в вышеприведенном тексте полужирным шрифтом). В разделе задаются: Nexp Число повторений экспериментов метода Монте-Карло stock Номер конечной вершины графа сетевой модели distr Целочисленный код вида распределения длительностей работ в сетевом графе (перечень возможных видов распределения и соответствующие коды см. в тексте программы) t_Х Двумерные массивы, задающие параметры распределения для каждой работы (i,j) сетевого графа. Смысл параметров t_1, t_2, t_3 зависит от вида распределения, задаваемого значением distr (смысл параметра, задаваемого каждым массивом см. в тексте программы). bounds Массив с границами диапазонов (интервалов) значений критического пути, используемый для сбора статистики попаданий значения в каждый интервал. Результаты выводятся в файл, обозначаемый переменной reportfile. 121 Недостатком метода Монте-Карло являются большие затраты машинного времени, требуемые для достижения большей статистической точности (известно, что для уменьшения дисперсии результата в k раз, число испытаний необходимо увеличить в 2 k раз). Вопрос 14. Концепции имитационного моделирования. Аналитические модели, как и модели вообще строятся для некоторых допущений. В случае аналитических моделей эти допущения могут ухудшать точность получаемых на их основе результатов в силу ограничений, накладываемых используемым математическим аппаратом. Кроме того, получение аналитических выражений для расчета показателей часто представляет большую трудность. Альтернативным подходом к решению задач оценки показателей является исследование системы на основе имитационной модели, с помощью которой можно получить результаты для случаев произвольных распределений временных интервалов и других случайных величин. Такую модель можно построить с помощью специальной моделирующей системы, что ускоряет процесс создания, улучшает характеристики конечного результата (программной модели) и имеет ряд других достоинств. Как уже обсуждалось ранее поведение (процесс функционирования) динамической дискретной системы можно рассматривать как последовательность состояний 1 2 ( ), ( ),... ( ) n z t z t z t в моменты времени 1 2 , ,... n t t t . При этом факты смены состояния системой рассматриваются как события. В основу идеи имитационного моделирования положен принцип, согласно которому на ЭВМ осуществляется воспроизведение (имитация) процесса функционирования исследуемой системы в контексте смены ее состояний в результате происходящих в ней событий. В процессе проведения имитации собираются данные о состоянии системы или отдельных ее элементов в определенные моменты времени, что позволяет в конце процесса моделирования провести агрегирование и обработку собранных данных и получить значения нужных исследователю показателей. Пусть, например, нам необходимо исследовать работу системы массового обслуживания (СМО) с очередью и одним обслуживающим прибором (Рис. 32). 122 Рис. 32. Одноканальная система массового обслуживания с очередью Заявки, образующие входящий поток, поступают в систему в случайные моменты времени. Если обслуживающий прибор (канал) свободен, заявка принимается на обслуживание, которое продолжается некоторое время (его величина является, как правило, также случайной), после чего она уходит из системы (выходящий поток). Если в момент прихода заявки канал занят, заявка попадает в очередь ждущих заявок. Решая задачу нахождения показателей системы, для описания состояния процесса достаточно использовать один параметр ( ) i z t , который означает число заявок в системе в момент времени i t Имитацию процесса обслуживания заявки в можно провести, определяя моменты ожидаемого изменения состояния (наступления события), связанных с изменением состояния ( ) i z t . В данном случае, это моменты поступления очередной заявки в систему и моменты окончания обслуживания заявки, находящейся в обслуживающем приборе. Моменты наступления будущих событий могут быть найдены на основе рекуррентных выражений с помощью функций распределения интервалов времени путём проведения случайных испытаний аналогично тому, как это производилось в методе статистических испытаний. Это позволяет построить алгоритм имитации, состоящий из повторения следующей совокупности шагов: находится момент наступления ближайшего события, событие с минимальным временем — наиболее раннее событие; стрелки модельных часов передвигаются на этот момент времени; определяется тип происшедшего события; в зависимости от типа события модифицируются значения переменных, описывающих состояние системы (в данном случае, число находящихся в системе заявок), и определяются следующие моменты наступления событий. Логическая последовательность шагов моделирования показана на Рис. 33. 123 Перевести модельные часы = T T мин Какое событие наступило? z=z-1 Определить момент ухода следующей заявки Собрать статистику Собрать статистику Определить момент следующей заявки прихода Обработать данные и вывести результаты z=z+1 Уход заявки Приход заявки Нет Да Определить момент наступления ближайшего события T мин Задать начальные условия: Т=0 Тприхода=0 Тухода= Тмод= z=0 const T ? Рис. 33. Блок-схема имитации процессов в одноканальной СМО с очередью |