ФОРМИРОВАНИЕ СЛУЧАЙНЫХ ЧИСЕЛ С ЗАДАННЫМ РАСПРЕДЕЛЕНИЕМ. 

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

Необходимость получения случайных чисел подчиняющихся распределению определенного вида при моделировании связана со случайным характером изучаемых процессов. Для получения таких чисел служит равномерно распределенная последовательность случайных чисел на интервале [0, 1), которая используется для получения случайных чисел любого типа распределения. В программное обеспечение ЭВМ включены специальные программы - датчики случайных чисел, обращение к которым приводит к выдаче случайного значения в интервале [0, 1). Число значащих цифр зависит от реализации датчика случайных чисел и  возможностей ЭВМ. Для описания системы с очередью и одним прибором необходим именно такой генератор. Обычно генератор задан в виде функции и выдает шестизначное случайное число равномерно распределенное на интервале от 0,000000 до 0,999999 включительно. Для удобства дальнейшего изложения будем считать, что эта функция имеет имя RAND.

Алгоритмов  генерирования случайных чисел достаточно много чаще всего используется следующий. Представим для простоты, что необходимо генерировать случайные четырехзначные равномерно распределенные число на интервале от 0,0000 до 0,9999 включительно. Для этого в алгоритме используют два положительных, нечетных целых числа, каждое из которых может содержать до четырех цифр. Первое из этих двух чисел, никогда не меняющее свое значение называется "ядром", второе, изменяющееся - "множителем". Каждый раз, когда надо получить новое случайное число, значение множителя изменяют в соответствии с некоторой последовательностью. Первым шагом алгоритма является умножение ядра на множитель. Результат (в общем случае) - восьмиразрядное целое число. Его используют для получения нового значения множителя, применяемого на следующем шаге алгоритма. При этом правые четыре цифры произведения используются в качестве нового множителя, средние, умноженные на 10-4 - в качестве случайного числа. Например, пусть число 5167 выбрано в качестве ядра, начальное значение 3729. Для выработки первых случайных чисел используют следующие шаги алгоритма:

  1. Получить произведение ядра и множителя: 5167*3729=19267743.

  2. Взять число 7743 (правые четыре цифры произведения) в качестве нового значения множителя.

  3. Число 0,2677 (средние четыре цифры произведения) использовать в качестве случайного числа.

При генерации второго случайного числа его значение будет равно 0,0080 (ядро 5167, умноженное на множитель 7743, дает 40008081 и определяет новый множитель 8081 и случайное число 0,0080) и т.д. Получаемая таким образом последовательность случайных чисел обладает двумя недостатками:

  1. Множитель и ядро могут быть нулями. 

  2. Последовательность случайных чисел, выработанных ранее повторяется. Количество случайных чисел, выработанных прежде, чем они могут повторяться, называется периодом (или длиной) генератора случайных чисел.

Для преодоления первого недостатка необходимо, что бы ядро и множитель были нечетными числами. Второй недостаток устранить сложнее. Вот как это делается в сиcтеме моделирования GPSS, содержащих восемь встроенных датчиков случайных чисел.

  1.  Ядро и множитель заключены в интервале нечетных целых чисел от 1 до 2147483647 включительно.

  2. Любой датчик имеет восемь отличных друг от друга встроенных ядер: 37584381, 1909996635, 442596621, 340029185, 1964463183, 1235671459, 1480745561 и 2030226625. При генерации очередного числа значение соответствующего ядра выбирается случайно среди восьми возможных значений.

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

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

Для рассматриваемой задачи с очередью и одним прибором, необходимо иметь целые значения равномерно распределенных случайных чисел для задания интервалов прибытия заявок и интервалов обслуживания. Специфика описания выборок случайных чисел приводит к необходимости определения наименьшего и наибольшего значения целых чисел в выборке. Например, необходимо установить, что время обслуживания распределено равномерно и заключено в интервале [12, 20]. Средним арифметическим выборки является 16, а размах (в статистическом смысле) 8. В имитационном моделировании размахом называют половину этой величины, что позволяет компактно записывать свойства выборки 16±4. Такую запись, общий вид которой A±B, часто используют для описания равномерного распределения, включающего целые значения от A-B до A+B где A и B также целые. Недостатком этой записи является невозможность задания четного числа значений. Запись 16±4 описывает выборку из десяти значений, 17±5 - из одиннадцати и т.д.

Случайное число из интервала A±B определяют добавлением к наименьшему возможному значению A-B "случайной доли" размаха (в статистическом смысле) 2*B. Значение датчика случайных чисел рассматривается как  "случайная доля", т.е. значение целого равномерно распределенного случайного числа определяется как целая часть результата вычисления :

(A - B) + RAND*2*B

Однако, при этом возникает проблема получения наибольшего значения A+B, т.к. максимальное значение датчика случайных чисел 0,999999. В этой связи вычисляют значение целого равномерно распределенного случайного числа по формуле:

(A - B) + RAND*(2*B+1)

Таким образом, если установлено 8±3, то имеем следующие равновероятные значения: 5, 6, 7, 8, 9, 10, 11. Вероятность получения каждого равна 1/7.

Кроме рассмотренного существуют другие методы генерирования случайных чисел.
В основе этих методов получения случайных чисел, распределенных по любым законам, так же лежит использование генератора случайных чисел в интервале 0…1. Наибольшее распространение получили следующие методы генерирования:

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

yi=a*yi-1*(mod m),

где a, m -постоянные числа; yi - случайное число.
Смешанный конгруэнтный метод. Этот метод отличается от предыдущего прибавлением к остатку от деления постоянного числа m:

yi=a*yi-1+m*(mod m),

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

Для определения длины периода генерируют случайные числа и сравнивают их с зарегистрированным числом, подсчитывая количество случайных чисел, полученных до совпадения с зарегистрированным числом. При проверке на случайность используют совокупность тестов проверки: частот; пар; комбинаций; серий; корреляции. 
В первых четырех тестах осуществляется разбиение диапазона распределения на t интервалов и выполняется подсчет количества попаданий случайных чисел в выделенные интервалы. Полученное эмпирическое распределение сравнивается с теоретическим. Для сравнения используются критерии согласия Колмогорова и c2.

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

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

Hosted by uCoz