solution.cpp

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

  }
  eScv += singleClasses;

  return eScv;

}

// compute the number of single classes that event e "solves" in its timeslot
// obviously when the event is taken out of its timeslot this is also the number 
// of single classes introduced by the move in the day left by the event
int Solution::singleClassesScv(int e) 
{
  int t = sln[e].first;
  int classes, singleClasses = 0;
  for(int i = 0; i < data->n_of_students; i++){
    if(data->student_events[i][e] == 1){
      classes = 0;
      for(int s = t - (t%9); s < t - (t%9) + 9; s++){
	if(classes > 1)
	  break;
	if( s != t){ // we are in the feasible region so there are not events sharing students in the same timeslot
	  for(int j = 0; j < (int)timeslot_events[s].size(); j++){
	    if(data->student_events[i][timeslot_events[s][j]] == 1){
	      classes += 1;
	      break;
	    }
	  }
	}
      }
      // classes = 0 means that the student under consideration has a single class in the day (for event e) but that W
      // but we are not interested in that here (it is counted in eventScv(e)) 
      if(classes == 1) 
	singleClasses +=1;
    }
  }
  return singleClasses;
}

void Solution::Move1(int e, int t)
{
  //move event e to timeslot t
  int tslot =  sln[e].first;
  sln[e].first = t;
  vector<int>::iterator i;
  for(i = timeslot_events[tslot].begin(); i !=timeslot_events[tslot].end(); i++){
    if( *i == e)
      break;
  }
  timeslot_events[tslot].erase(i); // erase event e from the original timeslot
  timeslot_events[t].push_back(e); // and place it in timeslot t
  // reorder in label order events in timeslot t
  sort(timeslot_events[t].begin(),timeslot_events[t].end());
  // reassign rooms to events in timeslot t
  assignRooms(t);
  // do the same for the original timeslot of event e if it is not empty
  if((int)timeslot_events[tslot].size() > 0)
    assignRooms(tslot);
}

void Solution::Move2(int e1, int e2)
{
  //swap timeslots between event e1 and event e2
  int t = sln[e1].first;
  sln[e1].first = sln[e2].first;
  sln[e2].first = t;
  vector<int>::iterator i;
  for(i = timeslot_events[t].begin(); i !=timeslot_events[t].end(); i++){
    if( *i == e1)
      break;
  }
  timeslot_events[t].erase(i);
  timeslot_events[t].push_back(e2);
  for(i = timeslot_events[sln[e1].first].begin(); i !=timeslot_events[sln[e1].first].end(); i++){
    if( *i == e2)
      break;
  }
  timeslot_events[sln[e1].first].erase(i);
  timeslot_events[sln[e1].first].push_back(e1);

  sort(timeslot_events[t].begin(),timeslot_events[t].end());
  sort(timeslot_events[sln[e1].first].begin(),timeslot_events[sln[e1].first].end());

  assignRooms( sln[e1].first);
  assignRooms( sln[e2].first);
}

void Solution::Move3(int e1, int e2, int e3)
{
  // permute event e1, e2, and e3 in a 3-cycle
  int t = sln[e1].first;
  sln[e1].first = sln[e2].first;
  sln[e2].first = sln[e3].first;
  sln[e3].first = t;
  vector<int>::iterator i;
  for(i = timeslot_events[t].begin(); i !=timeslot_events[t].end(); i++){
    if( *i == e1)
      break;
  }
  timeslot_events[t].erase(i);
  timeslot_events[t].push_back(e3);
  for(i = timeslot_events[sln[e1].first].begin(); i !=timeslot_events[sln[e1].first].end(); i++){
    if( *i == e2)
      break;
  }
  timeslot_events[sln[e1].first].erase(i);
  timeslot_events[sln[e1].first].push_back(e1);
  for(i = timeslot_events[sln[e2].first].begin(); i !=timeslot_events[sln[e2].first].end(); i++){
    if( *i == e3)
      break;
  }
  timeslot_events[sln[e2].first].erase(i);
  timeslot_events[sln[e2].first].push_back(e2);

  sort(timeslot_events[sln[e1].first].begin(),timeslot_events[sln[e1].first].end());
  sort(timeslot_events[sln[e2].first].begin(),timeslot_events[sln[e2].first].end());
  sort(timeslot_events[sln[e3].first].begin(),timeslot_events[sln[e3].first].end());

  assignRooms( sln[e1].first);
  assignRooms( sln[e2].first);
  assignRooms( sln[e3].first);
}

