О некоторых методах исследования алгоритмов поиска и оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

р Г Б ОА 1 о АПР 1935

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ЧЕКМАСОВ Максим Валентинович

О НЕКОТОРЫХ МЕТОДАХ ИССЛЕДОВАНИЯ АЛГОРИТМОВ ПОИСКА И ОПТИМИЗАЦИИ

Специальность: 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ 1995 г.

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель:

доктор физико-математических наук, профессор A.A. Жиглявски{

Официальные оппоненты:

доктор физико-математических наук, ст.науч сотр. Б.В. Седунов кандидат физико-математических наук, доцент А.Н. Коваленко

Ведущая организация: Санкт-Петербургский Технический Университет

Защита состоится 27 апреля 1995 г. в ~~~ часов на заседании диссертационного совета К 063.57.49 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, г. Санкт-Петербург, Старый Петергоф, Библиотечная площадь, дом 2, математико-механический факультет СПбГУ.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного з'ниверситета по адресу: 199034, г. Санкт-Петербург, Университетская набережная, дом 7/9.

Автореферат разослан " <?3" 1995 г.

Ученый секретарь

диссертационного Совета К 003.57.49, кандидат физ.-маг. наук, доцент

А.И. Шепелявый

Общая характеристика работы

Актуальность темы. В современных условиях научно-техничес-<ий прогресс в значительной мере определяется степенью исполь-ювания математических методов в управлении, автоматизации, 1ланировании и проектировании. Многие задачи при этом форму-шруются в виде задач поиска и оптимизации. Поэтому проблемы юиска и оптимизации являются важными проблемами современ-юй вычислительной математики и математической кибернетики. Эбласти приложений, где встречаются подобные задачи, включает в себя такие разные дисциплины, как медицина, информатика, 1скусствениый интеллект, техника. Решение указанных задач не-юсредственно связано с использованием компьютеров.

Большой вклад в развитие теории поиска внесли такие уче-пле, как А. Дорфман, Р. Альсведе, Д. Кнут и Г. Уинн. Ре-|ультаты в области оптимизации в значительной мере определяется работами таких ученых, как Й.Б. Моцкус, Р.Г. Стронгин, П.А. Растригин, С.М. Ермаков, A.A. Жиглявский, А.Г. Жилин-:кас, Ю.А. Сушков и других.

Дель работы. Целью работы является разработка и исследова-гие пассивных методов поиска объектов общей природы и ада-1тивных алгоритмов оптимизации, в том числе двух методов гло-5альной оптимизации, а также формулирование нового подхода к ^.следованию градиентного алгоритма.

Методы исследования. В работе применяются методы вычи-:лительной математики (теория приближений, равномерные сет-си), теории вероятностей (предельные теоремы, вероятностные 1еравенства), математической статистики (экстремальные поряд-:овые статистики).

Научная новизна.

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

с простым случайным выбором, который является составной частью некоторых <irur лтогически оптимальных схем покрытий.

- Рассмотрены две новые схемы исследования алгоритмов поиска глобального экстремума. Проведен > теоретическое обоснование использования предложенных схем и тщательное численное сравнение.

- Предложен новый подход к исследованию градиентного алгоритма, основанный на. изучении динамической системы, получающейся из градиентного алгоритма путем подходящей репорма-лизации.

Практическая ценность. С помощью предложенных в работе алгоритмов могут быть решены весьма сложные практические задачи. Все алгоритмы, предложенные в работе, реализованы в виде программ ЭВМ, составляющих единую библиотеку программ по методам поиска и оптимизации. Примеры численных расчетов, реализованных на ЭВМ, приведены в диссертации.

Апробация работы. Результаты работы неоднократно докладывались на семинарах лаборатории статистических методов и моделирования систем НИИММ СПбГУ, кафедры статистического моделирования СПбГУ, кафедры математической кибернетики СПбГУ. Сделаны доклады по теме диссертации на международной конференции "Model-Oriented Data Analysis III" (С.-Петербург, 1092) и международном семинаре "Mathematical Methods and Tools in Computer Simulation" (С.-Петербург, 1994).

Публикации. По теме диссертации опубликовано 4 работы.

Об-ьем работы. Диссертация состоит из введения, трех глав и заключения, изложена на 100 страницах, включая G таблиц. 33 рисунка и списка литературы, содержащего "Г, наименований.

Содержание работы

Во Введении кратко изложена актуальность темы исследования и описание решаемых задач.

Глава 1 посвящена оптимальным пассивным алгоритмам поиска. В § 1 Главы 1 даются понятия и результаты, которые будут использоваться в дальнейшем. В частности, приведены определения понятий теории поиска, равномерных последовательностей, случайных и квазислучайных последовательностей, приведены примеры указанных последовательностей и некоторые их свойства. Теория поиска рассмотрена с геометрической точки зрения и показана ее тесная связь с задачами построения оптимальных покрытий области поиска.

§ 2 посвящен описанию различных критериев оптимальности пассивных алгоритмов поиска (сеток) и сравнению различных сеток по этим критериям оптимальности. Рассмотрены типичные для математической статистики минимаксный, байесовский подходы, а также аналогичные стандартному в теории информации энтропийному критерию. Исследован целый ряд критериев, основанных на многогранниках Вороного, а также характеристики, связанные с интегрированием, наиболее известным из которых является разброс (discrepancy). Рассмотрены характеристики, связанные с покрытием области поиска Л', в частности р-разброс (dispersion) или минимальный радиус покрытия. Приведено обобщение понятия р-разброса по отношению к мере ft, заданной на множестве X. Пусть В € В - множество, принадлежащее некоторой системе В выпуклых множеств одного вида, Хл-- сетка, определенная в Я' и состоящая из N элементов. Тогда предлагаемый критерий представим в виде:

Р= с-(p^XtBfl)(XN))1/ ,

