Лекции по курсу имитационное моделирование экономических процессов составитель ст преп каф. Итим нохрина Г. Л. 2
 Скачать 1.44 Mb.
|
|
Метод срединных квадратов Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 12 i Z Z 2 0 7182 — 51 581 124 1 5811 0,5811 33 767 721 2 7677 0,7677 58 936 329 3 9363 0,9363 87 665 769 4 6657 0,6657 44 315 649 5 3156 0,3156 9 960 336 6 9603 0,9603 92 217 609 7 2176 0,2176 4 734 976 8 3497 0,3497 12 229 009 9 2290 0,229 5 244 100 10 2441 0,2441 5 958 481 11 9584 0,9584 91 853 056 12 8530 0,853 72 760 900 13 7609 0,7609 57 896 881 14 8968 0,8968 80 425 024 15 4250 0,425 18 062 500 16 625 0,0625 390 625 17 9062 0,9062 82 119 844 18 1198 0,1198 1 435 204 19 3520 0,352 12 390 400 20 3904 0,3904 15 241 216 21 2412 0,2412 5 817 744 22 8177 0,8177 66 863 329 23 8633 0,8633 74 528 689 24 5286 0,5286 27 941 796 25 9417 0,9417 88 679 889 26 6798 0,6798 46 212 804 27 2128 0,2128 4 528 384 28 5283 0,5283 27 910 089 29 9100 0,91 82 810 000 30 8100 0,81 65 610 000 31 6100 0,61 37 210 000 32 2100 0,21 4 410 000 33 4100 0,41 16 810 000 34 8100 0,81 65 610 000 35 6100 0,61 37 210 000 Таблица 1. Метод срединных квадратов Может показаться, что метод срединных квадратов обеспечивает хорошую перестановку элементов одного числа для получения следующего и такое случайное правило обеспечивает хороший способ генерирования слу- чайных чисел. В действительности это не совсем так. Одна из серьезных проблем состоит в том, что данный метод имеет стойкую тенденцию возвращать значения, которые стремятся к нулю. (Продолжите еще немного табл. 7.1 или назначьте Z o = 1009, первые четыре цифры из таблицы Rand Corporation.) Таким образом, нельзя рассчиты- вать на то, что хороший генератор случайных чисел можно создать, производя манипуляции с ка ким-либо од- ним числом для получения следующего. Метод срединных квадратов вовсе не является случайным, то есть непредсказуемым (это наиболее существенный его недостаток). На самом деле, если мы знаем одно число, сле- дующее число является полностью предопределенным, поскольку правило его получения неизменно. Фактически, когда задается Z o , предопределяется вся последовательность чисел Z t и U t . Это замечание касается всех арифметических генераторов (далее в главе мы будем рас- Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 13 сматривать только данный тип). Поэтому арифметические генераторы именуются псевдослу- чайны. Типы базовых датчиков: 1. физические (любой физический шум) – не используются, т.к. характеристики неста- бильны и реализацию повторить нельзя; 2. псевдослучайные – строятся на основе детерминированного алгоритма, но получен- ные результаты неотличимы от случайных. Псевдослучайные базовые датчики строятся по модели при заданном Хороший арифметический генератор случайных чисел должен обладать следующими свойствами. 1. Получаемые числа должны быть равномерно распределены в интервале [0, 1] и не должны иметь корреляции друг с другом, в противном случае результаты моделирования могут оказаться полностью недействительными. 2. Чтобы генератор можно было использовать на практике, он должен обладать быстро- действием и не требовать больших затрат памяти. 3. Генератор должен обеспечивать возможность точно воспроизводить заданный поток случайных чисел. Во-первых, это позволяет упростить отладку компьютерной программы и проверить, правильно ли она работает. Во-вторых, что гораздо важнее, вы можете ис- пользовать идентичные случайные числа при моделировании различных систем и выпол- нить их более точное сравнение. 4. В генераторе должен быть предусмотрен простой способ получения отдельных пото- ков случайных чисел. Как вы узнаете в дальнейшем, поток - это просто часть последова- тельности случайных чисел, производимых генератором, очередной поток начинается в том месте, где заканчивается предыдущий. Мы можем рассматривать различные потоки как отдельные и независимые генераторы (при условии, что весь поток, который, как правило, имеет длину 100 000 или более чисел, не применяется). Таким образом, пользователь может выделить определенный поток для конкретного источника случайности при моделировании Требования к базовым датчикам и их проверка 1. Отрезок апериодичности Периодом T и длиной отрезка апериодичности датчика называются наименьшие из величин, удовлетворяющие Чем больше T и L, тем лучше датчик (особенно L). Как определить их: 1. Берем V – достаточно большое число (обычно 2. Генерируем и проверяем ,запоминая. 3. Генерируем и проверяем . Если нет для , то и . Иначе запоминаем , для которого , и находим следующий , для кото- рого (если нужно, генерируются дополнительные величины). Тогда 4. Генерируем и и ищем первое совпадение . Тогда Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 14 2. Равномерность Должно быть для Проверка: 1. Берем и генерируем 2. Находим и разбиваем отрезок [0,1) на k равных частей (длиной ) 3. Для каждого числа определяем, в какой интервал оно попало: и заполняем массив : 4. По значениям этого массива строим гистограмму (для наглядности). 5. Используем критерий Выбираем уровень значимости (обычно 5%), а число степеней свободы . В таб- лицах находим значение и проверяем: если ,то «данные эксперимента не проти- воречат гипотезе о равномерности случайных чисел», иначе – «противоречат». 3. Некоррелированность 1. Генерируем 2. Вычисляем , (можно и больше). 3. Вычисляем 4. Проверяем для всех k Если да, то «данные эксперимента не противоречат гипотезе о равномерности случайных чи- сел», иначе – «противоречат». Здесь – уровень значимости, а берется из таблиц 4. Простейшие проверки Подходят для любой непрерывной случайной величины. 1. Математическое ожидание: 2. Дисперсия: Некоторые общие замечания по тестированию Число, разнообразие и диапазон сложности тестов для генераторов случайных чисел в полном смысле слова ставит в тупик. Что еще хуже, не существует (и, наверное, не будет существовать) единого мнения относительного того, какие тесты лучше. Однако, невзирая на любые проверки, даже если они Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 15 проводятся в огромном количестве, полностью убедить кого-либо в том, что какой-то из генераторов является «наилучшим», нельзя. Однако можно посоветовать подбирать тесты для генератора согласно замыслу его использования. Это приведет, например, к изучению поведения пар значений U i (вероятно, с помощью проверки по двухмерному сериальному критерию), если случайные числа действительно ис- пользуются парами при моделировании. В более широком смысле, этот совет подразумевает, что нужно быть более осторожными в выборе и тестировании генератора случайных чисел, если моделирование, в котором он будет использоваться, является очень дорогостоящим, требует результатов высокой точно- сти или же представляет собой важную составляющую крупных исследований. Модели базовых датчиков Линейные конгруэнтные генераторы Сегодня очень часто применяются линейные конгруэнтные генераторы (ЛКГ), созданные Леме- ром [Lehmer, 1951]. В них последовательность целых чисел Z b Z 2 ,... определяется по рекурсивной форму- ле Z i = (aZ i-1 + c)(mod m), (1) где т (модуль), а (множитель), с (приращение) и Z o (начальное число или значение) являются неот- рицательными целыми числами. Таким образом, согласно формуле (1), для получения Z i нужно разде- лить aZ i-1 + с на т, то есть Z i будет остатком этого деления. Поэтому 0 ≤ Z i ≤ m - 1, а чтобы получить ис- комые случайные числа U i (при i = 1,2,...) в интервале [0,1], примем U i = Z i /m. Мы концентрируем вни- мание главным образом на Z i , хотя следует иметь в виду и точный характер деления Z i на m в связи с раз- личиями в способах обработки разными компьютерами компиляторами чисел с плавающей запятой. Кроме того, что целые числа я, а, с и Z o должны быть неотрицательными, они должны удовлетворять неравенствам 0 < т, а < т, с < т и Z o < т. Против использования ЛКГ можно высказать следующие соображения. Во-первых:, значения Z it определенные по формуле (1), вовсе не являются случайными; это касается всех генераторов псевдо- случайных чисел. Однако, тщательно подбирая эти четыре параметра, мы стараемся вызвать такое по- ведение величин Z i при котором соответствующие величины U i представляются как независимые и равномерно распределенные случайные величины с распределением U(0, 1), когда они проверяются с помощью ряда тестов. Во-вторых, при использовании ЛКГ \] х могут принимать лишь рациональные ачения 0,1/т, 2/т,..., (т - 1)/т. В действительности f/j могут принимать только Качения мантисс этих величин в зависи- мости от определения констант т, а, с iZ 0 , а также от характера деления с плавающей запятой на т. Поэтому у нас нет бможности получить значение /7 ; между, например, 0,1/т и 0,9/т, в то время как i возможность должна возникать с вероятностью 0,8/тп > 0. Нам предстоит здиться, что для модуля m обычно выбирается очень большое значение, скажем, ' или больше, при котором точки в интервале [0,1], куда могут попадать значе-рия U t , располагаются очень плотно. Для т > 10 9 существует по меньшей мере 1 Млрд возможных значений. Но цикличность неизбежна. Согласно формуле (1), как только Z i получает значение, которое у нее уже было, сгенерируется та же самая последовательность ве- личин, и этот цикл повторяется бесконечно. Длина цикла называется периодом генератора. Для ЛКГ значение Z ; зависит только от предыдущего целого числа Z i-1 , а поскольку 0 < Z i < m - 1, период генера- тора не превышает величину т. Если период действительно равен т, считается, что ЛКГ имеет пол- ный период. Разумеется, если генератор имеет полный период, какое бы ни было выбрано начальное число Z o из последовательности {0,1,..., т - 1}, весь цикл будет воспроизведен в некотором порядке. Если же период генератора меньше полного, длина цикла будет зависеть от выбора определенного значения Z o , в этом случае мы будем говорить о периоде начального значения для этого генератора. Поскольку в широкомасштабных проектах имитационного моделирования могут использоваться сотни тысяч случайных чисел, очевидно, что для них требуются ЛКГ с длинными периодами. Более того, лучше всего иметь ЛКГ с полным периодом, поскольку тогда у нас есть уверенность, что каждое целое число в интервале от 0 до m - 1 возникнет в каждом цикле только один раз, а это способствует равномер- ности распределения значений U { . (Даже ЛКГ с полным периодом на некоторых участках цикла могут иметь неравномерное распределение. Например, если мы сгенерируем только m/2 последовательных значений Z i , могут остаться большие пробелы в последовательности возможных значений 0,1,…,т - 1.) Таким образом, полезно знать, как выбирать значения m, а и с так, чтобы у соответствующего ЛКГ был Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 16 полный период. Следующая теорема, доказанная Халлом и Добеллом [Hull and Dobell, 1962], дает нам определение параметров. Теорема 1. ЛКГ, определенный по формуле (1), имеет полный период тогда и только тогда, когда выпол- няются три следующих условия: а) единственное положительное целое число, на которое без остатка делятся как т, так и с, равно 1 (с явля- ется взаимно простым по отношению к m); б) если q является простым числом (делится только само на себя и на 1), на которое де- лится т, то а - 1 делится на q; в) если т делится на 4, то а - 1 тоже делится на 4. Из-за первого условия теоремы 1 ЛКГ работают по-разному с параметром с > 0 (смешанные ЛКГ) и с параметром с = 0 (мультипликативные ЛКГ). Смешанные генераторы При с > 0 выполнение первого условия теоремы 1 возможно, следовательно, мы можем получить полный период т. Сначала выберем значение т. Чтобы получить длинный период и высокую плотность величин U i , в интервале [0,1],величина т должна иметь большое значение. Кроме того, деление на т для получения остатка в формуле (1) — до- вольно длительная арифметическая операция. Поэтому желательно избежать явного выполнения тако- го деления. Выбор т, который является удачным во всех этих отношениях — т = 2 b , где b — число би- тов (двоичных знаков) в слове задействованного компьютера, которые действительно доступны для хранения данных. В частности, во многих компьютерах и компиляторах используются 32-битовые слова, при этом крайний левый бит является знаковым, следовательно, b = 31. Если b имеет до- статочно большое значение, например, b > 31, тогда т > 2 31 > 2,1*10 9 . Кроме того, выбирая т = 2 b мы действительно избегаем явного деления на т для большинства компьютеров, поскольку можно воспользоваться переполнением целых чисел. Наибольшее целое число, которое может быть представлено, равно 2 b - 1, и любая попытка сохранить большее целое число W (имеющее, например, h > b двоичных знаков) завершится потерей левых (наиболее значимых) h - b двоич- ных знаков целого числа, превысившего допустимый размер. Оставшиеся b двоичных знаков составляют ровно W(mod 2 b ). Как же следует выбирать значения а и с, когда т = 2 b , чтобы получить хороший смешан- ный ЛКГ? Опыт показывает, что лучше отказаться от использования смешанного ЛКГ вообще. Более простые и понятные мультипликативные ЛКГ зарекомендовали себя не хуже смешан- ных и применяются гораздо чаще. Мультипликативные генераторы Мультипликативные ЛКГ выгодно применять, так как для них не требуется определять параметр с, но у них не может быть полного периода, потому что первое условие теоремы 1 для них выполняться не будет (поскольку, например, m является положительным числом и как m, так и с = 0 делятся на него без остатка). Однако вы сможете убедиться, что можно получить пе- риод т - 1, если осторожно подбирать значения m и а. Мультипликативные ЛКГ появились еще до смешанных и исследовались более интенсивно. Большинство ЛКГ, применяемых сегодня, являются мультипликативными, поскольку факт улучшения эффективности, на которое возла- гались надежды в связи с введением смешанных генераторов, окончательно не доказан. Как и при использовании смешанных ЛКГ, для вычислений по-прежнему подходит вы- бор т = 2 b , таким образом мы избегаем явного деления. Однако можно доказать [Knuth, 1998a, р. 20], что в этом случае период составляет самое большее 2 b-2 , то есть лишь четвертая часть це- лых чисел от 0 до т - 1 может быть получена в качестве значений переменных Z i . (Фактически период составляет 2 b-2 , если значение Z o является нечетным, а параметр а имеет вид 8k + 3 или 8 k + 5 для некоторых значений k = 0,1,....) Кроме того, нам, как правило, неизвестно, куда попа- дут эти т /4 целых числа, то есть между полученными переменными Z, могут быть недопустимо большие промежутки. К тому же, если для параметра а мы выбираем вид 2 l + j (так что умно- жение Z i-1 на а заменяется смещением и прибавлением j), можно получить неудовлетворитель- ные статистические свойства. Известен, например, генератор RANDU, который имеет такие значения параметров: т = 2 31 , а = 2 16 + 3 = 65 539, с = 0 - и, как оказалось, очень неподходящие Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 17 статистические свойства, поэтому следует избегать его применения. Даже отказаться от выбо- ра а = 2 l +j, используя т = 2 b , - тоже не самый подходящий вариант параметра для мультипли- кативных ЛКГ, хотя бы потому что период т /4 короче и по этой причине возникает вероят- ность появления пропусков в значениях Z { . Из-за трудностей, возникавших в связи с выбором т = 2 b в мультипликативных ЛКГ, ос- новное внимание уделялось поиску других способов определения значения т. Метод, оказав- шийся довольно успешным, был представлен Хатчинсоном [Hutchison, 1966], который припи- сывает авторство идеи Лемеру. Вместо того чтобы использовать т = 2 b , было предложено опре- делять значение т как наибольшее простое число, которое меньше 2 b . Например, если b = 31, то наибольшее простое число, которое меньше 2 31 , соответственно будет составлять 2 31 — 1 = 2 147 483 647. Теперь для простого числа те можно показать, что период составляет т - 1, если а — это первообразный элемент по модулю |