Thread: Simulated Annealing in C++

  1. #1
    Registered User
    Join Date
    Feb 2015
    Posts
    1

    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;

  2. #2
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    You catch more help with pretty code. That looks like someone vomited on the keyboard.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    But it is better on the first attempt than what kelton2 has managed after 4 months of continuous prodding to improve their code formatting.

    The mistake from the OP was to actually "ask a question".
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    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:
    Quote 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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-27-2014, 12:10 AM
  2. Simulated Annealing Algorithm in C++
    By abady in forum C++ Programming
    Replies: 6
    Last Post: 03-12-2014, 08:59 PM
  3. working with simulated 2 and 3 dimensonal space
    By ashinms in forum C++ Programming
    Replies: 6
    Last Post: 08-18-2011, 08:07 PM

Tags for this Thread