Алгоритм имитации отжига

Question

Я реализовал моделируемый отжиг в C++, чтобы минимизировать (x-2)^2+(y-1)^2 в некотором диапазоне.

Я получаю различные выходные данные, которые не приемлемы для этого типа эвристического метода. Кажется, что решение сходится, но никогда не приближается к решению.

Мой код:

#include <bits/stdc++.h>
using namespace std;

double func(double x, double y)
{
    return (pow(x-2, 2)+pow(y-1, 2));
}
double accept(double z, double minim, double T,double d)
{
    double p = -(z - minim) / (d * T);
    return pow(exp(1), p);
}
double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

int main()
{
    srand (time(NULL));
    double x = fRand(-30,30);
    double y = fRand(-30,30);
    double xm = x, ym=y;
    double tI = 100000;
    double tF = 0.000001;
    double a = 0.99;
    double d=(1.6*(pow(10,-23)));
    double T = tI;
    double minim = func(x, y);
    double z;
    double counter=0;

    while (T>tF) {
        int i=1;
        while(i<=30) {
            x=x+fRand(-0.5,0.5);
            y=y+fRand(-0.5,0.5);
            z=func(x,y);
            if (z<minim || (accept(z,minim,T,d)>(fRand(0,1)))) {
                minim=z;
                xm=x;
                ym=y;
            }
            i=i+1;
        }
        counter=counter+1;
        T=T*a;
    }

    cout<<"min: "<<minim<<" x: "<<xm<<" y: "<<ym<<endl;
    return 0;
}

Как я могу получить его, чтобы достичь решения?

Answer 1

Есть несколько вещей, которые я считаю неправильными в вашей реализации алгоритма имитации отжига.

На каждой итерации вы должны смотреть на некоторых соседей z текущего минимума и обновлять их, если f(z) <минимум. Если f(z)> минимум, вы также можете принять новую точку, но с функцией вероятности принятия.

Проблема в том, что в вашем accept функция, параметр d слишком низко - он всегда вернется 0.0 и никогда не вызывать условия принятия. Попробуйте что-то вроде 1e-5; оно не должно быть физически правильным, оно должно только уменьшаться при понижении "температуры".

После обновления температуры во внешней петле следует поставить x=xm а также y=ymперед выполнением внутреннего цикла или вместо поиска соседей текущего решения вы будете, в основном, случайным образом бродить (вы тоже не проверяете границы).

Делая так, я обычно получаю вывод наподобие этого:

min: 8.25518e-05 x: 2.0082 y: 0.996092

Надеюсь, это помогло.