2020-01-14
391
АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математический факультет
Кафедра геоинформационных технологий
Построение единой программной среды
для решения задач глобальной оптимизации
Выполнил студент
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
Аффинная оценка функции e x 24
Представление аффинных форм на ЭВМ 25
Общие подформулы 25
Практическая реализация алгоритмов 27
Автоматический анализ функций 28
Эффективное распределение памяти 30
Структурирование результатов 32
Численные результаты 32
Заключение 36
Литература 37
Приложение 38
Введение
Общая задача, рассматриваемая в данной работе, состоит в поиске минимума ¦* некоторой целевой функции ¦:W®R, определенной на компактном множестве WÍRn и множества всех минимизирующих переменных W*(¦) = { x * Î W: ¦(x *) = ¦*}. Поскольку в общем случае компактное множество может иметь сложную структуру здесь полагается, что W является параллелепипедом [ x 1, 
1]´[ x 2, 2]´…´ [ x n, n] Í Rn.
Глобальная оптимизация без ограничений – одна из математических задач, рассматривается до сих пор и является очень сложной. Множество исследователей занимались решением этой задачи и некоторыми из них были приведены случаи NP -полных задач глобальной оптимизации. Точное доказательство NP- полноты очень трудоемко, но сложность решения не требует доказательства. В качестве примеров таких нелинейных задач, в которых поиск минимума (минимума или максимума) необходим для практики, можно привести задачу поиска направления и продолжительности радиационного облучения раковых опухолей, поиска состояния наименьшей энергии протеиновой молекулы, и задачу определения правильного соотношения составляющих смеси для оптимального протекания химической реакции.
|
|
|
Вначале работы приводится краткий обзор методов решения задачи глобальной оптимизации, основанных как на детерминированном и стохастическом подходах, и обсуждаются преимущества и недостатки этих методов. Методы ветвей и границ, относящиеся к детерминированным методам, представлены здесь более полно, так как они служат основой для широкого класса разрабатываемых алгоритмов.
Далее более подробно рассматриваются приемы реализации этих методов на ЭВМ, техника разработки и использования интервальной и аффинной арифметики для оценки диапазонов функций, и способы решения основных проблем, возникающих при разработке конкретных алгоритмов на практике.
В последней части приведены и прокомментированы числовые результаты, полученные при решении нескольких тестовых задач глобальной оптимизации различными методами.
Обзор основных методов глобальной оптимизации
Процедура общей глобальной оптимизации есть способ нахождения с заданной точностью минимума произвольной функции, для аргументов которой определены некоторые начальные границы. Допускается, чтобы границы переменных были бесконечными. Таким образом, идеальный оптимизатор (т.е. метод, решающий задачу общей глобальной оптимизации) есть черный ящик, на вход которого подается описание функции, ее связи, границы переменных и требуемая точность. Этот черный ящик генерирует на выходе одно из следующих состояний:
· Приближенные значения переменных, в которых функция достигает минимума с математически рассчитанными границами ошибок.
· Значения, которые аппроксимируют глобальный минимум с математически рассчитанной максимальной ошибкой.
· Функция не ограничена.
Первые два состояния можно охарактеризовать множеством параллелепипедов, гарантированно содержащих глобальный минимум. Другая возможность состоит в выдаче множества точек, для которого можно дать математически корректную вероятность того, насколько близко вычисленное наилучшее значение функции к ее глобальному минимуму. Эти ситуации соответствуют типу вывода по завершению детерминированного алгоритма или по завершению стохастического алгоритма соответственно. В следующих параграфах мы изучим такие алгоритмы подробнее. Для более детального рассмотрения этих алгоритмов можно обратится к работе [1], откуда и почерпнута значительная часть из ниже приведенных материалов.
|
|
|
