ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 5, с. 817-828
УДК 519.676
О СКОРОСТИ СХОДИМОСТИ ОДНОРОДНОГО МАРКОВСКОГО МОНОТОННОГО ПОИСКА ЭКСТРЕМУМА
© 2007 г. А. С. Тихомиров
(173003 Великий Новгород, ул. Большая Санкт-Петербургская, 41, Новгородский „ос. ун-т)
e-mail: tikho@novsu.ac.ru Поступила в редакцию 17.05.2006 г.
Приведена оценка скорости сходимости некоторых однородных марковских монотонных алгоритмов случайного поиска экстремума. Библ. 19.
Ключевые слова: случайный поиск, глобальная оптимизация, оценка скорости сходимости алгоритмов.
1. ВВЕДЕНИЕ
В работе продолжено начатое в [1] теоретическое исследование известного семейства марковских алгоритмов случайного поиска экстремума (см. [2]-[4]). Эти методы давно и успешно (см. [5]-[8]) используются для решения сложных задач оптимизации.
Отметим явную недостаточную теоретическую исследованность случайного поиска. Существенное отставание теории глобального случайного поиска от потребностей практики отмечено в [2], [3] и видно по [9]. Этим во многом и объясняются столь разные выводы о свойствах методов. Теоретическому исследованию случайного поиска и посвящена данная работа.
Наиболее простыми являются утверждения, касающиеся сходимости случайного поиска. Гораздо более интересны утверждения о скорости сходимости случайного поиска. По определению, будем называть метод "быстрым", если число вычислений целевой функции, требуемое для достижения заданной точности £ решения задачи, имеет медленный (логарифмический) порядок роста при стремлении £ к нулю. В [1] и в данной работе получены теоретические оценки скорости сходимости и с их помощью построен класс быстрых методов оптимизации "невырожденных" целевых функций. Для сравнения отметим, что оценки, приведенные в [2], [3] и [9], показывают гораздо более плохую - степенну ю (т.е. O(1/£a) при a > 0) зависимость требуемого числа вычислений целевой функции от £. Таким образом, в свете известных теоретических оценок скорости сходимости, методы стохастической глобальной оптимизации, как правило, являются "медленными" методами.
Исследуемый поиск можно считать "предельным случаем" (см. п. 2.3) алгоритма "имитация отжига" (simulated annealing). При этом известные теоретические оценки скорости сходимости (см. [9]) относят алгоритм "имитация отжига" к медленным методам оптимизации, а исследуемый поиск является быстрым.
Также отметим, что для получения быстрого поиска совсем не нужно жертвовать сходимостью метода. Кроме того, представленные методы остаются быстрыми, даже если не используют никакую априорную информацию о целевой функции (и вообще не содержат эвристических параметров). Что касается медленной скорости сходимости в наихудших случаях, то в свете результатов минимаксного подхода (см. [10]), в наихудших случаях медленным окажется любой метод оптимизации.
По поводу уменьшения доли случайности можно сказать, что рассматриваемое семейство методов допускает использование и расслоенных выборок, и случайных, и даже неслучайных сеток (см. [11]). Но на этом пути есть свои трудности. Например, хотя в поиске (см. [5]) можно заменить повторную выборку расслоенной, авторы в дальнейшем (см. [6]) предпочли быстро меняющийся (адаптирующийся) вид поиска. Такая адаптация также дает определенный выигрыш, хотя и затрудняет применение расслоенных выборок.
Что касается усложнений, направленных на улучшение алгоритма, то рассматриваемое семейство методов легко допускает различные модификации (легкость модификации - это одно из признанных достоинств методов случайного поиска). Отметим два направления совершенствования изучаемого поиска. Первое направление состоит в использовании "хороших" свойств це-
левой функции в некоторой окрестности глобального экстремума и в применении наряду со случайным поиском одного из методов локальной оптимизации (т.е. метода поиска локального максимума целевой функции). Как пример такого подхода, в [11] и [12] рассмотрен поиск, являющийся "смесью" случайного и детерминированного методов. Пусть выбран некоторый метод локальной оптимизации (например, градиентный метод) и рассмотренный в данной работе марковский случайный поиск. Общая идея состоит в том, что на каждом шаге нового поиска с некоторой вероятностью применяется локальный метод и с дополнительной вероятностью - глобальный случайный поиск. На целевую функцию при этом налагаются дополнительные ограничения, обеспечивающие реализуемость и быструю сходимость выбранного локального метода в некоторой (заранее не известной) окрестности экстремума. Оказывается, что в этой ситуации смесь методов оптимизации наследует хорошие свойства составляющих ее методов, а порядок трудоемкости такой смеси наследует свойства более быстрого локального метода.
Второе направление совершенствования предназначено для преодоления еще одного "слабого места" исследуемого поиска. В работе изучается очень просто устроенный марковский случайный поиск. На каждом своем шаге он помнит только одну (лучшую) из полученных ранее точек поиска. Если целевая функция вдали от точки глобального максимума имеет несколько локальных максимумов, близких по величине к глобальному максимуму, то эффективность такого поиска будет мала. Чтобы преодолеть указанный недостаток, нужно запоминать несколько "хороших" точек. Для этого можно воспользоваться генетическими алгоритмами. В частности, можно применить генетические алгоритмы 5.1.1 и 5.1.2 из [2] и 6.9 и 6.10 из [3], в которых в качестве составной части (в качестве переходных функций Qs) использовать переходные функции поиска теоремы 4 (см. ниже).
Отметим также, что оба указанных направления совершенствования можно объединить. Ясно, что изучение таких модификаций по прежнему требует теоретического исследования входящего в них компонента - марковского случайного поиска.
2. ПОСТАНОВКА ЗАДАЧИ 2.1. Пространство оптимизации
Назовем пространством оптимизации множество оптимизации X, снабженное метрикой р. Ограничимся случаем X = К и следующими вариантами метрик р(х,у):
Рр(х, У) =
( к ^ 1/р
Р
\г = 1
х, у) = тах - у \;
1 <г< к
здесь р > 1 - любое фиксированное число, х = (хь ..., хк) и у = (у1, ..., ук). Замкнутый шар обозначим через Зг(х) = {у е Кк: р(х, у) < г} и положим
ф(г) = те8к(ЯДх)) = Агк,
где mesk означает к-мерную меру Лебега, А = А (к, р) - константа, зависящая от размерности пространства и от метрики р.
2.2. Целевая функция
В дальнейшем всегда будет предполагаться, что целевая функция/: Кк ^ К ограничена сверху, измерима и удовлетворяет следующим условиям.
Условие 1. Функция / принимает максимальное значение в единственной точке х0 = ш^тах{/х):
х е Кк}.
Условие 2. Функция / непрерывна в точке х0.
Условие 3. Неравенство sup{/х): х е 8СГ (х0)} </(х0) выполнено для любого г > 0.
Ввиду условия 3, из сходимости/(хи) —-/(х0) следует, что р(хи, х0) —► 0. Отметим, что функции указанного класса могут быть многоэкстремальными в любой окрестности глобального максимума. Еще одно условие на целевую функцию будет введено ниже.
2.3. Случайный поиск
Случайным поиском называется произвольная последовательность случайных величин
{^Лг > о со значениями в К . Если последовательность образует марковскую цепь относительно потока с-алгебр с(^0, • • •, ^), то поиск называется марковским, а если для любого г > 0 неравенство /) >/_ 1) выполняется с вероятностью 1, то поиск является монотонным. Далее будут изучаться марковские монотонные случайные поиски с переходными функциями специального вида.
Опишем класс исследуемых поисков. Пусть Вх = {у е К : /(у) >/(х)}; рассмотрим (вообще говоря, неоднородную) марковскую цепь {^г }г- > 0 с начальной точкой = х и переходными функциями
Яг (х, ■ ) = 5х(■)Рг (х, Всх) + р(х, ■ п Вх), (2.1)
где через 5х обозначено распределение, сосредоточенное в точке х. Как обычно, Р1 (х, ■) при любых г и х е К является вероятностной мерой и Рг(■, А) для всех г и любого борелевского множества
А является борелевской функцией в К. Очевидно, что Я1(х, Вх) = 1 и, значит, неравенства /> /_ 1) выполняются с вероятностью 1 при всех г > 0.
Запишем алгоритм моделирования п шагов описанного поиска. Обозначение "п -— Р(')" читается так: "получить реализацию случайного вектора п с распределением Р".
Алгоритм 1
Шаг 1. -— x; i -— 1.
Шаг 2. n — Pi & - i, ■).
Шаг 3. Если f(n) > - i), то ^ — n, иначе ^ — ^ - i.
Шаг 4. Если i < n, то i — i + 1 и перейти к шагу 2, иначе STOP.
Ниже для вероятностей событий и математических ожиданий случайных величин, связанных со случайным поиском алгоритма 1, начинающимся в точке x е [ , используются обозначения Px и Ex.
Далее будем рассматривать однородный марковский монотонный случайный поиск, переходные функции которого определяются формулой (2.1), причем вероятности Pt(x, dy) не зависят от i и обладают симметричной плотностью p(x, y) вида
p (x, y) = g (p( x, y)), (2.2)
где p - метрика, а g - невозрастающая неотрицательная функция, определенная на полуоси (0,
Легко видеть, что тогдаp(x, x + y) = p(0, y) при всех y Ф 0, x е [ . Функцию g будем называть формой поиска. Чтобы функция p(x, y), определенная в (2.2), была плотностью, форма поиска g должна удовлетворять условию нормировки
] g( гЩ( г) = 1.
(0, +
Не умаляя общности, будем считать, что функция g непрерывна слева.
Однородный марковский поиск с переходными функциями (2.1), обладающими плотностями вида (2.2), будем называть однородным марковским монотонным симметричным случайным поиском.
Рассмотрим метод случайного поиска, в котором условие выбора "новой" точки поиска на шаге 3 алгоритма 1 заменено на следующее правило:
Гп с вероятностью рг, 1 _1 с вероятностью 1- рг,
где
= Г1, если f(n)> ),
Р [exp[р,.(/(п) --1))], если f(n)<f(^_i),
в > 0 при всех г. После такой замены поиск станет методом "имитация отжига" (simulated annealing). Таким образом, исследуемый поиск можно считать предельным случаем алгоритма "имитация отжига" (с в. = при всех г). Свойства исследуемого поиска, однако, сильно отличаются от свойств алгоритма "имитация отжига", и заслуживают отдельного исследования.
2.4. Цель поиска
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.