Введение

В современной математике достаточно большое внимание уделяется решению задач глобальной оптимизации и синтеза оптимального управления динамической системы. Эти задачи возникают в ходе проектирования конструкций самолетов, вертолетов, космических аппаратов, когда возникает необходимость оптимизации характерных параметров (вес, дальность полета, аэродинамические характеристики) и разработки управляющих модулей. Использование интервального анализа как базовой составляющей методов, позволяющих решить эти задачи, дает ряд существенных преимуществ. Такие методы обладают меньшей вычислительной сложностью (методы работают с интервалами и интервальными векторами, то есть обработка ведется не по точкам, а по множествам) и они менее требовательны к формулировке исходной задачи (например, нет необходимости требовать выпуклость минимизируемой функции) [1].

Целью данной работы являлось проведение сравнительного анализа интервальных методов глобальной условной оптимизации: метода дихотомии прямого образа, метода отсечки мнимых значений, метод стохастической отсечки и метода переменных направлений [2]. Необходимость проведения такого анализа обусловлена потребностью в практическом подтверждении эффективности методов и выявления степени и характера зависимости от определяющих параметров.

Интервальные числа

Основной идеей интервального анализа является окружение вещественных чисел интервалами, а вещественных векторов – интервальными векторами, или параллелотопами. Условимся в дальнейшем для обозначения интервала использовать строчные латинские буквы, заключенные в квадратные скобки (, , , ...) или, привычным представлением (, , , ...), для параллелотопа – то же обозначение, только начертание букв полужирное (, , , ...) или, как прямое произведение интервалов (, , ).

Интервальной оболочкой произвольного подмножества из называется наименьший интервал, содержащий это множество. Для того, чтобы указать, что берется интервальная оболочка множества, оно будет заключаться в квадратные скобки. В данной работе все вычисления и алгоритмы выполняются для специального случая, когда все интервальные оболочки являются замкнутыми в интервалами. Множество таких интервалов обозначается (стоит заметить, что и оба принадлежат , так как являются одновременно открытыми и замкнутыми).

Интервал является односвязным подмножеством из . Как у любого подмножества, у интервала есть свои характеристики. Для произвольного интервала определены:

нижняя граница (обозначается как или ):

верхняя граница (обозначается как или ):

ширина (обозначается как , определена только для непустого интервала):

средняя точка (обозначается как , определена только для ограниченного и непустого интервала):

Интервальные векторы

Интервальный вектор, или параллелотоп, является структурой, которую интервальный анализ сопоставляет вещественному вектору. Параллелотоп является односвязным подмножеством из и определяется как прямое произведение замкнутых интервалов: . Множество интервальных векторов будем обозначать как . Так же как и для интервала для параллелотопа определены:

нижняя граница (обозначается как или ):

верхняя граница (обозначается как или ):

ширина (обозначается как , определена только для непустого параллелотопа):

средняя точка (обозначается как , определена только для ограниченного и непустого интервала):

Определение операций над интервалами и интервальными векторами

Для интервалов можно определить любые унарные или бинарные операции. Для замкнутости интервалов используется понятие интервально оболочки. Таким образом, если - некоторая бинарная операция, то

если - некоторый унарный оператор, то

Для параллелотопов унарные и бинарные операции определяются как соответствующие покомпонентные операции.

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

Функции включения

Пусть имеется некоторая функция , действующая из в . Назовем интервальной функцией включения для , действующей из в , если

Функция включения позволяет гарантированно оценить образ функции независимо от того, каким бы он ни был: выпуклым или невыпуклым, связным или несвязным. В действительности очень многое зависит от способа построения данной функции.

Рис. 1. Образ прямоугольной области

Как видно из рис. 1, функция включения может давать очень плохую оценку образа. Тем не менее, полученное множество всегда является параллелотопом, а прямоугольную область намного проще обрабатывать. В общем случае полученный параллелотоп состоит не только из истинных значений, которые принимает искомая функция, но и из тех, которые в принципе не могут быть достигнуты. Будем называть эти значения виртуальными (на рис. 1 выделены серым цветом). Эффект, из-за которого образ функции дополняется до некоторого покрывающего его параллелотопа виртуальными значениями, называется эффектом зависимости. С данной проблемой можно справиться несколькими способами: можно разрабатывать новые способы построения функций включения, стремясь уменьшить множество виртуальных значений, или же осуществлять проверку значений, полученных в ходе вычисления значения функции включения.

Инвертор

Инвертор - функция , которая по заданному интервалу , функции и параметру точности находит в области поиска множество параллелотопов $П$ такое, что $П$ :

и л и

Оценкой прямого образа функции на области будем называть .

Приведём алгоритм процедуры $П$ :

если - завершить работу;
если или , - добавить параллелотоп в множество $П$ и завершить работу;
в противном случае - применить бисекцию к параллелотопу и для полученных параллелотопов и повторно запустить процедуры $П$ и $П$ .

