T
T
tj572019-01-13 18:18:56
Mathematics
tj57, 2019-01-13 18:18:56

How to fix bugs in implementations of gradient descent and simulated annealing methods?

There are implementations of the above methods in Matlab:
Gradient Descent

clc;
iters=1000;% кол-во итераций
 
xr=0; % нахождение глобального минимума функции
yr=0;
dr=sqrt(xr*xr+yr*yr);
Z=Func(xr,yr);% значение функции в этой точке
 
k=100; % выбираем начальную точку из диапазона (-k,k)
x0=-k+rand(1,1)*(k-(-k));
y0=k;
x00=x0;
y00=y0;
Z0=Func(x00,y00);
 
step=1e-4;% шаг
w=1.9;% параметр (1,2]
 
for i=1:1:iters
    Grad_dx= (Func(x0+step,y0)-Func(x0,y0))/step; % определяем для текущей точки значение градиента
    Grad_dy=(Func(x0,y0+step)-Func(x0,y0))/step;
    Grad_Norm=sqrt(Grad_dx*Grad_dx+Grad_dy*Grad_dy);
    if (Grad_Norm< 1e-8)
        break;
    end
    % адаптивный выбор шага d
    tempStep1=step;
    tempStep2=step/w;
    tempStep3=step*w;
    % определяем положение следующей точки
    x1=x0-tempStep1*Grad_dx/Grad_Norm;
    x2=x0-tempStep2*Grad_dx/Grad_Norm;
    x3=x0-tempStep3*Grad_dx/Grad_Norm;
    y1=y0-tempStep1*Grad_dy/Grad_Norm;
    y2=y0-tempStep2*Grad_dy/Grad_Norm;
    y3=y0-tempStep3*Grad_dy/Grad_Norm;
    Func1=Func(x1,y1);
    Func2=Func(x2,y2);
    Func3=Func(x3,y3);
    F=[Func1;Func2;Func3];
    min_Func=min(min(F));
    if (min_Func==Func1)
        step=tempStep1;
    else
        if (min_Func==Func2)
            step=tempStep2;
        else
            if (min_Func==Func3)
                step=tempStep3;
            end
        end
    end
    x0=x0-step*Grad_dx/Grad_Norm;
    y0=y0-step*Grad_dy/Grad_Norm;
    
    new_dr=sqrt(x0*x0+y0*y0);
    diff=abs(new_dr-dr);
    disp(x0);
    Q(i)=diff;
    
end
 
plot( Q, 'g', 'LineWidth', 1);
xlabel('i') ;
ylabel('\DeltaF') ;
grid on

Simulated annealing:
clc;
 
xr=0; % нахождение глобального минимума функции
yr=0;
dr=sqrt(xr*xr+yr*yr);
Z=Func(xr,yr);% значение функции в этой точке
 
k=100; % выбираем начальную точку из диапазона (-k,k)
x0=-k+rand(1,1)*(k-(-k));
y0 = k;
x00=x0;
y00=y0;
Z0=Func(x00,y00);
 
T0=100; % задаем начальную температуру системы
 
for i=1:1:250 % по изменению температуры
    T=T0/(1+i); % на каждой итерации понижаем температуру
    for j=1:100
        dx=-T+rand(1,1)*(T-(-T));% генерация след точки по равномерному распределению
        dy=-T+rand(1,1)*(T-(-T));
        dE=Func(x0+dx,y0+dy)-Func(x0,y0); % расчет приращения энергии при переходе в новое состояние
        h=1/(1+exp(dE/T));  %расчет вероятности перехода 
        buf=rand(1);
        % проверка на переход в новое состояние
        % если условие выполняется то точка принимается, если нет то заново
        % генерация 
        if(buf <=h)
            x0=x0+dx;
            y0=y0+dy;
            break;
        end
    end
   new_dr=sqrt(x0*x0+y0*y0);
    diff=abs(new_dr-dr);
    disp(x0);
    Q(i)=diff;
end
 
p = plot( Q, 'r', 'LineWidth', 1);
xlabel('i') ;
ylabel('\DeltaF') ;
set(p, 'Color', 'g');
axis([0 250 0 100 ]);
grid on
hold on

According to the teacher, the gradient descent method uses an inaccurate method for estimating partial derivatives, and the annealing simulation method is simply an error (I didn’t say which one). How can these errors be corrected (and how to understand which error is in the annealing simulation method)?

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question