/***************************************************************************                          Unconstrained_Ant.cpp  -  description                             -------------------    begin                : Fri Mar 21 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 ***************************************************************************/#include "config.h"#include "Unconstrained_Ant.h"// The constructor initializes an antUnconstrained_Ant::Unconstrained_Ant(int ps, Random* ri, map<int,pair<double,double> >* pi, double** qm, double cc, bool ls) {  r_number = ri;  pheromone = pi;  problem_size = ps;  q_matrix = qm;  constructed_solution = NULL;  c_const = cc;  ls_usage = ls;}// the deconstructor deletes the constructed solution if necessaryUnconstrained_Ant::~Unconstrained_Ant(){  if (constructed_solution != NULL) {    delete(constructed_solution);  }  }// The method 'construct' constructs a solution to an unconstrained, binary problemvoid Unconstrained_Ant::construct() {    current_solution.clear();  positives.clear();  if (constructed_solution != NULL) {    delete(constructed_solution);  }  for (int count = 0; count < problem_size; count++) {    double rnum = r_number->next();    double sum = (*pheromone)[count].first + (*pheromone)[count].second;    if (rnum < ((*pheromone)[count].first / sum)) {      current_solution.push_back(0);    }    else {      current_solution.push_back(1);      positives.push_back(count);    }  }}/* In 'evaluate' the solution quality is determined and the constructed solution plus its quality is put   into a new instance of class 'Solution' */void Unconstrained_Ant::evaluate() {  double val = solutionQuality();  constructed_solution = new Solution();  constructed_solution->solution = current_solution;  constructed_solution->quality = val;  if (ls_usage) {    localsearch();  }}/* Method 'localsearch' is a steepest descent local search based on the one-flip neighborhood. The localsearch is applied to the current solution */void Unconstrained_Ant::localsearch() {  double sol_value = constructed_solution->quality;  map<int,double> flip_values;  for (int i = 0; i < problem_size; i++) {    bool positive_flip = true;    if (current_solution[i] == 1) {      positive_flip = false;    }    else {      positive_flip = true;    }    double flip_value = 0.0;    if (positive_flip) {      flip_value = q_matrix[i][i];      for (vector<int>::iterator aP = positives.begin(); aP != positives.end(); aP++) {	flip_value = flip_value + q_matrix[i][*aP] + q_matrix[*aP][i];      }    }    else {      flip_value = -1.0 * q_matrix[i][i];      for (vector<int>::iterator aP = positives.begin(); aP != positives.end(); aP++) {	if ((*aP) != i) {	  flip_value = flip_value - q_matrix[i][*aP] - q_matrix[*aP][i];	}      }    }    flip_values[i] = flip_value;  }  double stop = false;  while (!stop) {    int flip_position = 0;    double best_flip_value = 0.0;    for (int i = 0; i < problem_size; i++) {      if (flip_values[i] > best_flip_value) {	flip_position = i;	best_flip_value = flip_values[i];      }    }    if (best_flip_value > 0.0) {      sol_value = sol_value + best_flip_value;      flip_values[flip_position] = -1.0 * flip_values[flip_position];      if (current_solution[flip_position] == 0) {	current_solution[flip_position] = 1;	for (int i = 0; i < problem_size; i++) {	  if (i != flip_position) {	    if (current_solution[i] == 0) {	      flip_values[i] = flip_values[i] + q_matrix[i][flip_position] + q_matrix[flip_position][i];	    }	    else {	      flip_values[i] = flip_values[i] - q_matrix[i][flip_position] - q_matrix[flip_position][i];	    }	  }	}      }      else {	current_solution[flip_position] = 0;	for (int i = 0; i < problem_size; i++) {	  if (i != flip_position) {	    if (current_solution[i] == 0) {	      flip_values[i] = flip_values[i] - q_matrix[i][flip_position] - q_matrix[flip_position][i];	    }	    else {	      flip_values[i] = flip_values[i] + q_matrix[i][flip_position] + q_matrix[flip_position][i];	    }	  }	}      }    }    else {      stop = true;      constructed_solution->solution = current_solution;      constructed_solution->quality = sol_value;    }  }}/* The method 'solutionQuality' computes the objective function value of a solution */double Unconstrained_Ant::solutionQuality() {  double ret_val = c_const;  //cout << "c_const: " << c_const << endl;  for (int i = 0; i < problem_size; i++) {    for (int j = 0; j < problem_size; j++) {      ret_val = ret_val + (((double)current_solution[i]) * ((double)current_solution[j]) * q_matrix[i][j]);    }  }  return ret_val;}