EasyLocal++ Documentation


 
Main Page   Modules   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

easylocal::TabuListManager Class Template Reference

#include <EasyLocal.h>

Inheritance diagram for easylocal::TabuListManager

Inheritance graph
[legend]
Collaboration diagram for easylocal::TabuListManager:

Collaboration graph
[legend]
List of all members.

Public Methods

  • 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
  • void SetLength (unsigned int min, unsigned int max)
  • void Clean ()
  • unsigned int MinTenure () const
  • unsigned int MaxTenure () const
  • virtual bool Inverse (const Move &mv1, const Move &mv2) const=0

Protected Methods

Protected Attributes

Friends

  • std::ostream& operator<< (std::ostream &, const TabuListManager< Move > &)

Detailed Description

template<class Move> class easylocal::TabuListManager

The Tabu List Manager handles a list of 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 Move is inserted in the list, the ones which their iteration count has expired are removed.

Definition at line 235 of file EasyLocal.h.


Constructor & Destructor Documentation

template<class Move>
easylocal::TabuListManager< Move >::TabuListManager<Move> ( int min = 0,
int max = 0 ) [protected]
 

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).

Parameters:
min   the minimum tabu tenure
max   the maximum tabu tenure

Definition at line 250 of file EasyLocalTemplates.cpp.

template<class Move>
easylocal::TabuListManager<Move>::~TabuListManager<Move> ( ) [inline, protected, virtual]
 

Virtual destructor.

Definition at line 273 of file EasyLocal.h.


Member Function Documentation

template<class Move>
bool easylocal::TabuListManager< Move >::Aspiration ( const Move & mv,
fvalue mv_cost,
fvalue curr,
fvalue best ) const [protected, virtual]
 

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.

Parameters:
mv   the move
mv_cost   the move cost
curr   the cost of the current state
best   the cost of the best state found so far
Returns:
true if the aspiration criterion is satisfied, false otherwise

Definition at line 340 of file EasyLocalTemplates.cpp.

Referenced by ProhibitedMove().

template<class Move>
void easylocal::TabuListManager< Move >::Clean ( ) [virtual]
 

Deletes all the elements of the tabu list.

Reimplemented from easylocal::ProhibitionManager.

Definition at line 286 of file EasyLocalTemplates.cpp.

template<class Move>
void easylocal::TabuListManager< Move >::InsertIntoList ( const Move & mv ) [protected]
 

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

Parameters:
mv   the move to add

Definition at line 350 of file EasyLocalTemplates.cpp.

Referenced by InsertMove().

template<class Move>
void easylocal::TabuListManager< Move >::InsertMove ( const Move & mv,
fvalue mv_cost,
fvalue curr,
fvalue best ) [virtual]
 

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

Parameters:
mv   the move to add
mv_cost   the move cost
best   the best state cost found so far

Reimplemented from easylocal::ProhibitionManager.

Definition at line 263 of file EasyLocalTemplates.cpp.

template<class Move>
bool easylocal::TabuListManager<Move>::Inverse ( const Move & mv1,
const Move & mv2 ) const [pure virtual]
 

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.
Parameters:
mv1   the move to be tested
mv2   the move used for comparison

Referenced by ListMember().

template<class Move>
bool easylocal::TabuListManager< Move >::ListMember ( const Move & mv ) const [protected]
 

Checks whether the inverse of a given move belongs to the tabu list.

Parameters:
mv   the move to check
Returns:
true if the inverse of the move belongs to the tabu list, false otherwise

Definition at line 297 of file EasyLocalTemplates.cpp.

Referenced by ProhibitedMove().

template<class Move>
unsigned int easylocal::TabuListManager<Move>::MaxTenure ( ) const [inline]
 

Returns the maximum number of iterations a move is considered tabu.

Returns:
the maximum tabu tenure

Definition at line 261 of file EasyLocal.h.

template<class Move>
unsigned int easylocal::TabuListManager<Move>::MinTenure ( ) const [inline]
 

Returns the minimum number of iterations a move is considered tabu.

Returns:
the minimum tabu tenure

Definition at line 257 of file EasyLocal.h.

template<class Move>
bool easylocal::TabuListManager< Move >::ProhibitedMove ( const Move & mv,
fvalue mv_cost,
fvalue curr,
fvalue best ) const [virtual]
 

Checks whether the given move is prohibited.

Parameters:
mv   the move to check
mv_cost   the move cost
curr   the current state cost
best   the best state cost found so far
Returns:
true if the move mv is prohibited, false otherwise

Reimplemented from easylocal::ProhibitionManager.

Definition at line 279 of file EasyLocalTemplates.cpp.

template<class Move>
void easylocal::TabuListManager<Move>::SetLength ( unsigned int min,
unsigned int max ) [inline]
 

Sets the length of the tabu list to be comprised in the range [min, max].

Parameters:
min   the minimum tabu tenure
max   the maximum tabu tenure

Definition at line 252 of file EasyLocal.h.

template<class Move>
void easylocal::TabuListManager<Move>::UpdateAspirationFunction ( fvalue mv_cost,
fvalue curr_cost,
fvalue best_cost ) [inline, protected]
 

Updates the function associated with the aspiration criterion. For default it does nothing.

Parameters:
mv_cost   the cost of the move
curr   the cost of the current solution
best   the cost of the best solution found so far

Definition at line 281 of file EasyLocal.h.

Referenced by InsertMove().


Friends And Related Function Documentation

template<class Move>
std::ostream& operator<< ( std::ostream & os,
const TabuListManager< Move > & tl ) [friend]
 

Prints out the current status of the Tabu List Manager.

Definition at line 317 of file EasyLocalTemplates.cpp.


Member Data Documentation

template<class Move>
unsigned long easylocal::TabuListManager<Move>::iter [protected]
 

The current iteration.

Definition at line 287 of file EasyLocal.h.

template<class Move>
unsigned int easylocal::TabuListManager<Move>::max_tenure [protected]
 

The maximum tenure of the tabu list.

Definition at line 285 of file EasyLocal.h.

template<class Move>
unsigned int easylocal::TabuListManager<Move>::min_tenure [protected]
 

The minimum tenure of the tabu list.

Definition at line 285 of file EasyLocal.h.

template<class Move>
std::list< ListItem< Move > > easylocal::TabuListManager<Move>::tlist [protected]
 

The list of tabu moves.

Definition at line 288 of file EasyLocal.h.


The documentation for this class was generated from the following files:
 
Go to: the Main Page of the documentation.