Опишем алгоритм

Шаг 1. Задать функцию , область поиска , интервал и параметр точности . Создать пустое множество параллелотопов $П$ .

Шаг 2. Запустить процедуру $П$ .

Шаг 3. Вернуть $П$ .

Рис. 2. Иллюстрация случаев алгоритма SIVIA

Метод дихотомии прямого образа

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

Приведем подробный алгоритм метода.

Шаг 1. Задать – область поиска, – параметр точности, отвечающий за размер параллелотопа во множестве $П$ , которое будет вырабатываться инвертором, и – параметр точности остановки алгоритма. Рекомендуется выбирать и одного порядка, так как в противном случае, точность ответа будет снижена вследствие того, что либо произойдет окончание работы алгоритма по критерию малости инвертируемого интервала, либо найденный параллелотоп, содержащий точку глобального минимума, будет слишком большим.

Шаг 2. С помощью естественной функции включения найти прямой образ функции на области поиска .

Шаг 3. Дихотомически разделить интервал на два интервала и .

Шаг 4. Инвертировать интервал (с помощью алгоритма ). В ходе данного шага выработается множество параллелотопов $П$ .

Шаг 5. Если множество $П$ , вырабатываемое инвертором непустое, перейти к шагу 6, если пустое – к шагу 7.

Шаг 6. Если , то произвольный элемент из множества $П$ гарантированно содержит точку глобального минимума искомой функции. Если , то положить интервал равным и вернуться к шагу 3.

Шаг 7. Положить интервал равным и вернуться к шагу 3.

Метод отсечки виртуальных значений

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

Приведем подробный алгоритм метода.

Шаг 1. Задать – область поиска, - параметр сетки (), - параметр разбиения и – параметр точности при инвертировании. Рекомендуется выбирать параметр сетки не превышающим 5, так как количество параллелотопов, образуемых на шаге 2 алгоритма равно , где – размерность параллелотопа (например, при и на шаге 2 выработается 1024 параллелотопа, при и выработается уже 4096 параллелотопов). Параметры разбиения и точности при инвертировании определяются так же, как и в методе дихотомии прямого образа.

Шаг 2. Оператор сжатия. Вследствие наличия зависимости количества мнимых значений от размера области поиска и структуры функции (промежутков монотонности, точек разрыва и т.п.) строится разбиение области поиска, для последующего сжатия множества мнимых значений, следующим образом:

Шаг 2.1. Создать множество параллелотопов , состоящее из единственного элемента .

Шаг 2.2. Если равно нулю, закончить построение разбиения и перейти к шагу 3. Иначе перейти к шагу 2.3.

Шаг 2.3. Создать временное множество параллелотопов .

Шаг 2.4. Для каждого параллелотопа из выполнить следующую процедуру:

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

Шаг 2.4.2. Разделить относительно помещенной точки параллелотоп на непересекающихся параллелотопов. Пусть – точка разбиения, – делимый параллелотоп. Процедура деления состоит из n шагов. На первом шаге исходный параллелотоп делится на два параллелотопа и . На втором шаге каждый из полученных на первом шаге параллелотопов делится на два других. Получаем 4 параллелотопа: , , , . И так далее.

Рис. 3. Пример деления параллелотопа

Шаг 2.4.3. Каждый из полученных параллелотопов добавить в множество .

Шаг 2.5. Заменить содержимое множества содержимым множества .

Шаг 2.6. Уменьшить на единицу и вернуться к шагу 2.2.

Шаг 3. Положить начальный образ .

Шаг 4. Последовательно перебирая все параллелотопы , выполнить: .

Шаг 5. Разбить образ на непересекающиеся интервалы шириной : , , где – число полученных интервалов.

Шаг 6. Поочередно инвертировать каждый из полученных на шаге 5 интервалов. Как только выработанное инвертором множество будет непустым, произвольный параллелотоп из полученного множества гарантированно будет содержать точку глобального минимума.

Метод стохастической отсечки

Приведем подробный алгоритм метода.

Шаг 1. Задать – область поиска, - количество циклов (), – параметр точности при инвертировании. Параметры разбиения и точности при инвертировании определяются так же, как и в методе дихотомии прямого образа.

Шаг 2. Положить начальную оценку образа , .

Шаг 3. Оператор сжатия. Если равно нулю - перейти к шагу 8, в противном случае - к шагу 4.

Шаг 4. Случайным образом взять две точки , . Выработать с помощью инвертора множества $П$ и $П$ (для интервалов , соответственно).

Шаг 5. Если $П$ - пустое, то положить . В противном случае положить

Шаг 6. Если $П$ - пустое, то положить . В противном случае положить

Шаг 7. Уменьшить на единицу. Перейти к шагу 3.

Шаг 8. Разбить образ на непересекающиеся интервалы шириной : , , где – число полученных интервалов.

