Линейный конгруэнтный метод

Физические ГСЧ

Примером физических ГСЧ могут служить: монета («орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в качестве которого используют шумящее тепловое устройство, например, транзистор (рис. 1–2).

Рис. 1. Схема аппаратного метода генерации случайных чисел

Рис. Диаграмма получения случайных чисел аппаратным методом

Алгоритмические ГСЧ

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

r_{i + 1} = f (r_i).

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

Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности квазислучайных чисел.

Рассмотрим несколько алгоритмических методов получения ГСЧ:

• метод серединных квадратов;
• метод серединных произведений;
• метод перемешивания;
• линейный конгруэнтный метод.

Метод серединных квадратов

Имеется некоторое четырехзначное число R 0. Это число возводится в квадрат и заносится в R 1. Далее из R 1 берется середина (четыре средних цифры) — новое случайное число — и записывается в R 0. Затем процедура повторяется (см. рис. 22.6). Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij, а 0.ghij — с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис. 22.6, так и на последующих подобных рисунках.

Рис. 22.6. Схема метода серединных квадратов

Недостатки метода: 1) если на некоторой итерации число R 0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R 0; 2) генератор будет повторять последовательность через Mⁿ шагов (в лучшем случае), где n — разрядность числа R 0, M — основание системы счисления.

Для примера на рис. 22.6: если число R 0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 2⁴ = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.

Описанный выше способ был предложен Джоном фон Нейманом и относится к 1946 году. Поскольку этот способ оказался ненадежным, от него очень быстро отказались.

Метод серединных произведений

Число R 0 умножается на R 1, из полученного результата R 2 извлекается середина R 2^* (это очередное случайное число) и умножается на R 1. По этой схеме вычисляются все последующие случайные числа (см. рис. 22.7).

Рис. 22.7. Схема метода серединных произведений

Метод перемешивания

В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R 0. Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R 0^*. Точно так же, циклически сдвигая содержимое ячейки R 0 вправо на 1/4 длины ячейки, получаем второе число R 0^**. Сумма чисел R 0^* и R 0^** дает новое случайное число R 1. Далее R 1 заносится в R 0, и вся последовательность операций повторяется (см. рис. 22.8).

Рис. 22.8. Схема метода перемешивания

Обратите внимание, что число, полученное в результате суммирования R 0^* и R 0^**, может не уместиться полностью в ячейке R 1. В этом случае от полученного числа должны быть отброшены лишние разряды. Поясним это для рис. 22.8, где все ячейки представлены восемью двоичными разрядами. Пусть R 0^* = 10010001₂ = 145₁₀, R 0^** = 10100001₂ = 161₁₀, тогда R 0^* + R 0^** = 100110010₂ = 306₁₀. Как видим, число 306 занимает 9 разрядов (в двоичной системе счисления), а ячейка R 1 (как и R 0) может вместить в себя максимум 8 разрядов. Поэтому перед занесением значения в R 1 необходимо убрать один «лишний», крайний левый бит из числа 306, в результате чего в R 1 пойдет уже не 306, а 00110010₂ = 50₁₀. Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при переполнении ячейки производится автоматически в соответствии с заданным типом переменной.

Линейный конгруэнтный метод

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

r_{i + 1} = mod(k · r_i + b, M).

M — модуль (0 < M); k — множитель (0 ≤ k < M); b — приращение (0 ≤ b < M); r 0 — начальное значение (0 ≤ r 0 < M).

Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью. Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом, а при b ≠ 0 — смешанным конгруэнтным методом.

Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2 ^N, поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M, меньшего, чем 2 ^N: в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа r_{i + 1}ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна, равное 2³¹ – 1, и таким образом, M = 2³¹ – 1.

Одним из требований к линейным конгруэнтным последовательностям является как можно большая длина периода. Длина периода зависит от значений M, k и b. Теорема, которую мы приведем ниже, позволяет определить, возможно ли достижение периода максимальной длины для конкретных значений M, k и b.

Теорема. Линейная конгруэнтная последовательность, определенная числами M, k, b и r ₀, имеет период длиной M тогда и только тогда, когда:

• числа b и M взаимно простые;
• k – 1 кратно p для каждого простого p, являющегося делителем M;
• k – 1 кратно 4, если M кратно 4.

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

Пример 1 M = 2N k = 3 + 8 · q (или k = 5 + 8 · q) b = 0 r0 — нечетно

Было установлено, что ряд псевдослучайных чисел, генерируемых на основе данных из примера 1, будет повторяться через каждые M /4 чисел. Число q задается произвольно перед началом вычислений, однако при этом следует иметь в виду, что ряд производит впечатление случайного при больших k (а значит, и q). Результат можно несколько улучшить, если b нечетно и k = 1 + 4 · q — в этом случае ряд будет повторяться через каждые M чисел. После долгих поисков k исследователи остановились на значениях 69069 и 71365.

Пример 2 M = 231 – 1 k = 1 220 703 125 b = 7 r0 = 7

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

Мультипликативный метод генерации псевдослучайных чисел был предложен Д. Г. Лехмером (D. H. Lehmer) в 1949 году.

 

 

12) Метод суперпозиции