void Solution::randomMove()
{
  //pick at random a type of move: 1, 2, or 3
  int moveType, e1;
  moveType = (int)(rg->next()*3) + 1;
  e1 = (int)(rg->next()*(data->n_of_events));
  if(moveType == 1){  // perform move of type 1
    int t = (int)(rg->next()*45);
    Move1( e1, t);
    //cout<< "event " << e1 << " in timeslot " << t << endl;
  }
  else if(moveType == 2){ // perform move of type 2
    int e2 = (int)(rg->next()*(data->n_of_events));
    while(e2 == e1) // take care of not swapping one event with itself
      e2 = (int)(rg->next()*(data->n_of_events));
    Move2( e1, e2);
    // cout << "e1 "<< e1 << " e2 " << e2 << endl; 
  }
  else{ // perform move of type 3
    int e2 = (int)(rg->next()*(data->n_of_events));
    while(e2 == e1)
      e2 = (int)(rg->next()*(data->n_of_events));
    int e3 = (int)(rg->next()*(data->n_of_events));
    while(e3 == e1 || e3 == e2) // take care of having three distinct events
      e3= (int)(rg->next()*(data->n_of_events));
    //cout<<"e1 " << e1 << " e2 " << e2 << " e3 " << e3<< endl;
    Move3( e1, e2, e3);
  }
}

