unconstrained_ant.cpp

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

/***************************************************************************
                          Unconstrained_Ant.cpp  -  description
                             -------------------
    begin                : Fri Mar 21 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

 ***************************************************************************/

#include "config.h"
#include "Unconstrained_Ant.h"

// The constructor initializes an ant

Unconstrained_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 necessary

Unconstrained_Ant::~Unconstrained_Ant(){

  if (constructed_solution != NULL) {
    delete(constructed_solution);
  }  
}

// The method 'construct' constructs a solution to an unconstrained, binary problem

void 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 local
search 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;
}