This document is for version 0.4.x, an updated version relative to 0.5.x is in the works.

METSlib is primarily about Tabu Search algorithm, a variant of the local search that tries to avoid remaining entrapped in local minima using memory of the exploration made.

Although, given the nature of metaheuristics, its not possible to give a totally general implementation the aim of METSlib is to provide a sound framework and a modular toolkit of reusable components that ease building custom solutions.

Before using the provided algorithms the developer needs to implement his own problem inside the framework.

The first mandatory class to derive from is mets::feasible_solution. There are two mandatory methods: one for cost evaluation (that will be minimized by the algorithm) and another to copy one solution into another.

class feasible_solution
{
public:
  virtual double cost_function() const = 0;
  virtual void copy_from(const feasible_solution& o) = 0;
  ...
};

There will usually be some other custom methods to generate a starting point (randomly or greedily) and to operate on the solution.

One other needed interface is mets::move or its mets::mana_move subclass.

The methods that must overridden from mets::move are just apply and unapply. "apply" should change the solution to be one of its neighbors while "unapply" should undo the last move (unless using mets::complex_move it's not required to undo more than one move). E.g. a swap_move may swaps two variables in apply and swaps the same two in unapply, a set_move may sets a variable to some value when applied and restores the previous value when unapplied.

class move
{
  public:
    virtual void apply(feasible_solution& sol) = 0;
    virtual void unapply(feasible_solution& sol) = 0;
    ...
  };

If the developer plans to use mets::simple_tabu_search he must derive from mets::mana_move (instead of mets::move) and also override the clone(), operator==() and hash() functions.

  class mana_move : public move
  {
  public:
    virtual mana_move* clone() const = 0;
    virtual bool operator==(const mana_move& other) const = 0;
    virtual size_t hash() const = 0;
    ...
  };

The clone method should return a newly created copy of self, operator== should check if two moves have to be considered the same w.r.t the tabu list (so that the same move is not made again, if already present) and hash() should return a number representing the move (always the same for the same move, see wikipedia).

Choosing the move types (the usual set, clear, swap, or other types) the developer implicitly gives a definition of neighborhood for his problem. To allow the exploration of the neighborhood by METSlib algorithms the developer needs to implement his own mets::move_manager. With the move_manager the developer can choose (once for all, or at each iteration) which moves of the neighborhood should be explored by the algorithms.

class move_manager {
public:
   virtual void refresh(feasible_solution& sol) = 0;
   ...
protected:
   std::deque<move*> moves_m;
};

If the choice of the moves does not depend on the current solution the developer can fill the moves_m list pushing the needed moves in the ctor of the derived class. In the more common situation in which one needs to adjust the moves at each iteration the the move_m list can be manipulated at each iteration overriding the refresh(...) method.

Once implemented the model in the framework, as specified by the former paragraphs, the developer can build his algorithm to solve his model, using his implemented neighborhood exploration strategy.

To build the algorithm (lets say Tabu Search) the developer needs to choose, and perhaps compose, a termination_criteria_chain, a tabu_list_chain, an aspiration_criteria_chain, and, if logging is needed, a search_listener. All the chains are chain of responsibility objects, they can be chained together to form composite criteria.

The developer will need a termination criteria to tell the algorithm when to stop.

The provided criteria are: mets::iteration_termination_criteria, mets::noimprove_termination_criteria, and mets::threshold_termination_criteria, or a composition of them. If they are not sufficient, its possible to implement other criteria deriving from mets::termination_criteria_chain.

=== tabu_list_chain ===

The only provided tabu list is, at the moment, the mets::simple_tabu_list, a memory of the recently made moves. This list requires that all the moves are derived from mets::mana_move. The only needed parameter is the tenure of the list. The tenure can be changed using the tenure(int) method.

The toolkit provides the standard mets::best_ever_aspiration_criteria that is usually enough.

Once all the pieces are in place the mets::tabu_search algorithm can be instantiated and started. If multi staged search is needed (a multistart or an iterated local search) it can be coded easily by the developer. When implementing a multi staged search keep in mind that tabu lists can be reused, but termination criteria must be destroyed and created again.

== METSlib class diagram ==

Look at TabuSearchTutorial for some example code.

Attachments:

• mets-class-diagram.png