easylocal.h

一个tabu search算法框架

/** 
    @file EasyLocal.h
    @brief Class declarations

    This file contains all the class declarations of the EasyLocal++
    framework.   
    
   @author Andrea Schaerf ([e-mail]), 
            Luca Di Gaspero ([e-mail])
   @version 0.2
   @date 18 Jan 2002
   @note This version works both with MS Visual C++ and the GNU C++ 
         compiler. Yet, it is extensively tested only with the GNU compiler.
*/

#ifndef __EASYLOCAL_H
#define __EASYLOCAL_H

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <list>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstdio>

/** This function is provided by a bison parser for batch 
    experiment file processing */
extern "C++" int yyparse(); 

/** This is the input file of the ExpSpec language interpreter */
extern FILE *yyin;
/** This is the output file of the ExpSpec language interpreter */
extern FILE *yyout;  

/** The easylocal namespace embeds all the classes of the framework. */
namespace easylocal {
  /** A random number generator. Generates pseudo-random integer values in the
      range [a, b].
      @param a the lower bound of the range
      @param b the upper bound of the range
      @return a value in the range [a, b]
  */
  int Random(int a, int b);

  /** This constant multiplies the value of the Violations function in the
      hierarchical formulation of the Cost function (i.e., 
      CostFunction(s) = HARD_WEIGHT * Violations(s) + Objective(s)).
      @todo The use of the global HARD_WEIGHT is a rough solution, 
      waiting for an idea of a general mechanism for managing cost function 
      weights.
  */
#ifndef HARD_WEIGHT
#define HARD_WEIGHT 1000
#endif
	
  /** These are used by the Tester class for returning 
      a code error to the parser. */
  const int RUNNER_NOT_FOUND = 1, RUNNER_TYPE_MISMATCH = 2;
	
  /** The fvalue definition represent the codomain of the cost and of the 
      objective function. For default it is set to double, but the user 
      can provide its own definition. 
      In this case, the user must define its own double-valued distance 
      function between fvalues.
      @todo Find a more general mechanism.
  */
#ifndef fvalue
#define fvalue double
#endif

  /** It is the precision above which the computed difference of the
      cost function and the expected value should be considered
      different. */
  const double EPS = 1.0E-6;

  /** This function computes the distance between two @c fvalues and
      returns its value as a double.

      @param x the first function value
      @param y the second function value
      @return the distance between x and y
  */
  inline double distance(fvalue x, fvalue y);
		
  /** @defgroup Helpers Helper classes 
      Helper classes perform actions related to some specific aspects of the
      search. For example, the @c NeighborhoodExplorer is responsible
      for everything concerning the neighborhood: candidate move
      selection, update current state by executing a move, and so on.
      Different @c NeighborhoodExplorers may be defined in case of
      composite search, each one handling a specific neighborhood
      relation used by the algorithm.  

      Helper classes cooperate among themselves.  For example, the @c
      NeighborhoodExplorer is not responsible for the move prohibition
      mechanisms (such as maintaining the tabu list), which are
      delegated to another helper, namely the @c ProibitionManager.
  
      Helper classes do not have their own internal data, but they work on the
      internal state of the runners that invoke them, and interact with
      them through function parameters.  
  */

  // forward class tag declaration
  template <class Input, class State> class Runner;

  /** The State Manager is responsible for all operations on the state
      which are independent of the neighborhood definition, such as
      generating a random state, and computing the cost of a state.
      No @c Move template is supplied to it.  
      @ingroup Helpers
  */
  template <class Input, class State>
  class StateManager
  {
  public:
    /** Generates a random state.
	@note @bf To be implemented in the application.
	@param st the state generated */
    virtual void RandomState(State &st) = 0; 
    /** Possibly updates redundant state data. It is used by the
	output manager to make the state consistent.
	@param st the state to be updated
    */
    virtual void UpdateRedundantStateData(State &st) 
    {}
    virtual fvalue SampleState(State &st, int samples);
    virtual fvalue ImprovedSampleState(State &st, int samples, Runner<Input,State>* r);      
		
    // State Evaluation functions
    virtual fvalue CostFunction(const State& st) const;
    virtual fvalue Objective(const State& st) const;
    virtual fvalue Violations(const State& st) const;
				
    // debug functions
    virtual void PrintState(const State& st) const;
    virtual void Check() const;
		
