Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Уразаева Татьяна Альфредовна

кандидат экономических наук

заведующая, ФГБОУ ВО «Поволжский государственный технологический университет»

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

DOI:

10.7256/2306-4196.2016.6.19397

Дата направления статьи в редакцию:

06-06-2016


Дата публикации:

02-02-2017


Аннотация: Предметом исследования являются методы оптимизации и, в частности, методы случайного поиска (глобальных) экстремумов функций. Объектом исследования являются проблемы случайного поиска, связанные с заменой потока равномерно распределенных истинно случайных чисел на псевдослучайные последовательности. Авторами был сконструирован модельный пример, способный наглядно продемонстрировать возникновение ограничений метода равномерного случайного поиска в условиях, когда длина периода используемой псевдослучайной последовательности сравнима с потенциально достижимым количеством вычислений целевой функции на данном классе традиционных вычислителей. Показано наличие серьезных ограничений генератора псевдослучайных чисел, встроенного в VBA-подсистему пакета Microsoft Office, при использовании в алгоритмах случайного поиска. При синтезе модельной целевой функции были использованы методы алгебры и анализа. Основные результаты исследования были получены на основе проведения множества численных экспериментов и использования методов сравнения и обобщения. Основными выводами проведенного исследования являются тезис о нецелесообразности использования на современном этапе встроенного в VBA-подсистему пакета Microsoft Office датчика псевдослучайных чисел в алгоритмах случайного поиска и рекомендация замены встроенного датчика на генераторы нового поколения, такие как, например, «вихрь Мерсенна».


Ключевые слова:

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

УДК:

519.853.4

Abstract: The subject of the research is the methods of optimization, in particular, methods of random search for the global extremum of functions. The object of the research is the problems of the random search connected with the replacing the flow of equally distributed truly random numbers with pseudorandom sequences. The authors have created a simulative example that can clearly demonstrate limitations of the method of equal random search in case when the period length of a pseudo-random sequence used is comparable to potentially achievable number of target function calculations in the given group of traditional calculations. The authors demonstrate that there are serious limitations of the random number generator installed in the VBA-subsystem of the Microsoft Office package when using the option of random search in algorithms. When synthesizing the model target function, the author has used the methods of algebra and analysis. The main results of the research is the statement about impractibility of using the pseudo-random number generator installed in the VBA-subsystem of the Microsoft Office package in random search algorithms and recommendations on how to replace the installed sensor with the new generation generators such as Mersenne twister.   


Keywords:

Mersenne twister, smooth function, linear congruential generator, nonlinear programming, continuous function, optimization, stochastic optimization, Rosenbrock function, objective functions, extremum

Введение

