easylocal.h

一个tabu search算法框架

    double cooling_rate;  /**< The cooling rate of the temperature 
			     (temperature = temperature * cooling_rate 
			     at regular intervals). */
    unsigned int neighbor_sample; /**< The Number of moves tested 
				     at each temperature. */
  };
	
  /** @defgroup Solvers Solver classes
      Solver classes control the search by generating the initial solutions, 
      and deciding how, and in which sequence,
      runners have to be activated (e.g. tandem, multistart, hybrid
      search). In addition, they communicate with the external
      environment, by getting the input and delivering the output. They
      are linked to one or more runners (for simple or composite
      search, respectively) and to some of the helpers.  
  */
	
  /** An Abstract Solver is an abstract interface for the Solver concept.
      It simply defines the signature for them, independently of the
      problem definition classes.
      @ingroup Solvers
  */
  class AbstractSolver
  {
  public:
    /** Virtual destructor. */
    virtual ~AbstractSolver() {}
    /** Performs a full solving procedure by finding an initial state, 
     running the attached runner and delivering the output. */    
    virtual void Solve() = 0;
    /** Start again a solving procedure, running the attached runner from
	the current internal state. */
    virtual void ReSolve() = 0;
    /** Tries multiple runs on different initial states and records the
	best one.
	@param n the number of trials  */
    virtual void MultiStartSolve(unsigned int n) = 0;
  };
  
  /** A Solver represents the external layer of EasyLocal++; it
      implements the Abstract Solver interface and furthermore is
      parametrized with the Input and Output of the problem.  @ingroup
      Solvers 
  */
  template <class Input, class Output>
  class Solver : public AbstractSolver
  {
  public:
    virtual void Solve() = 0;
    virtual void SetInput(Input* in);
    Input* GetInput();
    Output* GetOutput();
    void SetOutput(Output* out);
  protected:
    Solver(Input* in = NULL, Output* out = NULL);
    /** Updates the output by translating the best state found by the
	solver to an output object. */
    virtual void DeliverOutput() = 0;
    Input* p_in; /**< A pointer to the input object. */
    Output* p_out; /**< A pointer to the output object. */
  };
	
  /** A Local Search Solver has an internal state, and defines the ways for
      dealing with a local search algorithm.
      @ingroup Solvers
  */
  template <class Input, class Output, class State>
  class LocalSearchSolver : public Solver<Input, Output>
  {public:
    void SetInitTrials(int t);
    void Solve();
    /** Uses the final state of previous (Re)Solve execution as 
	the initial one
	This is useful for running on a set of continuously changing 
	instances. */
    virtual void ReSolve();
    virtual void MultiStartSolve(unsigned int n);
    void SetInput(Input* in);
    virtual void Check();
    fvalue InternalStateCost();
  protected:
    LocalSearchSolver(StateManager<Input,State>* sm, 
		      OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL);
    /**
       Lets all the managed runners Go, and then it collects the best state
       found.
    */
    virtual void Run() = 0; 
    /** Returns the number of iterations performed in the search. */
    virtual unsigned long NumberOfIterations() const = 0;
    void DeliverOutput();
    virtual void FindInitialState();
    void ComputeCost();
    StateManager<Input,State>* p_sm; /**< A pointer to the attached 
					state manager. */
    OutputManager<Input,Output,State>* p_om; /**< A pointer to the attached
						output manager. */
    fvalue internal_state_cost;  /**< The cost of the internal state. */
    State internal_state;        /**< The internal state of the solver. */
    unsigned int number_of_init_trials; /**< Number of different initial 
					   states tested for a run. */
  };
	
  /** The Simple Local Search solver handles a simple local search algorithm
      encapsulated in a runner.
      @ingroup Solvers
  */
  template <class Input, class Output, class State>
  class SimpleLocalSearch : public LocalSearchSolver<Input,Output,State>
  {
  public:
    void SetRunner(Runner<Input,State> *r);
  protected:
    SimpleLocalSearch(StateManager<Input,State>* sm, 
		      OutputManager<Input,Output,State>* om,
		      Runner<Input,State>* r, Input* in = NULL, Output* out = NULL);
    SimpleLocalSearch(StateManager<Input,State>* sm, 
		      OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL);
    void Run(); 
    unsigned long NumberOfIterations() const;
    Runner<Input,State>* p_runner; /**< A pointer to the managed runner. */				   
  };
	
	
  /** A Multi Runner solver handles a set of runners.
      @ingroup Solvers
  */
  template <class Input, class Output, class State>
  class MultiRunnerSolver : public LocalSearchSolver<Input,Output,State>
  {
  public:
    void ClearRunners();
    void AddRunner(Runner<Input,State> *r);
    void SetRunner(Runner<Input,State> *r, unsigned int i);		
  protected:
    MultiRunnerSolver(StateManager<Input,State>* sm, 
		      OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL);
    unsigned long NumberOfIterations() const;
    unsigned long total_iterations; /**< The overall number of iterations
				       performed by all the managed 
				       runners. */
    unsigned int start_runner;      /**< The index of the runner to
				       start with. */
    std::vector<Runner<Input,State>* > runners; /**< The vector of
						   the linked runners. */
  };
	
  /** A Comparative Solver applies different runners to the same instances
      (and the same initial solutions).
      @ingroup Solvers
  */
  template <class Input, class Output, class State>
  class ComparativeSolver : public MultiRunnerSolver<Input,Output,State>
  {
  protected:
    /** Constructs a comparative solver by providing it links to
     a state manager, an output manager, an input, and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param in a pointer to an input object
     @param out a pointer to an output object
    */
    ComparativeSolver(StateManager<Input,State>* sm, 
		      OutputManager<Input,Output,State>* om, 
		      Input* in = NULL, Output* out = NULL) 
      : MultiRunnerSolver<Input,Output,State>(sm,om,in,out) {}
    void Run();  
    State start_state; /**< The start state is equal for each runner used
			  and is kept in this variable. */
  };
	
  /** The Token-ring Solver alternates n runners for a number of
      rounds.   
      @ingroup Solvers
  */
  template <class Input, class Output, class State>
  class TokenRingSolver : public MultiRunnerSolver<Input,Output,State>
  {public:
    void SetRounds(unsigned int r);
    void SetStartRunner(unsigned int sr);
    void Check();
    void Print(std::ostream& os = std::cout) const;
  protected:
    TokenRingSolver(StateManager<Input,State>* sm, 
		    OutputManager<Input,Output,State>* om, Input* in = NULL, Output* out = NULL); 
    // Run all runners circularly on the same thread
    void Run();
    int max_idle_rounds; /**< Maximum number of runs without improvement 
			     allowed. */
    //    unsigned int start_runner;
  };
	
  /** @defgroup Testers Tester classes
      Tester classes represent a simple predefined interface of the user
      program. They help the user in debugging the code, adjusting the
      techniques, and tuning the parameters.  Testers also allow the
      user to instruct the system to perform massive batch
      experiments, and collect the results in aggregated form.  
  */

  /** The Abstract Move Tester is an interface for a tester that handles
      moves.
      @ingroup Testers
  */	
  template <class Input, class Output, class State>
  class AbstractMoveTester 
  {
  public:
    AbstractMoveTester(std::string s);
    /** Virtual destructor. */
    virtual ~AbstractMoveTester() {}
    std::string Name();
    /** The method shall execute the test menu on a given state 
	@param st the state
     */
    virtual void RunTestMenu(State& st) = 0;
    /** The method shall set the input of the linked objects according
	to the parameter.
	@param in a pointer to the input object
    */
    virtual void SetInput(Input* in) = 0;
  protected:
    std::string name; /**< The name of the move tester */
  };
	
  /** A Move Tester allows to test the behavior of a given
      neighborhood explorer.
      @ingroup Testers
  */
  template <class Input, class Output, class State, class Move>
  class MoveTester : public AbstractMoveTester<Input,Output,State>
  {
  public:
    MoveTester(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, NeighborhoodExplorer<Input,State,Move>* ne, std::string nm, Input* in = NULL);
    void RunTestMenu(State& st);
    void SetInput(Input *in);
  protected:
    void ShowMenu();
    void ExecuteChoice(State& st);
    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. */
    OutputManager<Input,Output,State>* p_om; /**< A pointer to the attached
						output manager. */
    Input* p_in;  /**< A pointer to the input object. */
    Output out;   /**< The output object. */
    int choice;   /**< The option currently chosen from the menu. */
  };
  
  /** The State Tester allows to test a State Manager.
      @ingroup Testers
  */
  template <class Input, class Output, class State>
  class StateTester
  {
  public:
    StateTester(StateManager<Input,State>* s, 
		OutputManager<Input,Output,State>* o, Input* in = NULL);
    /** Virtual destructor. */
    virtual ~StateTester() {} 
    void RunTestMenu(State& s);
    void RunInputMenu(State& s);
    void SetInput(Input *in);
  protected:
    void ShowMenu();
    void ShowReducedMenu();
    void ExecuteChoice(State& st);
    StateManager<Input,State>* p_sm; /**< A pointer to the attached 
					state manager. */
    OutputManager<Input,Output,State>* p_om; /**< A pointer to the attached
						output manager. */
    Input* p_in; /**< A pointer to an input object. */
    Output out;  /**< The output objecct. */
    int choice;  /**< The option currently chosen from the menu. */
  };

  /** This class represent the interface between the tester 
      and the interpreter of the batch experiment language. 
      @ingroup Testers
  */
  class AbstractTester
  {
  public:
    /** Virtual destructor. */
    virtual ~AbstractTester() {}
    /** Loads an input instance identified by the string passed as parameter.
	@param id the instance identifier. */
    virtual void LoadInstance(std::string id) = 0;
    /** Adds the runner identified by the name and the type passed as 
	parameter to the attached solver.
	@param name the name of the runner to add
	@param type the type of the runner to add
    */
    virtual int AddRunnerToSolver(std::string name, std::string type) = 0;
    void SetSolverTrials(unsigned int t);
    void SetLogFile(std::string s);
    void SetOutputPrefix(std::string s);
    void SetPlotPrefix(std::string s);
    /** Starts the solving procedure and collects the results. */
    virtual void StartSolver() = 0;
    /** Sets the parameter of the runner specified by the pair (name, type).
	They will be passed as a parameter box that contains them.
	@param name the name of the runner to set
	@param type the type of the runner to set
	@param pb a parameter box containing the parameters to set */
    virtual void SetRunningParameters(std::string name, std::string type, const ParameterBox& pb) = 0; 
  protected:
    unsigned int trials; /**< Number of trials the solver will be run */
    std::ostream* logstream; /**< An output stream where to write running information. */
    std::string output_file_prefix; /**< The file prefix to be used for 
				         writing the outcome of each trial. */
    std::string plot_file_prefix;  /**< The prefix to be used for
				      writing the progress of each run in a plot file. */
  };
	
  /** A Tester collects a set of basic testers (move, state, ...) and
      allows to access them through sub-menus. It represent the external
      user interface provided by the framework.
      @ingroup Testers
  */
  template <class Input, class Output, class State>
  class Tester : public AbstractTester
  {
  public:
    Tester(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in = NULL);
    /** Virtual destructor. */
    virtual ~Tester() {}
    void RunMainMenu();
    void SetInput(Input *in);
    void SetMoveTester(AbstractMoveTester<Input,Output,State>* p_amt, int i);
    void AddMoveTester(AbstractMoveTester<Input,Output,State>* p_amt);
    void CleanMoveTesters();
    void SetStateTester(StateTester<Input,Output,State>* p_st);
    void CleanRunners();
    void SetRunner(Runner<Input,State>* p_ru, unsigned int i);
    void AddRunner(Runner<Input,State>* p_ru);
    void SetSolver(TokenRingSolver<Input,Output,State>* p_so);
    void SetSolverParameters(unsigned int rounds, unsigned int start_runner = 0); 
    void LoadInstance(std::string id);
    int AddRunnerToSolver(std::string name, std::string type);
    void SetRunningParameters(std::string name, std::string type, const ParameterBox& pb);
    void StartSolver();
    void ProcessBatch(std::string filename);
    void CleanSolver();
    void Check();
    void Print(std::ostream& os = std::cout) const;
  protected:
    void ShowMainMenu();
    void ShowMovesMenu();
    void ShowRunMenu();
    void ShowDebuggingMenu();
    void ExecuteMainChoice();
    void ExecuteMovesChoice();
    void ExecuteRunChoice();
    void ExecuteDebuggingMenu();
    std::vector<AbstractMoveTester<Input,Output,State>* > move_testers;
    /**< The set of attached move testers. */
    std::vector<Runner<Input,State>* > runners; /**< The set of attached 
						   runners. */
    TokenRingSolver<Input,Output,State>* solver; /**< A token ring solver
						    to be used for batch
						    file processing. */
    StateTester<Input,Output,State>* state_tester;  /**< A state tester. */
    StateManager<Input,State>* p_sm;  /**< A pointer to a state manager. */
    OutputManager<Input,Output,State>* p_om; /**< A pointer to an output producer. */
    State test_state; /**< The current state managed by the tester. */
    Input* p_in; /**< A pointer to the input object. */
    Output out; /**< The output object. */
    int choice, /**< The option currently chosen from the menu. */
      sub_choice; /** The suboption currently chosen from the menu. */
  };
}; // end namespace easylocal

#endif // define __EASYLOCAL_H