Механики
 Скачать 4.29 Mb.
|
|
7600 00 0,7600 248 Раздел 6. Имитационное моделирование Метод произведений аналогичен методу квадратов. Отличие состоит в том, что перемножаются два n -разрядных целых числа, одно из которых, называемое ядромили множителем, не меняется, а второе, называемое множимым, формируется из n последних (правых) разрядов полученного 2 n -разрядного числа, представляющего собой произведение ядра и множимого. Естественно, что вначале, как и в методе квадратов, необходимо грамотно выбрать исходные значения ядра и множителя. Пример 3. Ядро = 5167; множитель = 3729 Множимое Произведение Случайное число 3729 19 2677 43 0,2677 7743 40 0080 81 0,0080 8081 41 7545 27 0,7545 4527 23 3910 09 0,3910 1009 05 2135 03 0,2135 3501 …. … Здесь, в отличие от предыдущего примера, в качестве следующего значения множителя выбираются не средние разряды полученного произведения, а последние n разрядов произведения. Конгруэнтные методы генерирования случайных чисел получили наиболее широкое распространение для формирования на ЭВМ псевдо- случайных последовательностей [13]. Два целых числа a и b называются конгруэнтными (сравнимыми) по модулю m , где m – целое число, если разность ( b a − ) делится на m без остатка, а числа a и b дают одинаковые остатки от деления на m Например, 2568 и 148 (по модулю 10), 1746 и 511 (по модулю 5), 6493 и 2221 ( по модулю 2) и т.д. Конгруэнтные методы описываются в виде рекуррентного соотноше- ния следующего вида: ...) , 2 , 1 , 0 ( ) (mod 1 = + = + i m X X i i µ λ , где m X i , , , µ λ – неотрицательные целые числа; 0 X – начальное значение псевдослучайной последовательности; λ – множитель; µ – аддитивная константа; m – модуль. Каждое новое значение 1 + i X псевдослучайной последовательности представляет собой целочисленный остаток от деления на модуль m суммы произведения предыдущего значения i X на множитель λ и аддитивной константы µ . Последовательность псевдослучайных чисел в интервале (0; 1) формируется путем деления полученных целочисленных значений i X на модуль m : ...) , 2 , 1 ( / = = i m X x i i Описанный метод генерирования псевдослучайных чисел получил название смешанного конгруэнтного метода. Раздел 6. Имитационное моделирование 249 В некоторых случаях используется более простой метод генерирования псевдослучайных чисел, представляющий собой частный случай смешанного метода, когда 0 = µ , и получивший название мультипликативного конгруэнтного метода. В этом случае рекур- рентное соотношение имеет вид: ...) , 2 , 1 , 0 ( ) (mod 1 = = + i m X X i i λ На каждом шаге полученное случайное число (множимое) умножается на некоторое постоянное число (множитель) и затем делится на другое постоянное число (делитель). В качестве нового случайного числа принимается остаток от деления, который служит дробной частью случайного числа, равномерно распределённого в интервале (0; 1). Пример 4. Первое постоянное число (множитель) = 1357; второе постоянное число (делитель) = 5689. Исходное число Произведение Частное, целая часть Остаток Случайное число 1357 1 8414 49 323 3902 0,3902 3902 5 2950 14 930 4244 0,4244 4244 5 7591 08 1012 1840 0,1840 1840 … … … … Проверка__на_периодичность'>Проверка_генераторов_равномерно_распределенных_псевдослучайных_чисел_«'>6.2.2. Проверка генераторов равномерно распределенных псевдослучайных чисел «Когда не знаешь, что именно ты делаешь, де-лай это тщательно» (Правило для лаборантов) Достоверность и точность результатов имитационного моделирова- ния в значительной степени определяется качеством используемых в мо- делях программных генераторов псевдослучайных последовательностей. Проверка генераторов равномерно распределенных псевдослучайных чисел предполагает формирование большой совокупности или, как гово- рят, представительной выборки случайных чисел и выполнение множества проверочных тестов, позволяющих оценить качество генераторов. Различают три вида проверки программных генераторов равномерно распределенных псевдослучайных чисел: • на периодичность; • на случайность; • на равномерность. Проверка на периодичность требует обязательного определения длины периода, что в значительной степени определяет качество генератора случайных чисел. Чем больше длина периода, тем генератор более качественный. Проверка на случайность. При проверке на случайность программных генераторов двоичных случайных чисел можно использовать 250 Раздел 6. Имитационное моделирование совокупность тестов, а именно тесты проверки: • частот; • пар; • комбинаций; • серий; • корреляции. Тест проверки частот предполагает разбиение диапазона распре- деления на несколько интервалов и подсчет количества (частот или вероятностей) попаданий случайных чисел в выделенные интервалы. Тест проверки пар заключается в подсчете количества "1" для каждого разряда всей совокупности выработанных генератором двоичных случайных чисел. Очевидно, количество "1" во всех разрядах должно составлять примерно 50% от количества выработанных генератором случайных чисел. Тест проверки комбинаций сводится к подсчету "1" в случайных числах, количество которых в среднем должно составлять половину от количества разрядов. Тест проверки серий заключается в подсчете количества различных длин последовательностей одинаковых значений (1 или 0). Тест проверки корреляции заключается в определении коэффициента корреляции между последовательностями случайных чисел, вырабаты- ваемых двумя разными генераторами. Проверка на равномерность. При проверке на равномерность можно использовать тест проверки частот, так как гистограмма частот хорошо отражает равномерность распределения случайных чисел по всему диапазону изменения. 6.2.3. Методы формирования псевдослучайных чисел с заданным законом распределения Методы формирования псевдослучайных чисел с заданным законом распределения основаны на использовании генераторов равномерно распределённых случайных величин. При этом наибольшее распростра- нение получили следующие методы: • аналитический (метод обратной функции); • табличный; • метод композиций, основанный на функциональных особенностях генерируемых распределений. Аналитический метод заключается в построении математической зависимости, связывающей значения случайной величины с заданным законом распределения со значениями случайной величины, распреде- лённой равномерно в интервале (0; 1). Суть аналитического метода иллюстрируется на графике (рис.6.3). Пусть задана некоторая функция распределения ) ( x F , значения которой лежат в интервале (0; 1). Положим, что имеется генератор равномерно Раздел 6. Имитационное моделирование 251 распределённых в том же интервале случайных чисел: ) 1 ; 0 ( ∈ S . Тогда, генерируя последовательность значений , , , 3 2 1 s s s и откладывая их по оси ординат, можно найти соответствующие значения , , , 3 2 1 x x x случайной величины X , распределённой по заданному закону ) ( x F Выведем аналитическую зависимость для расчета значений случайной величины, распределённой по экспоненциальному закону с функцией: x e x F α − − = 1 ) ( , где 0 > α – параметр экспоненциального распределения. Для этого, в соответствии с выше изложенным, необходимо решить уравнение s x F = ) ( , где s – значение равномерно распределённой в интервале (0; 1) случайной величины. Таким образом, имеем: s e x = − − α 1 или s e x − = − 1 α Логарифмируя левую и правую части последнего выражения, после некоторых преобразований получим: ) 1 ln( 1 s x − − = α или s x ln 1 α − = Отметим, что α 1 представляет собой математическое ожидание экспоненциально распределённой случайной величины. Оба полученных выражения равнозначны, поскольку с позиций теории вероятностей случайные величины s и ) 1 ( s − распределены по одному и тому же равномерному закону в интервале (0; 1). В то же время, последнее выражение предпочтительнее, поскольку не требует выполнения «лишней» операции вычитания, что позволяет уменьшить время моделирования с учетом того, что в процессе моделирования генерируются миллионы случайных чисел. ) (x F X 0 1 685 0 1 = s 243 0 2 = s 976 0 3 = s 2 x 1 x 3 x Рис.6.3. Графическая иллюстрация аналитического метода 252 Раздел 6. Имитационное моделирование Достоинства аналитического метода: • высокая точность метода; • не требуется составления и хранения в памяти таблиц, как в табличном методе. Недостатки аналитического метода: • метод распространяется только на те функции, которые позволяют вычислить интеграл от функции плотности аналитически; • использование численных методов вычисления интегралов приводит к погрешностям и большим затратам машинного времени; • выражение, используемое для вычислений, содержит в себе функции вычисления логарифмов, возведения в степень, вычисления радикалов, что требует значительных затрат машинного времени. Табличный метод заключается в формировании таблицы, содержа- щей пары чисел: значение функции распределения ) (x F и соответствую- щее ему значение x случайной величины. В качестве аргумента при обращении к таблице используется значение ) 1 ; 0 ( ∈ s равномерно распре- деленной случайной величины S , задающее значение функции распреде- ления ) (x F , а в качестве функции – значение x случайной величины X с соответствующим законом распределения ) (x F Значение случайного числа, находящегося между узлами табуляции, обычно рассчитывается методом линейной интерполяции. В ранних версиях GPSS для генерирования случайных чисел, распределённых по экспоненциальному закону, использовался табличный генератор со следующими значениями функции распределения ) (x F (от 0 до 0.9997) и соответствующими им значениями случайной величины x (от 0 до 8): ) (x F 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.75 0.8 0.84 0.88 x 0 0.104 0.222 0.335 0.509 0.69 0.915 1.2 1.38 1.6 1.83 2.12 0.9 0.92 0.94 0.95 0.96 0.97 0.98 0.99 0.995 0.998 0.999 0.9997 2.3 2.52 2.81 2.99 3.2 3.5 3.9 4.6 5.3 6.2 7 8 Представленные в таблице значения ) (x F и x соответствуют экспо- ненциальному распределению с математическим ожиданием, равным единице. Если математическое ожидание экспоненциально распределённой случайной величины отличается от 1, то полученное с помощью этой таблицы значение случайной величины умножается на значение математического ожидания. Заметим, что табулирование функции выполнено с переменным ша- гом: в начале таблицы шаг изменения аргумента (значений экспоненциаль- ной функции распределения ) (x F ) равен 0.5, а в конце – 0.0007. Это обу- словлено необходимостью обеспечить приемлемую методическую погреш- Раздел 6. Имитационное моделирование 253 ность, возникающую в результате линейной интерполяции при вычисле- нии значений случайной величины, находящихся между узлами табуляции. Достоинства табличного метода: • существует принципиальная возможность построения таблицы для формирования случайных последовательностей с любым законом распределения, в том числе полученного экспериментальным путём; • можно обеспечить любую заданную точность генерирования случайных чисел за счет увеличения количества интервалов табуляции (уменьшения шага табуляции); • для генерирования случайных величин с заданным законом распределения вероятностей требуется только генератор равномерно распределенных случайных чисел и выполнение несложных операций, занимающих мало времени. Недостатки табличного метода: • значительные затраты памяти для хранения большого числа таблиц с разными законами распределений; • наличие методической погрешности, обусловленной применением линейной интерполяции для определения значений случайных чисел, находящихся между узлами табуляции; • для уменьшения методической погрешности формирования слу- чайных последовательностей при использовании линейной интерполяции следует увеличивать количество точек табуляции, что приводит к увеличению размера таблиц и, как следствие, к дополнительным затратам памяти и времени; • в связи с неодинаковой скоростью изменения функции распределения для обеспечения высокой точности формирования случайных последовательностей табулирование должно выполняться с переменным шагом, выбор которого связан с определёнными проблемами. Метод композиций основан на функциональных особенностях вероятностных распределений, таких как распределение Эрланга, гипоэкспоненциальное и гиперэкспоненциальное распределения. Метод используется, как правило, в тех случаях, когда не удаётся получить аналитическим методом решение в явном виде. Например, значения случайных величин, распределённых по закону Эрланга и гипоэкспоненциальному закону могут быть получены путём сложения нескольких экспоненциально распределённых случайных величин, а значе- ния случайных величин, распределённых по гиперэкспоненциальному закону – путём вероятностного формирования смеси из нескольких экспоненциально распределённых случайных величин с разными матема- тическими ожиданиями. Для оценки качества случайных последовательностей с заданным законом распределения наиболее часто используют тест проверки частот и метод доверительного интервала для математического ожидания. 254 Раздел 6. Имитационное моделирование 6.3. Введение в систему имитационного моделирования GPSS World «Ошибаться человеку свойственно, но оконча- тельно всё запутать может только компьютер» (Пятый закон ненадежности) GPSS (General Purpose Simulation System) – общецелевая система имитационного моделирования (СИМ), предназначенная для разработки моделей сложных систем с дискретным и непрерывным характером функционирования и проведения экспериментов с целью изучения свойств и закономерностей процессов, протекающих в них, а также выбора наилучшего проектного решения среди нескольких возможных вариантов. Среди множества реализаций GPSS одной из наиболее доступных и популярных является GPSS World для работы на персональных компьютерах под управлением ОС Windows. GPSS World обладает удобным многооконным пользовательским интерфейсом, встроенными средствами визуализации и интерактивного управления процессом моделирования, обширной библиотекой встроенных процедур, включаю- щей, в том числе, генераторы случайных величин для более чем двух десятков вероятностных распределений. Все это делает процесс модели- рования эффективным и наглядным. В GPSS World включены специальные средства для моделирования большого класса дискретных систем со стохастическим характером функционирования, в частности, систем и сетей массового обслуживания, что позволяет сделать модели ясными и лаконичными. 6.3.1. Состав системы имитационного моделирования GPSS World Система имитационного моделирования GPSS World включает: • язык GPSS – высокоуровневый язык имитационного модели- рования; • язык PLUS (Programming Language Under Simulation) – встроенный в GPSS язык программирования низкого уровня; • компилятор – программа для трансляции (перевода) с языка высокого уровня на язык компьютера. Объектами СИМ GPSS World являются: • «Модель» или «GPSS-модель» – программа, написанная на языке GPSS и представляющая собой последовательность операторов, описывающих логику работы моделируемой системы, каждый из которых реализует некоторую конкретную функцию. • «Процесс моделирования» – непосредственно исполняемый объект, создаваемый в результате трансляции объекта «GPSS-модель»; реализация «процесса моделирования» заключается в перемещении в модели некоторых подвижных объектов, называемых транзактами. |