easylocal.h

一个tabu search算法框架

	@param st the state to modify
	@param mv the move to be applied
    */
    virtual void MakeMove(State &st, const Move& mv) = 0;
		
    // evaluation function
    virtual fvalue DeltaCostFunction(const State& st, const Move & mv);
		
    // debugging/statistic functions
    virtual void NeighborhoodStatistics(const State &st);
    void PrintMoveInfo(const State &st, const Move& mv, std::ostream& os = std::cout);
    
    /** Prompts for reading a move in the neighborhood of a given state
	from an input stream.
	
	@param st the start state
	@param mv the move read from the input stream
	@param is the input stream
    */
    virtual void InputMove(const State &st, Move& mv, std::istream& is = std::cin) const {}
				
    void SetInput(Input* in);
    Input* GetInput();
    void Check();
  protected:
    NeighborhoodExplorer(StateManager<Input,State>* sm, Input* in = NULL);
    NeighborhoodExplorer(StateManager<Input,State>* sm, ProhibitionManager<Move>* pm, Input* in = NULL);
		
    StateManager<Input,State>* p_sm; /**< A pointer to the attached 
					state manager. */
    Input* p_in; /**< A pointer to the input object. */
    virtual fvalue DeltaObjective(const State& st, const Move & mv);
    virtual fvalue DeltaViolations(const State& st, const Move & mv);
		
    
    Move best_move; /**< The best move found in the exploration of the
		         neighborhood (used from the neighborhood enumerating
			 functions such as BestMove). */

    Move start_move;  /**< The start move in the exploration of 
			 the neighborhood. */
    // the prohibition manager used with memory based strategies
    ProhibitionManager<Move>* p_pm; /**< A pointer to the attached
				       prohibition manager (used in case
				       of memory based strategy. */
  };

  /** @defgroup Parameters Parameter handling classes
      This group of classes handles a general parameter passing mechanism
      to runners.
      It is needed because in principle it is not possible to know neither 
      the number nor the type of paramerter a given runner need.
  */

  /** The type of values for the parameters of the runners.
      @ingroup Parameters
  */
  union ValueType {
    unsigned long natural; /**< The type for a natural value. */
    unsigned int short_natural; /**< The type for a small natural value. */
    double real; /**< The type for a real value. */
  };
		
  /** The parameter data class maintains the binding between name of the
      parameter, its type and its value.
      @ingroup Parameters
  */
  class ParameterData {
    std::string name;
    std::string type;
    ValueType value;
  public:
    ParameterData(std::string,std::string,ValueType);
    std::string Name() const;
    std::string Type() const;
    ValueType Value() const;  
  };
	
  /** A paramter box maintains a list of parameters that could be passed
      to a runner.
      @ingroup Parameters
  */
  class ParameterBox
  {
  public:
	void Put(std::string name, std::string type, ValueType value);
    void Put(std::string name, unsigned long value);
    void Put(std::string name, unsigned int value);
    void Put(std::string name, double value);
    void Get(std::string name, std::string type, ValueType& value) const;
    void Get(std::string name, unsigned long& value) const;
    void Get(std::string name, unsigned int& value) const;
    void Get(std::string name, double& value) const;
    void Clear();
  protected:
    std::list<ParameterData> parameters; /**< The list of parameters contained
					    in the parameter box. */
  };

  /** @defgroup Runners Runner classes
      Runner classes are the algorithmic core of the framework. They are 
      responsible for performing a run of a local search technique, 
      starting from an initial state and leading to a final one. 
  */

  /** This is the interface for an abstract runner. 
      Each runner has many data objects for representing the state of
      the search (current state, best state, current move, number of
      iterations, ...), and it maintain links to all the helpers,
      which are invoked for performing specific tasks on its own
      data. Example of actual runners are tabu search and 
      simulated annealing.  
      @ingroup Runners
  */
  template <class Input, class State>
  class Runner 
  {  
  public:
    /** Virtual destructor. */
    virtual ~Runner() {}
    Runner(std::string s = "Runner name", std::string t = "Runner type");
    /** Performs a full run of the search method. */
    virtual void Go() = 0;
    /** Performs a given number of steps of the search method.
	@param n the number of steps to make */	
    virtual void Step(unsigned int n) = 0;
    /** Outputs some informations about the runner on a given output stream
	(cout for default).
	@param os the output stream */
    virtual void Print(std::ostream& os = std::cout) const = 0;
    /** Sets the internal state of the runner to be equal to the parameter.
	@param st the state to become the new internal state */ 
    virtual void SetCurrentState(const State& st) = 0;
    /** Gets the internal state of the runner. 
	@return the current state of the runner */
    virtual State GetCurrentState() = 0;
    /** Gets the cost of the internal state of the runner.
	@return the cost of the current state of the runner */
    virtual fvalue CurrentStateCost() = 0; 
    /** Gets the best state found by the runner.
	@return the best state found by the runner */
    virtual State GetBestState() = 0;
    /** Gets the cost of the best state found by the runner.
	@return the cost of the best state found by the runner */
    virtual fvalue BestStateCost() = 0;
    /** Computes the cost of the current state. */
    virtual void ComputeCost() = 0;
    /** Checks whether the lower bound of the cost function has been
	reached.
	@return true if the lower bound of the cost function has reached,
	false otherwise */
    virtual bool LowerBoundReached() = 0;
    /** Gets the number of iterations performed by the runner.
	@return the number of iterations performed */
    virtual unsigned long NumberOfIterations() const = 0;
    /** Reads runner parameters from the standard input and it sets them. */
    virtual void ReadParameters() = 0;
    std::string Name();
    std::string Type();
    void SetName(std::string s);
    /** Sets the internal input pointer to the new value passed as parameter.
     	@param in the new input object  */
    virtual void SetInput(Input* in) = 0;
    /** Returns the input pointer which the object is attached to.
	@return the pointer to the input object */
    virtual Input* GetInput() = 0;
    /** Checks wether the object state is consistent with all the related
	objects. */
    virtual void Check() = 0;
    /** Sets the runner parameters, passed through a parameter box.
	@param pb the object containing the parameter setting 
	for the runner */
    virtual void SetParameters(const ParameterBox& pb) = 0;
  protected:
    std::string name, /**< The name of the runner. */
      type; /**< The type of the runner. */
  };

  /** A Move Runner is an instance of the Runner interface which it compel
      with a particular definition of @Move (given as template instantiation).
      It is at the root of the inheritance hierarchy of actual runners.
      @ingroup Runners
  */
  template <class Input, class State, class Move>
  class MoveRunner : public Runner<Input,State>
  {
  public:
    /** Virtual destructor. */
    virtual ~MoveRunner() {};
    void Go();
    void Step(unsigned int n);
    void SetCurrentState(const State& s);
    State GetCurrentState();
    fvalue CurrentStateCost();
    State GetBestState();
    fvalue BestStateCost();
    void ComputeCost(); 
    bool LowerBoundReached();
    unsigned long NumberOfIterations() const;
    unsigned long MaxIteration() const;
    void SetMaxIteration(unsigned long max);
    void SetInput(Input* in);
    Input* GetInput();
    void Print(std::ostream& os = std::cout) const;
    void SetParameters(const ParameterBox& pb);
    /** Sets the output stream which is used to write the plot of the
	cost function during a run.
	@param os the output stream to use (cerr for default).
    */
    void SetPlotStream(std::ostream* os = &std::cerr) 
    { pos = os; }
    void Check();
  protected:
    MoveRunner(StateManager<Input,State>* s, 
	       NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL, 
	       std::string name = "Runner name", std::string type = "Move Runner");
    virtual void InitializeRun();
    /** Actions to be performed at the end of the run. */
    virtual void TerminateRun() {};
    virtual void ComputeMoveCost(); 
    virtual void UpdateIterationCounter();
    bool MaxIterationExpired();
    /** Encodes the criterion used to stop the search. */
    virtual bool StopCriterion() = 0;
    /** Encodes the criterion used to select the move at each step. */
    virtual void SelectMove() = 0;
    virtual bool AcceptableMove();
    virtual void MakeMove();
    /** Stores the move and updates the related data. */
    virtual void StoreMove() {}
    virtual void UpdateStateCost();
		
    // input
    Input* p_in; /**< A pointer to the input object. */
		
    // helpers
    StateManager<Input,State>* p_sm; /**< A pointer to the attached 
					state manager. */
    NeighborhoodExplorer<Input,State,Move>* p_nhe; /**< A pointer to the 
						      attached neighborhood 
						      explorer. */
		
    // state data
    State current_state; /**< The current state object. */
    fvalue current_state_cost; /**< The cost of the current state. */
    bool current_state_set; /**< A flag that whether the current state is set.
			       It is so until a new input is given. */
    Move current_move;      /**< The currently selected move. */
    fvalue current_move_cost; /**< The cost of the selected move. */
		
    State best_state;         /**< The best state object. */
    fvalue best_state_cost;   /**< The cost of the best state. */
		
    unsigned long iteration_of_best; /**< The iteration when the best 
					state has found. */
    unsigned long max_idle_iteration; /**< The maximum number of iterations
					 allowed since the best state has
					 been found. */
		
    unsigned long number_of_iterations; /**< The overall number of iterations
					   performed. */
    unsigned long max_iteration;  /**< The overall maximum number 
				     of iterations allowed. */
		
    std::ostream* pos; /**< The output stream used for plotting. */
  };

   /** The Steepest Descent runner performs a simple local search.
      At each step of the search, the best move in the neighborhood of current
      solution is selected and performed.
      It is worth noticing that this algorithm leads straightly to the 
      nearest local minimum of a given state.
      @ingroup Runners
  */	
  template <class Input, class State, class Move>
  class SteepestDescent : public MoveRunner<Input,State,Move>
  {
  public:
    void Print(std::ostream& os = std::cout) const;
    void ReadParameters() {}
  protected: 
    SteepestDescent(StateManager<Input,State>* s, 
		    NeighborhoodExplorer<Input,State,Move>* ne, 
		    Input* in = NULL);
    void InitializeRun();
    void TerminateRun();
    bool StopCriterion();
    bool AcceptableMove();
    void SelectMove();
  };

  /** The Hill Climbing runner considers random move selection. A move
      is then performed only if it does improve or it leaves unchanged
      the value of the cost function.  
      @ingroup Runners 
  */
  template <class Input, class State, class Move>
  class HillClimbing : public MoveRunner<Input,State,Move>
  {public:
    void Print(std::ostream& os = std::cout) const;
    void ReadParameters();
  protected: 
    HillClimbing(StateManager<Input,State>* s, 
		 NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL);
    void InitializeRun();
    void TerminateRun();
    bool StopCriterion();
    bool AcceptableMove();
    void StoreMove();
    void SelectMove();
  };
  
  /** The Tabu Search runner explores a subset of the current
      neighborhood. Among the elements in it, the one that gives the
      minimum value of the cost function becomes the new current
      state, independently of the fact whether its value is less or
      greater than the current one.
      
      Such a choice allows the algorithm to escape from local minima,
      but creates the risk of cycling among a set of states.  In order to
      prevent cycling, the so-called tabu list is used, which
      determines the forbidden moves. This list stores the most recently
      accepted moves, and the inverses of the moves in the list are
      forbidden.  
      @ingroup Runners
  */
  template <class Input, class State, class Move>
  class TabuSearch : public MoveRunner<Input,State, Move>
  {public:
    void ReadParameters();
    void Print(std::ostream& os = std::cout) const;
    void SetInput(Input* in);
    void SetParameters(const ParameterBox& pb);
  protected:
    TabuSearch(StateManager<Input,State>* s, 
	       NeighborhoodExplorer<Input,State,Move>* ne,
	       TabuListManager<Move>* tlm, Input* in = NULL);
    void SetTabuListManager(TabuListManager<Move>* tlm,
			    int min_tabu = 0, int max_tabu = 0);
    void InitializeRun();
    bool StopCriterion();
    void SelectMove();
    bool AcceptableMove();
    void StoreMove();
    TabuListManager<Move>* p_pm; /**< A pointer to a tabu list manger. */
  };

  /** The Simulated annealing runner relies on a probabilistic local
      search technique whose name comes from the fact that it
      simulates the cooling of a collection of hot vibrating atoms.

      At each iteration a candidate move is generated at random, and
      it is always accepted if it is an improving move.  Instead, if
      the move is a worsening one, the new solution is accepted with
      time decreasing probability.

      @ingroup Runners
   */
  template <class Input, class State, class Move>
  class SimulatedAnnealing : public MoveRunner<Input,State,Move>
  {
  public:
    void ReadParameters();
    void SetParameters(const ParameterBox& pb);
    void Print(std::ostream& os = std::cout) const;
  protected: 
    SimulatedAnnealing(StateManager<Input,State>* s, 
		       NeighborhoodExplorer<Input,State,Move>* ne, Input* in = NULL);
    void InitializeRun();
    void TerminateRun();
    bool StopCriterion();
    void UpdateIterationCounter();
    void SelectMove();
    bool AcceptableMove();
  protected:
    double temperature; /**< The current temperature. */
    double start_temperature; /**< The starting temperature. */
    double min_temperature;   /**< The minimum temperature allowed before 
				 stopping the search. */