Xreferat.com » Рефераты по математике » Сравнительный анализ методов оптимизации

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

loading="lazy" src="http://xreferat.ru/image/54/1306482479_54.gif" alt="Сравнительный анализ методов оптимизации" width="117" height="49" align="BOTTOM" border="0" />, Сравнительный анализ методов оптимизации.


Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.

Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.

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

Пусть заданы следующие параметры:


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


Примем Сравнительный анализ методов оптимизации и Сравнительный анализ методов оптимизации. Тогда Сравнительный анализ методов оптимизации (рисунок 7).


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

Рисунок 7 - Поведение исходной функции на заданном отрезке


Проведем несколько итерации методом дихотомии:


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


Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:


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


Так как f (x1) > f (x2), то a: =x1, b оставляем прежним. Тогда на третьем шаге:


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


Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.


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

Рисунок 8 - Получение решения методом дихотомии


Для метода золотого сечения:


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


Так как f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:


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


Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда на третьем шаге:


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


И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.


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

Рисунок 9 - Получение решения методом золотого сечения

2.2 Методы безусловной минимизации функций многих переменных


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


2.2.1 Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x1 и x2.


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

Рисунок 10 - Циклический покоординатный спуск.


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

Шаг 0. Выбрать х О En, критерий достижения точности e и шаг Сравнительный анализ методов оптимизации. Найти f (x1 (0),x2 (0)).

Шаг 1. Принять x1 (1) = x1 (0) +Сравнительный анализ методов оптимизации. Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 2.

Шаг 2. Принять x1 (1) = x1 (0) - Сравнительный анализ методов оптимизации. Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 3.

Шаг 3. Принять x2 (1) = x2 (0) +Сравнительный анализ методов оптимизации. Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то перейти к шагу 4.

Шаг 4. Принять x2 (1) = x2 (0) - Сравнительный анализ методов оптимизации. Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 4, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то принять исходную точку за минимум.

Шаг 5. Проверить условие достижения точности Сравнительный анализ методов оптимизации.

Если в процессе решения с шагом Сравнительный анализ методов оптимизации не получено решения, то принять Сравнительный анализ методов оптимизации


2.2.2 Алгоритм Хука-Дживса

Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);

б) перемещение в направлении убывания.


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

Рисунок 11 - Метод Хука-Дживса


Трактовать данный метод можно по-разному. Рассмотрим один из многочисленных вариантов.

Опишем один из алгоритмов данного метода.

Шаг 1. Выбираем начальную точку и находим в ней значение функции.

Шаг 2. Обозначим координаты начального вектора: Сравнительный анализ методов оптимизации.

Тогда, соответственно, угол направления движения


Сравнительный анализ методов оптимизации.


Рассчитываем координаты 4-х точек в окрестности начальной по следующим формулам:


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

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

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

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


Находим в указанных точках значения функции. Если какое-нибудь из них оказалось меньше значения функции в точке x0, то принимаем его за исходное.

Шаг 3. Сравниваем полученные значения с f (x1 (0),x2 (0)). Если какое-нибудь из них оказалось меньше значения функции в 0-й точке точке, то принимаем его за исходное и переходим к шагу 5.

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

Шаг 5. Проверить условие достижения точности


Сравнительный анализ методов оптимизации.


Если данное условие не выполнено, возвращаемся к шагу 2.

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

Пусть заданы следующие условия:


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


Тогда по методу циклического покоординатного спуска будет выполнен счет следующего вида:


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

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


Т. к. Сравнительный анализ методов оптимизации, будем двигаться в противоположную сторону по оси абсцисс с тем же шагом:


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

Сравнительный анализ методов оптимизации,


поэтому продолжаем двигаться дальше с тем же шагом в данном направлении до достижения указанной точности, в противном случае уменьшаем шаг (Сравнительный анализ методов оптимизации):


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


Результаты работы данного алгоритма представлены на рисунке 12. Листинг программы приведен в приложении Б.


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

Рисунок 12 - Решение поставленной задачи методом спуска


Перейдем к методу Хука-Дживса. Обозначим координаты начального вектора: Сравнительный анализ методов оптимизации.

Тогда, соответственно, угол направления движения


Сравнительный анализ методов оптимизации.


Найдем значения функции 4-х точек в окрестности начальной:


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

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

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

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


Минимальное значение функция принимает в точке2, поэтому движемся в заданном направлении 2 пока идет уменьшение функции до достижения указанной точности, в противном случае уменьшаем шаг


(Сравнительный анализ методов оптимизации):

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


Конечный результат получен на ЭВМ за 36 итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.


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

Рисунок 12 - Решение поставленной задачи методом спуска


2.2.4 Минимизация по правильному симплексу

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

В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 - правильного тетраэдра.

Если х0 - одна из вершин правильного симплекса в En то координаты остальных п вершин х1,. ., хn можно найти, например, по формулам:


