On the Experience of Using Various Pseudorandom Number Sensors in Random Search Algorithms for the Global Extremum of Functions

Urazaeva Tatiana Alfredovna PhD in Economics Head of the Department of Information Systems in the economy, Volga State University of Technology 424032, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Pavlenko, 60 bor1@mari-el.com Other publications by this author

Smirnova Svetlana Yur'evna Master's degree student of the Department of Information Systems in Economics at Volga State University of Technology 424000, Russia, Republic of Mari El, Yoshkar-Ola, Lenin's square, 3 svetiki_2807@mail.ru

Алгоритмы случайного поиска получили достаточно широкое распространение при решении задач как безусловной, так и условной оптимизации, как при поиске локальных, так и глобальных экстремумов ^{[1, 8]}. Их популярность объясняется весьма мягкими требованиями к непрерывности и гладкости функций, а также отсутствием необходимости вычисления производных. Несмотря на определенную критику методов случайного поиска, их использование в условиях роста вычислительной мощности современных компьютеров остается весьма полезным ^[10]. С другой стороны, решение многих задач и в технике, и в социально-экономической сфере сводится к решению задач оптимизации. Замечая, что в последние годы постановка многих экономико-математических моделей стала нелинейной ^{[2, 3, 5, 7]}, а некоторые функционалы, используемые в этих моделях, разрывны и негладки (например "Value at Risk" при прямых вычислениях ^[9]), можно сказать о росте интереса к алгоритмам случайного поиска со стороны математической экономики.

Учитывая значительные трудности в получении большого потока равномерно распределенных случайных чисел на компьютерах с традиционной архитектурой, мы будем рассматривать случайный поиск, базирующийся на использовании датчиков псевдослучайных чисел (ДПСЧ). Соответственно, настоящая статья посвящена исследованию влияния используемого ДПСЧ на точность вычислений и/или на достижимость результата.

В качестве модельного примера будем решать задачу поиска глобального минимума функции, для которой, во-первых, всегда есть возможность улучшения текущего найденного минимума, и, во-вторых, каждое следующее улучшение по вычислительной трудоемкости выше предыдущего шага, по крайней мере, для исследуемого алгоритма равномерного случайного поиска ^[8].

Для удовлетворения названных требований была сконструирована функция

`f(x, quad y)=(sin[3/((x-1)^2+3(y-1)^2)])/(r(x, quad y)+100)` ,

где `r(x, quad y)=(1-x)^2+100(y-x^2)^2` – функция Розенброка ^[13].

Особенностью функции `f` является наличие у нее бесконечного, но счетного количества экстремумов, см. рис. 1. При этом очевидно, что глобальный минимум функции `f` стремится к `-0.01` .

Рис.1. Визуализация функции `f` с помощью линий уровня

Сложный характер поведения функции в окрестности точки `(1, quad 1)` демонстрирует рис. 2.

Рис. 2. Линии уровня функции `f` в окрестности точки `(1, quad 1)` на четырех различных масштабах при фиксированном точечном разрешении

Результаты численных экспериментов приведены на рис. 3. На рисунке `k` – это количество шагов алгоритма. Группа из пяти траекторий слева, визуализирующих процесс минимизации, соответствует пяти экспериментам, в которых использовался штатный ДПСЧ Microsoft Office (первая группа экспериментов). Некоторые из этих траекторий совпали. Не трудно заметить, что все процессы завершились на одном и том же значении минимума (уровень, помеченный меткой `L0` ) при близких значениях счетчика итераций, что странно, учитывая названные особенности минимизируемой функции.

Рис. 3. Процессы минимизации. Левая группа траекторий соответствует использованию стандартного ДПСЧ Microsoft Office (шкала оси абсцисс снизу), правая – использованию датчика MT19937 (шкала оси абсцисс сверху).

Интерпретируем результаты первой группы экспериментов. В работах ^{[4, 6]} было показано, что стандартный ДПСЧ Microsoft Office имеет весьма ограниченный период `2^24` и, во многом, проблемы с характеристиками случайности битов ^[6]. Данная ситуация приводит к проблемам использования этого ДПСЧ в методах типа Монте-Карло и, по-видимому, в нашем случае. Необходимо убедится в этом и, по возможности, исправить описанную ситуацию.

В 1997 году японскими математиками Макото Мацумото и Такудзи Нисимурой был предложен ДПСЧ, основанный на свойствах простых чисел Мерсена и в связи с этим получивший название «вихрь Мерсена» ^[11]. Один из вариантов этого ДПСЧ, называемый MT19937, имеет огромный период, равный числу Мерсенна `2^19937 - 1` , обеспечивает равномерное распределение генерируемых псевдослучайных чисел в `623` измерениях (для лучших известных линейных конгруэнтных генераторов это число измерений не превышает четырех) и может быть относительно эффективно реализован на 32-разрядных компьютерах. Результаты пяти численных экспериментов поиска экстремума с датчиком MT19937, реализованным на VBA ^[12], представлены группой траекторий справа на рис. 3. Наглядно видна возможность преодоления барьера `L0` .

Многие математические модели, которые возникают как в естественных, так и в общественных науках, в частности, в экономике, носят нелинейный характер. При исследовании таких моделей достаточно часто используют подходы, основанные на идеях метода Монте-Карло. Современная вычислительная техника позволяет достигнуть здесь числа статистических испытаний `2^32` и более. Столь значительное количество испытаний потенциально позволяет существенно повысить точность решений, но в ряде случаев может привести к некорректным результатам.

В данном исследовании был продемонстрирован еще один механизм возникновения таких некорректных результатов и было показано, что использование новых, длиннопериодических ДПСЧ, например таких, как MT19937, позволяет избежать проблем подобного рода. При этом важно указать на то, что традиционные, относительно короткопериодические датчики можно с успехом использовать лишь при незначительном количестве статистических испытаний (не более периода ДПСЧ) и/или при отладке.