Введение к работе
Актуальность темы. Важным разделом оптимизации - одной из центральных задач вычислительной и прикладной математики - является теория глобальной оптимизации. Достаточно широко распространенными методами решения задач глобальной оптимизации являются методы глобального случайного поиска. Однако многие имеющиеся алгоритмы содержат большое число параметров, выбор которых определяется скорее эвристическими соображениями и опытом пользователя, чем строгими математическими результатами. В целом, несмотря на появление в последнее время ряда математических монографий по этой тематике, теория глобального случайного поиска представляется гораздо менее разработанной, чем, скажем, теория локальной оптимизации.
Темой диссертации является изучение скорости сходимости некоторых марковских алгоритмов глобального случайного поиска, причем основное внимание уделяется изучению Порядков оценок этой скорости сходимости сверху и снизу при стремлению требуемой точности Ъ к нулю. Если целью поиска является определение эсс. = o-"wj*w«.3c (х} (предположим, что такая точка единственна, а функция |- вычисляется без случайной ошибки) с точностью до Є в некоторой подходящей метрике, то хорошей характеристикой случайного поиска, использующего только значения целевой функции f , будет являться величина Еть , где ~С$_ - число вычислений функции f , необходимое для первого "попадания поиска в є. - окрестность х0 . Зту величину естественно называть трудоемкостью рассматриваемого случайного поиска. Другой естественной характеристикой скорости сходимости является такое число АЧ )у) вычислений целевой функции, при котором достижение I - окрестности зср гарантировано с вероятностью . «ункция N(t,x) будет называться гарантированным числом шагов случайного поиска.
Оценки этих характеристик и рассматриваются в диссертации, причем ~( и /V ( j у) будут в точности совпадать с "числом шагов" соответствующего случайного поиска.
Цель работы - исследование трудоемкости и гарантированного числа шагов некоторых классов марковских случайных поисков, причем параметры ("форма") поиска подбираются таким образом,
- 4 -чтобы сделать эти характеристики минимальными хотя бы по порядку при ->.0.
Общая методика выполнения исследований. В работе использовалась теория вероятностей, общая теория марковских процессов с дискретным временем и вариационное исчисление.
Научная новизна. В работе содержится ряд новых результатов, а именно:
построен такой однородный марковский случайный поиск, трудоемкость и гарантированное число шагов которого (аппроксимация "по аргументу") имеют вид 0 (c(x,f ,02^0 . В случае регулярного поведения целевой функции в окрестности экстремума коэффициент с Qoc, f, і} ограничен по Ь . При этом для построения поиска не нужна информация о целевой функции.
показано, что для широкого класса неоднородных мар-
*
ковских случайных поисков, обладающих естественным свойством симметрии, трудоемкость не может быть меньше, чем С1&и,.\.
- построенный однородный поиск применен для оценки макси
мального значения целевой функции. Выведенные оценки трудоем
кий и гарантированного числа шагов (аппроксимация "по функ-
'ции") в целом аналогичны оценкам при аппроксимации "по аргументу".
рассмотрен поиск, являющийся вероятностной смесью случайного и детерминированного методов. Показано, что если в окрестности экстремума целевая функция "достаточно хороша", то порядок трудоемкости смеси наследует свойства более быстрого локального метода.
показано, что учет априорной информации о целевой функции (заданной в виде коэффициента ассиметрии) позволяет минимизировать константы при порядках оценок трудоемкости и гарантированного числа шагов однородного случайного поиска.
при наличии априорной оценки коэффициента ассиметрии построен такой неоднородный поиск, гарантированное число шагов которого (при фиксированной надежности) для регулярных в окрестности экстремума целевых функций имеет порядок I &~ I \%
«
- при более богатой информации о целевой функции построен
такой неоднородный поиск, который гарантирует попадание в
-окрестность точки экстремума с вероятностью 1 за конечное число шагов M(l-,l). При этом, для регулярных в -окрестности экстремума функций №{>!)- О([.-^.1 \~).
Практическая ценность. Построен легко моделируемый глобальный случайный поиск, который имеет "хорошие" (логарифмические) порядки трудоемкости и гарантированного числа шагов. Этот поиск успешно использовался (совместно с другими методами численной оптимизации) для решения некоторых реальных задач большой размерности. Разработанная техника получения оценок трудоемкости и гарантированного числа шагов, а также их оптимизации с учетом априорных сведений о целевой функции позволяет надеяться на получение содержательных результатов, связанных с анализом и оптимизацией более сложных используемых на практике алгоритмов.
Апробация. Результаты работы докладывались 'на третьей международной конференции "Model-Oriented Data Analysis", СПб, 1992 и на семинарах кафедры статистического моделирования математико- механического факультета СПбГУ.
Публикации. Основные результаты диссертации опубликованы в работах C1-3J.
Объем и структура работы. Диссертация состоит из введения, двух глав и заключения и занимает 160 страниц. Список литературы содержит 47 наименований.