close

Вход

Забыли?

вход по аккаунту

?

otchet po mo

код для вставкиСкачать
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования "Нижегородский государственный университет им. Н.И. Лобачевского"
Факультет вычислительной математики и кибернетики
Кафедра теории управления и динамики машин
КУРСОВАЯ РАБОТА
"Диагональные компонентные методы Я.Пинтера"
Выполнил: студент группы 8409
Авдеев Алексей Дмитриевич
Научный руководитель:
Доцент кафедры ТУиДМ,
кандидат физ.-мат. наук
Городецкий Станислав Юрьевич
Нижний Новгород, 2010
Содержание
1. Постановка задачи.
2. Диагональные алгоритмы.
3. Вычислительная схема.
4. Пример работы алгоритма.
5. Эксперименты.
6. Использованная литература.
1. Постановка задачи
Предположим, что целевая функция является многоэкстремальной, недифференцируемой, заданной в форме чёрного ящика и удовлетворяющей в области поиска (где D есть N-мерный гиперинтервал) условию Липшица с неизвестной константой Липшица . Таким образом будем рассматривать задачу
,
, ,
Где - заданные вектора, а обозначает евклидову норму. Также будем предполагать, что проведения испытания целевой функции даже в одной точке требует значительных вычислительных затрат.
2. Диагональные алгоритмы
Диагональный подход может быть неформально описан следующим образом. Каждый алгоритм, принадлежащий этой схеме, последовательно разбивает гиперинтервал поиска D на множество адаптивно генерируемых гиперинтервалов с вершинами и главными диагоналями (под главной диагональю будем понимать отрезок, соединяющий и гиперинтервала ), так что
, Формула описывает текущее диагональное разбиение области поиска D на k-итераций диагонального алгоритма. В ней обозначает границу подобласти , значение - число гиперинтервалов на начало итерации k алгоритма, и - число новых гиперинтервалов, сгенерированных алгоритмом при разбиении некоторого выбранного гиперинтервала на k-й итерации (при этом выбранный гиперинтервал текущего разбиения области поиска замещается новыми гиперинтервалами).
Поскольку проведение испытаний целевой функции даже в одной точке требует больших вычислительных затрат, в каждом гиперинтервале функция вычисляется только в двух точках, являющихся вершинами и гиперинтервала . На каждой итерации производится оценка "пригодности" гиперинтервалов текущего разбиения для дальнейшего дробления, где пригодность гиперинтервала часто может быть проинтерпретирована как вероятность того, что точка глобального минимума целевой функции принадлежит области .
Пригодность гиперинтервала численно выражается при помощи значения , называемого характеристикой интервала.
3. Вычислительная схема.
Предположим, что уже были выполнены итераций диагонального алгоритма. Итерация состоит из следующих шагов.
Шаг 1 (Вычисление характеристик). Для каждого гиперинтервала , , текущего разбиения , вычислить его характеристику
, ,
где v есть вектор параметром алгоритма.
Шаг 2 (Выбор гиперинтервала для разбиения). Выбрать гиперинтервал из с индексом t, , таким что
. (1)
Если имеется несколько гиперинтервалов с наибольшей характеристикой, то выбрать гиперинтервал с наименьшим индексом t, удовлетворяющим условию (1).
Шаг 3 (Условие остановки). Если
,
Где есть заданная точность, а и b - вершины главной диагонали начального гиперинтервала D, t находится по формуле, и обозначает евклидову норму, то завершить работу алгоритма. Принять в качестве оценки глобального минимума значение
,
достигаемое в точке
.
В противном случае перейти на Шаг 4.
Шаг 4 (Новое разбиение). Разбить гиперинтервал на , новых гиперинтервалов при помощи стратегии (оператора) разбиения P, т.е.
.
Шаг 5 (Новые испытания). Произвести новых испытаний функции в вершинах, соответствующих главной диагонали каждого из новых гиперинтервалов.
Установить
.
Увеличить счётчик итераций и перейти на Шаг 1.
4. Пример работы алгоритма.
Здесь я бы хотел привести пример работы конкретного диагонального алгоритма со схемой Деления пополам и характеристикой гиперинтервала с использованием метода ломаных.
, , Делаем измерения в точках a и b и строим оценку для исходного гиперинтервала. Находим точку разбиения S.
Делим гиперинтервал D по большей стороне, делаем измерения в точках на границах гиперинтервала, строим оценки, выбираем наилучшую оценку и ищем точку разбиения.
И т.д. до тех пор, пока не выполнится условие останова.
5. Эксперименты
Мною на языке C# была написана программа, позволяющая производить поиск минимума двумерных многоэкстремальных функций методом, описанным в работе. Ниже я хотел бы привести некоторые экспериментальные результаты, которые мне удалось получить.
Пример работы алгоритма на многоэкстремальной функции при небольшой точности.
Пример работы алгоритма на этой же функции, но с увеличением точности.
Можно заметить, что при большой точности метод практически попал в точку минимума функции.
Поиск минимума той же функции с большой фиксированной оценкой константы Липшица.
Можно заметить, что при больших значениях константы Липшица метод начинает вырождаться в метод равномерного перебора и проводит значительно большее число испытаний.
Пример работы метода на квадратичной функции.
Функция cos(10*x)^3+sin(10*y)^3
ТочностьКонстанта ЛипшицаКоличество разбиенийМинимум0,01285-0,9870,013130-0,550,0154100,630,01106990,990,012010560,990,01501868-0,960,0110031450,78
Можно заметить, что число испытаний растёт в линейной зависимости от выбора константы Липшица. При больших значениях константы и малой точности алгоритм может находить точки, далёкие от минимума.
Функция cos(10*x)^3+sin(10*y)^3
ТочностьКонстанта ЛипшицаКоличество разбиенийМинимум0,001285-0,9870,0013290-0,999670,0015768-0,99880,001107657-0,99850,0012013326-0,9987
Можно заметить, что с увеличением точности вычислений рост числа испытаний стал более зависим от увеличения константы Липшица.
Если сравнивать данный метод с методом равномерного перебора, то диагональный метод делает гораздо меньше испытаний при правильном выборе константы Липшица. К примеру, чтобы соблюсти точность 0,0001 на параллелепипеде [-2; 2,3]^2, методу равномерного перебора пришлось бы сделать 18490 испытаний, в то время как диагональный метод делает всего 338 испытаний функции.
6. Использованная литература
1. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: Учебное пособие. Н.Новгород: Изд. Нижегород. ун-та, 2007.
2. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. - М.: Физматлит, 2008. - 352 c. - ISBN 978-5-9221-1032-7..
Документ
Категория
Рефераты
Просмотров
36
Размер файла
855 Кб
Теги
otchet
1/--страниц
Пожаловаться на содержимое документа