control.cpp

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

#include "Control.h"

Control::Control( int argc, char** argv ) {
  
  // parse the command line options to set all vars
  
  if( ( argc % 2 == 0 ) || ( argc == 1 ) ) {
    cerr << "Parse error: Number of command line parameters incorrect\n";
    cerr << "Usage:" << endl;
    cerr << argv[ 0 ] << " -i InputFile [-o OutputFile] [-n NumberOfTries] [-s RandomSeed] [-t TimeLimit] [-p ProblemType] [-tau0 TAU0] [-alpha ALPHA] [-beta BETA] [-gamma GAMMA] [-rho RHO] [-q0 Q0] [-colonysize COLONYSIZE] [-factor FACTOR] [-fpiter FPITER] [-fpsteps FPSTEPS] [-spsteps SPSTEPS]" << endl;
    exit(1);
  }
  
  for( int i = 1; i < argc / 2 + 1; i++ ) {
    parameters[ argv[ i * 2 - 1 ] ] = argv[ i * 2 ];
  }
  
  nrTry = 0;
  
  // check for input parameter
  
  if( parameterExists( "-i") ) {
    is = new ifstream( getStringParameter( "-i" ).c_str() );
  } else {
    cerr << "Error: No input file given, exiting" << endl;
    cerr << "Usage:" << endl;
    cerr << argv[ 0 ] << " -i InputFile [-o OutputFile] [-n NumberOfTries] [-s RandomSeed] [-t TimeLimit] [-p ProblemType] [-tau0 TAU0] [-alpha ALPHA] [-beta BETA] [-gamma GAMMA] [-rho RHO] [-q0 Q0] [-colonysize COLONYSIZE] [-factor FACTOR] [-fpiter FPITER] [-fpsteps FPSTEPS] [-spsteps SPSTEPS]" << endl;
    exit(1);
  }
  
  // check for ouput parameter
  
  if( parameterExists( "-o" ) ) {
    os = new ofstream( getStringParameter( "-o" ).c_str() );
  } else {
    cerr << "Warning: No output file given, writing to stdout" << endl;
    os = &cout;
  }
  
  // check for number of tries parameter
  
  if( parameterExists( "-n" ) ) {
    maxTry = getIntParameter( "-n" );
    cout << "Max number of tries " << maxTry << endl;
  } else {
    cerr << "Warning: Number of tries is set to default (10)" << endl;
    maxTry = 10; // default number of tries
  }
  
  // check for time limit parameter
  
  if( parameterExists( "-t" ) ) {
    timeLimit = getDoubleParameter( "-t" );
    cout <<"Time limit " << timeLimit << endl;
  } else {
    cerr << "Warning: Time limit is set to default (90 sec)" << endl;
    timeLimit = 90; // default time limit
  }
  
  // check for problem instance type parameter for the local search
  
  if( parameterExists( "-p" ) ) {
    problemType = getIntParameter( "-p" );
    cout <<"Problem instance type " << problemType << endl;
  } else {
    //cerr << "Warning: The problem instance type is set by default to 1 (easy)" << endl;
    problemType = 1; // default problem type
  }
  
  
  // check for maximum steps parameter for the local search
  
  if( parameterExists( "-m" ) ) {
    maxSteps = getIntParameter( "-m" );
    cout <<"Max number of steps in the local search " << maxSteps << endl;
  } else {
    //cerr << "Warning: The maximum number of steps for the local search is set by default to 100" << endl;
    maxSteps = 100; // default max steps
  }
  
  // check for time limit parameter for the local search
  
  if( parameterExists( "-l" ) ) {
    LS_limit = getDoubleParameter( "-l" );
    cout <<"Local search time limit " << LS_limit << endl;
  } else {
    cerr << "Warning: The local search time limit is set to default (99999 sec)" << endl;
    LS_limit = 99999; // default local search time limit
  }
  
  // check for probability parameter for each move in the local search
  
  if( parameterExists( "-p1" ) ) {
    prob1 = getDoubleParameter( "-p1" );
    cout << "LS move 1 probability " << prob1 <<endl;
  } else {
    cerr << "Warning: The local search move 1 probability is set to default 1.0" << endl;
    prob1 = 1.0; // default local search probability for each move of type 1 to be performed
  }
  
  if( parameterExists( "-p2" ) ) {
    prob2 = getDoubleParameter( "-p2" );
    cout <<"LS move 2 probability " << prob2 << endl;
  } else {
    cerr << "Warning: The local search move 2 probability is set to default 1.0" << endl;
    prob2 = 1.0; // default local search probability for each move to be performed
  }
  
  if( parameterExists( "-p3" ) ) {
    prob3 = getDoubleParameter( "-p3" );
    cout <<"LS move 3 probability " << prob3 <<  endl;
  } else {
    cerr << "Warning: The local search move 3 probability is set to default 0.0" << endl;
    prob3 = 0.0; // default local search probability for each move to be performed
  }
  
  // check for random seed
  
  if( parameterExists( "-s" ) ) {
    seed = getIntParameter( "-s" );
    srand( seed );
  } else {
    seed = time( NULL );
    cerr << "Warning: " << seed << " used as default random seed" << endl;
    srand( seed );
  }
  // EXTRA CODE ADDED TO CONTROL FOR PARSING COMMAND LINE
  //
  //
  if( parameterExists( "-tau0" ) ) {
    TAU0 = getDoubleParameter( "-tau0" );
    cout <<"TAU0 pheromone value " << TAU0 <<  endl;
    }
  //  else {
  //    TAU0 = 0.5;
  //    cerr << "Warning:" << TAU0 << " used as default TAU0 pheromone parameter" << endl;
  //  }
  if( parameterExists( "-alpha" ) ) {
    ALPHA = getDoubleParameter( "-alpha" );
    cout << "ALPHA global update value " << ALPHA << endl;
  }
  //  else {
  //    ALPHA = 0.1;
  //    cerr << "Warning:" << ALPHA << " used as default ALPHA global update parameter" << endl;
  //  }
  if( parameterExists( "-beta" ) ) {
    BETA = getDoubleParameter( "-beta" );
    cout <<"BETA heuristic value " << BETA <<  endl;
  }
  //  else {
  //    BETA = 3.0;
  //    cerr << "Warning:" << BETA << " used as default BETA heuristic parameter" << endl;
  //  }
  if( parameterExists( "-gamma" ) ) {
    GAMMA = getDoubleParameter( "-gamma" );
    cout <<"GAMMA heuristic value " << GAMMA <<  endl;
  }
  //  else {
  //    GAMMA = 2.0;
  //    cerr << "Warning:" << GAMMA << " used as default GAMMA heuristic parameter" << endl;
  //  }
  if( parameterExists( "-rho" ) ) {
    RHO = getDoubleParameter( "-rho" );
    cout <<"RHO evaporation value " << RHO <<  endl;
  } 
  //  else {
  //    RHO = 0.1;
  //      cerr << "Warning:" << RHO << " used as default RHO evaporation parameter" << endl;
  //  }
  if( parameterExists( "-q0" ) ) {
    Q0 = getDoubleParameter( "-q0" );
    cout <<"Q0 exploration probability value " << Q0 <<  endl;
  } 
  //  else {
  //    Q0 = 0.0;
  //    cerr << "Warning:" << Q0 << " used as default QO exploration probability parameter" << endl;
  //  }
  if( parameterExists( "-colonysize" ) ) {
    COLONYSIZE = getIntParameter( "-colonysize" );
    cout <<"COLONYSIZE value " << COLONYSIZE <<  endl;
  } 
  //  else {
  //    COLONYSIZE = 15;
  //    cerr << "Warning:" << COLONYSIZE << " used as default COLONYSIZE parameter" << endl;
  //  }
  if( parameterExists( "-factor" ) ) {
    FACTOR = getDoubleParameter( "-factor" );
    cout <<"FACTOR pheromone update value " << FACTOR <<  endl;
  } 
  //  else {
  //    FACTOR = 100000.0;
  //    cerr << "Warning:" << FACTOR << " used as default FACTOR pheromone global update parameter" << endl;
  //  }
  if( parameterExists( "-fpiter" ) ) {
    FPITER = getIntParameter( "-fpiter" );
    cout <<"FPITER local search value " << FPITER <<  endl;
  } 
  //  else {
  //    FPITER = 1;
  //    cerr << "Warning:" << FPITER << " used as default FPITER first phase number of iterations parameter" << endl;
  //  }
  if( parameterExists( "-fpsteps" ) ) {
    FPSTEPS = getIntParameter( "-fpsteps" );
    cout <<"FPSTEPS local search value " << FPSTEPS <<  endl;
  } 
  //  else {
  //    FPSTEPS = 5000;
  //    cerr << "Warning:" << FPSTEPS << " used as default FPSTEPS first phase number of steps in local search parameter" << endl;
  //  }
  if( parameterExists( "-spsteps" ) ) {
    SPSTEPS = getIntParameter( "-spsteps" );
    cout <<"SPSTEPS local search value " << SPSTEPS <<  endl;
  } 
  //  else {
  //    SPSTEPS = 2000;
  //    cerr << "Warning:" << SPSTEPS << " used as default SPSTEPS second phase number of steps in local search parameter" << endl;
  //  }
  
}