Сравнительный анализ методов оптимизации (6), где

d1 Сравнительный анализ методов оптимизации, d2 Сравнительный анализ методов оптимизации,


a- длина ребра. Вершину х0 симплекса, построенного по формулам (6), будем называть бaзовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой-либо вершины, например, хk симметрично относительно центра тяжести хc остальных вершин симплекса. Новая и старая вершины Сравнительный анализ методов оптимизациии хk связаны соотношением:


Сравнительный анализ методов оптимизации, где xcСравнительный анализ методов оптимизации.


В результате получается новый правильный симплекс с тем же ребром и вершинами Сравнительный анализ методов оптимизации=2xc - хk, хi, i= 0,. ., n, i№ k. Таким образом, происходит перемещение симплекса в пространстве Еn. На рисунке 13 представлена иллюстрация этого свойства симплекса в пространстве Е2.

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

Рисунок 13 - Построение нового симплексa в E2 отрaжением точки х: a - нaчaльный симплекс х0, х1, Сравнительный анализ методов оптимизации; б - новый симплекс х0, х1, Сравнительный анализ методов оптимизации; центр отрaжения - точкa xc = (х0+ х1) /2


Поиск точки минимума функции f (x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f (х) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.

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


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


Вычислить f (х1 (0),x2 (0)).

Шаг 1. Вычислить значения f (х) в вершинах симплекса х1,. ., xn.

Шаг 2. Упорядочить вершины симплекса х0,. ., хn так, что бы f (х1 (0),x2


(0)) Ј …Ј Јf (х1) Ј f (хn-1) Ј f (хn).


Шаг 3. Найти среднее значение функции:


Сравнительный анализ методов оптимизации.


Проверить условие Сравнительный анализ методов оптимизации из учета того, что:


Сравнительный анализ методов оптимизации (3.38)


Если оно выполнено, то вычисления прекратить, полагая х* » х0, f * » f (x0). В противном случае перейти к шагу 4.

Шаг 4. Найти


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


и выполнить отражение вершины хn. К примеру, для отражения вершины А следует найти точку


Сравнительный анализ методов оптимизации.


Тогда отраженная вершина будет иметь вид:


Сравнительный анализ методов оптимизации.


Если f (Е) <f (xn), то перейти к построению нового симплекса, иначе - перейти к шагу 5.

Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром (редуцирование), считая базовой вершиной х0. Остальные n вершин симплекса найти по формуле хi = (хi + х0) /2, i=1,. ., n. Перейти к шагу 1.

Геометрическая иллюстрация работы алгоритма в пространстве показана на рисунке 14, где точки х0, х1, х2 - вершины начального симплекса, а пунктиром указаны процедуры отражения.


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

Рисунок 14 - Поиск точки минимума функции Сравнительный анализ методов оптимизациис помощью правильных симплексов в пространстве Сравнительный анализ методов оптимизации


Замечания:

1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).

2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.

2.2.5 Поиск точки минимума по деформируемому симплексу

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


Сравнительный анализ методов оптимизации (7)


Геометрическая иллюстрация этих процедур для пространства E2 приведена на рисунках 15 и 16.


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

Рисунок 15 - Пробные точки z1,z2,z3,z4 для перехода к новому симплексу


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

Рисунок 16 - Новые симлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения (г).


Так как величина a О (0;

1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве En для n Ј 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0 О En, по формулам


Сравнительный анализ методов оптимизации, (8)


где e i - i-й базисный вектор; a- параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi в формулах (9): a = 1/2, b = 1 и g =2.

Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс. Вычислить f (х0).

Шаг 1. Вычислить значения функции в вершинах симплекса х1,..., xn.

Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f (х0) Ј … Ј f (хn).

Шаг 3. Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * » х0, f * » f (х0). Иначе - перейти к шагу 4.

Шаг 4. Найти Сравнительный анализ методов оптимизациии пробные точки zk, k=1, …, 4 пo формулам (9). Найти f (z*) = min f (zk). Если f (z*) < f (zn). то положить xn=z* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая хi = (хi + х0) /2, i = 1,. ., n и перейти к шагу 1.

Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х0 снова строят симплекс, полагая а = ||x0-xn||.

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


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

Пусть заданы следующие условия:


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


Для первой вершины:


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


Для второй вершины:


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


Для третьей вершины:


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


Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:


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


Рассмотрим метод симплекса.

Находим координаты отраженной вершины Е и значение в ней функции:


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


Т. к. Сравнительный анализ методов оптимизации, то строим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса.

Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.


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

Рисунок 17 - Практическая реализация симплекс-метода


Перейдем к методу деформируемого симплекса.

Введем коэффициенты уменьшения и увеличения: Сравнительный анализ методов оптимизации.

Найдем значения функции 4-х точек в окрестности начальной:


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

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

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

Сравнительный
    <div class=

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: