easylocaltemplates.cpp

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

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

  /**
     Outputs the name of the runner on a given output stream.

     @param os the output stream
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::Print(std::ostream& os) const
  { os << name << " : " << type << std::endl; }

  /**
     Checks wether the object state is consistent with all the related
     objects.
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::Check() 
  { 
    assert(p_in != NULL);
    assert(p_in == p_sm->GetInput());  
    assert(p_in == p_nhe->GetInput());
  }


  /**
     Sets the internal state of the runner to the value passed as parameter.

     @param s the state to become the current state of the runner
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::SetCurrentState(const State& s) 
  { 
    current_state = s; 
    current_state_set = true; 
    current_state_cost = p_sm->CostFunction(current_state); 
  }

  /**
     Retrieves the internal state of the runner.
     
     @return the current state of the runner
  */
  template <class Input, class State, class Move>
  State MoveRunner<Input,State,Move>::GetCurrentState() 
  { return current_state; }

  /**
     Returns the cost of the internal state.

     @return the cost of the current state
  */
  template <class Input, class State, class Move>
  fvalue MoveRunner<Input,State,Move>::CurrentStateCost() 
  { return current_state_cost; }

  /**
     Returns the best state found so far by the runner.
     
     @return the best state found
  */
  template <class Input, class State, class Move>
  State MoveRunner<Input,State,Move>::GetBestState() 
  { return best_state; }

  /** 
      Returns the cost of the best state found so far by the runner.

      @return the cost of the best state found
  */
  template <class Input, class State, class Move>
  fvalue MoveRunner<Input,State,Move>::BestStateCost() 
  { return best_state_cost; }

  /** 
      Computes explicitely the cost of the current state (used 
      at the beginning of a run for consistency purpose).
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::ComputeCost()  
  { current_state_cost = p_sm->CostFunction(current_state); }

  /**
     Checks whether the lower bound of the cost function has been reached.
     The tentative definition verifies whether the current state cost is
     equal to zero.
  */
  template <class Input, class State, class Move>
  bool MoveRunner<Input,State,Move>::LowerBoundReached() 
  { return current_state_cost == 0; }

  /**
     Returns the number of iterations elapsed.

     @return the number of iterations performed by the runner
  */
  template <class Input, class State, class Move>
  unsigned long MoveRunner<Input,State,Move>::NumberOfIterations() const 
  { return number_of_iterations; }

  /**
     Returns the maximum value of iterations allowed for the runner.

     @return the maximum value of iterations allowed
  */
  template <class Input, class State, class Move>
  unsigned long MoveRunner<Input,State,Move>::MaxIteration() const 
  { return max_iteration; }

  /**
     Sets a bound on the maximum number of iterations allowed for the runner.
     
     @param max the maximum number of iterations allowed */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::SetMaxIteration(unsigned long max)  
  { max_iteration = max; }

  /**
     Sets the runner 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 MoveRunner<Input,State,Move>::SetParameters(const ParameterBox& pb)
  {   
    pb.Get("max idle iteration",max_idle_iteration);
    pb.Get("max iteration", max_iteration);
  }

  /**
     Performs a full run of a local search method.
   */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::Go()
  { 
    assert(current_state_set);
    InitializeRun();
    while (!MaxIterationExpired() && !StopCriterion() && !LowerBoundReached())
      { 
	UpdateIterationCounter();
	SelectMove();
#ifdef TRACE_MOVES
	Print(); std::cerr << "press any key ... "; std::cin.get();
#endif
	if (AcceptableMove())
	  { 
	    MakeMove();
	    UpdateStateCost();
	    StoreMove();
	  }
      }
    TerminateRun();
  }

  /**
     Actually performs the move selected by the local search strategy.
   */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::MakeMove() 
  { 
#ifdef TRACE_MOVES
    p_nhe->PrintMoveInfo(current_state,current_move,std::cerr);
#endif
#ifdef COST_DEBUG
    fvalue ocost = current_state_cost;
    State previous_state = current_state;
#endif
    p_nhe->MakeMove(current_state,current_move); 
#ifdef COST_DEBUG
    fvalue ncost = p_sm->CostFunction(current_state);
    if (distance(ncost,(ocost+current_move_cost)) > EPS)
      {
	std::cerr << "Error in computing delta_cost: " 
		  << ncost-(ocost+current_move_cost) << std::endl;
	std::cerr << "Current iteration : " << number_of_iterations << std::endl;
	std::cerr << "Previous state : " << std::endl;
	std::cerr << previous_state << std::endl;
	std::cerr << "Current state : " << std::endl;
	std::cerr << current_state << std::endl;
	p_nhe->PrintMoveInfo(previous_state,current_move,std::cerr);
	char s[3];
	std::cout << "Press enter to continue...";
	std::cin.getline(s,3);
      }
#endif
#ifdef PLOT_DATA
    assert(pos); // the plot output stream must be set
    *pos << number_of_iterations << "\t" << current_state_cost << std::endl;
#endif
  }

  /**
     Performs a given number of steps of the local search strategy.

     @param n the number of steps
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::Step(unsigned int n)
  { 
    assert(current_state_set);
    for (unsigned int i = 0; i < n; i++) 
      { 
	UpdateIterationCounter();
	SelectMove();
	if (AcceptableMove())
	  { MakeMove();
	  UpdateStateCost();
	  StoreMove();
	  if (LowerBoundReached())
	    break;
	  }
      }
  }

  /**
     Computes the cost of the selected move; it delegates this task to the
     neighborhood explorer.
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::ComputeMoveCost() 
  { current_move_cost = p_nhe->DeltaCostFunction(current_state,current_move); }

  /**
     Updates the counter that tracks the number of iterations elapsed.
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::UpdateIterationCounter() 
  { number_of_iterations++; }

  /**
     Verifies whether the upper bound on the number of iterations
     allowed for the strategy has been reached.

     @return true if the maximum number of iteration has been reached, false
     otherwise
  */
  template <class Input, class State, class Move>
  bool MoveRunner<Input,State,Move>::MaxIterationExpired() 
  { return number_of_iterations > max_iteration; }

  /** 
      Checks whether the selected move can be performed.
      Its tentative definition simply returns true
  */
  template <class Input, class State, class Move>
  bool MoveRunner<Input,State,Move>::AcceptableMove() 
  { return true; }

  /**
     Updates the cost of the internal state of the runner.
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::UpdateStateCost() 
  { current_state_cost += current_move_cost; }

  /**
     Initializes all the runner variable for starting a new run.
  */
  template <class Input, class State, class Move>
  void MoveRunner<Input,State,Move>::InitializeRun()
  {
    number_of_iterations = 0;
    iteration_of_best = 0;
    ComputeCost();
    best_state = current_state;
    best_state_cost = current_state_cost;
  }

  // Actual Runners


  // Hill Climbing
  

  /**
     Constructs a hill climbing 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>
  HillClimbing<Input,State,Move>::HillClimbing(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
    : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Hill Climbing")
  { 
    //  max_idle_iteration = 0; 
  }

  /**
     Reads the hill climbing parameters from the standard input.
  */
  template <class Input, class State, class Move>   
  void HillClimbing<Input,State,Move>::ReadParameters() 
  { 
    std::cout << "HILL CLIMBING -- INPUT PARAMETERS" << std::endl;
    std::cout << "Number of idle iterations: ";
    std::cin >> max_idle_iteration;
  }
  
  /**
     The select move strategy for the hill climbing simply looks for a
     random move.
  */
  template <class Input, class State, class Move>   
  void HillClimbing<Input,State,Move>::SelectMove() 
  { 
    p_nhe->RandomMove(current_state,current_move); 
    ComputeMoveCost();
  }

  /**
     The hill climbing initialization simply invokes 
     the superclass companion method.
  */
  template <class Input, class State, class Move>
  void HillClimbing<Input,State,Move>::InitializeRun()
  { 
    MoveRunner<Input,State,Move>::InitializeRun(); 
    assert(max_idle_iteration > 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 HillClimbing<Input,State,Move>::TerminateRun()
  { 
    best_state = current_state;
    best_state_cost = current_state_cost;
  }

  /**
     The stop criterion for the hill climbing strategy is based on the number
     of iterations elapsed from the last strict improving move performed.
  */
  template <class Input, class State, class Move>
  bool HillClimbing<Input,State,Move>::StopCriterion()
  { return number_of_iterations - iteration_of_best >= max_idle_iteration; }

  /**
     A move is accepted if it is non worsening (i.e., it improves the cost
     or leaves it unchanged).
  */
  template <class Input, class State, class Move>
  bool HillClimbing<Input,State,Move>::AcceptableMove()
  { return current_move_cost <= 0; }

  /**
     The store move for hill climbing simply updates the variable that
     keeps track of the last improvement.
  */
  template <class Input, class State, class Move>
  void HillClimbing<Input,State,Move>::StoreMove()
  { 
    if (current_move_cost < -EPS)
      {
	iteration_of_best = number_of_iterations;
      }
  }

  /**
     Outputs some hill climbing statistics on a given output stream.

     @param os the output stream
  */
  template <class Input, class State, class Move>
  void HillClimbing<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 << "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;
    os << current_state << std::endl;
    os << std::endl;
  }

  // Steepest Descent

  /**
     Constructs a steepest descent 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>
  SteepestDescent<Input,State,Move>::SteepestDescent(StateManager<Input,State>* s, NeighborhoodExplorer<Input,State,Move>* ne, Input* in)
    : MoveRunner<Input,State,Move>(s, ne, in, "Runner name", "Steepest Descent")
  {}

  /**
     Selects always the best move in the neighborhood.
  */
  template <class Input, class State, class Move>   
  void SteepestDescent<Input,State,Move>::SelectMove()