EasyLocal++ Documentation


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

easylocal::TabuSearch Class Template Reference

#include <EasyLocal.h>

Inheritance diagram for easylocal::TabuSearch

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

Collaboration graph
[legend]
List of all members.

Public Methods

Protected Methods

Protected Attributes


Detailed Description

template<class Input, class State, class Move> class easylocal::TabuSearch

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.

Definition at line 707 of file EasyLocal.h.


Constructor & Destructor Documentation

template<class Input, class State, class Move>
easylocal::TabuSearch< Input, State, Move >::TabuSearch<Input, State, Move> ( StateManager< Input, State > * s,
NeighborhoodExplorer< Input, State, Move > * ne,
TabuListManager< Move > * tlm,
Input * in = NULL ) [protected]
 

Constructs a tabu search runner by linking it to a state manager, a neighborhood explorer, a tabu list manager, and an input object.

Parameters:
s   a pointer to a compatible state manager
ne   a pointer to a compatible neighborhood explorer
tlm   a pointer to a compatible tabu list manager
in   a poiter to an input object

Definition at line 1282 of file EasyLocalTemplates.cpp.


Member Function Documentation

template<class Input, class State, class Move>
bool easylocal::TabuSearch< Input, State, Move >::AcceptableMove ( ) [protected, virtual]
 

In tabu search the selected move is always accepted. That is, the acceptability test is replaced by the prohibition mechanism which is managed inside the selection.

Reimplemented from easylocal::MoveRunner.

Definition at line 1371 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::InitializeRun ( ) [protected, virtual]
 

Initializes the run by invoking the companion superclass method, and cleans the tabu list.

Reimplemented from easylocal::MoveRunner.

Definition at line 1342 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::Print ( std::ostream & os = std::cout ) const [virtual]
 

Outputs some tabu search statistics on a given output stream.

Parameters:
os   the output stream

Reimplemented from easylocal::MoveRunner.

Definition at line 1411 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::ReadParameters ( ) [virtual]
 

Reads the tabu search parameters from the standard input.

Reimplemented from easylocal::Runner.

Definition at line 1309 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::SelectMove ( ) [protected, virtual]
 

Selects always the best move that is non prohibited by the tabu list mechanism.

Reimplemented from easylocal::MoveRunner.

Definition at line 1354 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::SetInput ( Input * in ) [virtual]
 

Sets the internal input pointer to the new value passed as parameter.

Parameters:
in   the new input.

Reimplemented from easylocal::MoveRunner.

Definition at line 1299 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::SetParameters ( const ParameterBox & pb ) [virtual]
 

Sets the tabu search parameters, passed through a parameter box.

Parameters:
pb   the object containing the parameter setting for the algorithm

Reimplemented from easylocal::MoveRunner.

Definition at line 1380 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::SetTabuListManager ( TabuListManager< Move > * tlm,
int min_tabu = 0,
int max_tabu = 0 ) [protected]
 

Sets the tabu list manager according to the one passed as parameter.

Parameters:
tlm   a pointer to a compatible tabu list manager
min_tabu   the minimum tabu tenure for a move
max_tabu   the maximum tabu tenure for a move

Definition at line 1328 of file EasyLocalTemplates.cpp.

Referenced by TabuSearch().

template<class Input, class State, class Move>
bool easylocal::TabuSearch< Input, State, Move >::StopCriterion ( ) [protected, virtual]
 

The stop criterion is based on the number of iterations elapsed from the last strict improvement of the best state cost.

Reimplemented from easylocal::MoveRunner.

Definition at line 1362 of file EasyLocalTemplates.cpp.

template<class Input, class State, class Move>
void easylocal::TabuSearch< Input, State, Move >::StoreMove ( ) [protected, virtual]
 

Stores the move by inserting it in the tabu list, if the state obtained is better than the one found so far also the best state is updated.

Reimplemented from easylocal::MoveRunner.

Definition at line 1394 of file EasyLocalTemplates.cpp.


Member Data Documentation

template<class Input, class State, class Move>
TabuListManager< Move > * easylocal::TabuSearch<Input, State, Move>::p_pm [protected]
 

A pointer to a tabu list manger.

Definition at line 724 of file EasyLocal.h.


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