solution.cpp

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

#include "Solution.h"

Solution::Solution(Problem* pd, Random* rnd) {

  data = pd;
  rg = rnd;
  slnInit();
}

void Solution::slnInit() {

  pair<int,int> initPair;
  initPair.first = -1 ;
  initPair.second = -1 ;
  for (int i = 0; i < (*data).n_of_events; i++ ){
    sln.push_back( initPair ) ;
  }
 
}

void Solution::copy(Solution *orig)
{
  sln = orig->sln;
  data = orig->data; 
  timeslot_events = orig->timeslot_events;
  feasible = orig->feasible;
  scv = orig->scv;
  hcv = orig->hcv;
}

void Solution::RandomInitialSolution( )
{
  // assign a random timeslot to each event
  for(int i = 0; i < data->n_of_events; i++){
    int t = (int)(rg->next() * 45);
    sln[i].first = t;
    timeslot_events[t].push_back(i);
  }
  // and assign rooms to events in each non-empty timeslot
  for(int j = 0; j < 45; j++){
    if((int)timeslot_events[j].size())
      assignRooms(j);
  }
}

bool Solution::computeFeasibility()
{ 
  for (int i = 0; i < data->n_of_events; i++) {    
    for (int j = i+1; j < data->n_of_events; j++) {
      if ((sln[i].first == sln[j].first) && (sln[i].second == sln[j].second)) { 
	feasible = false;
	return false;                                // only one class can be in each room at any timeslot
      }
      if ((data->eventCorrelations[i][j] == 1) && (sln[i].first == sln[j].first)) {
	feasible = false;
        return false;                                // two events sharing students cannot be in the same timeslot
      }
    }
    if( data->possibleRooms[i][sln[i].second]  == 0 ){
      feasible = false;
      return false;                 // each event should take place in a suitable room
    }
  }
  // if none of the previous hard constraint violations occurs the timetable is feasible
  feasible = true;
  return true;
}

int Solution::computeScv()
{
  int consecutiveClasses, classesDay;
  bool attendsTimeslot;

  scv = 0; // set soft constraint violations to zero to start with

  for(int i = 0; i < data->n_of_events; i++){ // classes should not be in the last slot of the day
    if( sln[i].first%9 == 8 )
      scv += data->studentNumber[i];  // one penalty for each student attending such a class
  }

  for (int j = 0; j < data->n_of_students; j++) { // students should not have more than two classes in a row
    consecutiveClasses = 0;
    for (int i = 0; i < 45; i++) { // count consecutive classes on a day
      if ((i % 9) == 0) {
	consecutiveClasses = 0;
      }
      attendsTimeslot = false;
      for (int k = 0; k < (int)timeslot_events[i].size(); k++) {
	if (data->student_events[j][timeslot_events[i][k]] == 1) {
	  attendsTimeslot = true;
	  consecutiveClasses = consecutiveClasses + 1;
	  if (consecutiveClasses > 2) {
	    scv = scv + 1;
	  }
	  break;
	}
      }
      if(!attendsTimeslot)
	consecutiveClasses = 0;
    }
  }
  for (int j = 0; j < data->n_of_students; j++) { //students should not have a single class on a day
    classesDay = 0;
    for (int d = 0; d < 5; d++) {   // for each day
      classesDay = 0;               //number of classes per day
      for(int t = 0; t < 9; t++){   // for each timeslot of the day
	for (int k = 0; k < (int)timeslot_events[9*d+t].size(); k++) { 
	  if (data->student_events[j][timeslot_events[9*d+t][k]] == 1) {
	    classesDay = classesDay + 1;
	    break;
	  }
	}
	if(classesDay > 1) // if the student is attending more than one class on that day
	  break;	   // go to the next day
      }  
      if (classesDay == 1) {
	scv = scv + 1;
      }
    }
  }
  return scv;
}

int Solution::computeHcv()
{

  hcv = 0; // set hard constraint violations to zero to start with
  // and count them
  for (int i = 0; i < data->n_of_events; i++) {     
    for (int j = i+1; j < data->n_of_events; j++) {
      if ((sln[i].first == sln[j].first) && (sln[i].second == sln[j].second)) { // only one class can be in each room at any timeslot
	hcv = hcv + 1;
      }
      if ((sln[i].first == sln[j].first) && (data->eventCorrelations[i][j] == 1)) {  // two events sharing students cannot be in the same timeslot
	hcv = hcv + 1;
      }
    }
    if( data->possibleRooms[i][sln[i].second]  == 0 )  // an event should take place in a suitable room
      hcv = hcv + 1;
  }
 
  return hcv;
}

//compute hard constraint violations involving event e
int Solution::eventHcv(int e)
{
  int eHcv = 0; // set to zero hard constraint violations for event e
  int t = sln[e].first; // note the timeslot in which event e is
  for (int i = 0; i < (int)timeslot_events[t].size(); i++){
    if ((timeslot_events[t][i]!=e)){ 
      if (sln[e].second == sln[timeslot_events[t][i]].second) {
	eHcv = eHcv + 1; // adds up number of events sharing room and timeslot with the given one
	//cout << "room + timeslot in common "  <<eHcv <<" event " << i << endl;
      }   
      if(data->eventCorrelations[e][timeslot_events[t][i]] == 1) {
	eHcv = eHcv + 1;  // adds up number of incompatible( because of students in common) events in the same timeslot
	//cout << "students in common " << eHcv <<" event " << i << endl;
      }
    }
  }
  // the suitable room hard constraint is taken care of by the assignroom routine
  return eHcv;
}

