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

Если в процессе решения с шагом

не получено решения, то принять

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

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

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

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

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

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

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

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

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

.

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

.

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

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

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

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

и переходим к шагу5.

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

.

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

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

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

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

Т. к.

, будем двигаться в противоположную сторону по оси абсцисс с тем же шагом:

,

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

):

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

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

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

.

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

.

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

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

(

):

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

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

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

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

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

Если х⁰ - одна из вершин правильного симплекса в E_n то координаты остальных п вершин х¹,. ., хⁿ можно найти, например, по формулам:

(6), где

d₁

, d₂ ,

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

и х^k связаны соотношением:

, где x^c .

В результате получается новый правильный симплекс с тем же ребром и вершинами

=2x^c - х^k, хⁱ, i= 0,. ., n, i¹k. Таким образом, происходит перемещение симплекса в пространстве Е_n. На рисунке 13 представлена иллюстрация этого свойства симплекса в пространстве Е₂.

Рисунок 13 - Построение нового симплексa в E₂ отрaжением точки х: a - нaчaльный симплекс х⁰, х¹,

; б - новый симплекс х⁰, х¹, ; центр отрaжения - точкax^c = (х⁰+ х¹) /2

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

Шаг 0. Выбрать параметр точности e, базовую точку х⁰, ребро

и построить начальный симплекс по формулам:

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

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

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

⁽⁰⁾⁾£ …££f (х¹) £f (х^n-1) £f (хⁿ).

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

.

Проверить условие

из учета того, что:

(3.38)

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

Шаг 4. Найти

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

.

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

.