aco-acs.cpp

蚁群算法用于求解课程表安排问题。在linux下面实现的

/***************************************************************************
                         ACO-ACS.cpp   -   description
                            -----------------------
begin                   : Sunday March 10 18:46:50 CET 2002
copyright               : (C) 2002 by Max Manfrin
email                   : [e-mail]
***************************************************************************/

/***************************************************************************
*                                                                          *
*   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.                                    *
*                                                                          *
***************************************************************************/

#include "Control.h"
#include "Problem.h"
#include "Solution.h"
#include "Random.h"
#include "Ant.h"

#include <fstream>
#include <algorithm>
#include <math.h>
#include <limits.h>

// ACS PARAMETERS 
double TAU0;
double ALPHA;
double BETA;
double GAMMA;
double RHO;
double Q0;
int COLONYSIZE;
double FACTOR;
int FPITER;
int FPSTEPS;
int SPSTEPS;

Random* rnd;
time_t t;
vector<int> connection_degree;
vector<int> n_of_features;
Problem* problem;
vector<int> ordered_events;
vector<Ant*> colony;
Solution* bestSolution;
int bestfitness;
int bestquality;
double** pheromoneMatrix;
double** totalMatrix;
double delta_tau;
int mySteps;
//ofstream pheromatrix("file.max");

//Check if the copy between solution is done right
void check_copySolution(Solution* destination, Solution* origin){
  cout << "Origin      scv:" << &origin->scv << " value:"<< origin->scv << endl;
  cout << "Destination scv:" << &destination->scv << " value:" << destination->scv << endl;
  cout << "Origin      hcv:" << &origin->hcv << " value:" << origin->hcv << endl;
  cout << "Destination hcv:" << &destination->hcv << " value:" << destination->hcv << endl;
  cout << "Origin      feasible:" << &origin->feasible << " value:" << origin->feasible << endl;
  cout << "Destination feasible:" << &destination->feasible << " value:" << destination->feasible <<endl;
  cout << "Origin      data:" << &origin->data << " value:" << origin->data << endl;
  cout << "Destination data:" << &destination->data << " value:" << destination->data << endl;
  cout << "Origin      sln:" << &origin->sln << " value:";
  for (int i=0; i < (int)origin->sln.size(); i++){
    cout << origin->sln[i].first << "," << origin->sln[i].second << " ";
  }
  cout << endl;
  cout << "Destination sln:" << &destination->sln << " value:";
  for (int i=0; i < (int)destination->sln.size(); i++){
    cout << destination->sln[i].first << "," << destination->sln[i].second << " ";
  }
  cout << endl;
  cout << "Origin      timeslot_events:" << &origin->timeslot_events << " value:" << endl;
  for (int i=0; i <45; i++){
    cout << "   " << "Timeslot:" << i << " Events:"; 
    for (int j=0; j < (int)origin->timeslot_events[i].size(); j++){
      cout << origin->timeslot_events[i][j] << " ";
    }
    cout << endl;
  }
  cout<< endl;
  cout << "Destination timeslot_events:" << &destination->timeslot_events << " value:" << endl;
  for (int i=0; i < 45; i++){
    cout << "   " << "Timeslot:" << i << " Events:"; 
    for (int j=0; j < (int)destination->timeslot_events[i].size(); j++){
      cout << destination->timeslot_events[i][j] << " ";
    }
    cout << endl;
    }
  cout << endl;


}

// Print the pheromoneMatrix[ts][events]
//void print_pheromoneMatrix(){
  //  cout << "PHEROMONE MATRIX" << endl;
//  for (int j=0; j < problem->n_of_events; j++){
    //    cout << "Event " << j <<":";
//    for (int i=0; i < 45; i++){
//      pheromatrix << pheromoneMatrix[i][j] << " ";
//    }
//    pheromatrix << endl;
//  }
//  pheromatrix << endl;
//}

