solution.cpp

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

	break;   
    }  
    if(foundbetter){
      foundbetter = false;
      continue;
      } 
    }
    evCount++;
  }
  }
  computeFeasibility();
  if(feasible){ // if the timetable is feasible
    evCount = 0;
    int neighbourHcv;
    for( int i = 0; evCount < data->n_of_events; i = (i+1)% data->n_of_events){ //go through the events in the list
      if(stepCount > maxSteps || timer.elapsedTime(Timer::VIRTUAL) > LS_limit)
	break;
      int currentScv = eventScv(eventList[i]);
      //cout << "event " << eventList[i] << " cost " << currentScv<<endl;
      if(currentScv == 0 ){ // if there are no scv
	evCount++; // increase counter
	continue;  //go to the next event       
      }
      // otherwise try all the possible moves
      int t_start = (int)(rg->next()*45); // try moves of type 1
      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){ // each with given propability
	  stepCount++;
	  Solution *neighbourSolution = new Solution( data, rg );
	  neighbourSolution->copy( this );
	  neighbourSolution->Move1(eventList[i],t);
	  //cout<< "event " << eventList[i] << " timeslot " << t << endl;
	  neighbourHcv =  neighbourSolution->eventAffectedHcv(eventList[i]); //count possible hcv introduced by move
	  if(neighbourHcv == 0){ // consider the move only if no hcv are introduced
	    //cout<< "reintroduced hcv" << neighbourSolution->computeHcv()<< endl;
	    neighbourScv = neighbourSolution->eventScv(eventList[i])  // respectively Scv involving event e 
	      + singleClassesScv(eventList[i]) // + single classes introduced in day of original timeslot
	      - neighbourSolution->singleClassesScv(eventList[i]); // - single classes "solved" in new day
	    //cout<< "neighbour cost " << neighbourScv<<" " << neighbourHcv<< endl;
	    if( neighbourScv < currentScv){
	      //cout<<"current scv " << computeScv() << "neighbour " << neighbourSolution->computeScv()<< 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 the given probability
	  stepCount++;
	  Solution *neighbourSolution = new Solution( data, rg );
	  neighbourSolution->copy( this );
	  //cout<< "event " << eventList[i] << " second event " << eventList[j] << endl;
	  neighbourSolution->Move2(eventList[i],eventList[j]);
	  //count possible hcv introduced with the move
	  neighbourHcv = neighbourSolution->eventAffectedHcv(eventList[i]) + neighbourSolution->eventAffectedHcv(eventList[j]); 
	  if( neighbourHcv == 0){ // only if no hcv are introduced by the move
	    //cout<< "reintroduced hcv" << neighbourSolution->computeHcv()<< endl;
	    // compute alterations on scv for neighbour solution 
	    neighbourScv =  neighbourSolution->eventScv(eventList[i]) + singleClassesScv(eventList[i]) - neighbourSolution->singleClassesScv(eventList[i])
	      + neighbourSolution->eventScv(eventList[j]) + singleClassesScv(eventList[j]) - neighbourSolution->singleClassesScv(eventList[j]);
	    // cout<< "neighbour cost " << neighbourScv<<" " << neighbourHcv<< endl;
	    if( neighbourScv < currentScv + eventScv(eventList[j])){ // if scv are reduced
	      //cout<<"current scv " << computeScv() << "neighbour " << neighbourSolution->computeScv()<< endl;
	      copy( neighbourSolution ); // do the move
	      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 try one of the 2 possibles 3-cycles
	    stepCount++;
	    Solution *neighbourSolution = new Solution( data, rg );
	    neighbourSolution->copy( this );
	    neighbourSolution->Move3(eventList[i],eventList[j], eventList[k]);
	    // cout<< "event " << eventList[i] << " second event " << eventList[j] << " third event "<< eventList[k] << endl;
	    // compute the possible hcv introduced by the move
	    neighbourHcv = neighbourSolution->eventAffectedHcv(eventList[i]) + neighbourSolution->eventAffectedHcv(eventList[j]) 
	      + neighbourSolution->eventAffectedHcv(eventList[k]);
	    if(neighbourHcv == 0){ // consider the move only if hcv are not introduced 
	      // compute alterations on scv for neighbour solution 
	      neighbourScv = neighbourSolution->eventScv(eventList[i]) + singleClassesScv(eventList[i]) - neighbourSolution->singleClassesScv(eventList[i])
		+ neighbourSolution->eventScv(eventList[j]) + singleClassesScv(eventList[j]) - neighbourSolution->singleClassesScv(eventList[j])
		+ neighbourSolution->eventScv(eventList[k]) + singleClassesScv(eventList[k]) - neighbourSolution->singleClassesScv(eventList[k]);
	      // cout<< "neighbour cost " << neighbourScv<<" " << neighbourHcv<< endl;
	      if( neighbourScv < currentScv+eventScv(eventList[j])+eventScv(eventList[k])){
		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 the same probability try the other possible 3-cycle for the same 3 events
	    stepCount++;
	    Solution *neighbourSolution = new Solution( data, rg );
	    neighbourSolution->copy( this );
	    neighbourSolution->Move3(eventList[i],eventList[k], eventList[j]);
	    // cout<< "event " << eventList[i] << " second event " << eventList[k] << " third event "<< eventList[j] << endl;
	    // compute the possible hcv introduced by the move
	    neighbourHcv = neighbourSolution->eventAffectedHcv(eventList[i]) + neighbourSolution->eventAffectedHcv(eventList[k]) 
	      + neighbourSolution->eventAffectedHcv(eventList[j]);
	    if(neighbourHcv == 0){ // consider the move only if hcv are not introduced 
	      // compute alterations on scv for neighbour solution 
	      neighbourScv = neighbourSolution->eventScv(eventList[i]) + singleClassesScv(eventList[i]) - neighbourSolution->singleClassesScv(eventList[i])
		+ neighbourSolution->eventScv(eventList[k]) + singleClassesScv(eventList[k]) - neighbourSolution->singleClassesScv(eventList[k])
		+ neighbourSolution->eventScv(eventList[j]) + singleClassesScv(eventList[j]) - neighbourSolution->singleClassesScv(eventList[j]);
	      // cout<< "neighbour cost " << neighbourScv<<" " << neighbourHcv<< endl;
	      if( neighbourScv < currentScv+eventScv(eventList[k])+eventScv(eventList[j])){
		copy( neighbourSolution );
		delete neighbourSolution;
		evCount = 0;
		foundbetter = true;
		break;
	      }
	    }
	    delete neighbourSolution;
	  }   
	}
	if(foundbetter)
	  break;  
      }
      if(foundbetter){
	  foundbetter = false;
	  continue;
      }
      }
      evCount++;
    }
  }
}

// assign rooms to events in timeslot t
void Solution::assignRooms(int t)
{
  val.clear();
  dad.clear();
  vector<int> assigned; // vector keeping track for each event if it is assigned or not
  int lessBusy= 0; // room occupied by the fewest events
  int busy[data->n_of_rooms]; // number of events in a room
  int N = (int)timeslot_events[t].size(); 
  int V = N+2+data->n_of_rooms;
  // initialize the bipartite graph
  size = IntMatrixAlloc(V+1,V+1);
  flow = IntMatrixAlloc(V+1,V+1);
  for (int i = 0; i <= V; i++) {
    for (int j = 0; j <= V; j++) { 
      size[i][j] = 0;
      flow[i][j] = 0;
    }
  }
  for(int i =0; i < N; i++){ 
    size[1][i+2] = 1; 
    size[i+2][1] = -1;
    for(int j = 0; j < data->n_of_rooms; j++)
      if(data->possibleRooms[timeslot_events[t][i]][j] == 1){   
	size[i+2][N+j+2] = 1; 
	size[N+j+2][i+2] = -1;
	size[N+j+2][V] = 1;
	size[V][N+j+2] = -1;
	}
    }
  maxMatching(V); // apply the matching algorithm  
  for(int i =0; i < N; i++){ // check if there are unplaced events
    assigned.push_back(0);
    for(int j = 0; j < data->n_of_rooms; j++){
      if(flow[i+2][N+j+2] == 1){
	sln[timeslot_events[t][i]].second = j;
	// cout << "room " << j << endl;
	assigned[i] = 1;
	busy[j] =+ 1;
      }
    }
  }
  for(int i = 0; i < N; i++){ // place the unplaced events in the less busy possible rooms
    if(assigned[i] == 0){
      for(int j = 0; j < data->n_of_rooms; j++){
	if(data->possibleRooms[timeslot_events[t][i]][j] == 1){
	  lessBusy = j;
	  break;
	}
      }
      for(int j = 0; j < data->n_of_rooms; j++){
	if(data->possibleRooms[timeslot_events[t][i]][j] == 1){
	  if(busy[j] < busy[lessBusy])
	    lessBusy = j;
	}
      }
      sln[timeslot_events[t][i]].second = lessBusy;
    }
  }
  free(size); // don't forget to free the memory
  free(flow);
}

// maximum matching algorithm
void Solution::maxMatching(int V)
{
  
  while(networkFlow(V)){  
    int x = dad[V];
    int y = V;
    while( x != 0){
      flow[x][y] = flow[x][y] + val[V];
      flow[y][x] = - flow[x][y];
      y = x; 
      x = dad[y];
    }
  }
}

//network flow algorithm
bool Solution::networkFlow(int V)
{
  int k,t,min=0;
  int priority = 0;
  val.clear();
  dad.clear();
  for( k = 1; k <= V+1; k++){
    val.push_back( -10); // 10 unseen value
    dad.push_back( 0);
  }
  val[0] = -11;  //sentinel
  val[1] = -9; // the source node
  for( k = 1; k != 0; k = min, min = 0){
    val[k] = 10+val[k];
    //cout << "val" << k << val[k] << endl;
    if(val[k] == 0)
      return false;
    if( k == V)
      return true;
    for(t = 1; t <= V; t++){  
      //cout<< " valt" << t << " = " << val[t]<< endl;   
      if(val[t] < 0){
	//cout << "flow" << k << t << "= "<< flow[k][t]<< endl; 
	priority = - flow[k][t];
	if( size[k][t] > 0) 
	  priority += size[k][t];
	if(priority > val[k]) 
	  priority = val[k];
	priority = 10 - priority;
	if(size[k][t] && val[t] < - priority){  // forse qui dovrei spezzare l'if in due cosi' che non calcolo le priority quando non le uso...
	  val[t] = -priority;
	  dad[t] = k;
	}
	if(val[t] > val[min])
	  min = t;
      }
    }
  }
  return false;
}