Читайте также:
|
Метод более сложный, использует информацию о предыдущих точках. Поиск по методу Хука-Дживса состоит из последовательности шагов вокруг выбранной базисной точки, и в случае успеха с выбором базисной точки, следует поиск по образцу.
Алгоритм:
1 Этап
Выбирается начальная точка b1, которую будем называть базисной точкой. Выбирается шаг hj для каждой переменной xj.
2 Этап «Этап исследования»
1 шаг
Вычисляется значение искомой ф-ции f(x) в базисной точке и ее окрестностях
2 шаг
Вычисляется переменная xj, для каждой переменной вычисляется ф-ция в точке j=1,2,…,n. i1, это единичный вектор в направлении x1.
В том случае, если направление становится меньше, то базовая точка заменяется на точке b1+h1e1.
Если нет, то начинаем поиск в прошлом направлении.
Если значение в этой точке больше, чем значение в базовой точке, то в качестве базовой точке берем точки b1-h1e1.
Если мы не получили уменьшение точки ни в том, ни в ином случае, то j увеличиваем на 1 и считаем для след. Координаты x2.
Аналогично до тех пор, пока j!=n. Получаем новую базисную точку b2. Таким образом, на шаге 2, мы исследовали окрестность базовой точки, и нашли новую базовую точку.
Шаг 3
на этапе исследования. В том случае, если не получилось найти в окрестности найти новую базовую точку, то значение шага по всем координатам уменьшается на порядок. Идет переход к шагу 2.
Этап 3. «Поиск по образцу»
На данном этапе используется информация, полученная на 2 этапе
1 Шаг
Из найденной базовой точки b2 двигаемся в направлении b 2- b1. Это направление выбирается потому, что мы уже получили направление функции. Вычисляем новую точку P1=b1+2(b2-b1).
2 Шаг
Производится исследование точки P1. То есть, для точки P1 производится полное исследование.
3Шаг
Если в результате исследования, мы нашли точку, в которой значение функции уменьшилось, то м ее обозначаем как новую базовую точку, и переходим к шагу 1 третьего этапа. Если в окрестности P1 мы не нашли новой точки, то переходим к этапу исследования для точки b2.
4 этап.
Процесс завершается, когда длина шага h по все координатам будет меньше эпсилон(заданного).
Метод Нелдера-Мида.(Посмотреть мою реализацию)
Мой код MatLab:
function [ min,i ] = NeylerMid(x1, x2, y1, y2, accu)
max = [(x2+x1)/2 (y2+y1)/2];
norm = [(x2 - 0.5*max(1)) (y1 + 0.5*max(2))];
min = [(x1 + 0.5*max(1)) (y1 + 0.5*max(2))];
D = inf;
i = 0;
while D > accu
%Вычислем значение функции в вершинах симплекса
F_treangle = [f(max) f(norm) f(min)];
i = i +1;
sort(F_treangle);
h = MaxS(max, norm, min, F_treangle);
l = MinS(max, norm, min, F_treangle);
g = SG(max, norm, min, F_treangle);
max = h;
norm = g;
min = l;
%Находим центр тяжести
c = (min+norm) / 3;
%Отражение
r = [ (2*c(1) - h(1)) (2*c(2) - h(2))];
if(f(r) < f(l))
e = [ (-1*c(1) + 2*r(1)) (-1*c(2) + 2*r(2))];
if(f(e) < f(l))
max = e;
h = e;
else
max = r;
h = r;
end
elseif(f(l) < f(r) && f(r)<f(g))
max = r;
h = r;
elseif(f(g) <f(r) && f(r)<f(h))
t = max;
max = r;
r = t;
h = max;
s = SWAG(h,c);
if(f(s) < f(h))
max = s;
h = s;
else
max = l +(h-l)/2;
h = max;
norm = l + (h-g)/2;
g = norm;
end
elseif(f(h)<f(r))
s = SWAG(h,c);
if(f(s) < f(h))
max = s;
h = s;
else(f(s) > f(h))
max = l +(max-l)/2;
h = max;
norm = l + (norm-l)/2;
g = norm;
end
end
D = Dispers(min, norm, max);
end
end
function [ h ] = MaxS(a,b,c, F)
if(f(a) == F(3))
h = a;
elseif(f(b) == F(3))
h = b;
else
h = c;
end
end
function [l] = MinS(a,b,c, F)
if(f(a) == F(1))
l = a;
elseif(f(b) == F(1))
l = b;
else
l = c;
end
end
%Нахождение следующего после h по величине значения
function [g] = SG(a,b,c, F)
if(f(a) == F(2))
g = a;
elseif(f(b) == F(2))
g = b;
else
g = c;
end
end
%Веполняем сжатие
function [s] = SWAG(h,c)
s = [ (0.5*h(1) - 0.5*c(1)) (0.5*h(2) - 0.5*c(2))];
end
%Вычисляем дисперсию
function [D] = Dispers(x1, x2, x3)
X = [ (x1(1)^2 + x2(1)^2 + x3(1)^2) (x1(2)^2 + x2(2)^2 + x3(2)^2)];
x = [ ((x1(1) + x2(1) + x3(1))^2) ((x1(2) + x2(2) + x3(2))^2) ];
D = (X - (x/3))/2;
end
Метод основан на том, что из n мерного пространства рассматривается множество из n+1 точки (симплекс).В двумерном пространстве, симплекс – треугольник, В трехметром – тетраэдр. Сравнение значения функции во всех вершинах симплекса, и перемещение симплекса в направлении минимального значения функции. Особенно хорошо работает, если n<6.
Алгоритм:
1. Начальный симплекс: f1= f(x1),f2=f(x2),…,fn+1=f(xn+1)
2. Значение функции fh, fl
3. Находятся центры тяжести всех точек симплекса, кроме точки h. Находится значение ф-ции в этой точке fn+2=f(xn+2)
4. Отражение. Точка с максимальным значением(точка h) отражается относительно центра тяжести n+2, получается точка n+3.
5. Растяжение. Этот этап применяется в том случае, если значение ф-ции в точке n+3будет меньше значения в минимальной точке симплекса. Тогда вектор (n+2, n+3) до точки n+4
xn+4=xn+2+¥(xn+3-xn+2)Если в результате растяжения получили, что значение функции меньше, чем в минимальной точке симплекса, то точка xh меняется на точку xn+4, если нет, то xh меняется на точку xn+3, и в том, и в другом случае, происходит переход к п.2
6. Пункт 6 выполняется после нахождения точки n+3, и в том случае, когда значение ф-ции в точке n+3 больше, чем во всех точках симплекса, кроме h. В этом случае производится сжатие симплекса (т.е. точка n+3 по тому же самому направлению приближается к точке n+2
xn+5=xi+0.5(xi-xl). Точка xh меняется на точку xn+5, и происходит переход к п.2
7. Редукция. Выполняется в том случае, если значение ф-ции в найденной точке xn+3 будет хуже, чем значение в наихудшей точке xh. Тогда происходит преобразование координат по данной формуле xi=xl+0.5(xi-xl). Происходит переход к п.2
8. Поиск заканчивается, когда ((1/n+1)∑n+1i=1(f(xi)-f(xn+2))2)1/2<=e
Данный многогранник хорошо адаптируется к топографии целевой ф-ции. Он может вытягиваться вдоль длинных наклонных плоскостей, изменять направление своего движения во впадинах, и сжимается около точки минимума. С помощью операций растяжения и сжатия, размер и формы многогранника маштабируются, и тем самым, удоветворяют заданной топологии
Дата добавления: 2015-02-16; просмотров: 166 | Поможем написать вашу работу | Нарушение авторских прав |