easylocaltemplates.cpp

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

/**
   @file EasyLocalTemplates.cpp
   @brief Template implementation

   This file contains all the definition of the EasyLocal++
   template classes/functions.
   
   @author Andrea Schaerf ([e-mail]), 
           Luca Di Gaspero ([e-mail])
   @version 0.2
   @date 15 Jun 20.2
   @note This version works both with MS Visual C++ and the GNU C++ 
         compiler. Yet, it is extensively tested only with the GNU compiler.
 */


namespace easylocal {

  /** 
      Computes the distance between two values in the codomain of the
      cost function and returns it as a double precision value.

      @param x first value
      @param y second value
      @return the distance between x and y
  */
  inline double distance(fvalue x, fvalue y)
  {
    return x > y ? x-y : y-x;
  }

  // State Manager functions

  /**
     Looks for the best state out of a given number of sampled
     states.
     
     @param st the best state found
     @param samples the number of sampled states
   */
  template <class Input, class State>
  fvalue StateManager<Input,State>::SampleState(State &st, int samples)
  { 
    int s = 1;
    RandomState(st);
    fvalue cost = CostFunction(st);
    State best_state = st;
    fvalue best_cost = cost;
    while (s < samples)
      { 
	RandomState(st);
	cost = CostFunction(st);
	if (cost < best_cost)
	  { 
	    best_state = st;
	    best_cost = cost;
	  }
	s++;
      }
    st = best_state;
    return best_cost;
  }

  /** 
      Looks for the best state out of a given number of states
      which are obtained by random generation and are improved 
      running a local search algorithm upon them.
      
      @param st the best state found
      @param samples the number of sampled states
      @param r a pointer to a runner to be used to improve the sampled
  */
  template <class Input, class State>
  fvalue StateManager<Input,State>::ImprovedSampleState(State &st, int samples, Runner<Input,State>* r)
  { // same of SampleState, except that each sample is let run using r
    // before comparing its value
    int s = 1;
    RandomState(st);
    r->SetCurrentState(st);
    r->Go();
    st = r->GetCurrentState();
    fvalue cost = CostFunction(st);
    State best_state = st;
    fvalue best_cost = cost;
    do 
      { 
	cost = CostFunction(st);
	if (cost < best_cost)
	  { 
	    best_state = st;
	    best_cost = cost;
	  }
	RandomState(st);
	r->SetCurrentState(st);
	r->Go();
	st = r->GetCurrentState();
	s++;
      }
    while (s <= samples);
    st = best_state;
    return best_cost;
  }

  /** 
      Evaluates the cost function value in a given state.  
      The tentative definition computes a weighted sum of the violation 
      function and the objective function.
     
     @param st the state to be evaluated
     @return the value of the cost function in the given state */
  template <class Input, class State>
  fvalue StateManager<Input,State>::CostFunction(const State& st) const 
  { return HARD_WEIGHT * Violations(st) + Objective(st); } 

  /** 
      Outputs some informations about the state passed as parameter.

      @param st the state to be inspected
  */
  template <class Input, class State>
  void StateManager<Input,State>::PrintState(const State& st) const
  {
    std::cout << st << std::endl;
    std::cout << "Total cost : " << CostFunction(st) << std::endl;
    std::cout << "    Violations : " << Violations(st) << std::endl;
    std::cout << "    Objective : " << Objective(st) << std::endl;
  }

  /**
     A tentative definition of the violation function: 
     by default, it simply returns 0 and outputs a warning message.

     @param st the state to be evaluated
     @return the value of the violations function in the given state
  */
  template <class Input, class State>  
  fvalue StateManager<Input,State>::Violations(const State& st) const
  { 
    std::cout << "Warning: violations function not implemented yet!" << std::endl;
    return 0; 
  }

   /**
     A tentative definition of the objective function: 
     by default, it simply returns 0 and outputs a warning message.

     @param st the state to be evaluated
     @return the value of the violations function in the given state
  */
  template <class Input, class State>  
  fvalue StateManager<Input,State>::Objective(const State& st) const
  { 
    std::cout << "Warning: violations function not implemented yet!" << std::endl;
    return 0; 
  }
 
  /**
     Sets the internal input pointer to the new value passed as parameter.
     
     @param in the new input object
  */
  template <class Input, class State>  
  void StateManager<Input,State>::SetInput(Input* in) 
  { p_in = in; }

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

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

  /**
     Builds a state manager object linked to the provided input.

     @param in a pointer to an input object
  */
  template <class Input, class State>  
  StateManager<Input,State>::StateManager(Input* in) 
    : p_in(in)  
  {}

  // Output Manager functions


  /**
     Reads a state from an input stream.

     @param st the state to be read
     @param is the input stream
  */
  template <class Input, class Output, class State>
  void OutputManager<Input,Output,State>::ReadState(State &st, std::istream &is) const
  {
    Output out(p_in);
    is >> out;
    InputState(st,out);
  }

  /**
     Writes a state on an output stream.

     @param st the state to be written,
     @param os the output stream
  */
  template <class Input, class Output, class State>
  void OutputManager<Input,Output,State>::WriteState(const State &st, std::ostream &os) const
  {
    Output out(p_in);
    OutputState(st,out);  
    os << out;
  }

