aco-acs.cpp

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

  vector<int>::iterator pos;
  for (int i=0; i < problem->n_of_events; i++){
    ordered_events.push_back(i);
  }
  for (pos = ordered_events.begin(); pos != ordered_events.end(); ++pos){
    stable_sort(ordered_events.begin(), ordered_events.end(), eventsort);
  }

  //  cout << "Ordered Events:";
  //  for (int i=0; i < problem->n_of_events; i++){
  //    cout << ordered_events[i] << " ";
  //  }
  //  cout << endl;

  // CREATE THE PHEROMONE MATRIX
  // double** pheromoneMatrix[timeslots][events]
  //
  pheromoneMatrix = DoubleMatrixAlloc(45, problem->n_of_events);
  totalMatrix = DoubleMatrixAlloc(45, problem->n_of_events);  

  // CREATE THE ANT COLONY
  //
  for(int i=0; i < COLONYSIZE; i++){
    colony.push_back(new Ant());
  }

  // CREATE SOLUTION FOR LOCAL SEARCH
  //
  Solution* perturbedSolution = new Solution(problem, rnd);


  // RUN A NUMBER OF TRIES, CONTROL TAKE CARE OF THAT
  //
  while( control.triesLeft()){

    control.beginTry();


    // ******************************
    // ** 1 ** INITIALIZATION PHASE
    // ******************************

    // - bestSolution
    //
    bestSolution = new Solution(problem, rnd);
    bestSolution->feasible = false;
    bestSolution->scv = INT_MAX;
    bestSolution->hcv = INT_MAX;

    // - pheromoneMatrix[45][n_of_events] = TAU0
    // - colony[COLONYSIZE] 
    //
    for (int i=0; i < 45; i++){
      for (int j=0; j < problem->n_of_events; j++){
	pheromoneMatrix[i][j] = TAU0;
      }
    }
    //    cout << "PHEROMONE MATRIX INITIALIZED" << endl;
    //    print_pheromoneMatrix();

    int iteration_counter = 0; 
    
    while (control.timeLeft()){
      
      iteration_counter++;

      for(int i=0; i < COLONYSIZE; i++){
	(colony[i]->current_event) = ordered_events[0];
	delete (colony[i]->currentSolution);
	(colony[i]->currentSolution) = new Solution(problem, rnd);
	for (int j=0; j < 45; j++){
	  for (int k=0; k < problem->n_of_students; k++){
	    colony[i]->student_eventsMatrix[j][k] = 0;
	  }
	}
	for (int j=0; j < 5; j++){
	  for (int k=0; k < problem->n_of_students; k++){
	    colony[i]->student_dayMatrix[j][k] = 0;
	  }
	}
      }
      
      // **********************************
      // ** 2 ** BUILDING SOLUTIONS PHASE
      // **********************************
      
      // Ants build the solution in parallel
      //

      for(int i=0; i < COLONYSIZE; i++){
	for(int step=0; step < problem->n_of_events; step++){

	  colony[i]->solutionStep(step);
	  
	  // Ants applies the local update rule
	  // tau[i][j] = ((1 - rho) * tau[i][j]) + (rho * delta_tau[i][j]))
	  // Simple ACS set delta_tau[i][j] = tau0
	  // Ant-Q set delta_tau[i][j] = (gamma * max(tau[k][l]))
	  // where tau[k][l] are the events still to insert in the solution
	  // 
#ifdef DEBUG
//	  cout << endl;
//	  cout << "Before Local Update Pheromone Matrix [" << (colony[i]->currentSolution)->sln[ordered_events[step]].first << "][" << ordered_events[step] << "]:" << pheromoneMatrix[(colony[i]->currentSolution)->sln[ordered_events[step]].first][ordered_events[step]] << endl;
#endif
	  pheromoneMatrix[(colony[i]->currentSolution)->sln[ordered_events[step]].first][ordered_events[step]] = (((1.0 - RHO) * pheromoneMatrix[(colony[i]->currentSolution)->sln[ordered_events[step]].first][ordered_events[step]]) + (RHO * TAU0));
#ifdef DEBUG
//	  cout << "After  Local Update Pheromone Matrix [" << ((colony[i]->currentSolution)->sln[ordered_events[step]]).first << "][" << ordered_events[step] << "]:" << pheromoneMatrix[(colony[i]->currentSolution)->sln[ordered_events[step]].first][ordered_events[step]] << endl;
//	  cout << endl;
#endif
	}
      }

#ifdef DEBUG
      //cout << "PHEROMONE MATRIX AFTER LOCAL UPDATE RULE" << endl;
      //      print_pheromoneMatrix();
#endif

      // Then a matching algorithm based on a deterministic network flow algorithm assigns rooms to events in each non-empty timeslot
      //
      for(int i=0; i< COLONYSIZE; i++){
	for (int j=0; j < 45; j++){
	  if((int)(colony[i]->currentSolution)->timeslot_events[j].size()){
	    (colony[i]->currentSolution)->assignRooms(j);
	  }
	} 
      }

#ifdef DEBUG
      for (int i=0; i < COLONYSIZE; i++){
	(colony[i]->currentSolution)->feasible = (colony[i]->currentSolution)->computeFeasibility();
	(colony[i]->currentSolution)->hcv = (colony[i]->currentSolution)->computeHcv();
	(colony[i]->currentSolution)->scv = (colony[i]->currentSolution)->computeScv(); 
	colony[i]->fitness = ((((colony[i]->currentSolution)->hcv) * 1000) + ((colony[i]->currentSolution)->scv));
	cout << "Before local search Ant:" << i << " has build a solution with hcv: " << (colony[i]->currentSolution)->hcv << " and scv:" << (colony[i]->currentSolution)->scv << " and a fitness of " << colony[i]->fitness << endl;
      }
#endif 

      // APPLY THE LOCAL SEARCH ROUTINE
      // Two phase strategy
      //
      if (iteration_counter < FPITER){
	mySteps = FPSTEPS;
      }
      else {
	mySteps = SPSTEPS;
      }
      for(int i=0; i < COLONYSIZE; i++){
	perturbedSolution->copy(colony[i]->currentSolution);
	perturbedSolution->localSearch(mySteps);
	colony[i]->currentSolution->copy(perturbedSolution);
      }


      // *******************************
      // ** 3 ** GLOBAL UPDATING PHASE
      // *******************************
      
      // Compute the quality of each solution
      //
      for (int i=0; i < COLONYSIZE; i++){
	(colony[i]->currentSolution)->feasible = (colony[i]->currentSolution)->computeFeasibility();
	(colony[i]->currentSolution)->hcv = (colony[i]->currentSolution)->computeHcv();
	(colony[i]->currentSolution)->scv = (colony[i]->currentSolution)->computeScv(); 
	colony[i]->fitness = ((((colony[i]->currentSolution)->hcv) * 1000) + ((colony[i]->currentSolution)->scv));
#ifdef DEBUG
	cout << "Ant:" << i << " has build a solution that has feasibility: " << (colony[i]->currentSolution)->feasible << " and a fitness of " << colony[i]->fitness << endl;
#endif
	// Compare each solution with bestSolution 
	// and if better update bestSolution
	//
	
	// BOTH UNFEASIBLE
	// CHECK HCV 
	//
	if (( (colony[i]->currentSolution)->feasible == false) &&  (bestSolution->feasible == false)){
	  if ( (colony[i]->currentSolution)->hcv < bestSolution->hcv ){
	    bestSolution->copy(colony[i]->currentSolution);
	    bestquality = colony[i]->currentSolution->hcv + colony[i]->currentSolution->scv;
	    bestfitness = colony[i]->fitness;
	  }
	}
	// NEW ONE FEASIBLE AND BEST UNFEASIBLE
	//
	else {
	  if(( (colony[i]->currentSolution)->feasible == true) && (bestSolution->feasible == false )){
	    bestSolution->copy(colony[i]->currentSolution);
	    bestquality = colony[i]->currentSolution->hcv + colony[i]->currentSolution->scv;
	    bestfitness = colony[i]->fitness;
	  }
	  // BOTH FEASIBLE
	  // CHECK SCV
	  //
	  else {
	    if(( (colony[i]->currentSolution)->feasible == true) && (bestSolution->feasible == true)){
	      if( (colony[i]->currentSolution)->scv < bestSolution->scv ){
		bestSolution->copy(colony[i]->currentSolution);
		bestquality = colony[i]->currentSolution->hcv + colony[i]->currentSolution->scv;
		bestfitness = colony[i]->fitness;
	      }
	    }
	  }
	}
      }

#ifdef DEBUG
      cout << "Iteration: " << iteration_counter << " feasibility: " << bestSolution->feasible << " fitness: " << bestfitness << endl;
#endif
      
      control.setCurrentCost(bestSolution);
      // UPDATE THE PHEROMONE MATRIX
      //
      for (int i=0; i < 45; i++){
	for (int j=0; j < problem->n_of_events; j++){
	  //#ifdef DEBUG
	  //	cout << "Before Global update Evaporation Pheromone Matrix [" << i << "][" << j << "]:" << pheromoneMatrix[i][j] << endl;
	  //#endif
	  pheromoneMatrix[i][j] = ((1.0 - ALPHA) * pheromoneMatrix[i][j]);
	  //#ifdef DEBUG
	  //	cout << "After  Global update Evaporation Pheromone Matrix [" << i << "][" << j << "]:" << pheromoneMatrix[i][j] << endl;
	  //#endif
	}
      }
      delta_tau = (FACTOR / ((1.0 + (double)bestquality)));
      for (int i=0; i < problem->n_of_events; i++){
#ifdef DEBUG
//	cout << "Before Global update Reinforcement Pheromone Matrix [" << bestSolution->sln[i].first << "][" << i << "]:" << pheromoneMatrix[bestSolution->sln[i].first][i] << endl;
#endif
	pheromoneMatrix[bestSolution->sln[i].first][i] =  (pheromoneMatrix[bestSolution->sln[i].first][i] + (ALPHA * delta_tau));
#ifdef DEBUG
//	cout << "After  Global update Reinforcement Pheromone Matrix [" << bestSolution->sln[i].first << "][" << i << "]:" << pheromoneMatrix[bestSolution->sln[i].first][i] << endl;
#endif
      }

#ifdef DEBUG
      //cout << "PHEROMONE MATRIX AFTER GLOBAL UPDATE RULE" << endl;
      //      print_pheromoneMatrix();
#endif

    }
    control.endTry(bestSolution);
    delete bestSolution;
  }
  delete problem;
  delete perturbedSolution;
  //  delete &control;
  //  delete rnd;
}