easylocaltemplates.cpp

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

     The tentative definition computes a weighted sum of the variation of 
     the violations function and of the difference in the objective function.

     @param st the start state
     @param mv the move
     @return the variation in the cost function
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::DeltaCostFunction(const State& st, const Move & mv)
  { return HARD_WEIGHT * DeltaViolations(st,mv) + DeltaObjective(st,mv); }

  /**
     Sets the prohibition manager to the value passed as input.
     
     @param pm a pointer to a prohibition manager
  */
  template <class Input, class State, class Move>  
  void NeighborhoodExplorer<Input,State,Move>::SetProhibitionManager(ProhibitionManager<Move>* pm) 
  { p_pm = pm; }


  /**
     Looks for the best move in the exploration of the neighborhood of a given 
     state. (i.e., the one that gives the best improvement in the cost 
     function).
     
     @param st the state
     @param mv the best move in the state st
     @return the cost of move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::BestMove(const State &st, Move& mv)
  {  
    FirstMove(st,mv); 
    fvalue mv_cost = DeltaCostFunction(st,mv);
    best_move = mv; 
    fvalue best_delta = mv_cost;
    do // look for the best move
      { 
	mv_cost = DeltaCostFunction(st,mv);
#ifdef COST_DEBUG
	std::cerr << mv << ' ' << mv_cost << std::endl;
#endif
	if (mv_cost < best_delta) 
	  { 
	    best_move = mv;
	    best_delta = mv_cost;
	  }
	NextMove(st,mv);
      }
    while (!LastMoveDone(mv));
    mv = best_move;
    return best_delta;
  }

  /**
     Outputs some statistics about the neighborhood of the given state.
     In detail it prints out the number of neighbors, the number of 
     improving/non-improving/worsening moves and their percentages.
     
     @param st the state to inspect
  */
  template <class Input, class State, class Move>  
  void NeighborhoodExplorer<Input,State,Move>::NeighborhoodStatistics(const State &st)
  {  
    unsigned int neighbors = 0, improving_neighbors = 0, 
      worsening_neighbors = 0, non_improving_neighbors = 0;
    Move mv;
    fvalue mv_cost;

    FirstMove(st,mv);
    do 
      { 	
	neighbors++;
        mv_cost = DeltaCostFunction(st,mv);
	if (mv_cost < 0)
	  improving_neighbors++;
	else if (mv_cost > 0)
	  worsening_neighbors++;
	else
	  non_improving_neighbors++;
	NextMove(st,mv);
      }
    while (!LastMoveDone(mv));
    std::cout << "Neighborhood size: " <<  neighbors << std::endl
	      << "   improving moves: " << improving_neighbors << " ("
	      << (100.0*improving_neighbors)/neighbors << "%%)" << std::endl
	      << "   worsening moves: " << worsening_neighbors << " ("
	      << (100.0*worsening_neighbors)/neighbors << "%%)" << std::endl
      	      << "   non-improving moves: " << non_improving_neighbors << " ("
	      << (100.0*non_improving_neighbors)/neighbors << "%%)" << std::endl;
  }

  /** 
      Generates the first move in the exploration of the neighborhood of a 
      given state. 
      By default, it invokes the RandomMove function and records mv as 
      start move.

      @param st the state
  */
  template <class Input, class State, class Move>
  void NeighborhoodExplorer<Input,State,Move>::FirstMove(const State& st, Move& mv) 
  { 
    RandomMove(st,mv); 
    start_move = mv;
  }

  /**
     Returns the best move found out of a number of sampled moves from a given
     state.
     
     @param st the state
     @param mv the best move found
     @param samples the number of sampled moves
     @return the cost of the move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::SampleMove(const State &st, Move& mv, int samples)
  {  
    int s = 1;
    RandomMove(st,mv);
    fvalue mv_cost = DeltaCostFunction(st,mv);
    best_move = mv;
    fvalue best_delta = mv_cost;
    do // look for the best sampled move
      { 
	mv_cost = DeltaCostFunction(st,mv);
	if (mv_cost < best_delta)
	  { 
	    best_move = mv;
	    best_delta = mv_cost;
	  }
	RandomMove(st,mv);
	s++;
      }
    while (s < samples);
    mv = best_move;
    return best_delta;
  }

  /** 
      Looks for the best move in a given state that is non prohibited.
      
      @param st the state
      @param mv the best non prohibited move in st
      @param curr the cost of the state st
      @param best the cost of the best state found so far
      @return the cost of the move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::BestNonProhibitedMove(const State &st, Move& mv, fvalue curr, fvalue best) 
  {
    register fvalue mv_cost;
    bool tabu_move;
    bool all_moves_tabu = true;
	
    FirstMove(st,mv); 
    mv_cost = DeltaCostFunction(st,mv);
    best_move = mv;
    fvalue best_delta = mv_cost;
    do  // look for the best non prohibited move 
      { // (if all moves are prohibited, then get the best)
	tabu_move = p_pm->ProhibitedMove(mv,mv_cost,curr,best);      
	if (   (mv_cost < best_delta && !tabu_move)
	       || (mv_cost < best_delta && all_moves_tabu)
	       || (all_moves_tabu && !tabu_move))
	  { 
	    best_move = mv;
	    best_delta = mv_cost;
	  }
	if (!tabu_move) 
	  all_moves_tabu = false;
	NextMove(st,mv);
	mv_cost = DeltaCostFunction(st,mv);
      }
    while (!LastMoveDone(mv));
    mv = best_move;
    return best_delta;
  } 

  
  /**
     Returns the best non prohibited move found out of a number of sampled 
     moves from a given state.
     
      @param st the state
      @param mv the best non prohibited move found
      @param samples the number of sampled moves
      @param curr the cost of the state st
      @param best the cost of the best state found so far
      @return the cost of the move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::SampleNonProhibitedMove(const State &st, Move& mv, int samples, fvalue curr, fvalue best)
  {  
    int s = 1;
    fvalue mv_cost;
    bool tabu_move;
    bool all_moves_tabu = true;
	
    RandomMove(st,mv);
    mv_cost = DeltaCostFunction(st,mv);
    best_move = mv;
    fvalue best_delta = mv_cost;
    do 
      { 
	tabu_move = p_pm->ProhibitedMove(mv,mv_cost,curr,best);      
	if (   (mv_cost < best_delta && !tabu_move)
	       || (mv_cost < best_delta && all_moves_tabu)
	       || (all_moves_tabu && !tabu_move))
	  { 
	    best_move = mv;
	    best_delta = mv_cost;
	  }
	if (!tabu_move) 
	  all_moves_tabu = false;
	RandomMove(st,mv);
	mv_cost = DeltaCostFunction(st,mv);
	s++;
      }
    while (s < samples);
    mv = best_move;
    return best_delta;
  }


  /**
     Outputs some informations about a move in a given state on a stream.

     @param st the state
     @param mv the move
     @param os an output stream
  */
  template <class Input, class State, class Move>  
  void NeighborhoodExplorer<Input,State,Move>::PrintMoveInfo(const State &st, const Move& mv, std::ostream& os)
  {
    os << "Move : " << mv << std::endl;
    os << "Start state cost : " << p_sm->CostFunction(st) << std::endl;
    os << "\tViolations : " << p_sm->Violations(st) << std::endl;
    os << "\tObjective  : " << p_sm->Objective(st) << std::endl;
	
    os << "Move cost : " << DeltaCostFunction(st,mv) << std::endl;
    os << "\tViolations : " << DeltaViolations(st,mv) << std::endl;
    os << "\tObjective  : " << DeltaObjective(st,mv) << std::endl;
	
    State st1 = st;
    MakeMove(st1,mv);
    os << "Final state cost : " << p_sm->CostFunction(st1) << std::endl;  
    os << "\tViolations : " << p_sm->Violations(st1) << std::endl;
    os << "\tObjective  : " << p_sm->Objective(st1) << std::endl;
	
    os << "Error : " << p_sm->CostFunction(st1) - DeltaCostFunction(st,mv) - p_sm->CostFunction(st) << std::endl;
  }

  /**
     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 NeighborhoodExplorer<Input,State,Move>::SetInput(Input* in) 
  { p_in = in; }

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

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

  /** 
      Evaluates the variation of the violations function obtained by 
      performing a move in a given state.
      The tentative definition simply makes the move and invokes the 
      companion StateManager method (Violations) on the initial and on the
      final state.
      
      @param st the state
      @param mv the move to evaluate
      @return the difference in the violations function induced by the move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::DeltaViolations(const State& st, const Move & mv)
  {
    State st1 = st;
    MakeMove(st1,mv);
    return p_sm->Violations(st1) - p_sm->Violations(st);
  }

  /**
     Evaluates the variation of the objective function obtained by performing
     a move in a given state.
     The tentative definition simply makes the move and invokes the 
      companion StateManager method (Objective) on the initial and on the
      final state.
      
      @param st the state
      @param mv the move to evaluate
      @return the difference in the objective function induced by the move mv
  */
  template <class Input, class State, class Move>  
  fvalue NeighborhoodExplorer<Input,State,Move>::DeltaObjective(const State& st, const Move & mv)
  {
    State st1 = st;
    MakeMove(st1,mv);
    return p_sm->Objective(st1) - p_sm->Objective(st);
  }

  /**
     Checks whether the whole neighborhood has been explored.
     The tentative definition verifies is the move passed as parameter 
     coincides with the start move.

     @param mv the move to check
     @return true if the whole neighborhood has been explored, false otherwise
  */
  template <class Input, class State, class Move>  
  bool NeighborhoodExplorer<Input,State,Move>::LastMoveDone(const Move &mv) 
  { return mv == start_move; } 

  // Runner functions

  /**
     Constructs a runner and associates a name and a type to it.

     @param s the name of the runner
     @param t the type of the runner (used for parameter setting)
  */
  template <class Input, class State>
  Runner<Input,State>::Runner(std::string s, std::string t)
    : name(s), type(t) 
  {}

  /** 
      Inspects the name of the runner.
      
      @return the name of the runner
  */
  template <class Input, class State>
  std::string Runner<Input,State>::Name() 
  { return name; }

  /** 
      Inspects the type of the runner.
      
      @return the type of the runner
  */
  template <class Input, class State>
  std::string Runner<Input,State>::Type()
  { return type; }

  /**
     Sets the name of the runner to the given parameter.
     
     @param s the name to give to the runner
  */
  template <class Input, class State>
  void Runner<Input,State>::SetName(std::string s) 
  { name = s; } 

  /**
     Creates a move runner and links it to a given state manager, neighborhood
     explorer and input objects. In addition, it sets its name and type to
     the given values.

     @param sm a pointer to a compatible state manager
     @param ne a pointer to a compatible neighborhood explorer
     @param in a pointer to the input object
     @param name the name of the runner
     @param type the type of the runner
  */
  template <class Input, class State, class Move>
  MoveRunner<Input,State,Move>::MoveRunner(StateManager<Input,State>* sm, NeighborhoodExplorer<Input,State,Move>* ne, Input* in, std::string name, std::string type)
    : Runner<Input,State>(name,type), p_in(in), p_sm(sm), p_nhe(ne)
  { 
    if (in != NULL)
      current_state.SetInput(in);
    number_of_iterations = 0;
    max_iteration = ULONG_MAX;
    current_state_set = false; 
  }

  /**
     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 MoveRunner<Input,State,Move>::SetInput(Input* in) 
  { 
    p_in = in; 
    current_state.SetInput(in);
    current_state_set = false;
    p_nhe->SetInput(in);
  }

  /**