  /**
     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 OutputManager<Input,Output,State>::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 Output, class State>
  Input* OutputManager<Input,Output,State>::GetInput() 
  { return p_in; }
  
  /**
     Checks wether the object state is consistent with all the related
     objects.
  */
  template <class Input, class Output, class State>  
  void OutputManager<Input,Output,State>::Check() const
  { 
    assert(p_in != NULL && p_sm->GetInput() == p_in); 
  }

  // Prohibition Manager functions
  // up to now, the only actual prohibition manager is the tabu list manager

  /** 
      Constructs a tabu list manager object which manages a list of 
      the given tenure (i.e., the number of steps a move is considered tabu).
      
      @param min the minimum tabu tenure
      @param max the maximum tabu tenure
  */
  template <class Move>
  TabuListManager<Move>::TabuListManager(int min, int max)
    : min_tenure(min), max_tenure(max), iter(0)
  { }

  
  /**
     Inserts the move in the tabu list and updates the aspiration function.

     @param mv the move to add
     @param mv_cost the move cost
     @param best the best state cost found so far
  */
  template <class Move>
  void TabuListManager<Move>::InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best)
  { 
    InsertIntoList(mv); 
    UpdateAspirationFunction(mv_cost,curr,best); 
  }

  /**
     Checks whether the given move is prohibited.

     @param mv the move to check
     @param mv_cost the move cost
     @param curr the current state cost
     @param best the best state cost found so far
     @return true if the move mv is prohibited, false otherwise
  */
  template <class Move>
  bool TabuListManager<Move>::ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const
  { return ListMember(mv) && !Aspiration(mv,mv_cost,curr,best); }

  /** 
      Deletes all the elements of the tabu list.
  */
  template <class Move>
  void TabuListManager<Move>::Clean()
  { tlist.clear(); }

  /** 
      Checks whether the inverse of a given move belongs to the tabu list.
      
      @param mv the move to check
      @return true if the inverse of the move belongs to the tabu list, 
      false otherwise
  */
  template <class Move>
  bool TabuListManager<Move>::ListMember(const Move& mv) const
  {
    std::list<ListItem<Move> >::const_iterator p = tlist.begin();
    while (p != tlist.end())
      {
	if (Inverse(mv,p->elem))
	  return true;
	else
	  p++;
      }
    return false;
  }

  /** 
      Writes the current status of the tabu list on a output stream.
      
      @param os the output stream
      @param tl the tabu list manager to output
  */
  template <class Move>
  std::ostream& operator<<(std::ostream& os, const TabuListManager<Move>& tl)
  {
    std::list<ListItem<Move> >::const_iterator p = tl.tlist.begin();
    while (p != tl.tlist.end())
      {
	os << p->elem << " (" << p->out_iter - tl.iter << ")" << std::endl;
	p++;
      }
    return os;
  }

  /**
     Checks whether the aspiration criterion is satisfied for a given move.
     By default, it verifies if the move cost applied to the current state
     gives a value lower than the best state cost found so far.

     @param mv the move
     @param mv_cost the move cost
     @param curr the cost of the current state
     @param best the cost of the best state found so far
     @return true if the aspiration criterion is satisfied, false otherwise
  */
  template <class Move>
  bool TabuListManager<Move>::Aspiration(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const 
  { return curr + mv_cost < best; }

  /**
     Inserts the move into the tabu list, and update the list removing
     the moves for which the tenure has elapsed.

     @param mv the move to add
  */
  template <class Move>
  void TabuListManager<Move>::InsertIntoList(const Move& mv)
  {
    int tenure = Random(min_tenure,max_tenure);
    ListItem<Move> li(mv, iter+tenure);
    tlist.push_front(li);
	
    std::list<ListItem<Move> >::iterator p = tlist.begin();
    while (p != tlist.end())
      if (p->out_iter == iter)
	p = tlist.erase(p);
      else
	p++;
    iter++;
  }

  // Neighborhood explorer functions

  /**
     Constructs a neighborhood explorer passing a pointer to a state manager 
     and a pointer to the input.
     
     @param sm a pointer to a compatible state manager
     @param in a pointer to an input object
  */
  template <class Input, class State, class Move>  
  NeighborhoodExplorer<Input,State,Move>::NeighborhoodExplorer(StateManager<Input,State>* sm, Input* in) 
    :  p_sm(sm), p_in(in), p_pm(NULL)
  {}

  /**
     Constructs a neighborhood explorer which has a prohibition manager too.
     It accepts a pointer to a state manager, a pointer to the
     prohibition manager, and a pointer to the input.
     
     @param sm a pointer to a compatible state manager
     @param pm a pointer to a compatible prohibition manager
     @param in a pointer to an input object
  */
  template <class Input, class State, class Move>  
  NeighborhoodExplorer<Input,State,Move>::NeighborhoodExplorer(StateManager<Input,State>* sm, ProhibitionManager<Move>* pm, Input* in) 
    :  p_sm(sm), p_in(in), p_pm(pm)
  {}

  /**
     Evaluates the variation of the cost function obtainted by applying the
     move to the given state.