hc-mmas-ubqp.cpp

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

/***************************************************************************
                          hc-mmas-ubqp.cpp  -  description
                             -------------------
    begin                : Fri Mar 21 15:46:28 CET 2003
    copyright            : (C) 2003 by Christian Blum
    email                : [e-mail]
 ***************************************************************************/

/***************************************************************************
    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: [e-mail]
    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 issues
int 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 instance
int problem_size;

// n_of_ants: the number of ants
long 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 values
double 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 instance
int n_of_trials = 1;

// ls: usage of local search
bool ls = true;

// ants: the list of ants
list<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 values
double c_const;

// pheromone: the structure that holds the pheromone values
map<int,pair<double,double> >* pheromone;

// t: a variable that is involved in initializing the random generator
time_t t;

// rnd: a random generator
Random* 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,