Об опыте использования различных датчиков псевдослучайных чисел в алгоритмах случайного поиска глобального экстремума функций

Уразаева Татьяна Альфредовна кандидат экономических наук заведующая, ФГБОУ ВО «Поволжский государственный технологический университет» 424032, Россия, Республика Марий Эл, г. Йошкар-Ола, ул. Павленко, 60 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 Другие публикации этого автора

Смирнова Светлана Юрьевна магистр, кафедра ИСЭ, ФГБОУ ВО «Поволжский государственный технологический университет» 424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3 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, позволяет избежать проблем подобного рода. При этом важно указать на то, что традиционные, относительно короткопериодические датчики можно с успехом использовать лишь при незначительном количестве статистических испытаний (не более периода ДПСЧ) и/или при отладке.