Алгоритмы случайного поиска получили достаточно широкое распространение при решении задач как безусловной, так и условной оптимизации, как при поиске локальных, так и глобальных экстремумов [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` .

func_rosen_000

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

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

func_rosen_001

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

Результаты численных экспериментов

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

process_000

Рис. 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, позволяет избежать проблем подобного рода. При этом важно указать на то, что традиционные, относительно короткопериодические датчики можно с успехом использовать лишь при незначительном количестве статистических испытаний (не более периода ДПСЧ) и/или при отладке.

Библиография
1. Аоки М. Введение в методы оптимизации / М. Аоки. М.: Наука, 1977. 344 с.
2. Бородин А.В. Модель ценообразования на рынке розничных ссудных продуктов коммерческого банка / А.В. Бородин // Экономика. Теория и практика: материалы IV международной научно-практической конференции (17 декабря 2015 г.). Саратов: Издательство ЦПМ "Академия Бизнеса", 2015. С. 46-49.
3. Бородин А.В. Об одном подходе к оптимизации инвестиционных и страховых портфелей / А.В. Бородин // Обозрение прикладной и промышленной математики. 2001. Т. 8. В. 1. С. 110-111.
4. Бородин А.В. Об отдельных аспектах применения методологии Монте-Карло в оценке риска кредитного портфеля в среде Microsoft Office / А.В. Бородин // Экономика. Теория и практика: материалы международной научно-практической конференции (13 августа 2014 г.). Саратов: Издательство ЦПМ "Академия Бизнеса", 2014. C. 22-36.
5. Бородин А.В. Оптимизация стоимости владения объектно-ориентированной метасистемой в условиях заданной модели угроз / А.В. Бородин // Обозрение прикладной и промышленной математики. 2006. Т. 13. В. 5. С. 843-844.
6. Бородин А.В. Реконструкция и исследование датчика псевдослучайных чисел в VBA-подсистеме Microsoft Office / А.В. Бородин // NB: Кибернетика и программирование. 2014. № 4. С. 14-45.-DOI: 10.7256/2306-4196.2014.4.12648.
7. Бородин А.В. Экономические приложения нелинейной оптимизации / А.В. Бородин, Т.А. Уразаева // Пятые Вавиловские чтения. Мировое сообщество и Россия на пути модернизации. Экономика и управление в современном обществе. Йошкар-Ола: Марийский государственный технический университет, 2002. С. 280-286.
8. Жиглявский А.А. Методы поиска глобального экстремума / А.А. Жиглявский, А.Г. Жилинскас. М.: Наука, 1991. 248 с.
9. Уразаева Т.А. Алгебра рисков: теория и алгоритмы / Т.А. Уразаева. Йошкар-Ола: Поволжский государственный технологический университет, 2013. 209 с.
10. Химмельблау Д. Прикладное нелинейное программирование / Д. Химмельблау. М.: Мир, 1975. 534 с.
11. Matsumoto M. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator / M. Matsumoto, T. Nishimura // ACM Transactions on Modeling and Computer Simulation (TOMACS). Special issue on uniform random number generation. 1998. Vol. 8. Iss. 1. P. 3-30. - DOI:10.1145/272991.272995.
12. Mersenne Twister VBA Class // Directory of Open Source for Quantitative Finance and Trading.-URL: http://www.quantcode.com/modules/mydownloads/singlefile.php?cid=9&lid=610/. Дата обращения: 18.07.2014.
13. Rosenbrock H.H. An automatic method for finding the greatest or least value of a function / H.H. Rosenbrock // The Computer Journal.-1960. Vol. 3. P. 175-184. - DOI: 10.1093/comjnl/3.3.175.
References
1. Aoki M. Vvedenie v metody optimizatsii / M. Aoki. M.: Nauka, 1977. 344 s.
2. Borodin A.V. Model' tsenoobrazovaniya na rynke roznichnykh ssudnykh produktov kommercheskogo banka / A.V. Borodin // Ekonomika. Teoriya i praktika: materialy IV mezhdunarodnoi nauchno-prakticheskoi konferentsii (17 dekabrya 2015 g.). Saratov: Izdatel'stvo TsPM "Akademiya Biznesa", 2015. S. 46-49.
3. Borodin A.V. Ob odnom podkhode k optimizatsii investitsionnykh i strakhovykh portfelei / A.V. Borodin // Obozrenie prikladnoi i promyshlennoi matematiki. 2001. T. 8. V. 1. S. 110-111.
4. Borodin A.V. Ob otdel'nykh aspektakh primeneniya metodologii Monte-Karlo v otsenke riska kreditnogo portfelya v srede Microsoft Office / A.V. Borodin // Ekonomika. Teoriya i praktika: materialy mezhdunarodnoi nauchno-prakticheskoi konferentsii (13 avgusta 2014 g.). Saratov: Izdatel'stvo TsPM "Akademiya Biznesa", 2014. C. 22-36.
5. Borodin A.V. Optimizatsiya stoimosti vladeniya ob''ektno-orientirovannoi metasistemoi v usloviyakh zadannoi modeli ugroz / A.V. Borodin // Obozrenie prikladnoi i promyshlennoi matematiki. 2006. T. 13. V. 5. S. 843-844.
6. Borodin A.V. Rekonstruktsiya i issledovanie datchika psevdosluchainykh chisel v VBA-podsisteme Microsoft Office / A.V. Borodin // NB: Kibernetika i programmirovanie. 2014. № 4. S. 14-45.-DOI: 10.7256/2306-4196.2014.4.12648.
7. Borodin A.V. Ekonomicheskie prilozheniya nelineinoi optimizatsii / A.V. Borodin, T.A. Urazaeva // Pyatye Vavilovskie chteniya. Mirovoe soobshchestvo i Rossiya na puti modernizatsii. Ekonomika i upravlenie v sovremennom obshchestve. Ioshkar-Ola: Mariiskii gosudarstvennyi tekhnicheskii universitet, 2002. S. 280-286.
8. Zhiglyavskii A.A. Metody poiska global'nogo ekstremuma / A.A. Zhiglyavskii, A.G. Zhilinskas. M.: Nauka, 1991. 248 s.
9. Urazaeva T.A. Algebra riskov: teoriya i algoritmy / T.A. Urazaeva. Ioshkar-Ola: Povolzhskii gosudarstvennyi tekhnologicheskii universitet, 2013. 209 s.
10. Khimmel'blau D. Prikladnoe nelineinoe programmirovanie / D. Khimmel'blau. M.: Mir, 1975. 534 s.
11. Matsumoto M. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator / M. Matsumoto, T. Nishimura // ACM Transactions on Modeling and Computer Simulation (TOMACS). Special issue on uniform random number generation. 1998. Vol. 8. Iss. 1. P. 3-30. - DOI:10.1145/272991.272995.
12. Mersenne Twister VBA Class // Directory of Open Source for Quantitative Finance and Trading.-URL: http://www.quantcode.com/modules/mydownloads/singlefile.php?cid=9&lid=610/. Data obrashcheniya: 18.07.2014.
13. Rosenbrock H.H. An automatic method for finding the greatest or least value of a function / H.H. Rosenbrock // The Computer Journal.-1960. Vol. 3. P. 175-184. - DOI: 10.1093/comjnl/3.3.175.