где с = [^(единичного шара в эвклидовой метрике)]1'1*, d — размерность пространства и

Пх.в.лСХ-я) =«"p{/i(B) : В ев, хЛ-П^ = й} •

В случае, к.>гда В - множество шаров, введенное определение р-разброеа совпадает со стандартным.

Пусть Т € Т - некоторая цель поиска, принадлежащая множеству целей Т. Рассмотрена задача выбора множеств разбиения как непересекающихся интервалов в случае размерное :и пространства (I = 1. Покизнно. что при использовании пассивных

методов для поиска цели с априорным распределением тг(4) оптимальным по отношению к энтропии разбиением является расстановка интервалов поиска пропорционально it(t).

Представлены примеры типичных сеток на X = [0,1], проведено вычисление различных критериев для рассматриваемых сеток.

В § 3 рассмотрена задача построения оптимальных сеток для интегрирования характеристических функций от параллелепипедов. Пусть X = 0 - единичный куб в Rd: X = в = [О, l]d; f(x, в) -характеристическая функция точки # = :-,(>d) в X, то есть

f 1 если а^. < 0,- (j = 1,. .., ci), J/i = = !{*(<«} = ^

I 0 dпротивном случае.

d

Пусть Т(в) = П - интеграл функции f{x,6) по X. Т(в) оцени-j-i

вается линейной оценкой:

1 " 1 ~ jE/M-jrEi.

i=l i: ц <е

Точность этой оценки часто измеряют с помощью так называемого />^-разброса:

D"n = sup «€[0,1]''

Данная величина имеет наибольшую асимптотическую скорость убывания log N/N при N —» оо. Это значение скорости улучшено с использованием вида функции /. Вначале оценивается в

некоторым согласующимся с наблюдениями 0', а затем строится d

оценка Т = П в1-. Делается это следующим образом. i=i

Берется план, состоящий из N =.dk точек вида

(.г,,0,0,...,0) (г = 1

(О, .г,-,0, . . . ,0) (ial,...,H),

4=1 1=1

(0,0,...., а-,-) (¿-1.....к).

где 0 = х0 < < .. . < Хь < 1 = Согласующиеся с на-

блюдениями множества для в = (0\,... представляют собой параллелепипеды вида

Q(ii,...,id) = (1)

где »j,.. .,ij - целые, 0 < ij < к для всех j = 1,.. ,,d. Минималь-

d

ное и максимальное значения объема Т(в) — П равны соответственно

d d

П*., и IWi-,=l ,=l

В качестве критерия для выбора плана рассматривается минимаксный критерий

И|с(«1,..-,*лг) = «ир|Г-Г(в)|в вир sup |5Г-2"(*)| = в >......<<«ев(1,.....

= \ sup in *•■,+» - п

Расположенные на равном расстоянии точки Х{ = j^j-, i = 1 ,...,& задают гиперкуб в качестве параллелепипеда

с наибольшим значением ошибки |Т — Г(0)[, и поэтому

v"c (гп.....ITi) = 5 (* - Gil) ) " ^ при ^00 ■

Такой выбор точек плана показывает, что скорость сходимости равна, по крайней мере, const х f, к —»• оо. Это наилучшее из возможных значений скорости для минимаксного критерия, и поэтому указанная выше константа может служить критерием асимптотической оптимальности. Рассмотрен численный пример оптимального расположения точек плана для d = 2 и N = 2.

§ 4 посвнщен алгоритмам построения покрытий пространства тарами одинакового радиуса. Пусть Ю.1' - (¡-мерное эиклидопо пространство, /i - мера Лебега, Л — шар в И"*, /i(B) > 0, С = [О, 1)J - полуоткрытый куб в R'', сторону которого параллельны осям

координат, я (С) = 1 - длина, стороны куба. Назовем трансляцией множества К- на вектор а параллельный перенос К- на вектор а и обозначим {К + а}. Определим К как счетную систему шаров В. Если шары В С. 1С организуют полное покрытие куба С (то есть если х € С, то х е В, где В С /С), то система множеств {К + £,■}, где Х( € Zl', полносг-ью покрывает пространство К. . В этом случае определим плотность покрытия как

«=£/«(*). (2)

где суммирование ведется по всем В С. 1С. Очевидно, что <5 > 1. Чем меньше значение плотности покрытия, тем более экономное покрытие мы построили.

Для случая неполного покрытия определим

так, что Ф(/С,С) - относительная мера части куба С, не покрываемой шарами системы К. Если значение Ф(1С, С) мало, то шары системы К покрывают большую часть куба. Определим величину

ф+(£) = й^"<(С)_00ф(х;, с), (з)

которая является относительной мерой непокрытия всего пространства.

В теореме существования оптимальных покрытий ¿-мерного пространства, предложенной Роджерсом, строится оценка математического ожидания величины (3) на основе случайной выборки центров шаров покрытия. В настоящей диссертации показано, что если использовать расслоенную выборку центров шаров покрытия, то полученные оценки могут быть только лучше. Введем обозначения Ф"г и Ф^"' для.математического ожидания величины (3) в случае расслоенной и случайной выборок соответственно. Справедлива следующая теорема.

Теорема 1 Для любого шара В и положительного вещественного числа в Ф^г < ф"1<г и существует такая система Л" трансляций

шара В и такое в, что данное неравенство будет строгим: <

ф""'.

Далее в работе предложен алгоритм построения нерешетчатых покрытий, близких к оптимальным. Пусть имеется куб С = [0, 1)^. il размерность пространства, р - евклидова метрика, N - фиксированное натуральное число. Задача состоит в построении покрытия куба С шарами В радиуса г, 0 < г < 1. В кубе С строится кубическая сетка Ндг, состоящая из Nd элементов вида

.....i,.....id = 0,1.....N-l.

\N N NJ

Описание алгоритма следующее.

Алгоритм 1

1. Точка a-'i = (0,0,. .. ,0) е Едг; полагаем г = 1.

2. Полагаем к = О.

3. Точка z - независимая реализация случайного rf-мерного вектора с равномерным по сетке 3уу распределением.

4. Если p(z,Xj) < г хотя бы для одного j = 1,. .., i, то

• Полагаем к = к + 1;

• Если к > STOP, то переходим к Шагу 6;

• Переходим к Шагу 3.

о. Запоминаем точку х,- = z; полагаем i = г + 1 и переходим к Шагу 2.

6. Останов.

После окончания работы алгоритма предусмотрен следующий механизм проверки получения полного покрытия куба. Все точки сетки E.v проверяются на вхождение Хотя бы в один из шаров покрытия. Если находится точка сетки, не принадлежащая покрытию, покрытие достраивается шаром с центром в Данной точке. После окончания указанной процедуры увеличение радиуса шарив покрытия в соответствии со следующей теоремой обеспечивает получение полного покрытия.

Теорема 2 Пусть С = [0,1]"*. Есл и любая точка сетки с длиной

к

шага по каждой координате принадлежит U Bc(xi), то любая

¡=1

t

точка куба С принадлежит U Bc+h\fii(xi)> = 2JV'

<=1

Алгоритм 1 реализован в виде компьютерной программы, с помощью которой получены численные результаты для различных значений размерности пространства d и радиуса шаров г.

Глава 2 посвящена исследованию алгоритмов поиска глобального экстремума. В § 1 Главы 2 рассмотрены общие понятия глобальной оптимизации. Проблема глобальной оптимизации может быть представлена в общем виде следующим образом. Пусть X -некоторое множество, которое называется множеством оптимизации, и /:.¥—♦ R - неизвестная функция из некоторого функционального класса J7, называемая целевой функцией. Тогда задача состоит в аппроксимации величины

Г = sup f(x) (4)

reX

и/или в нахождении точки х, из Л', где / принимает значение, близкое к /*.

В § 2 рассмотрена общая схема построения адаптивных алгоритмов покрытий в предположении, что они построены для оптимизации целевой функции с фиксированной погрешностью 6 > О по ef значениям.

В § 3 рассмотрена схема построения покрытий пространства шарами разного радиуса.

Пусть имеется целевая функция f(x) € Lip (X,L,p), заданная на некотором множестве .V 6 RJ, 6 > 0 - вещественное число, определяющее требуемую точность, и X = . .} - выборка точек в .V. получаемая последовательно. Будем считать, что константа Липшица L известна (в противном случае строится ее оценка). Опишем общую схему алгоритма построения покрытия шарами разного радиуса..

лгоритм 2

1. Вычислим значение целевой функции / в точке положим /; = /(.г,), е, = 6/Ь, « = 2.

2. Возьмем очередную точку .т; 6 X.

3. Если р(< для некоторого j = 1,...,г — 1, то положим с,- = 0, г —» г + 1 и переходим на Шаг 2.

Если р(х;,ху) > е,-, для любого = 1,. . ., г — 1, то переходим на Шаг 4.

4. (а) Вычисляем /(ж,).

(b) Если /(г,-) < то положим = /,*_,, е, = - /(*,•)! + А) и переходим на Шаг 2, изменяя 1 —> + 1.

(c) Если /(г,-) > /*_,, то положим /¡* = /(а;,), е} = -/;*| + 6) для всех 3 = 1,.. .,! и переходим на Шаг 2, заменяя г —> г + 1.

Имеются три естественных правила останова для Алгоритма 2:

(1) число Лг точек последовательности X достигает определенного значения;

(п) число Л = точек а;,-, в которых вычислялась целевая

функция / достигает определенного значения;

(Ш) Шаг 4 не посещался заданное число успешных итераций.

Пусть N - выбранное правило останова. Целью работы Алго-

■V

ритма 2 является построение покрытия Ы £;, р) множества

'=1

Л' шарами разного радиуса. Радиус шара с центром в некоторой точке ж, выборки характеризует перспективность поиска глобального экстремума а окрестности .г,-. Чем больше значение радиуса шара г, тем менее перспективна область поиска в окрестности данной точки. В соответствии с Алгоритмом 2 значения функции вычисляются не во всех точках выборки, а лишь в тех, которые вошли в последовательность центров шлроп покрытия. По результатам работы компьютерных программ, реализующих указанный

алгоритм, представлены графики некоторых характеристик Алгоритма 2.

§ 4 посвящен исследованию точности случайной и расслоенной выборок в методе ветвей и вероятностных границ. Теоретические выводы о точности статистических выводов, построенных по элементам расслоенной выборки, по сравнению с аналогичными выводами, построенными по случайной выборке, проверены численно. Среди прочих, представлены графики функций

М ~an о/ ч E(,'mJ - М)г

Фи, 1/а) = - и Ф(/,2/а) = ——-гтт">

' > М — Етщ ' E(r,N - MY

по критерию среднего и дисперсии, где ri„,j, - соответствующие расслоенной и случайной выборкам порядковые статистики А/ = ess sup»j, а — параметр формы распределения экстремальным значений.

В качестве основного примера для численного сравнения выбрано множество оптимизации X = [0, l]1*, где <1 - размерност! пространства, и целевая функция вида

/(а\г*) = -рг(х,х"). (5]

С точки зрения оптимизации максимизация целевой функции (5] эквивалентна рассмотрению

Р*(Х; Л', р) = f />(r,X)p(cte)

в качестве критерия оптимальности для выбора плана X.

По результатам компьютерного моделирования представлен!, графики, демонстрирующие доминирование расслоенной выбор ки над случайной по рассматриваемому критерию.

В Главе 3 приведено численное исследование различных вариан тов градиентного алгоритма с точки зрения поведения динами ческой системы, которую образует этот алгоритм. § 1 Главы ; посвящен описанию механизма ренормализации области поиске •V, приведены примеры типичных динамических систем.

В I; 2 кратко описаны необходимые понятия эргодической те орич. показатели Ляпунова, обсуждается понятие эргодическо1 скорости сходимости алгоритма.

3 посвящен исследованию градиентного алгоритма и обсуждению численных результатов.

Пусть Л (/х г' неотрицательно-определенная матрица, и пусть целевая функция является квадратичной

/(.г) = / Л,.

Не умаляя общности, можно заменить матрицу А на диагональную матрицу Н, диагональными элементами которой являются расположенные по возрастанию собственные числа матрицы Л. Тогда алгоритм можно записать в виде

ГЫ1 = (/ - , (б)

где I - единичная матрица размера Л х Н. Оптимальная длина шага гц. градиентного алгоритма определяется из условия минимизации

.с1(1~<Ч11)Н(Г-якН)*к

н принимает значение

Использовалась ренормализация, которая оставляет минимизируемую точку в начале координат (О,. ... 0) и просто масштабирует тц на его же норму, чтобы ренормализованный процесс всегда оставался на единичной сфере. Скорость сходимости на итерации А- является отношением норм

11-^1 II

Это выражение можно интерпретировать как обратное к отношении» констант ренормалиэации на каждом шаге.

По результатам исследования алгоритма для квадратичной функции в случае размерности пространства <1 = 3 сделаны следующие выгоды.

(¡) Асимпготичгекая скорость сходимости алгоритма зависит как от функции, так и от начальной точки. Для квадратичной функции скорость зависит от наименьшего и наибольшего значений собственных чисел квадратичной формы, определяющей функцию. Зависимость от начальной точки очень слш.'НЯ!! благодаря наличию фракталоподпбной сгруп'чры

П

(и) Было высказано предположение, которое не доказано аналитически, что ренормализованный алгоритм притягивается к двумерной плоскости. Наличие фракталоподобной структуры ставит под сомнение возможность найти доказательство этого факта в литературе.

(ш) В предположении притяжения к размерности 2 найден двухточечный аттрактор, чьи значения точно задают скорость, аттрактор зависит от начальной точки.

Введение коэффициента ослабления в градиентный алгоритм, то есть

полностью меняет асимптотическое поведение алгоритма. Для фиксированной И в зависимости от значения 7 ренормализованный процесс притягивается к периодическим траекториям, независящим от начальной точки, то есть показывает хаотическое поведение.

В Заключении кратко сформулированы основные результаты работы и предложены направления дальнейших исследований.

Основные результаты работы

1. Проведена систематизация критериев для пассивных алгоритмов поиска и сравнение различных алгоритмов поиска по данным критериям.

2. Показано, что применение расслоенной выборки дает улучшение по сравнению со случайной выборкой в схемах построения асимптотически оптимальных покрытий пространства шарами одинакового радиуса и приведена схема построения покрытий, близких к оптимальным, использующая квазислучайные сетки.

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

О < 7 < 1 ,

4.

Проведено сравнение случайных и квазислучайных методе ветвей и вероятностных границ.

сеток в

5. Проведено численное исследование некоторых свойств градиентного алгоритма, основанных на рассмотрении его как динамической системы в ренормализованном пространстве.

Автор глубоко признателен Анатолию Александровичу Жигляв-

скому и Сергею Михайловичу Ермакову за постоянную помощь

и поддержку при выполнении данной работы.

Список литературы

[1] M.V. Chekmasov., M.V. Kondratovich. Covering based on a stratified sample. // В трудах межд. конф. MODA-3 (W.G. Miiller, H.P. Wynn, A.A. Zhigljavsky (ред.)), Physica-Verlag, 1993, c. 265268.

[2] M.V. Chekmasov. Comparison of random and stratified sampling in some problems of approximation and search. // В трудах межд. сем. MMTCS-94 (S.M. Ermakov (ред.)), Изд. СПбГУ, 1994, с. 50-51.

[3] A.A. Zhigljavsky, M.V. Chekmasov. Optimizing step-length of the gradient algorithms for quadratic programming problems. // В трудах межд. сем. MMTCS-94 (S.M. Ermakov (ред.)), Изд. СПбГУ. 1994, с. 75-77.

[4] М.В. Чекмасов. Применение вероятностных методов для задач построения оптимальных покрытий. // Вестник СПбГУ. 4, 1994, с. 320 123.

[5] A.A. Zhigljavsky, M.V. Chekmasov. Comparison of independent, stratified and random covering sampling schemes in optimization problems. // Mathematical and Computer Modelling, (в печати).