Control::~Control() {
}

bool
Control::parameterExists( string paramName ) {
	for( map< string, string >::iterator i = parameters.begin(); i != parameters.end(); i++ ) {
		if( i-> first == paramName )
			return true;
	}
	return false;
}

int
Control::getIntParameter( string paramName ) {
	if( parameterExists( paramName ) )
		return atoi( parameters[paramName].c_str() );
	else {
		return 0;
	}
}

double
Control::getDoubleParameter( string paramName ) {
	if( parameterExists( paramName ) )
		return atof( parameters[paramName].c_str() );
	else {
		return 0;
	}
}

string
Control::getStringParameter( string paramName ) {
	if( parameterExists( paramName ) )
		return parameters[paramName];
	else {
		return 0;
	}
}

void
Control::resetTime() {
	timer.resetTime();
}

double
Control::getTime() {
	return timer.elapsedTime( Timer::VIRTUAL );
}

void
Control::beginTry() {
	srand( seed++ );
	(*os) << "begin try " << ++nrTry << endl;
	resetTime();
	feasible = false;
	bestScv = INT_MAX;
	bestEvaluation = INT_MAX;
}

void
Control::endTry( Solution *bestSolution) {
  (*os) << "begin solution " << nrTry << endl;
  if(bestSolution->feasible){
    (*os) << "feasible: evaluation function = " << bestSolution->scv <<endl;
    for(int i = 0; i < (*bestSolution).data->n_of_events; i++)
      (*os) << bestSolution->sln[i].first << " " ;
    (*os) << endl;
    for(int i = 0; i < (*bestSolution).data->n_of_events; i++)
      (*os) << bestSolution->sln[i].second << " " ;
    (*os) << endl;
  }
  else{
    (*os) << "unfeasible: evaluation function = " << (bestSolution->computeHcv() * 1000000) + bestSolution->computeScv() <<endl;
  }
  (*os) << "end solution " << nrTry << endl;
  (*os) << "end try " << nrTry << endl;

  // The following output might be used if the ./checksln program wants to be used to check the validity of solutions.
  // Remember that the output file has then to have the .sln extension and has to have the same name as the .tim instance file
  /*for(int i = 0; i < (*bestSolution).data->n_of_events; i++){
    (*os) << bestSolution->sln[i].first << " "<< bestSolution->sln[i].second;
    (*os) << endl;
    }*/
}

void
Control::setCurrentCost(Solution *currentSolution ) {
  //if( timeLeft() ) {
	  int currentScv = currentSolution->scv;
	  if( currentSolution->feasible && currentScv < bestScv ) {
	    bestScv = currentScv;
	    bestEvaluation = currentScv;
	    double time = getTime();
	    (*os) << "best " << bestScv << " time ";
			os->flags( ios::fixed );
			(*os) << ( time < 0 ? 0.0 : time ) << endl;
	  }
	  else if(!currentSolution->feasible){ 
	    int currentEvaluation = (currentSolution->computeHcv() * 1000000) + currentSolution->computeScv();
	    if(currentEvaluation < bestEvaluation){
	      bestEvaluation = currentEvaluation;
	      double time = getTime();
	    (*os) << "best " << bestEvaluation << " time ";
			os->flags( ios::fixed );
			(*os) << ( time < 0 ? 0.0 : time ) << endl;
	    }
	  }
	  //}
}