Thread: 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.

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?

Originally Posted by Neo1

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.