//compute hard constraint violations that can be affected by moving event e from its timeslot
int Solution::eventAffectedHcv(int e)
{
  int aHcv = 0; // set to zero the affected hard constraint violations for event e
  int t = sln[e].first; // t timeslot where event e is
  for (int i = 0; i < (int)timeslot_events[t].size(); i++){
    for(int j= i+1;  j < (int)timeslot_events[t].size(); j++){
      if (sln[timeslot_events[t][i]].second == sln[timeslot_events[t][j]].second) {
	aHcv = aHcv + 1; // adds up number of room clashes in the timeslot of the given event (rooms assignement are affected by move for the whole timeslot)
	//cout << "room + timeslot in common "  <<aHcv <<" events " << timeslot_events[t][i] << " and " << timeslot_events[t][j] << endl;
      }
    }
    if(timeslot_events[t][i] != e){   
      if(data->eventCorrelations[e][timeslot_events[t][i]] == 1) {
	aHcv = aHcv + 1;  // adds up number of incompatible (because of students in common) events in the same timeslot
	// the only hcv of this type affected when e is moved are the ones involving e
	//cout << "students in common " << aHcv <<" event " << timeslot_events[t][i] << endl;
      }
    }
  }
  // the suitable room hard constraint is taken care of by the assignroom routine
  return aHcv;
}

//evaluate the "only one class can be in each room at any timeslot" hcv for all the events in the timeslot of event e, 
//excluding the ones involving e that are already taken into account in eventHcv(e)
//int Solution::affectedRoomHcv(int e)
//{
//  int t = sln[e].first;
//  int roomHcv = 0;
//  for(int i= 0;  i < (int)timeslot_events[t].size(); i++){
//    if(i != e)
//      for(int j= i+1;  j < (int)timeslot_events[t].size(); j++){
//	if(j != e)
//	  if (sln[timeslot_events[t][i]].second == sln[timeslot_events[t][j]].second)
//	    roomHcv += 1;
//      }
//  }
//  return roomHcv;
//}

// evaluate all the "only one class can be in each room at any timeslot" hcv this time for all the events in timeslot t
int Solution::affectedRoomInTimeslotHcv(int t)
{
 int roomHcv = 0;
  for(int i= 0;  i < (int)timeslot_events[t].size(); i++){
    for(int j= i+1;  j < (int)timeslot_events[t].size(); j++){
	  if (sln[timeslot_events[t][i]].second == sln[timeslot_events[t][j]].second)
	    roomHcv += 1;
    }
  }
  return roomHcv;
}

// evaluate the number of soft constraint violation involving event e
int Solution::eventScv(int e)
{
  int eScv = 0;
  int t = sln[e].first;
  bool foundRow; 
  int singleClasses = data->studentNumber[e]; // count each student in the event to have a single class on that day
  int otherClasses = 0;

  if( t%9 == 8) // classes should not be in the last slot of the day
    eScv += data->studentNumber[e]; 

  for(int i = 0; i < data->n_of_students; i++){ 
    if(data->student_events[i][e] == 1){ // student should not have more than two classes in a row
      if( t%9 < 8){          // check timeslots before and after the timeslot of event e
	foundRow = false;
	for(int j = 0; j < (int)timeslot_events[t+1].size(); j++){
	  if( data->student_events[i][timeslot_events[t+1][j]] == 1){
	    if(t%9 < 7){
	      for(int k =0; k < (int)timeslot_events[t+2].size(); k++){
		if(data->student_events[i][timeslot_events[t+2][k]] == 1){
		  eScv += 1;
		  foundRow = true;
		  break;
		}
	      }
	    }
	    if(t%9 > 0){
	      for(int k =0; k < (int)timeslot_events[t-1].size(); k++){
		if( data->student_events[i][timeslot_events[t-1][k]] == 1){
		  eScv += 1;
		  foundRow = true;
		  break;
		}
	      }
	    }
	  }
	  if(foundRow)
	    break;
	}
      }    
      if(t%9 >1){
	foundRow = false;
	for(int j = 0; j < (int)timeslot_events[t-1].size(); j++){
	  for(int k =0; k < (int)timeslot_events[t-2].size(); k++){
	    if( data->student_events[i][timeslot_events[t-1][j]] == 1 && data->student_events[i][timeslot_events[t-2][k]] == 1){
	      eScv += 1;
	      foundRow = true;
	      break;
	    }
	  }
	  if(foundRow)
	    break;
	}
      }
     
      otherClasses = 0; // set other classes on the day to be zero for each student
      for(int s = t - (t%9); s < t-(t%9)+9; s++){ // students should not have a single class in a day
	if( s != t){
	  for(int j = 0; j < (int)timeslot_events[s].size(); j++){
	    if(data->student_events[i][timeslot_events[s][j]] == 1){
	      otherClasses += 1;
	      break;
	    }
	  }
	  if( otherClasses > 0){ // if the student has other classe on the day
	    singleClasses -= 1;  // do not count it in the number of student of event e having a single class on that day
	    break;
	  }
	}
      }
    }