    void SetInput(Input* in);
    Input* GetInput();
  protected:
    StateManager(Input* in = NULL);
    Input* p_in; /**< A pointer to the input object. */
  };

  /** The Output Manager is responsible for translating between
      elements of the search space and output solutions.  It also
      delivers other output information of the search, and stores and
      retrieves solutions from files.  This is the only helper that
      deals with the @c Output class.  All other helpers work only on
      the @c State class, which represents the elements of the search
      space used by the algorithms.  
      @ingroup Helpers
  */	
  template <class Input, class Output, class State>
  class OutputManager
  {
  public:
    /** Transforms the given state in an output object. 
	@param st the state to transform 
	@param out the corresponding output object. */
    virtual void OutputState(const State &st, Output& out) const = 0;
    /** Transforms an output object in a state object. 
	@param st the resulting state
	@param out the output object to transform */
    virtual void InputState(State &st, const Output& out) const = 0;
    virtual void ReadState(State &st, std::istream &is) const;
    virtual void WriteState(const State &st, std::ostream &os) const;
		
    virtual void Check() const;
    void SetInput(Input* in);
    Input* GetInput();
  protected:
    /** Constructs an output manager by providing it a state manager
     and an input object.
     @param sm a pointer to a state manager
     @param in a pointer to an input object */
    OutputManager(StateManager<Input,State>* sm, Input* in = NULL) 
      :  p_sm(sm), p_in(in) {}
    StateManager<Input,State>* p_sm; /**< A pointer to an attached 
					state manager. */
    Input* p_in;  /**< A pointer to an input object. */
  };
	
  
  /** The Prohibition Manager deals with move prohibition mechanisms
     that prevents cycling and allows for diversification.  
     
     This class is at the top of the hierarchy: we have also a more
     specific prohibition manager, which maintains a list of @c Move
     elements according to the prohibition mechanisms of tabu search.  
     @ingroup Helpers
  */
  template <class Move>
  class ProhibitionManager
  {
  public:
    /** Marks a given move as prohibited, according to the prohibition
	strategy.
	@param mv the move
	@param mv_cost the cost of the move
	@param curr the cost of the current solution
	@param best the cost of the best solution found so far  */
    virtual void InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) = 0;
    /** Checks whether the given move is prohibited, according to the
	prohibition strategy.
	@param mv the move
	@param mv_cost the cost of the move
	@param curr the cost of the current solution
	@param best the cost of the best solution found so far
	@return true if the move is prohibited, false otherwise */
    virtual bool ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best) const = 0;
    /** Resets the prohibition manager mechanisms. */
    virtual void Clean() = 0;
    /** Checks whether the state of the prohibition manager is consistent
	with the attached objects. */
    virtual void Check() {}
  };

  // forward class tag declaration
  template <class Move> class ListItem;

  /** The Tabu List Manager handles a list of @c Move elements according
      to the prohibition mechanisms of tabu search.
      Namely it maintains an item in the list for a number of iterations 
      that varies randomly in a given range.
      Each time a new @c Move is inserted in the list, the ones which their 
      iteration count has expired are removed.
      @ingroup Helpers
  */
  template <class Move>
  class TabuListManager : public ProhibitionManager<Move>
  {
#ifndef __GNUC_MINOR__
    friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&);
#elif __GNUC_MINOR__ > 7 
    friend std::ostream& operator<< <>(std::ostream&, const TabuListManager<Move>&);
#else 
    friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&);
