Thread: Simulated Annealing Algorithm in C++

  1. #1
    Registered User abady's Avatar
    Join Date
    Mar 2014
    Posts
    5

    Simulated Annealing Algorithm in C++

    Hi all,

    I'm pleased to join this forum, I read some posts and read and practiced in the tutorial which was wonderful. As it might be obvious, I'm still a beginner at C++ programming, I have tried to implement some optimization algorithms (related to database) in C++, I cannot say it is going as far as I thought it will be, some errors does not even make sense, I will cut to the chase, I need to implement SA (Simulated Annealing) in C++, SA, which is an example of the Randomized Algorithms, functions on the concept of randomness and probability. In addition, I searched the internet with no (let say "accurate") code that might give me insight on how to begin, I only found one code for SA that I could understand, and edited it (which will be shown below), still looking to enhance and correct it more.

    The code for SA is as follows:
    Code:
    #include "stdafx.h"
    #include <iostream>
    #include <time.h>
    #include <stdlib.h>
    #include <cmath>
    
    
    using namespace std;
    
    double f(double x) //I should add another parameter for the energy
    {
        return x = pow(x, 4) + (4 / 3)* pow(x, 3) - 4 * pow(x, 2) + 5;  //(I have to 
    }
    
    
    int main()
    {
    
        double first_run, second_run, third_run;        //(first, second and third run) are defined for the purpose of comparing the resulting
        time_t systime;                                // solutions of the three runs will be chosen as the final solution
        time(&systime);
        srand((unsigned int)systime);
        double  alpha = 0.9;                         //alpha is used for the cooling schedule of the temperature            
        const double e = 2.718281828;
    
    
    
    
    
    
        double x = 10; //setting an initial value of x (state)
    
        cout << "Initial State = " << x << "\t, and F(x)= " << f(x) << endl;
    
        double L = f(x);
    
        for (double T = 80; T > 0.00008; T *= alpha) //T = T * alpha which used as a cooling schedule 
        {
    
    
            for (int i = 0; i<200; i++) //This loop is for the process of iteration (or searching for new states)
            {
                double xNew = x + ((rand() / (double)RAND_MAX) * 2 - 1);
                double LNew = f(xNew);
    
                if (LNew < L || (rand() / (double)RAND_MAX) <= pow(e, -(LNew - L) / T))
                {
                    L = LNew;
                    x = xNew;
                }
            }
    
    
        }
    
        cout << "Final state = " << x << "\t, total of F(x) = " << f(x) << endl << endl;
    
    
    
        cin.get();
        return 0;
    }
    Any suggestions Or comments that might guide me is deeply appreciated, however, important to note, if I made a mistake or broke a rule of the forum please inform me Gently .

    Oh! by the way, if the concept of Simulated Annealing is not clear, you may refer to the following papers which can be found in a simple Google search:
    1. Simulated Annealing Algorithms: an overview.
    2. An Introduction to Interacting Simulated
      Annealing.
    3. Query Optimization (there is a sub-section for Simulated Annealing in this paper that explains SA briefly)


    Thank you very much for reading and I hope I can get your point of view on this matter.
    Last edited by abady; 03-10-2014 at 02:47 PM.

  2. #2
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Without getting into the algorithm itself, here are some changes that would make your code better imo:

    1. #include <stdlib.h> should be #include <cstdlib>, same goes for <time.h> which should be <ctime>.
    2. There is no need for you to store the time in a variable, just call time directly as the argument for srand:

    Code:
    srand(time(NULL));
    3. You never use the doubles declared in line 19, get rid of them.
    4. You have a lot of unnecessary vertical whitespace, get rid of it.
    5. You don't need the stdafx.h header, it is used for precompiled Windows headers.
    6. You should check if your compiler supports C++11, then you could drop all the C-specific rand/time stuff and use <chrono> and mt19937 instead.
    7. In C++, a literal such as '4' is an int, while a literal such as '4.0' is a double. If you want to use doubles you should make sure that all youre literals are doubles as well, for example, you have '(4 / 3)' in line 12, which should be 4.0/3.0.

    Other than these things, what improvements are you looking for? Are you unhappy with the results of the algorithm?
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Neo1 View Post
    2. There is no need for you to store the time in a variable, just call time directly as the argument for srand:
    And again, if your compiler supports C++11, you should substitute NULL for nullptr (given stdafx.h, I'm guessing you are using Visual Studio, which supports nullptr in recent versions).

    5. You don't need the stdafx.h header, it is used for precompiled Windows headers.
    While it may not be necessary (although it may speed up your compilation), I would say you are wrong on the second part. It's not used for precompiled headers. It's a precompiled header, plan and simple. You are responsible for putting in stuff yourself.

    6. You should check if your compiler supports C++11, then you could drop all the C-specific rand/time stuff and use <chrono> and mt19937 instead.
    Agreed, and if my speculation of you using Visual Studio is correct, then the compiler supports <random> and <chrono>. See documentation at cppreference.com for info on how to use these headers.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User abady's Avatar
    Join Date
    Mar 2014
    Posts
    5
    Thank you very much.

    I edited the code using what you suggested plus adding some other stuff as well.
    I'm happy with the result so far but I might need to modify it further soon, I will let you know if that happens as I would like to know your suggestion and need your suppert at that point.

    Thank you very much for both of you

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Lol what's annealing?

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    Quote Originally Posted by MutantJohn View Post
    Lol what's annealing?
    Simulated annealing - Wikipedia, the free encyclopedia

  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Ooh, physicists would be good at this. This is a very interesting topic I've never seen before. And no, this is not sarcasm. I'll have to read that beast of an article later but thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. working with simulated 2 and 3 dimensonal space
    By ashinms in forum C++ Programming
    Replies: 6
    Last Post: 08-18-2011, 08:07 PM
  2. Replies: 16
    Last Post: 01-20-2011, 10:58 PM
  3. which algorithm ?
    By jack_carver in forum C Programming
    Replies: 8
    Last Post: 02-15-2009, 11:41 AM
  4. O(n) algorithm
    By wu_weidong in forum C Programming
    Replies: 16
    Last Post: 10-05-2005, 05:52 PM
  5. my grandfather's chess algorithm can beat your grandfather's chess algorithm...
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 08-17-2001, 06:52 PM

Tags for this Thread