СКАЧАТЬ:  metod-pokoordinatnogo-spuska.zip [13,63 Kb] (cкачиваний: 143)

Лабораторная работа

“Оптимизация методом покоординатного спуска  ”

Метод покоординатного спуска (метод Гаусса-Зейделя).

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

В методе покоординатного спуска направление движения к экстремуму выбирается поочерёдно вдоль каждой из координатных осей управляемых параметров.

Рассмотрим процесс поиска минимума экстремума целевой функции F() для n-мерной задачи оптимизации при =(х₁, х₂,…х_n)^T. Предположим, что осуществляется поиск минимума функции F(). Тогда улучшению её на (k+1)-м шаге будет соответствовать условие

Задача максимилизации  функции F() можно свести к задаче минимизации пути умножения F() на -1.

Из выбранной начальной точки поиска ₀  выполняется пробный шаг h₀

в положительном направлении одной из координатных осей (обычно вдоль оси первого управляемого параметра x₁). В новой точке с координатами x_1.1=x_1.0+h₀; x_2.1=x_2.0;...; x_n.1=x_n.0  вычисляется значение целевой функции F(₁) и сравнивается с ее значением в начальном точке F(₀). Если F(₁)<F(₀), что направление принимается для осуществления дальнейшего пошагового движения к экстремуму в соответствии с выражением

x_1.k+1=x_1.k+h₀

 В противном случае производится возраст в исходную точку ₀  и движение осуществляется в отрицательном направлении оси x₁:  

x_1.k+1=x_1.k-h₀

Движение в выбранном направлении оси  x₁ выполняется до тех пор, пока целевая функция улучшается, т.е. выполняется условие. При его нарушении на (k+1)-м шаге производится возврат в предыдущую точку, определяется направление движения вдоль следующей координатной оси  x₂ и совершаются  спуски в направлении, обеспечивающем улучшение целевой функции:

 X_2.k+1=x_2.kh₀

После осуществления спусков вдоль всех n осей первый цикл спусков N=1 завершается и начинается новый цикл N=2. Если на очередном цикле поиска движение оказалось невозможным ни по одной из осей, тогда уменьшается шаг поиска

h_N=h_N-1γ

Где γ – коэффициент уменьшения шага:   0< γ<1.

Далее поиск экстремума продолжается с уменьшенным шагом.

Условие окончания поиска

h _N<h_min

При достижении условия поиск прекращается и полученная точка  принимается в качестве искомой экстремальной точки .  Точка  при этом  находится в некоторой малой окрестности точки , ограничиваемой задаваемый минимальным значением шага поиска h_min.

Параметрами алгоритма покоординатного спуска являются h₀ , h_min и γ. Алгоритм обеспечивает сходимость к решению , за конечное число итераций, если функции F() квадратична в окрестности экстремума.

Оптимизация на языке Pascal.

program Ramil;

label 1,2;

function f(x,y:real):real;

begin

f:=5.35+1.06*y-11.06*x

end;

var x,y,h,h1,u:real;

begin

write('x0=');

readln(x);

write('y0=');

readln(y);

write('h0=');

readln(h);

write('hmin=');

readln(h1);

write('u=');

readln(u);

repeat

if f(x,y)>f(x+h,y) then h:=-h;

1: if (x>=0.25)and(x<=0.5) then

begin

x:=x+h;

goto 1

end;

if f(x,y)>f(x,y+h) then h:=-h;

2: if (y>=340)and(y<=345) then

begin

y:=y+h;

goto 2

end;

h:=h-h*u;

until h<=h1;

writeln('x=',x);

writeln('y=',y);

writeln('f=',f(x,y));

readln;

end.