Thread: Simulated Annealing in C++

I am interested in implementing simulated annealing and am having difficulty with my implementation. All the costs are computed and stored in the dist array. From my understanding, simulated annealing works as follows:

1. Generate a random solution
2. Calculate its cost using some cost function
3. Generate a random neighboring solution
4. Calculate the new solution's cost
5. Compare them:
   5.1: If cnew < cold: move to the new solution
   5.2: If cnew > cold: maybe move to the new solution
6. Repeat steps 3-5 above until an acceptable solution is found or you reach some maximum number of iteration
   Code:

    double max = dist[1]; 
   int idx=0;
   for(int ix = 1; ix < ITERS; ix++){
   double temp = (1/500)*((1/ix)- (1/ITERS));
   
   for(int m = 0; m < 100; m++){
               if (dist[m] < max) {
               max = dist[m];
               idx = m; 
           }
           else if (dist[m] > max) {
               if (((max - dist[m])/temp) > unifRand()) {
               max = dist[m];
               idx = m; }
           } } }
   return idx;

You catch more help with pretty code. That looks like someone vomited on the keyboard.

Interesting topic!!

I'd never heard of "simulated annealing" before today. So I'm not really qualified to give you advice there.....

Programming-wise:

1. You're using integer literals inappropriately. For example, in your calculation for temp you do (1/500). Plain numbers like this are integers in C/C++ -- this will come out as 0. You should write 1.0/500.0 for anything that needs to be a double.
For variables that you really want to be integers (like your iterator, "ix"), cast them to double when you use them.

<Aside> Actually, only one side of a binary operator needs to be double, then the other side will get converted too. However I think it is good to know what your data types are!

2. You then enter a loop -- but if dist[m] is equal to max then you'll get an infinite loop. I think you just want an "else" here.



Anyway -- just my two cents, as I really don't know what I'm talking about. I think your code is wrong to loop through every element in dist -- wikipedia (Simulated annealing - Wikipedia, the free encyclopedia) says:

Originally Posted by wikipedia

For certain problems, simulated annealing may be more efficient than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.

I think the idea is that you pick a number at random, then check either side of it. The assumption being that the numbers form some sort of graph. I also think you've supposed to use temp as the iterator (as well as the accuracy control).

I tried it; it worked, but it was much slower than a linear search.

Sorry I couldn't be of much help. Only learned about this today!