easylocaltemplates.cpp

来自「一个tabu search算法框架」· C++ 代码 · 共 2,039 行 · 第 1/5 页

  { current_move_cost = p_nhe->BestMove(current_state,current_move); }

  /**
     Invokes the companion superclass method, and initializes the move cost
     at a negative value for fulfilling the stop criterion the first time
  */     
  template <class Input, class State, class Move>
  void SteepestDescent<Input,State,Move>::InitializeRun()
  { 
    MoveRunner<Input,State,Move>::InitializeRun(); 
    current_move_cost = -1; // needed for passing the first time 
                            // the StopCriterion test
  }

  /**
     The search is stopped when no (strictly) improving move has been found.
  */
  template <class Input, class State, class Move>
  bool SteepestDescent<Input,State,Move>::StopCriterion()
  { return current_move_cost >= 0; }

  /**
     A move is accepted if it is an improving one.
  */
  template <class Input, class State, class Move>
  bool SteepestDescent<Input,State,Move>::AcceptableMove()
  { return current_move_cost < 0; }

    /**
     At the end of the run, the best state found is set with the last visited
     state (it is always a local minimum).
  */
  template <class Input, class State, class Move>
  void SteepestDescent<Input,State,Move>::TerminateRun()
  { 
    best_state = current_state;
    best_state_cost = current_state_cost;
  }
  
  /**
     Outputs some steepest descent statistics on a given output stream.

     @param os the output stream
  */
  template <class Input, class State, class Move>
  void SteepestDescent<Input,State,Move>::Print(std::ostream & os) const
  {  
    MoveRunner<Input,State,Move>::Print(os);
    os << "PATAMETERS: " << std::endl;
    os << "  Max iteration : " << max_iteration << std::endl;
    os << "RESULTS : " << std::endl;
    os << "  Number of iterations : " << number_of_iterations << std::endl;
    os << "  Current state [cost: " 
       << current_state_cost << "] " << std::endl;
    os << current_state << std::endl;
    os << std::endl;
  }

  // Tabu Search
  
  /**
     Constructs a tabu search runner by linking it to a state manager, 
     a neighborhood explorer, a tabu list manager, and an input object.

     @param s a pointer to a compatible state manager
     @param ne a pointer to a compatible neighborhood explorer
     @param tlm a pointer to a compatible tabu list manager
     @param in a poiter to an input object
  */
  template <class Input, class State, class Move>
  TabuSearch<Input,State,Move>::TabuSearch(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, TabuListManager<Move>* tlm, Input* in)
    : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Tabu Search")
  { 
    if (in != NULL)
      best_state.SetInput(in);
	
    SetTabuListManager(tlm); 
    p_pm = tlm;
    p_nhe->SetProhibitionManager(p_pm);
  }

  /**
     Sets the internal input pointer to the new value passed as parameter.
     
     @param in the new input.
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::SetInput(Input* in) 
  { 
    MoveRunner<Input,State,Move>::SetInput(in);
    best_state.SetInput(in); 
  }

  /**
     Reads the tabu search parameters from the standard input.
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::ReadParameters()
  {
    int min_tabu, max_tabu;
    std::cout << "TABU SEARCH -- INPUT PARAMETERS" << std::endl;
    std::cout << "Length of the tabu list (min,max): ";
    std::cin >> min_tabu >> max_tabu;
    p_pm->SetLength(min_tabu,max_tabu);
    std::cout << "Number of idle iterations: ";
    std::cin >> max_idle_iteration;
  }

  /**
     Sets the tabu list manager according to the one passed as parameter.
     
     @param tlm a pointer to a compatible tabu list manager
     @param min_tabu the minimum tabu tenure for a move
     @param max_tabu the maximum tabu tenure for a move
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::SetTabuListManager(TabuListManager<Move>* tlm, int min_tabu, int max_tabu)
  { 
    p_pm = tlm;
    if (max_tabu != 0) // if min_tabu and max_tabu are properly set
      p_pm->SetLength(min_tabu,max_tabu);
    p_nhe->SetProhibitionManager(p_pm);
  }


  /**
     Initializes the run by invoking the companion superclass method, and
     cleans the tabu list.
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::InitializeRun()
  {
    MoveRunner<Input,State,Move>::InitializeRun(); 
    assert(max_idle_iteration > 0);
    p_pm->Clean();
  }

  /** 
      Selects always the best move that is non prohibited by the tabu list 
      mechanism.
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::SelectMove() 
  { current_move_cost = p_nhe->BestNonProhibitedMove(current_state, current_move, current_state_cost, best_state_cost); }

  /**
     The stop criterion is based on the number of iterations elapsed from
     the last strict improvement of the best state cost.
  */
  template <class Input, class State, class Move>  
  bool TabuSearch<Input,State,Move>::StopCriterion()
  { return number_of_iterations - iteration_of_best >= max_idle_iteration; }

  /** 
      In tabu search the selected move is always accepted.
      That is, the acceptability test is replaced by the 
      prohibition mechanism which is managed inside the selection.
  */
  template <class Input, class State, class Move>  
  bool TabuSearch<Input,State,Move>::AcceptableMove() { return true; }

  
  /**
     Sets the tabu search parameters, passed through a parameter box.

     @param pb the object containing the parameter setting for the algorithm
  */
  template <class Input, class State, class Move>  
  void TabuSearch<Input,State,Move>::SetParameters(const ParameterBox& pb)
  {
    unsigned int min_tabu, max_tabu;
    MoveRunner<Input,State,Move>::SetParameters(pb);
    pb.Get("min tenure", min_tabu);
    pb.Get("max tenure", max_tabu);
    p_pm->SetLength(min_tabu,max_tabu);
  }

  /**
     Stores the move by inserting it in the tabu list, if the state obtained
     is better than the one found so far also the best state is updated.
  */
  template <class Input, class State, class Move>  
  void TabuSearch<Input,State,Move>::StoreMove()
  {
    p_pm->InsertMove(current_move, current_move_cost, current_state_cost, best_state_cost);
    if (current_state_cost + EPS < best_state_cost)
      { 
	iteration_of_best = number_of_iterations;
	best_state = current_state;
	best_state_cost = current_state_cost;
      }
  }

  /**
     Outputs some tabu search statistics on a given output stream.

     @param os the output stream
  */
  template <class Input, class State, class Move>
  void TabuSearch<Input,State,Move>::Print(std::ostream & os) const
  {  
    MoveRunner<Input,State,Move>::Print(os);
    os << "PATAMETERS: " << std::endl;
    os << "  Max idle iteration : " << max_idle_iteration << std::endl;
    os << "  Max iteration : " << max_iteration << std::endl;
    os << "  Tenure : " << p_pm->MinTenure() << '-' << p_pm->MaxTenure() << std::endl;
    os << "RESULTS : " << std::endl;
    os << "  Number of iterations : " << number_of_iterations << std::endl;
    os << "  Iteration of best : " << iteration_of_best << std::endl;
    os << "  Current state [cost: " 
       << current_state_cost << "] " << std::endl
       << current_state << std::endl;
    os << "  Best State    [cost: " 
       << best_state_cost << "] " << std::endl
       << best_state << std::endl << std::endl;
    os << "Tabu list : " << std::endl;
    os << *p_pm; 
    os << std::endl << std::endl;
  }

  // Simulated Annealing

  /**
     Constructs a simulated annealing runner by linking it to a state manager, 
     a neighborhood explorer, and an input object.

     @param s a pointer to a compatible state manager
     @param ne a pointer to a compatible neighborhood explorer
     @param in a poiter to an input object
  */
  template <class Input, class State, class Move>
  SimulatedAnnealing<Input,State,Move>::SimulatedAnnealing(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
    : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Simulated Annealing")
  { 
    min_temperature = 0.0001;
  }

  /**
     Reads the simulated annealing parameters from the standard input.
  */  
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::ReadParameters()
  {
    std::cout << "SIMULATED ANNEALING -- INPUT PARAMETERS" << std::endl;
    std::cout << "Start temperature: ";
    std::cin >> start_temperature;
    std::cout << "Cooling rate: ";
    std::cin >> cooling_rate;
    std::cout << "Neighbors sampled at each temperature : ";
    std::cin >> neighbor_sample;
  }

  /**
     Initializes the run by invoking the companion superclass method, and
     setting the temperature to the start value.
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::InitializeRun()
  {
    MoveRunner<Input,State,Move>::InitializeRun(); 
    assert(start_temperature > 0 && cooling_rate > 0 && neighbor_sample > 0);
    temperature = start_temperature;
  }

  /**
     Stores the current state as best state (it is obviously a local minimum).
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::TerminateRun()
  { 
    best_state = current_state;
    best_state_cost = current_state_cost;
  }

  /**
     A move is randomly picked.
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::SelectMove() 
  { 
    p_nhe->RandomMove(current_state, current_move); 
    ComputeMoveCost(); 
  }

  /**
     Sets the simulated annealing  parameters, passed through a parameter box.

     @param pb the object containing the parameter setting for the algorithm
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::SetParameters(const ParameterBox& pb)
  {
    pb.Get("start temperature", start_temperature);
    pb.Get("cooling rate", cooling_rate);
    pb.Get("neighbors sampled", neighbor_sample);
    pb.Get("max iteration", max_iteration);
  }

  /**
     Outputs some simulated annealing statistics on a given output stream.

     @param os the output stream
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::Print(std::ostream & os) const
  {
    MoveRunner<Input,State,Move>::Print(os);
    os << "PATAMETERS: " << std::endl;
    os << "  Start temperature : " << start_temperature << std::endl;
    os << "  Cooling rate : " << cooling_rate << std::endl;
    os << "  Neighbor sample : " << neighbor_sample << std::endl;
    os << "  Max iteration : " << max_iteration << std::endl;
    os << "RESULTS : " << std::endl;
    os << "  Number of iterations : " << number_of_iterations << std::endl;
    os << "  Current state [cost: " 
       << current_state_cost << "] " << std::endl
       << current_state << std::endl;
  }

  /**
     The search stops when a low temperature has reached.
   */
  template <class Input, class State, class Move>
  bool SimulatedAnnealing<Input,State,Move>::StopCriterion()
  { return temperature <= min_temperature; }

  /**
     At regular steps, the temperature is decreased 
     multiplying it by a cooling rate.
  */
  template <class Input, class State, class Move>
  void SimulatedAnnealing<Input,State,Move>::UpdateIterationCounter() 
  { number_of_iterations++; 
  if (number_of_iterations % neighbor_sample == 0)
    temperature *= cooling_rate;
  }

  /** A move is surely accepted if it improves the cost function
      or with exponentially decreasing probability if it is 
      a worsening one.
  */
  template <class Input, class State, class Move>
  bool SimulatedAnnealing<Input,State,Move>::AcceptableMove()
  { return (current_move_cost <= 0)
      || (((float)rand())/RAND_MAX < exp(-current_move_cost/temperature)); }

  /**
     Sets the internal input pointer to the new value passed as parameter.
     
     @param in a pointer to the new input object
  */
  template <class Input, class Output>
  void Solver<Input,Output>::SetInput(Input* in) 
  { p_in = in; }

  /**
     Sets the internal output pointer to the new value passed as parameter.
     
     @param out a pointer to the new output object
  */
  template <class Input, class Output>
  void Solver<Input,Output>::SetOutput(Output* out) 
  { p_out = out; }

  /** 
      Constructs a solver by providing it an input and an output objects.

      @param in a pointer to an input object
      @param out a pointer to an output object
  */
  template <class Input, class Output>
  Solver<Input,Output>::Solver(Input* in, Output* out)
    : p_in(in), p_out(out) 
  {}

  /**
     Returns the input pointer which the object is attached to.
     
     @return the pointer to the input
  */
  template <class Input, class Output>
  Input* Solver<Input,Output>::GetInput()
  { return p_in; }

  /**
     Returns the output pointer which the object is attached to.
     
     @return the pointer to the output
  */
  template <class Input, class Output>
  Output* Solver<Input,Output>::GetOutput()
  { return p_out; }

  /**
     Set the number of states which should be tried in 
     the initialization phase.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::SetInitTrials(int t) 
  { number_of_init_trials = t; }

  /**
     Sets the internal input pointer to the new value passed as parameter.
     
     @param in the new input.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::SetInput(Input* in)