#endif
  public:
    void InsertMove(const Move& mv, fvalue mv_cost, fvalue curr, fvalue best);
    bool ProhibitedMove(const Move& mv, fvalue mv_cost, fvalue curr, 
			fvalue best) const;
    /** Sets the length of the tabu list to be comprised in the range
	[min, max].
	@param min the minimum tabu tenure
	@param max the maximum tabu tenure */
    void SetLength(unsigned int min, unsigned int max) 
    { min_tenure = min; max_tenure = max; }
    void Clean();
    /** Returns the minimum number of iterations a move is considered tabu.
	@return the minimum tabu tenure */
    unsigned int MinTenure() const 
    { return min_tenure; }
    /** Returns the maximum number of iterations a move is considered tabu.
	@return the maximum tabu tenure */
    unsigned int MaxTenure() const 
    { return max_tenure; }
    /** Verifies whether a move is the inverse of another one. Namely it 
	tests whether mv1 is the inverse of mv2 (that will be an element of
	the tabu list).
	@note @bf To be implemented in the application.
	@param mv1 the move to be tested
	@param mv2 the move used for comparison  */
    virtual bool Inverse(const Move& mv1, const Move& mv2) const = 0;
  protected:
    TabuListManager(int min = 0, int max = 0);
    /** Virtual destructor. */
    virtual ~TabuListManager() {}
    virtual bool Aspiration(const Move&, fvalue mv_cost, fvalue curr, fvalue best) const; 
    void InsertIntoList(const Move& mv); 
    /** Updates the function associated with the aspiration criterion. 
	For default it does nothing.
	@param mv_cost the cost of the move
	@param curr the cost of the current solution
	@param best the cost of the best solution found so far */
    void UpdateAspirationFunction(fvalue mv_cost, fvalue curr_cost, fvalue best_cost) 
    {}
    bool ListMember(const Move&) const;
		
    unsigned int min_tenure, /**< The minimum tenure of the tabu list. */
      max_tenure;  /**< The maximum tenure of the tabu list. */
    unsigned long iter; /**< The current iteration. */
    std::list<ListItem<Move> > tlist; /**< The list of tabu moves. */
  };

  /** The class for a @c Move item in the Tabu List.
      It is simply a compound data made up of the @c Move itself and the 
      iteration at which the element shall leave the list.
  */
  template <class Move> 
  class ListItem
  {
    friend class TabuListManager<Move>;
#ifndef __GNUC_MINOR__
    friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&);
#elif __GNUC_MINOR__ > 7 
    friend std::ostream& operator<< <>(std::ostream&, const TabuListManager<Move>&);
#else 
    friend std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&);
#endif
  public:
    /** Creates a tabu list item constituted by a move 
	and the leaving iteration passed as parameters.
	@param mv the move to insert into the list
	@param out the iteration at which the move leaves the list.
    */
    ListItem(Move mv, unsigned long out)
      : out_iter(out) { elem = mv; }
  protected:
    Move elem;              /**< The move stored in the list item. */
    unsigned long out_iter; /**< iteration at which the element 
			       leaves the list */
  };
	
  /** Prints out the current status of the Tabu List Manager. */
  template <class Move>
  std::ostream& operator<<(std::ostream&, const TabuListManager<Move>&);
		 

  /** The Neighborhood Explorer is responsible for the strategy
      exploited in the exploration of the neighborhood, and for 
      computing the variations of the cost function due to a specific
      @c Move. 
      @ingroup Helpers
   */
  template <class Input, class State, class Move>
  class NeighborhoodExplorer
  {
  public:
    /** Virtual destructor. */
    virtual ~NeighborhoodExplorer() {}
		
    // move generating functions
    virtual void FirstMove(const State& st, Move& mv);
    /** Generates the move that follows mv in the exploration of the 
	neighborhood of the state st. 
	It returns the generated move in the same variable mv.
	
	@note @bf To be implemented in the application.
	@param st the start state 
	@param mv the move 
     */
    virtual void NextMove(const State &st, Move& mv) = 0;
    /** Generates a random move in the neighborhood of a given state.
	
	@note @bf To be implemented in the application.
	@param st the start state 
	@param mv the generated move 
    */
    virtual void RandomMove(const State &st, Move& mv) = 0;           
    virtual fvalue BestMove(const State &st, Move& mv);
    virtual fvalue SampleMove(const State &st, Move& mv, int samples);
    virtual fvalue BestNonProhibitedMove(const State &st, Move& mv, fvalue curr, fvalue best);
    virtual fvalue SampleNonProhibitedMove(const State &st, Move& mv, int samples, fvalue curr, fvalue best);
    // end of exploration detection
    virtual bool LastMoveDone(const Move &mv);

    /** States whether a move is feasible or not in a given state. 
	For default it acceptsall the moves as feasible ones, but it can
	be overwritten by the user.

	@param st the start state
	@param mv the move to check for feasibility
	@return true if the move is feasible in st, false otherwise
    */
    virtual bool FeasibleMove(const State &st, const Move mv) 
    { return true; }

    virtual void SetProhibitionManager(ProhibitionManager<Move> *pm);

    /** Modifies the state passed as parameter by applying a given
	move upon it.
	
	@note @bf To be implemented in the application.