THE NEW GENERATOR OF THE RANDOM UNIFORMLY DISTRIBUTED POINTS

Texto integral

При решении многих задач (например, поисковой глобальной оптимизации функций непрерывных переменных) возникает необходимость изучения целевой функции на основе серии измерений (вычислений) ее в заданном количестве точек. Для генерирования этих точек в пространстве координат обычно используются случайные последовательности с равномерным законом распределения, регулярные сетки и регулярные ЛПт последовательности. Каждый из этих способов обладает как достоинствами, так и недостатками. Создание «хорошего» датчика, который обеспечивает равномерное распределение точек как в пространстве независимых переменных (координат), так и относительно каждой из координат, представляет собой нетривиальную задачу. Для обычного генератора случайных последовательностей с равномерным законом распределения значений каждой из координат качество последовательностей целиком зависит от используемого датчика псевдослучайных чисел. Получаемая случайная последовательность точек обычно содержит локальные неоднородности, которые визуально выглядят как «сгустки точек» и «пустые места» как в пространстве всех переменных, так и по каждой из координат (или для групп координат). За счет этого осуществляется неравномерное изучение целевых функций. Однако это самый простой в реализации способ генерации равномерных последовательностей точек. Случайное размещение точек позволяет проводить статистический анализ свойств изучаемых функций и рассматриваемых алгоритмов. Регулярные сетки, в отличие от случайных генераторов, не имеют локальных неоднородностей, и любой фрагмент регулярной сетки сохраняет свойство равномерности (т. е. тоже является регулярной сеткой). Однако количество пробных точек n в регулярной сетке для сохранения свойства равномерности должно быть равно vm , где m - размерность пространства, v - количество точек вдоль каждой координаты. Количество пробных точек n может принимать только ряд фиксированных значений и с ростом размерности пространства число точек n сильно нарастает. Точки регулярной сеткой располагаются для m = 2 на прямых линиях, параллельных осям координат, а для 2 < m - на соответствующих параллельных плоскостях. Это свойство сильно уменьшает количество извлекаемой информации об исследуемых функциях относительно части координат. Например, при m = 2 и v = 10 из n = 100 точек двумерного пространства мы располагаем только 10 точками относительно каждой из координат. Регулярность сетки не позволяет также при каждом фиксированном n проводить соответствующие статистические исследования. Равномерность размещения точек и в пространстве, и по каждой из координат обеспечивает регулярный генератор ЛПт последовательностей. Размещение точек детерминированное (как у регулярной сетки) и оптимальное: точки равномерно распределены в пространстве и по каждой координате (упорядоченные значения каждой из координат всех точек находятся на равном расстоянии друг от друга). При удобной для вычислений двоичной реализации алгоритма построения последовательности указанное оптимальное свойство справедливо для n = 2q (q = 1, 2, 3, ...). При создании генератора возникают трудности удовлетворения обоим критериям оптимальности при произвольных значениях числа точек n и размерности m пространства. Сравнительно недавние исследования показали, что при возрастании m точки группируются в жгуты. Регулярность сетки также не позволяет при фиксированных n проводить соответствующие статистические исследования. Идея нового равномерного случайного распределения точек кратко высказана в [1]. В представленной работе идея алгоритмизована и свойства генератора частично исследованы. В генераторе псевдослучайных равномерно распределенных точек реализовано дополнительное условие (второе условие оптимальности в ЛПт генераторе): упорядоченные значения каждой координаты всех генерируемых точек находятся на равном расстоянии друг от друга. За счет наличия этого свойства более полно извлекается информация об изучаемых относительно координат функциях (например, при оптимизации функций). Так, если в пространстве двух переменных размещено 100 пробных точек и в них вычислена исследуемая функция, то и вдоль каждой координаты мы располагаем значениями функции также в 100 точках, которые расположены на одинаковом расстоянии (относительно координат) друг от друга. Случайное размещение точек в пространстве позволяет осуществлять статистический анализ свойств изучаемых функций и алгоритмов. Программная реализация генератора представлена в [2]. Основной результат. Опишем основную идею построения нового генератора случайных равномерно распределенных точек на примере получения значений по одной из координат (рис. 1). Заданное число точек равно n. Идем от конечной цели. Помещаем в интервал изменения выбранной (первой) координаты (в нормированном случае это интервал [-1; 1]) заданное число точек, например n точек, находящихся на одинаковом расстоянии друг от друга (рис. 1, а). Последовательность n чисел обычного генератора R[-1; 1] псевдослучайных равномерно распределенных в интервале [-1; 1] преобразуем в последовательность чисел нового генератора. Берем первое случайное число первой последовательности и находим ближайшее к нему число из исходной последовательности равноудаленных друг от друга чисел. Это и будет значение выбранной координаты для первой точки (рис. 1, б). Данный элемент из исходной эталонной последовательности исключаем (рис. 1, в). Затем аналогично переходим к поиску значения той же самой выбранной координаты для второй точки, ориентируясь на скорректированную эталонную последовательность (рис. 1, г) и т. д. После завершения этой процедуры получено n случайных последовательных значений выбранной координаты. Аналогично случайно выбираем n последовательных значений для следующей (второй) фиксированной координаты. Первое значение для первой координаты и первое значение для второй координаты дают первую случайную точку в двумерном пространстве. Количество координат также может принимать любое конечное значение. Реализации размещения точек на основе нового генератора в пространстве двух переменных при различном количестве точек n = 16, 40, 60, 80 представлены на рис. 2. п—а- -1 i -j -I-1-1 1 1 -1 -1 В Рис. 1. Выбор значений каждой координаты в новом генераторе x2 n - 40 x2 x n - 16 x Рис. 2. Фрагменты размещения точек нового генератора при различном заданном количестве точек: n = 16, 40, 60, 80 n - 60 x 2 Свойства генератора. Проведем статистические испытания нового генератора на равномерность точек в двумерном пространстве и сравним получаемые характеристики с аналогичными характеристиками для обычного случайного генератора, а в конце - и с характеристиками для оптимальных ЛПт последовательностей. Для получения статистик (оценок математического ожидания Пт и среднего квадратичного отклонения дТ количества точек, попадающих в выбранные подобласти рассматриваемой прямоугольной области) был разработан специализированный программный стенд. При расчете оценок каждый эксперимент повторялся 1 000 раз. Прямоугольная область разбивается на соответствующее число прямоугольных подобластей: k = 4, 9, 16, 25, 36, ... и подсчитываются оценки математического ожидания mт и среднего квадратичного отклонения дТ для количества точек, попадающих в каждую подобласть, при различных объемах n выборки или различном количестве точек s , попадающих в каждую подобласть (при этом n = s ■ k). В качестве примера на рис. 3, 4 представлены графики для mт при разбиении области на четыре подобласти. При этом для первого приведенного на графиках варианта на каждую подобласть приходится s = 20 точек и тогда общий объем точек равен n = 80 и т. д. Для всех приведенных вариантов проверены гипотезы (при уровне значимости 0?01) о равенстве математического ожидания соответствующему числу s : пт = 20 при n = 80; пт = 30 при n = 120; ...; mт = 100 при n = 400 для всех четырех подобластей. Все гипотезы приняты. Это говорит о среднем равномерном размещении точек в четырех подобластях. В указанном смысле оба генератора одинаково хороши. Такая же закономерность характерна и для k = 9, 16, 25, 36, ... . Второй характеристикой равномерности размещения точек в подобластях является ат - среднее квадратичное отклонение количества точек от математического ожидания. На рис. 5, 6 для k = 4 даны соответствующие оценки дт для ат. Среднее квадратичное отклонение количества точек в каждой подобласти для нового генератора в среднем в 1,55 раза меньше, чем для случайного генератора, что характеризует новый генератор как более «качественный». шт Номер подобласти Рис. 4. Пт для нового генератора ■ш п = ЕЮ * п = 120 -А П = 160 -*■ п = 200 -0- п = 240 -* п = 280 +- п = 320 -Ж п 360 ■X п 400 -■ П = 80 ■Ш- п = 120 г* п = 160 -т п = 200 о п = 240 -4 п = 280 V п = 320 п = 360 -X п = 400 1 •Т- 'Тw— Y Y т т ---у--- ------Т" А. А. А. А _ -ь -ь 12 3 4 Номер подобласти Рис. 3. Пт для обычного генератора пт g т Номер подобласти Рис. 5. &т для обычного генератора -Я п = 80 п = 120 ■* п = 160 ■т п = 200 -0- П = 240 п = 230 п = 320 ■эк п = 360 т* п = 400 g т Номер подобласти Рис. 6. дт для нового генератора * п = ЕЮ ♦ п = 120 ■* п = 160 -Т- п = 200 -о- п = 240 -4 П = 280 *- п = 320 т* п 360 п 400 На рис. 7 приведены графики зависимости дТ (среднего значения оценок аТ для всех подобластей выбранного варианта) от среднего количества точек s, приходящихся на каждую подобласть, при различном количестве k подобластей. С ростом среднего количества точек s (и соответственно с ростом n - k • s) возрастает средняя оценка аТ среднего квадратичного отклонения, но для нового генератора она всегда меньше, чем для обычного случайного генератора. Отношение X оценок дТ (для обычного и нового генераторов) для каждого k остается на одном уровне (который находится внутри доверительного интервала) и с ростом k от 4 до 100 уменьшается от величины 1,58 до 1,045: 1.58 (k = 4); 1,28 (k = 9); 1,9 (k = 16); 1,14 (k = 25); 1,10 (k = 36); 1,08 (k = 49); 1,07 (k = 64); 1,06 (k = 81); 1,045 (k = 100). В указанном смысле эффективность нового генератора всегда выше, чем обычного. На рис. 8 для конкретности представлены графики зависимости величины X отношения оценок аТ (обычного генератора и нового) при сравнительно малых и больших s. Параметр X можно именовать коэффициентом эффективности нового генератора по отношению к обычному случайному генератору. Чем на большее число k подобластей разбивается рассматриваемая прямоугольная область, тем более тонкая структура используется для характеристики генераторов и тем ближе X к единице. Эффективность обоих генераторов становится примерно одинаковой. Сравним для общности новый генератор случайно распределенных точек с оптимальным генератором ЛПт неслучайных последовательностей. Для каждого фиксированного s (среднего количества точек, приходящихся на каждую подобласть) и k (количества подобластей) в каждую подобласть попадает различное количество точек. Пример такого распределения точек при s - 3 и k - 36 (при этом общее количество точек n - s • k -108) представлен на рис. 9. Так как ЛПт генератор обеспечивает получение только одной реализации при любом фиксированном количестве точек, то для сравнения со случайными генераторами аналогом величины аТ - среднего значения оценки среднего квадратичного отклонения - будем считать обычную оценку среднего квадратичного отклонения (от среднего) для вышеуказанной реализации распределения точек по подобластям. Для ЛПт генератора эта характеристика разброса точек существенно меньше соответствующей величины дТ для нового генератора. Их отношение так же, как и при сравнении случайных генераторов, обозначаем через X? и оно характеризует эффективность ЛПт генератора по отношению к новому генератору. На рис. 10 приведены графики изменения X как функции от s при различных k. Т -» к = ♦ к = к = к = -о- к = ^к = s Количество точек в подобласти а Т ■» к = 4 * к = 9 *к = 16 ^ к = 25 -£>к = 36 -А к = 49 s Количество точек в подобласти Рис. 7. дт для обычного (а) и нового (б) генерг оров h к = 100 s Количество точек в подобласти Количество точек в подобласти Рис. 8. Поведение коэффициента эффективности X нового генератора по отношению к обычному генератору 10 15 20 25 30 Номера подобластей при их количестве к = 36 Рис. 9. Распреленпе количества точек по подобластям при я = 3и£=36 для ЛПт генератора Количество точек в подобласти Количество точек в подобласти Рис. 10. Поведение коэффициента эффективности X ЛПт генератора по отношению к новому генератору Таким образом, использование нового генератора при исследованиях алгоритмов поиска глобального экстремума функций непрерывных переменных (с селективным усреднением координат) подтвердило его преимущество по сравнению с простейшим датчиком случайных равномерно распределенных точек. Поясним этот факт. При поиске глобального экстремума перед совершением каждого рабочего шага проводится n пробных движений. Величина n обычно невелика и лежит в интервале [20; 200]. Часто n = 100. Для величины n, равной или максимально близкой к указанной, в таблице приведен коэффициент эффективности X нового генератора при различных возможных сочетаниях s и k: s k n X 1 100 100 1,069 2 49 98 1,03 3 36 108 1,122 4 25 100 1,153 6 16 96 1,204 11 9 99 1,313 25 4 100 1,562 При числе областей k = 100, когда на каждую из 100 подобластей приходится в среднем одна точка, коэффициент эффективности X = 1,069. Преимущество нового генератора совсем мало. Перед совершением первого рабочего шага вес каждого пробного движения велик. Надо хотя бы одной точкой попасть в окрестность искомого глобального экстремума. На следующих рабочих шагах осуществляется достаточно быстрое сокращение области поисковых движений и за счет этого на каждом следующем рабочем шаге область глобального экстремума (по отношению к области поисковых движений) увеличивается, а, следовательно, возрастает количество пробных точек, попадающих в эту область. Характеризовать область пробных движений можно все грубей, уменьшая количество подобластей вплоть до k = 4. При этом эффективность нового генератора с каждым шагом повышается. Последовательное изменение эффективности генератора отражено в таблице (при получении дт, по которым рассчитывались X, производилось 10 000 повторных испытаний). За счет отмеченного эффекта число итоговых рабочих шагов сокращается (по сравнению с использованием обычного генератора) на 1-2, т. е. вместо 5-7 шагов будет совершено 4-5 (при прочих равных условиях). В среднем время поиска глобального минимума сокращается на 25 %. Новый генератор имеет некоторое преимущество и по отношению с генератору ЛПт детерминированной последовательности точек, ибо для каждого фиксированного количества пробных точек n и заданной исходной точки поиска обеспечивает получение различных случайных реализаций пробных точек, что необходимо при статистическом анализе свойств алгоритмов и обеспечении более надежного (за счет многократных запусков алгоритма) поиска положения глобального экстремума. Все полученные закономерности выявлены при размерности пространства переменных, равной двум.

Sobre autores

A. Ruban

Siberian Federal University

Email: ai-rouban@mail.ru

A. Kuznetsov

Siberian Federal University

Bibliografia

Arquivos suplementares