// BINARY PREDICATE USED AS THE SORTING CRITERIA
// FOR BUILDING THE EVENT LIST
// ORDER EVENTS BY CONNECTION DEGREE
// THEN BY NUMBER OF FEATURE
// THEN BY NUMBER OF STUDENTS
// THEN BY LABEL (this is why stable_sort)
//
bool eventsort (const int& a, const int& b) {

  if (connection_degree[a] > connection_degree[b]){
    return true;
  }
  else {
    if ((connection_degree[a] == connection_degree[b])&&(n_of_features[a] < n_of_features[b])){
      return true;
    }
    else{
      if ((connection_degree[a] == connection_degree[b])&&(n_of_features[a] == n_of_features[b])&&(problem->studentNumber[a] > problem->studentNumber[b])){
	return true;
      }
      else{
	return false;
      }
    }
  }
}


int main( int argc, char** argv) {

  // CREATE THE CONTROL OBJECT
  // PARSING THE COMMAND LINE
  //
  Control control(argc, argv);

  // CREATE THE PROBLEM OBJECT
  // LOADING DATA FROM THE INSTANCE FILE PASSED AT THE COMMAND LINE
  //
  problem = new Problem(control.getInputStream()); 



  // SET THE PARAMETERS DEPENDING ON THE PROBLEM INSTANCE
  // easy   : <= 200 eventsdouble TAU0;
  // medium : > 200 events && <= 300 students
  // hard   : > 200 events && > 300 students
  
  if (problem->n_of_events <= 200) {

    // SETTINGS FOR EASY INSTANCE
    //
    cerr << "Warning: Settings for the easy instance loaded" << endl;
    TAU0 = 0.5;
    ALPHA = 0.1;
    RHO = 0.1;
    BETA = 3.0;
    GAMMA = 2.0;
    Q0 = 0.0;
    COLONYSIZE = 15;
    FACTOR = 100000.0;
    FPITER = 1;
    FPSTEPS = 5000;
    SPSTEPS = 2000;    
  }
  else {
    if (problem->n_of_students <= 300){

      // SETTINGS FOR MEDIUM INSTANCE
      //
      cerr << "Warning: Settings for the medium instance loaded" << endl;
      TAU0 = 10.0;
      ALPHA = 0.1;
      RHO = 0.1;
      BETA = 3.0;
      GAMMA = 2.0;
      Q0 = 0.0;
      COLONYSIZE = 15;
      FACTOR = 10000000000.0;
      FPITER = 10;
      FPSTEPS = 50000;
      SPSTEPS = 10000;
    }
    else {

      // SETTINGS FOR HARD INSTANCE
      //
      cerr << "Warning: Settings for the hard instance loaded" << endl;
      TAU0 = 10.0;
      ALPHA = 0.1;
      RHO = 0.1;
      BETA = 3.0;
      GAMMA = 2.0;
      Q0 = 0.0;
      COLONYSIZE = 10;
      FACTOR = 10000000000.0;
      FPITER = 20;
      FPSTEPS = 150000;
      SPSTEPS = 100000;
    }
  }



  // CREATE THE RANDOM NUMBERS GENERATOR OBJECT 
  // seed 1 for debugging purpose only
  rnd = new Random((unsigned) control.getSeed());  

  // PRECALCULATE THE LIST OF EVENTS 
  //
  for (int i=0; i < problem->n_of_events; i++){
    connection_degree.push_back(0);
    n_of_features.push_back(0);
  }
  // CALCULATE CONNECTION DEGREE AMONGST EVENTS
  //  
  for (int i=0; i < problem->n_of_events; i++){
    int sum = 0;
    for (int j=0; j < problem->n_of_events; j++){
      if (problem->eventCorrelations[i][j]){
	sum++;
      }
    }
    connection_degree[i] = sum;
  }
  // CALCULATE NUMBER OF FEATURES REQUIRED BY EACH EVENT
  //
  for (int i=0; i < problem->n_of_events; i++){
    int sum = 0;
    for (int j=0; j < problem->n_of_features; j++){
      if (problem->event_features[i][j]){
	sum++;
      }
    }
    n_of_features[i] = sum;
  }
  // CALL THE SORTING FUNCTION ON ALL THE ELEMENTS
  //