hc-mmas-ubqp.cpp

The software package provides a MAX-MIN Ant System implemented in the Hyper-Cube Framework for the

     the random generator, the pheromone value structure, and the problem instance information */
  for (int na = 0; na < n_of_ants; na++) {
    Unconstrained_Ant* ant = new Unconstrained_Ant(problem_size,rnd,pheromone,q_matrix,c_const,ls);
    ants.push_back(ant);
  }

  /* initialization of the three solutions 'best_so_far', 'restart_best' and 'iteration_best', which
     are used to update the pheromone values */
  Solution* best_so_far = NULL;
  Solution* restart_best = NULL;
  Solution* iteration_best = NULL;

  /* the following three variables are for collecting statistics on several trials */
  int best_solution_value = 0;
  vector<double> results;
  vector<double> times_best_found;

  /* the following for loop is for controlling the number of trials as specified by command line parameters */
  for (int trial_counter = 1; trial_counter <= n_of_trials; trial_counter++) {

    printf("begin try %d\n",trial_counter);

    // upon declaration of a variable of type 'Timer' the time is running ... 
    Timer timer;

    // 'iter' is the iteration counter
    int iter = 1;

    /* if the three solutions that are used for updating the pheromone values are initialized by a 
       previous trial, we delete them */
    if (best_so_far != NULL) {
      delete(best_so_far);
    }
    best_so_far = NULL;
    if (iteration_best != NULL) {
      delete(iteration_best);
    }
    iteration_best = NULL;
    if (restart_best != NULL) {
      delete(restart_best);
    }
    restart_best = NULL;

    // for every trial we reinitialize the pheromone values to 0.5 each */
    resetUniformPheromoneValues();

    /* the following four variable are for controlling the update and the restart of the algorithm 
       cf is the convergence factor
       bs_update regulates the use of the best_so_far solution for updating
       program_stop controls the termination of a trial
       restart controls the restart mechanism of the algorithm 
       time_taken is a variable for keeping the CPU times when checked */
    double cf = 0.0;
    bool bs_update = false;
    bool program_stop = false;
    bool restart = false;
    double time_taken = 0.0;

    /* this is the main loop of the algorithm. At each iteration ants produce a solution each and 
       the pheromone values are updated. */
    while (!program_stop) {

      // every ant constructs a solution, which is then evaluated 
      map<int,pair<double,double> > sgdupd;
      for (list<Unconstrained_Ant*>::iterator anAnt = ants.begin(); anAnt != ants.end(); anAnt++) {
	(*anAnt)->construct();
	(*anAnt)->evaluate();
      }
      
      // the iteration_best solution is determined
      if (iteration_best != NULL) {
	delete(iteration_best);
      }
      iteration_best = getBestSolutionInIteration();
           
      // .. as well as the average objective function values of the solutions in that iteration
      double average = getIterationAverage();

      if (iter == 1) {
	// if we are in the first iteration then we can initialize all the variables
	if (best_so_far != NULL) {
	  delete(best_so_far);
	}
	best_so_far = iteration_best->copy();
	if (restart_best != NULL) {
	  delete(restart_best);
	}
	restart_best = iteration_best->copy();
	time_taken = timer.elapsed_time(Timer::VIRTUAL);
	results.push_back((double)(best_so_far->quality - c_const));
	times_best_found.push_back(time_taken);
	printf("best %g\ttime %f\n",(best_so_far->quality - c_const),time_taken);
      }
      else {
	if (restart) {
	  // if this is the first iteration after a restart, then we do the following:
	  restart = false;
	  delete(restart_best);
	  restart_best = iteration_best->copy();
	  if (iteration_best->quality > best_so_far->quality) {
	    delete(best_so_far);
	    best_so_far = iteration_best->copy();
	    time_taken = timer.elapsed_time(Timer::VIRTUAL);
	    printf("best %g\ttime %f\n",(best_so_far->quality - c_const),time_taken);
	    results[trial_counter-1] = (double)(best_so_far->quality - c_const);
	    times_best_found[trial_counter-1] = time_taken;
	  }
	}
	else {
	  if (iteration_best->quality > restart_best->quality) {
	    delete(restart_best);
	    restart_best = iteration_best->copy();
	  }
	  if (iteration_best->quality > best_so_far->quality) {
	    delete(best_so_far);
	    best_so_far = iteration_best->copy();
	    time_taken = timer.elapsed_time(Timer::VIRTUAL);
	    printf("best %g\ttime %f\n",(best_so_far->quality - c_const),time_taken);
	    results[trial_counter-1] = (double)(best_so_far->quality - c_const);
	    times_best_found[trial_counter-1] = time_taken;
	  }
	}
      }
      if ((best_so_far->quality - c_const) > best_solution_value) {
	best_solution_value = (int)(best_so_far->quality - c_const);
      }
      
      // computation of the convergence factor
      cf = computeConvergenceFactor();

      /* if the best_so_far solution was used for updating the pheromone values and the
         convergence factor is greater than 0.99 we do a restart ... */
      if (bs_update && (cf > 0.99)) {
	bs_update = false;
	restart = true;
	cf = 0.0;
	resetUniformPheromoneValues();
      }
      else {
	/* ... otherwise: if convergence factor is greater than 0.99 we use the best_so_far
           solution from now on for updating */
	if (cf > 0.99) {
	  bs_update = true;
	}
	/* i_weight, r_weight, g_weight are the weights of influence for updating the pheromone values 
           they are set depending on the convergence factor cf */
	double i_weight = 0.0;
	double r_weight = 0.0;
	double g_weight = 0.0;
	if (!bs_update) {
	  if (cf < 0.4) {
	    i_weight = 1.0;
	    r_weight = 0.0;
	    g_weight = 0.0;
	  }
	  if ((cf >= 0.4) && (cf < 0.6)) {
	    i_weight = 2.0 / 3.0;
	    r_weight = 1.0 / 3.0;
	    g_weight = 0.0;
	  }
	  if ((cf >= 0.6) && (cf < 0.8)) {
	    i_weight = 1.0 / 3.0;
	    r_weight = 2.0 / 3.0;
	    g_weight = 0.0;
	  }
	  if (cf >= 0.8) {
	    i_weight = 0.0;
	    r_weight = 1.0;
	    g_weight = 0.0;
	  }
	}
	else {
	  // if bs_update = TRUE we use the best_so_far solution for updating the pheromone values
	  i_weight = 0.0;
	  r_weight = 0.0;
	  g_weight = 1.0;
	}

	/* We specifiy vector d, and then we update the pheromone vector towards vector d
	   depending on the learning rate l_rate */
	map<int,pair<double,double> > d;
	for (int i = 0; i < problem_size; i++) {
	  d[i].first = 0.0;
	  d[i].second = 0.0;
	}
	double sum = (i_weight * iteration_best->quality) + (g_weight * best_so_far->quality) + (r_weight * restart_best->quality);
	for (int i = 0; ((i < problem_size) && (i_weight > 0.0)); i++) {
	  if ((*iteration_best).solution[i] == 0) {
	    d[i].first = d[i].first + (i_weight * iteration_best->quality);
	  }
	  else {
	    d[i].second = d[i].second + (i_weight * iteration_best->quality);
	  }
	}
	for (int i = 0; ((i < problem_size) && (r_weight > 0.0)); i++) {
	  if ((*restart_best).solution[i] == 0) {
	    d[i].first = d[i].first + (r_weight * restart_best->quality);
	  }
	  else {
	    d[i].second = d[i].second + (r_weight * restart_best->quality);
	  }
	}
	for (int i = 0; ((i < problem_size) && (bs_update)); i++) {
	  if ((*best_so_far).solution[i] == 0) {
	    d[i].first = d[i].first + (g_weight * best_so_far->quality);
	  }
	  else {
	    d[i].second = d[i].second + (g_weight * best_so_far->quality);
	  }
	}

	for (int i = 0; i < problem_size; i++) {
	  d[i].first = d[i].first / sum;
	  d[i].second = d[i].second / sum;
	}
	for (int i = 0; i < problem_size; i++) {
	  (*pheromone)[i].first = (*pheromone)[i].first + (l_rate * (d[i].first - (*pheromone)[i].first));
	  (*pheromone)[i].second = (*pheromone)[i].second + (l_rate * (d[i].second - (*pheromone)[i].second));
	  if ((*pheromone)[i].first > tau_max) {
	    (*pheromone)[i].first = tau_max;
	  }
	  if ((*pheromone)[i].second > tau_max) {
	    (*pheromone)[i].second = tau_max;
	  }
	  if ((*pheromone)[i].first < tau_min) {
	    (*pheromone)[i].first = tau_min;
	  }
	  if ((*pheromone)[i].second < tau_min) {
	    (*pheromone)[i].second = tau_min;
	  }
	}
      }
      
      // in the following we check if the termination criteria are satisfied
      iter = iter + 1;
      
      if (time_limit_given && iter_limit_given) {
	if ((timer.elapsed_time(Timer::VIRTUAL) > time_limit) || (iter > n_of_iter)) {
	  program_stop = true;
	}
      }
      else {
	if (time_limit_given) {
	  if (timer.elapsed_time(Timer::VIRTUAL) > time_limit) {
	    program_stop = true;
	  }
	}
	else {
	  if (iter > n_of_iter) {
	    program_stop = true;
	  }
	}
      }
    }
    printf("end try %d\n",trial_counter);
  }

  /* the following lines are for writing the statistics about the experiments onto the screen
     1) the best solution found in all the trials
     2) the average of the best solutions found in all the trials
     3) the standard deviation of the average in 2)
     4) the average CPU at which the best solutions of the trials were found
     5) the standard deviation of the average in 4) */

  double r_mean = 0.0;
  double t_mean = 0.0;
  for (int i = 0; i < results.size(); i++) {
    r_mean = r_mean + results[i];
    t_mean = t_mean + times_best_found[i];
  }
  r_mean = r_mean / ((double)results.size());
  t_mean = t_mean / ((double)times_best_found.size());
  double rsd = 0.0;
  double tsd = 0.0;
  for (int i = 0; i < results.size(); i++) {
    rsd = rsd + pow(results[i]-r_mean,2.0);
    tsd = tsd + pow(times_best_found[i]-t_mean,2.0);
  }
  rsd = rsd / ((double)(results.size()-1.0));
  if (rsd > 0.0) {
    rsd = sqrt(rsd);
  }
  tsd = tsd / ((double)(times_best_found.size()-1.0));
  if (tsd > 0.0) {
    tsd = sqrt(tsd);
  }
  printf("statistics\t%d\t%f\t%f\t%f\t%f\n",best_solution_value,r_mean,rsd,t_mean,tsd);
  delete(rnd);
}