Курсовая работа: Сравнительный анализ методов оптимизации

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, 2, 3, 4, 5, 6, 7, 8, 9