Построение единой программной среды для решения задач глобальной оптимизации (стр. 1 из 9)
МИНИСТЕРСТВО ОБЩЕГО
И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ
АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математический факультет
Кафедра геоинформационных технологий
Построение единой программной среды
для решения задач глобальной оптимизации
Выполнил студент
5 курса, 441группы
Ахмеров Р.Р.
_________________________
(подпись)
Научный руководитель
ст. преподаватель
Жилин С.И.
_________________________
(подпись)
Допустить к защите Дипломная работа защищена
Зав. кафедрой "___"______________ 1999 г.
Поляков Ю.А., д.т.н, доцент ОЦЕНКА ________________
_______________________ Председатель ГАК
(подпись) _________________________
Ф.И.О.
"____"__________1999г. _________________________
(подпись)
Барнаул 1999
Реферат
В работе рассматривается вопрос решения задачи глобальной оптимизации. Обсуждаются основные методы для решения этой задачи, проводится их сравнительный анализ. Методы ветвей и границ представлены более полно, так как они служат базой для многих алгоритмов. Приводится детальное описание техники интервального и аффинного оценивания функций. Описываются основные ускоряющие способы для методов ветвей и границ, и выполняется их сравнительный анализ на основе примеров решений задачи глобальной минимизации для некоторых характерных функций. Также рассмотрены основные проблемы, возникающие при реализации таких алгоритмов на практике, и приведены способы их решения.
Работа содержит 6 рисунков, две таблицы и одно приложение. Общий объем работы составляет 39 страниц.
Содержание
Содержание 2
Введение 3
Обзор основных методов глобальной оптимизации 4
Стохастические методы 5
Моделируемый Отжиг 5
Методы кластеризации 6
Детерминированные методы 8
Метод ветвей и границ 8
Функции ограничения 10
Ограничение, основанное на константах Липшица 11
Интервальная арифметика 11
Обобщенная интервальная арифметика 12
Аффинная арифметика 13
Смешанная интервально-аффинная арифметика 16
Управление ошибкой округления 17
Оценка границ значений функций посредством
интервального разложения в ряд Тейлора 18
Схемы разбиения 19
Ускорение интервальных методов ветвей и границ 20
Back-Boxing 20
Аффинное оценивание элементарных функций 21
Аффинная оценка функции 
23
Аффинная оценка функции ex 24
Представление аффинных форм на ЭВМ 25
Общие подформулы 25
Практическая реализация алгоритмов 27
Автоматический анализ функций 28
Эффективное распределение памяти 30
Структурирование результатов 32
Численные результаты 32
Заключение 36
Литература 37
Приложение 38
Введение
Общая задача, рассматриваемая в данной работе, состоит в поиске минимума ¦* некоторой целевой функции ¦:W®R, определенной на компактном множестве WÍRn и множества всех минимизирующих переменных W*(¦) = {x* Î W: ¦(x*) = ¦*}. Поскольку в общем случае компактное множество может иметь сложную структуру здесь полагается, что W является параллелепипедом [x1,
1]´[ x2, 2]´…´ [ xn, n] Í Rn.Глобальная оптимизация без ограничений – одна из математических задач, рассматривается до сих пор и является очень сложной. Множество исследователей занимались решением этой задачи и некоторыми из них были приведены случаи NP-полных задач глобальной оптимизации. Точное доказательство NP-полноты очень трудоемко, но сложность решения не требует доказательства. В качестве примеров таких нелинейных задач, в которых поиск минимума (минимума или максимума) необходим для практики, можно привести задачу поиска направления и продолжительности радиационного облучения раковых опухолей, поиска состояния наименьшей энергии протеиновой молекулы, и задачу определения правильного соотношения составляющих смеси для оптимального протекания химической реакции.
Вначале работы приводится краткий обзор методов решения задачи глобальной оптимизации, основанных как на детерминированном и стохастическом подходах, и обсуждаются преимущества и недостатки этих методов. Методы ветвей и границ, относящиеся к детерминированным методам, представлены здесь более полно, так как они служат основой для широкого класса разрабатываемых алгоритмов.
Далее более подробно рассматриваются приемы реализации этих методов на ЭВМ, техника разработки и использования интервальной и аффинной арифметики для оценки диапазонов функций, и способы решения основных проблем, возникающих при разработке конкретных алгоритмов на практике.
В последней части приведены и прокомментированы числовые результаты, полученные при решении нескольких тестовых задач глобальной оптимизации различными методами.
Обзор основных методов глобальной оптимизации
Процедура общей глобальной оптимизации есть способ нахождения с заданной точностью минимума произвольной функции, для аргументов которой определены некоторые начальные границы. Допускается, чтобы границы переменных были бесконечными. Таким образом, идеальный оптимизатор (т.е. метод, решающий задачу общей глобальной оптимизации) есть черный ящик, на вход которого подается описание функции, ее связи, границы переменных и требуемая точность. Этот черный ящик генерирует на выходе одно из следующих состояний:
· Приближенные значения переменных, в которых функция достигает минимума с математически рассчитанными границами ошибок.
· Значения, которые аппроксимируют глобальный минимум с математически рассчитанной максимальной ошибкой.
· Функция не ограничена.
Первые два состояния можно охарактеризовать множеством параллелепипедов, гарантированно содержащих глобальный минимум. Другая возможность состоит в выдаче множества точек, для которого можно дать математически корректную вероятность того, насколько близко вычисленное наилучшее значение функции к ее глобальному минимуму. Эти ситуации соответствуют типу вывода по завершению детерминированного алгоритма или по завершению стохастического алгоритма соответственно. В следующих параграфах мы изучим такие алгоритмы подробнее. Для более детального рассмотрения этих алгоритмов можно обратится к работе [1], откуда и почерпнута значительная часть из ниже приведенных материалов.
Стохастические методы
Стохастическими методами для глобальной оптимизации называются бесконечные процессы, для которых вероятность посетить глобальный минимум достигает 1 при стремлении числа шагов к бесконечности. Наиболее простой из таких методов следующий:
Алгоритм 1: Случайный поиск
Инициализация: ¦min = ¥, xmin = any_number, и i = 0.
шаг 1: xi = случайное число.
шаг 2: если ¦( xi ) < ¦min установить xmin = xi, ¦min =¦( xi ).
шаг 3: увеличить i на 1 и перейти к шагу 1.
Если ¦ хотя бы кусочно непрерывна, то при i ® ¥, ¦min ® min ¦ на выбранной области. Этот процесс будет сходиться к глобальному минимуму не только на Rn, но и на любом множестве машинно-представимых чисел в случае реализации этой процедуры на компьютере.
Этот метод был изучен несколькими исследователями. Они показали, что если функция вычисляется в точках, равномерно распределенных в области W, то поиск наименьшего значения функции таким методом сходится к глобальному минимальному значению ¦* с вероятностью 1.
Моделируемый Отжиг
Моделируемый отжиг (simulated annealing - SA) - это другой стохастический метод, дающий хорошие результаты в целочисленной оптимизации, и, с недавнего времени, в общей глобальной оптимизации.
SA базируется на физической идее отжига (остывания) металлов в смысле поиска состояния наименьшей энергии этого металла. По этой причине SA оперирует такими словами как температура, соотносясь с физической интерпретацией. Математической интерпретацией отжига является процедура остывания, которая есть убывающая функция времени. Для целочисленной оптимизации SA можно трактовать как случайное блуждание со смещением. В общем, SA алгоритм может быть описан следующим образом:
Алгоритм 2: Простой Моделируемый Отжиг
Инициализация: Положить x0 = 0, и i = 0.
Шаг 1: Выбрать y в некоторой окрестности xi.
Шаг 2: Если ¦(y) < ¦( xi) установить xi+1 = y, перейти к шагу 4.
Шаг 3: Если (равномерно распределенное случайное число)< 
, установить xi+1 = y.
Шаг 4: Увеличить i на 1 и перейти к шагу 1.
здесь c(i) есть температура в момент времени i, и ¦ минимизируемая функция. В общем случае ожидается, что c(i) убывает до некоторого c¥ ¹ 0 при i ® ¥.
Для дискретного случая разработка этого алгоритма достаточно ясна. Достаточно только определить окрестность xi и функцию остывания c(i). Когда SA применяется к непрерывной задаче, идея окрестности даже более не ясна. Для непрерывного SA можно вначале определить направление поиска. Это делается путем случайного выбора точки на единичной гиперсфере с центром в xi, которая и дает нам нужное направление. После этого алгоритм выбирает случайную длину шага в этом направлении. Очевидным недостатком этой процедуры является то, что она не использует какую-либо локальную информацию (такую как дифференцируемость). Для учета этой проблемы предлагается случайным образом сочетать следующих два метода. Либо xi выбирается случайно, либо xi выбирается путем применения нескольких шагов поиска локального минимума для xi-1.