CODEWITHSUNDEEP
c++simulated-annealing
Sravanth Reddy
Sravanth Reddy

Reputation: 11

simulated annealing algorithm

I implemented simulated annealing in C++ to minimize (x-2)^2+(y-1)^2 in some range.

I'm getting varied output which is not acceptable for this type of heuristic method. It seems that the solution is converging but never quite closing in on the solution.

My code:

#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;
}

How can I get it to reach the solution?

Upvotes: 0

Views: 6503

Answers (1)

Bob__
Bob__

Reputation: 12799

There are a couple of things that I think are wrong in your implementation of the simulated annealing algorithm.

At every iteration you should look at some neighbours z of current minimum and update it if f(z) < minimum. If f(z) > minimum you can also accept the new point, but with an acceptance probability function.

The problem is that in your accept function, the parameter d is way too low - it will always return 0.0 and never trigger the condition of acceptance. Try something like 1e-5; it doesn't have to be physically correct, it only has to decrease while lowering the "temperature".

After updating the temperature in the outer loop, you should put x=xm and y=ym, before doing the inner loop or instead of searching the neigbours of the current solution you will basically randomly wander around (you aren't checking any boundaries too).

Doing so, I usually get some output like this:

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

Hope it helped.

Upvotes: 2

Related Questions