void Solution::localSearch(int maxSteps, double LS_limit = 999999, double prob1 = 1.0, double prob2 = 1.0, double prob3 = 0.0)
{
  // perform local search with given time limit and probabilities for each type of move
  timer.resetTime(); // reset time counter for the local search
 
  int eventList[data->n_of_events]; // keep a list of events to go through
  for(int i = 0; i < data->n_of_events; i++)
    eventList[i] = i;
  for(int i = 0; i < data->n_of_events; i++){ // scramble the list of events to obtain a random order
    int j = (int)(rg->next()*data->n_of_events);      
    int h = eventList[i];
    eventList[i] = eventList[j];
    eventList[j] = h;
  }
  /*cout <<"event list" <<endl;
  for(int i = 0 ; i< data->n_of_events; i++)
    cout<< eventList[i] << " ";
    cout << endl;*/
 
  int neighbourAffectedHcv = 0; // partial evaluation of neighbour solution hcv
  int neighbourScv = 0; // partial evaluation of neighbour solution scv
  int evCount = 0;     // counter of events considered
  int stepCount = 0; // set step counter to zero
  int foundbetter = false;
  computeFeasibility();
  if(!feasible ){ // if the timetable is not feasible try to solve hcv
  for( int i = 0; evCount < data->n_of_events; i = (i+1)% data->n_of_events){
    if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps )
       break;
    int currentHcv = eventHcv(eventList[i]);
    if(currentHcv == 0 ){ // if the event on the list does not cause any hcv
      evCount++; // increase the counter
      continue; // go to the next event
    }
    // otherwise if the event in consideration caused hcv
    int currentAffectedHcv;
    int t_start = (int)(rg->next()*45); // try moves of type 1
    int t_orig = sln[eventList[i]].first;
    for(int h = 0, t = t_start; h < 45; t= (t+1)%45, h++){ 
      if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps)
	break;
      if(rg->next() < prob1){ // with given probability
	stepCount++;
	Solution *neighbourSolution = new Solution( data, rg );
	neighbourSolution->copy( this );
	//cout<< "event " << eventList[i] << " timeslot " << t << endl;
	neighbourSolution->Move1(eventList[i],t);
	neighbourAffectedHcv = neighbourSolution->eventAffectedHcv(eventList[i]) + neighbourSolution->affectedRoomInTimeslotHcv(t_orig);
	currentAffectedHcv = eventAffectedHcv(eventList[i]) + affectedRoomInTimeslotHcv(t);
	if( neighbourAffectedHcv < currentAffectedHcv){
	  //cout<<"current hcv " << computeHcv() << "neighbour " << neighbourSolution->computeHcv()<< endl;
	  copy( neighbourSolution );
	  delete neighbourSolution;
	  evCount = 0;
	  foundbetter = true;
	  break;
	}
	delete neighbourSolution;
       }
    }
    if(foundbetter){
      foundbetter = false;
      continue;
    }
    if(prob2 != 0){
    for(int j= (i+1)%data->n_of_events; j != i ;j = (j+1)%data->n_of_events){ // try moves of type 2
      if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps)
	break;
      if(rg->next() < prob2){ // with given probability
	stepCount++;
	Solution *neighbourSolution = new Solution( data, rg );
	neighbourSolution->copy( this );
	neighbourSolution->Move2(eventList[i],eventList[j]);
	//cout<< "event " << eventList[i] << " second event " << eventList[j] << endl;
	neighbourAffectedHcv = neighbourSolution->eventAffectedHcv(eventList[i])+neighbourSolution->eventAffectedHcv(eventList[j]);
	currentAffectedHcv = eventAffectedHcv(eventList[i]) + eventAffectedHcv(eventList[j]);
	if( neighbourAffectedHcv < currentAffectedHcv){
	  //cout<<"current hcv " << computeHcv() << "neighbour " << neighbourSolution->computeHcv()<< endl;
	  copy( neighbourSolution );
	  delete neighbourSolution;
	  evCount = 0;
	  foundbetter = true;
	  break;
	}
	delete neighbourSolution;
      }
    }
    if(foundbetter){
      foundbetter = false;
      continue;
    }
    }
    if(prob3 != 0){
    for(int j= (i+1)%data->n_of_events; j != i; j = (j+1)%data->n_of_events){ // try moves of type 3
      if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps)
	break;
      for(int k= (j+1)%data->n_of_events; k != i ; k = (k+1)%data->n_of_events){
	if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps)
	  break;
	if(rg->next() < prob3){ // with given probability
	stepCount++;
	currentAffectedHcv = eventAffectedHcv(eventList[i]) + eventAffectedHcv(eventList[j]) + eventAffectedHcv(eventList[k]);
	Solution *neighbourSolution = new Solution( data, rg );
	neighbourSolution->copy( this );
	neighbourSolution->Move3(eventList[i],eventList[j], eventList[k]); //try one of the to possible 3-cycle
	//cout<< "event " << eventList[i] << " second event " << eventList[j] << " third event "<< eventList[k] << endl;
	neighbourAffectedHcv = neighbourSolution->eventAffectedHcv(eventList[i])+ neighbourSolution->eventAffectedHcv(eventList[j]) 
	  + neighbourSolution->eventAffectedHcv(eventList[k]);
	if( neighbourAffectedHcv < currentAffectedHcv ){
	  copy( neighbourSolution );
	  delete neighbourSolution;
	  evCount = 0;
	  foundbetter = true;
	  break;
	} 
	delete neighbourSolution;
	}
	if(timer.elapsedTime(Timer::VIRTUAL) > LS_limit || stepCount > maxSteps)
	  break;
	if(rg->next() < prob3){  // with given probability
	stepCount++;
	currentAffectedHcv = eventAffectedHcv(eventList[i]) + eventAffectedHcv(eventList[k]) + eventAffectedHcv(eventList[j]);
	Solution *neighbourSolution = new Solution( data, rg );
	neighbourSolution->copy( this );
	neighbourSolution->Move3(eventList[i],eventList[k], eventList[j]); //try one of the to possible 3-cycle
	//cout<< "event " << eventList[i] << " second event " << eventList[j] << " third event "<< eventList[k] << endl;
	neighbourAffectedHcv = neighbourSolution->eventAffectedHcv(eventList[i])+ neighbourSolution->eventAffectedHcv(eventList[k]) 
	  + neighbourSolution->eventAffectedHcv(eventList[j]);
	if( neighbourAffectedHcv < currentAffectedHcv ){
	  copy( neighbourSolution );
	  delete neighbourSolution;
	  evCount = 0;
	  foundbetter = true;
	  break;
	} 
	delete neighbourSolution;
	}
      }
      if(foundbetter)