Пусть функция распределения разыгрываемой НСВ Х задана линейной комбинацией двух функций распределения: F(x)= C₁ F₁(x) +C₂ F₂(x), где C₁>0, C₂>0. При , каждая из функций распределения стремится к единице, поэтому C₁ + C₂ =1.

Введем вспомогательную ДСВ Z с законом распределения:

Z
p	C1	C2

Выберем два независимых случайных числа r₁ и r₂. По числу r₁ разыграем возможное значение Z. Если z=1, то возможное значение х найдем из уравнения F₁(x) = r₂, а если z =2, то из уравненияF₂(x) = r₂.

Пример: Найти явные формулы для разыгрывания НСВ Х, заданной функцией распределения:

F(x) = 1- 0,25(e^-2x + 3e^-x).

Используя метод суперпозиций, представим функцию в виде F(x) =0,25(1 – e^-2x) +0,75 (1 – e^-x).

Откуда С₁ =0,25; С₂ =0,75; F₁(x) = 1 – e^-2x, F₂(x) = 1 – e^-x.

Введем ДСВZ:

Z
p	0,25	0,75

Интервал (0;1) разобьем на частичные интервалы (0; 0,25) и (0,25; 1).

Выберем случайные числа r₁ и r₂. Если r₁ принадлежит интервалу (0; 0,25), то решаем уравнение: 1 – e^-2x= r₂, если r₁ принадлежит интервалу (0,25; 1), то – уравнение: 1 – e^-x = r₂. Таким образом, получаем возможные значения НСВ Х.

 

23) Планирование эксперимента - это совокупность действий, направленных на получение эффективных опытов, проводимых для оценки влияния некоторых факторов на исследуемую величину. Пассивный эксперимент – меняется только один фактор, влияющий на исследуемую величину. Активный эксперимент – меняются все фактору в соответствии с составленным планом эксперимента.

Планируемые эксперименты делятся на:

· отсеивающие - предназначены для ранжирования;

· экстремальные эксперименты - предназначены для нахождения оптимального решения;

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

· эксперименты для оценки влияния факторов;

· эксперименты для специальных случаев.

Факторы в эксперименте бывают качественными и количественными.

Качественные факторы можно квантифицировать или приписать им числовые обозначения, тем самым перейти к количественным значениям.

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

На практике для факторов с непрерывной областью определения (например, для температуры) выбирают дискретное множество уровней.

Действующие факторы должны быть:

1) управляемыми;

2) операциональными (означает то, что нам известно то, как устанавливается значение фактора и что он означает);

3) однозначными (не должны зависеть от других факторов);

4) совместимыми (все сочетания осуществимы и безопасны).

Несовместимость может наблюдаться вблизи границ области определения.

При проведении многофакторного эксперимента возникают следующие задачи:

1) выбор оптимальной стратегии эксперимента в условиях неопределенности;

2) обработка результатов измерений;

3) проверка гипотез и принятие решений.

 

24) Планирование можно разделить на стратегическое и тактическое.

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

При этом решаются две основные задачи:

• идентификация факторов;
• выбор уровней факторов.

Под идентификацией факторов понимается их ранжирование по степени влияния на значение наблюдаемой переменной (показателя эффективности).

По итогам идентификации целесообразно разделить все факторы на две группы: первичные и вторичные.

Первичные – это те факторы, в исследовании влияния которых исследователь заинтересован непосредственно.

Вторичные – факторы, которые не являются предметом исследования, но их влиянием нельзя пренебречь.

Выбор уровней факторов производится с учетом двух противоречивых требований:

• уровни фактора должны перекрывать (заполнять) весь возможный диапазон его изменения;
• общее количество уровней по всем факторам не должно приводить к чрезмерному объему моделирования.

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

Эксперимент, в котором реализуются все возможные сочетания уровней факторов, называется полным факторным экспериментом (ПФЭ).

Общее число различных комбинаций уровней в ПФЭ для К факторов можно вычислить как

где – число уровней i -го фактора.

Если число уровней всех факторов одинаково, то

,

где L – число уровней.

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

Если такие взаимодействия считают отсутствующими или их эффектом можно пренебречь, проводят частичный факторный эксперимент (ЧФЭ).

Рассмотрим некоторые планы ЧФЭ.

1. Рандомизированный план предлагает выбор сочетания уровней для каждого прогона случайным образом.

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

Если первичный фактор А имеет уровней, то для каждого вторичного фактора также выбирается уровней.

Выбор комбинаций уровней факторов выполняется на основе специальной процедуры, которую рассмотрим на примере.

Пример. Пусть в эксперименте используется первичный фактор А и два вторичных фактора – В и С; число уровней факторов равно 4.

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

План полного факторного эксперимента

Значение фактора В	Значение фактора С
С 1	С 2	С 3	С 4
В 1	А 1	А 2	А 3	А 4
В 2	А 2	А 3	А 4	А 1
В 3	А 3	А 4	А 1	А 2
В 4	А 4	А 1	А 2	А 3

В результате имеем план, требующий 4 ґ 4 = 16 прогонов, в отличие от ПФЭ, для которого нужно 4³ = 64 прогона.