/***************************************************************************                          hc-mmas-ubqp.cpp  -  description                             -------------------    begin                : Fri Mar 21 15:46:28 CET 2003    copyright            : (C) 2003 by Christian Blum    email                : cblum@ulb.ac.be ***************************************************************************//***************************************************************************    Program's name: hc-mmas-ubqp    Ant Colony Optimization algorithm to tackle     Unary Binary Quadratic Programming    Copyright (C) 2003  Christian Blum    This program is free software; you can redistribute it and/or modify    it under the terms of the GNU General Public License as published by    the Free Software Foundation; either version 2 of the License, or    (at your option) any later version.    This program is distributed in the hope that it will be useful,    but WITHOUT ANY WARRANTY; without even the implied warranty of    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the    GNU General Public License for more details.    You should have received a copy of the GNU General Public License    along with this program; if not, write to the Free Software    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA    Author's contact details:     email: cblum@ulb.ac.be    mail address: Universite Libre de Bruxelles, IRIDIA,                  Av. Franklin Roosevelt 50, CP 194/6,                  B-1050 Brussels, Belgium ***************************************************************************/#ifdef HAVE_CONFIG_H#include <config.h>#endif#include "Timer.h"#include "Unconstrained_Ant.h"#include "Random.h"#include "utilstuff.h"#include "Solution.h"#include <string>#include <list>// the following five variables are involved in termination criteria issuesint n_of_iter = 1000;double time_limit = 100.0;bool time_limit_given = false;bool iter_limit_given = false;bool input_file_given = false;// problem_size: number of variables of the problem instanceint problem_size;// n_of_ants: the number of antslong int n_of_ants = 10;// l_rate: the learning rate (used for updating the pheromone values)double l_rate = 0.05;// tau_min, tau_max: lower, respecively upper, limit for the pheromone valuesdouble tau_min = 0.001;double tau_max = 0.999;// n_of_trials: the number of trials that is to be executed for the given problem instanceint n_of_trials = 1;// ls: usage of local searchbool ls = true;// ants: the list of antslist<Unconstrained_Ant*> ants;// q_matrix: the matrix that specifies the problem instance (as read from the instance file)double** q_matrix;// c_const: we add c_const to every objective function value in order to have all positive objective function valuesdouble c_const;// pheromone: the structure that holds the pheromone valuesmap<int,pair<double,double> >* pheromone;// t: a variable that is involved in initializing the random generatortime_t t;// rnd: a random generatorRandom* rnd;/* The method readFile is used to read the problem specification from a file */void readFile(string fileName) {  FILE* inputFile = fopen(fileName.c_str(), "r");  if (fscanf(inputFile, "%ld", &problem_size) < 0) {    printf("error reading problem size.\n");    exit(1);  }    q_matrix = DoubleMatrixAlloc(problem_size,problem_size);  for (int i = 0; i < problem_size; i++) {    for (int j = 0; j < problem_size; j++) {      q_matrix[i][j] = 0.0;    }  }  int entries;  if (fscanf(inputFile, "%ld", &entries) < 0) {    printf("error reading number of entries.\n");    exit(1);  }      if (fscanf(inputFile, "%lf", &c_const) < 0) {    printf("error reading c_const.\n");    exit(1);  }      for (int i = 0; i < entries; i++) {    int pos1;    int pos2;    double val;    if (fscanf(inputFile, "%ld", &pos1) < 0) {      printf("error reading first position.\n");      exit(1);    }    if (fscanf(inputFile, "%ld", &pos2) < 0) {      printf("error reading second position.\n");      exit(1);    }    if (fscanf(inputFile, "%lf", &val) < 0) {      printf("error reading value.\n");      exit(1);    }    q_matrix[pos1][pos2] = val;    q_matrix[pos2][pos1] = val;  }}/* The method read_parameters is used to read-in the command line parameters */void read_parameters(int argc, char **argv){  int iarg=1;  while (iarg < argc)  {    if (strcmp(argv[iarg],"-i")==0) {      readFile(argv[++iarg]);      input_file_given = true;    }    else if (strcmp(argv[iarg],"-t")==0) {       time_limit=atof(argv[++iarg]);      time_limit_given = true;    }    else if (strcmp(argv[iarg],"-maxiter")==0) {      n_of_iter=atoi(argv[++iarg]);      iter_limit_given = true;    }    else if (strcmp(argv[iarg],"-nants")==0) {      n_of_ants = atoi(argv[++iarg]);    }    else if (strcmp(argv[iarg],"-lrate")==0) {      l_rate = atof(argv[++iarg]);    }    else if (strcmp(argv[iarg],"-n")==0) {      n_of_trials=atoi(argv[++iarg]);    }    else if (strcmp(argv[iarg],"-ls")==0) {      if (strcmp(argv[++iarg],"yes")==0) {	ls = true;      }      else {	ls = false;      }    }    iarg++;  }  if (input_file_given == false) {    printf("No input file given.");    printf("\n");    exit(1);  }  if ((time_limit_given == false) && (iter_limit_given == false)) {    cout << endl;    cout << "please specify:" << endl;    cout << endl;    cout << "* a time limit (i.e., -t 20.0), or" << endl;    cout << "* an iteration limit (i.e., -maxiter 1000), or" << endl;    cout << "* both" << endl;    cout << endl;    exit(1);  }}/* The method getBestSolutionInIteration can be called after each ant has produced a solution.    The method returns the best one among the current solutions produced by the ants */Solution* getBestSolutionInIteration() {  Solution* sol;  bool start = true;  for (list<Unconstrained_Ant*>::iterator anAnt = ants.begin(); anAnt != ants.end(); anAnt++) {    if (start) {      start = false;      sol = (*anAnt)->constructed_solution;    }    else {      Solution* current = (*anAnt)->constructed_solution;      if ((*current).quality > (*sol).quality) {	sol = current;      }    }  }  return sol->copy();}/* The method getIterationAverage can be called after each ant has produced a solution.    The method returns the average objective function values of the current solutions produced by the ants */double getIterationAverage() {  double ret_val = 0.0;  for (list<Unconstrained_Ant*>::iterator anAnt = ants.begin(); anAnt != ants.end(); anAnt++) {    ret_val = ret_val + ((double)((*anAnt)->constructed_solution)->quality);  }  return (ret_val / (double)n_of_ants);}/* The method resetUniformPheromoneValues initializes (or resets) all the pheromone values to 0.5 */void resetUniformPheromoneValues() {  for (int i = 0; i < problem_size; i++) {    (*pheromone)[i].first = 0.5;    (*pheromone)[i].second = 0.5;  }}/* The method computeConvergenceFactor computes the convergence factor cf, which gives an   indication about the current state of the system in terms of its convergence */double computeConvergenceFactor() {  double ret_val = 0.0;  for (int i = 0; i < problem_size; i++) {    if ((tau_max - (*pheromone)[i].first) > ((*pheromone)[i].first - tau_min)) {      ret_val = ret_val + tau_max - (*pheromone)[i].first;    }    else {      ret_val = ret_val + (*pheromone)[i].first - tau_min;    }    if ((tau_max - (*pheromone)[i].second) > ((*pheromone)[i].second - tau_min)) {      ret_val = ret_val + tau_max - (*pheromone)[i].second;    }    else {      ret_val = ret_val + (*pheromone)[i].second - tau_min;    }  }  ret_val = ret_val / (2.0 * ((double)problem_size) * (tau_max - tau_min));  ret_val = (ret_val - 0.5) * 2.0;  return ret_val;}/* 'main' is the main body of the program */int main( int argc, char **argv ) {  // first the command line parameters have to be read  if ( argc < 2 ) {    exit(1);  }  else {    read_parameters(argc,argv);  }  // initialization of the random generator (using the current time)  rnd = new Random((unsigned) time(&t));  // initialization of the structure that holds the pheromone values  pheromone = new map<int,pair<double,double> >;  /* initialization of the list of ants (as information they receive the problem size,