Multi-threaded Simulated Annealing

Question

I wrote a multithreaded simulated annealing program but its not running. I am not sure if the code is correct or not. The code is able to compile but when i run the code it crashes. Its just a run time error.

#include <stdio.h> 
#include <time.h>
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <windows.h>
#include <process.h> 

using namespace std;



typedef vector<double> Layer; //defines a vector type

typedef struct {
   Layer Solution1;
   double temp1;
   double coolingrate1;
   int MCL1;
   int prob1;
}t; 
//void SA(Layer Solution, double temp, double coolingrate, int MCL, int prob){


double  Rand_NormalDistri(double mean, double stddev) {
 //Random Number from Normal Distribution

    static double n2 = 0.0;
    static int n2_cached = 0;
    if (!n2_cached) {
       // choose a point x,y in the unit circle uniformly at random
     double x, y, r;
     do {
  //  scale two random integers to doubles between -1 and 1
   x = 2.0*rand()/RAND_MAX - 1;
   y = 2.0*rand()/RAND_MAX - 1;

    r = x*x + y*y;
   } while (r == 0.0 || r > 1.0);

        {
       // Apply Box-Muller transform on x, y
        double d = sqrt(-2.0*log(r)/r);
      double n1 = x*d;
      n2 = y*d;

       // scale and translate to get desired mean and standard deviation

      double result = n1*stddev + mean;

        n2_cached = 1;
        return result;
        }
    } else {
        n2_cached = 0;
        return n2*stddev + mean;
    }
}



double   FitnessFunc(Layer x, int ProbNum)
{


    int i,j,k;
    double z; 
  double fit = 0;  
  double   sumSCH; 

 if(ProbNum==1){
  // Ellipsoidal function
  for(j=0;j< x.size();j++)
    fit+=((j+1)*(x[j]*x[j]));
}

 else if(ProbNum==2){
  // Schwefel's function
  for(j=0; j< x.size(); j++)
    {
      sumSCH=0;

      for(i=0; i<j; i++)
    sumSCH += x[i];
      fit += sumSCH * sumSCH;
    }
}

 else if(ProbNum==3){
  // Rosenbrock's function

  for(j=0; j< x.size()-1; j++)
    fit += 100.0*(x[j]*x[j] - x[j+1])*(x[j]*x[j] - x[j+1]) + (x[j]-1.0)*(x[j]-1.0);
}
  return fit;
}

double probl(double energychange, double temp){
    double a;
    a= (-energychange)/temp;
    return double(min(1.0,exp(a)));
}

int random (int min, int max){
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do{
        x = rand();
    }while (x >= RAND_MAX - remainder);
    return min + x % n;
}

//void SA(Layer Solution, double temp, double coolingrate, int MCL, int prob){
void SA(void *param){

    t *args = (t*) param;

    Layer Solution = args->Solution1;
    double temp = args->temp1;
    double coolingrate = args->coolingrate1;
    int MCL = args->MCL1;
    int prob = args->prob1;

    double Energy;
    double EnergyNew;
    double EnergyChange;
    Layer SolutionNew(50);

    Energy = FitnessFunc(Solution, prob);

    while (temp > 0.01){

        for ( int i = 0; i < MCL; i++){
            for (int j = 0 ; j < SolutionNew.size(); j++){

                SolutionNew[j] = Rand_NormalDistri(5, 1);
            }
            EnergyNew = FitnessFunc(SolutionNew, prob);
            EnergyChange = EnergyNew - Energy;

            if(EnergyChange <= 0){
                Solution = SolutionNew;
                 Energy = EnergyNew;    
            }
            if(probl(EnergyChange ,temp ) >  random(0,1)){
                //cout<<SolutionNew[i]<<endl;
                Solution = SolutionNew;
                 Energy = EnergyNew;
                cout << temp << "=" << Energy << endl;
            }
        }
        temp = temp * coolingrate;
    }

}




int main ()
{ 

 srand ( time(NULL) ); //seed for getting different numbers each time the prog is run


Layer SearchSpace(50); //declare a vector of 20 dimensions

//for(int a = 0;a < 10; a++){

for (int i = 0 ; i < SearchSpace.size(); i++){

    SearchSpace[i] = Rand_NormalDistri(5, 1);
}

t *arg1;
arg1 = (t *)malloc(sizeof(t));
arg1->Solution1 = SearchSpace;
arg1->temp1 = 1000;
arg1->coolingrate1 = 0.01;
arg1->MCL1 = 100;
arg1->prob1 = 3;

//cout << "Test " << ""<<endl;
_beginthread( SA, 0, (void*) arg1);
Sleep( 100 );

//SA(SearchSpace, 1000, 0.01, 100, 3);
//}

  return 0;
}

Please help.

Thanks Avinesh

Answer 1

As leftaroundabout pointed out, you're using malloc in C++ code. This is the source of your crash.

Malloc will allocate a block of memory, but since it was really designed for C, it doesn't call any C++ constructors. In this case, the vector<double> is never properly constructed. When

arg1->Solution1 = SearchSpace;

Is called, the member variable "Solution1" has an undefined state and the assignment operator crashes.

Instead of malloc try

arg1 = new t;

This will accomplish roughly the same thing but the "new" keyword also calls any necessary constructors to ensure the vector<double> is properly initialized.

This also brings up another minor issue, that this memory you've newed also needs to be deleted somewhere. In this case, since arg1 is passed to another thread, it should probably be cleaned up like

delete args;

by your "SA" function after its done with the args variable.

Answer 2

While I don't know the actual cause for your crashes I'm not really surprised that you end up in trouble. For instance, those "cached" static variables in Rand_NormalDistri are obviously vulnerable to data races. Why don't you use std::normal_distribution? It's almost always a good idea to use standard library routines when they're available, and even more so when you need to consider multithreading trickiness.

Even worse, you're heavily mixing C and C++. malloc is something you should virtually never use in C++ code – it doesn't know about RAII, which is one of the few intrinsically safe things you can cling onto in C++.