Шаг 9. Поочередно инвертировать каждый из полученных на шаге 5 интервалов. Как только выработанное инвертором множество будет непустым, некоторый параллелотоп из по-лученного множества гарантированно будет содержать точку глобального минимума.

Метод переменных направлений

Стратегия данного метода заключается в постоянном анализе лучшего на данный момент параллелотопа и хранение в памяти всех потенциальных на звание лучшего параллелотопа. Для описания работы алгоритма необходимо ввести понятие двойного буфера памяти. Двойным буфером памяти будем называть множество упорядоченных пар типа «параллелотоп» х «оценка прямого образа этого параллелотопа». Параллелотоп считается тем лучше, чем меньше нижняя граница его оценки прямого образа и чем меньше ширина его оценки прямого образа. На каждой итерации из двойного буфера выделяется лучший параллелотоп (если параллелотопов подходящих под определение «лучшего» несколько, то предпочтение отдается первому по порядку), который становится целевым. Далее происходит деление целевого параллелотопа относительно центральной точки (способ деление описан в методе отсечки виртуальных значений). Для вновь образованных параллелотопов оцениваются прямые образы и происходит реструктуризация двойного буфера (более подробно реструктуризация описана в самом алгоритме метода).

Приведем подробный алгоритм метода.

Шаг 1. Задать - область поиска и - параметр точности (отвечает за размерность выходного параллелотопа). Поместить в двойной буфер элемент . Данный метод выдает более точный результат при уменьшении .

Шаг 2. Если - закончить работу алгоритма (параллелотоп в буфере содержит точку глобального минимума), в противном случае перейти к шагу 3.

Шаг 3. Разделить целевой параллелотоп относительно центральной точки: . Для каждого из полученных параллелотопов оценить прямой образ и составить соответствующие пары: , . Создать второй двойной буфер и поместить туда образованные пары.

Шаг 4. В буфере найти лучший параллелотоп , остальные элементы добавить в буфер .

Шаг 5. Провести реструктуризацию буфера . Для этого производится перебор всех элементов буфера . Пусть рассматривается пара :

удалить пару из буфера ,
положить , удалить пару из буфера и начать перебор заново.

После перебора пара добавляется в буфер . Удалить буфер .

Шаг 6. Найти в буфере лучший элемент и положить параллелотоп равным соответствующему лучшему параллелотопу (при этом лучший параллелотоп удаляется из буфера ). Перейти к шагу 2.

Постановка задачи

Пусть имеется некоторый параллелотоп и заданная на нем функция . необходимо найти параллелотоп , такой что

Тестовые функции

First function of De Jong:

Рис. 4. График функции De Jong'а для случая n = 2

Schwefel's function:

Рис. 5. График функции Schwefel'я для случая n = 2

Easom's function:

Рис. 6. График функции Easom'а для случая n = 2

Сравнительный анализ сходимости метода

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

Определим - гиперкуб с длиной ребра . Близость к оценивается выражением

Хаусдорфово расстояние между множествами и определяется как

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

Рис. 7. Сходимость метода дихотомии прямого образа

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

Рис. 8. Сходимость метода отсечки виртуальных значений

Аналогичный график для метода стохастической отсчеки.

Рис. 9. Сходимость метода стохастической отсечки

Аналогичный график для метода переменных направлений.

Рис. 10. Сходимость метода переменных направлений

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

Сравнительный анализ роста количества итераций

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

Для метода дихотомии прямого образа получены следующие зависимости:

Рис. 11. Количество итераций метода дихотомии прямого образа

Для метода отсечки виртуальных значений получены следующие зависимости:

Рис. 12. Количество итераций метода отсечки виртуальных значений

Для метода стохастической отсечки получены следующие зависимости:

Рис. 13. Количество итераций метода стохастической отсечки

Для метода переменных направлений получены следующие зависимости:

Рис. 14. Количество итераций метода переменных направлений

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

Заключение

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

Библиографический список

Жолен Л., Кифер М. Дидри О., Вальтер Э. Прикладной интервальный анализ. – М.-Ижевск: Институт компьютерных исследований, 2007. – 468 с.
Пановский В.Н. Применение аппарата интервального анализа для поиска глобального экстремума функций // Труды МАИ. – 2012. – №51.
E. Hansen, G.W. Walster. Global optimization using interval analysis. – New York: Marcel Dekker, 2004. – 515 c.

Введение

Интервальные числа

Интервальные векторы

Определение операций над интервалами и интервальными векторами

Функции включения

Инвертор

Метод дихотомии прямого образа

Метод отсечки виртуальных значений

Метод стохастической отсечки

Метод переменных направлений

Постановка задачи

Тестовые функции

Сравнительный анализ сходимости метода

Сравнительный анализ роста количества итераций

Рекомендации по развитию методов

Заключение

Библиографический список