1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/tabu_search.h Thu Apr 27 14:53:23 2006 +0000
1.3 @@ -0,0 +1,530 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +
1.23 +#ifndef LEMON_TABU_SEARCH_H
1.24 +#define LEMON_TABU_SEARCH_H
1.25 +
1.26 +/// \ingroup experimental
1.27 +/// \file
1.28 +/// \brief TabuSearch algorithm.
1.29 +///
1.30 +/// \author Szabadkai Mark
1.31 +
1.32 +#include <lemon/bits/utility.h>
1.33 +#include <lemon/error.h>
1.34 +#include <lemon/time_measure.h>
1.35 +#include <functional>
1.36 +#include <deque>
1.37 +
1.38 +
1.39 +namespace lemon {
1.40 +
1.41 + /// \brief Default Traits for TabuSearch class.
1.42 + ///
1.43 + /// This template defines the needed types for the \ref TabuSearch class.
1.44 + /// Is main purpos is to simplify the main class's template interface,
1.45 + /// but it provides the EdgeIt type, passing to the concrete graph wheter
1.46 + /// it is directed or undirected.
1.47 +#ifdef DOXYGEN
1.48 + template< typename GRAPH, typename VALUE,
1.49 + typename HEIGHTMAP, typename BETTER, bool UNDIR >
1.50 +#else
1.51 + template< typename GRAPH, typename VALUE,
1.52 + typename HEIGHTMAP = typename GRAPH::template NodeMap<VALUE>,
1.53 + typename BETTER = std::less<VALUE>,
1.54 + bool UNDIR = UndirectedTagIndicator<GRAPH>::value >
1.55 +#endif
1.56 + struct TabuSearchDefaultTraits {
1.57 + typedef VALUE Value;
1.58 + typedef BETTER Better;
1.59 +
1.60 + typedef GRAPH Graph;
1.61 + typedef typename GRAPH::Node Node;
1.62 + typedef HEIGHTMAP HeightMap;
1.63 +
1.64 + typedef typename GRAPH::IncEdgeIt EdgeIt;
1.65 + };
1.66 +
1.67 + template< typename GRAPH, typename VALUE,
1.68 + typename HEIGHTMAP, typename BETTER >
1.69 + struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
1.70 + typedef VALUE Value;
1.71 + typedef BETTER Better;
1.72 +
1.73 + typedef GRAPH Graph;
1.74 + typedef typename GRAPH::Node Node;
1.75 + typedef HEIGHTMAP HeightMap;
1.76 +
1.77 + typedef typename GRAPH::OutEdgeIt EdgeIt;
1.78 + };
1.79 +
1.80 +
1.81 +
1.82 + /// \brief Policy hierarchy to controll the search algorithm.
1.83 + ///
1.84 + /// The fallowing template hierarchy offers a clean interface to define own
1.85 + /// policies, and combine existing ones.
1.86 + template< typename TS >
1.87 + struct TabuSearchPolicyConcept {
1.88 + void target( TS *ts ) {}
1.89 +
1.90 + void reset() {}
1.91 + bool onStep() { return false; }
1.92 + bool onStick() { return false; }
1.93 + bool onImprove( const typename TS::Value &best ) { return false; }
1.94 + };
1.95 +
1.96 + template< typename TS >
1.97 + struct YesPolicy {
1.98 + void target( TS *ts ) {}
1.99 +
1.100 + void reset() {}
1.101 + bool onStep() { return true; }
1.102 + bool onStick() { return true; }
1.103 + bool onImprove( const typename TS::Value &best ) { return true; }
1.104 + };
1.105 +
1.106 + template< typename TS >
1.107 + struct NoPolicy : public TabuSearchPolicyConcept<TS> {};
1.108 +
1.109 + /// \brief Some basic methode, how tow Policies can be combined
1.110 + struct PolicyAndCombination {
1.111 + static bool evaluate( const bool r1, const bool r2 ) {
1.112 + return r1 && r2;
1.113 + }
1.114 + };
1.115 +
1.116 + struct PolicyOrCombination {
1.117 + static bool evaluate( const bool r1, const bool r2 ) {
1.118 + return r1 || r2;
1.119 + }
1.120 + };
1.121 +
1.122 + /// \brief CombinePolicies
1.123 + ///
1.124 + /// It combines tow policies using the given combination methode (mainly
1.125 + /// some of the basic logical methodes) to create a new one.
1.126 +#ifdef DOXYGEN
1.127 + template< template<typename> class CP1, template<typename> class CP2,
1.128 + typename COMBINATION >
1.129 +#else
1.130 + template< template<typename> class CP1, template<typename> class CP2,
1.131 + typename COMBINATION = PolicyAndCombination >
1.132 +#endif
1.133 + struct CombinePolicies {
1.134 + template< typename TS >
1.135 + struct Policy {
1.136 + typedef CP1<TS> Policy1;
1.137 + typedef CP2<TS> Policy2;
1.138 +
1.139 + Policy1 policy1;
1.140 + Policy2 policy2;
1.141 +
1.142 + inline Policy() : policy1(), policy2() {}
1.143 + inline Policy( const Policy1 &cp1, const Policy2 &cp2 )
1.144 + : policy1(cp1), policy2(cp2) {}
1.145 +
1.146 + void target( TS *ts ) {
1.147 + policy1.target(ts), policy2.target(ts);
1.148 + };
1.149 +
1.150 + void reset() {
1.151 + policy1.reset(), policy2.reset();
1.152 + }
1.153 +
1.154 + bool onStep() {
1.155 + return cmb.evaluate( policy1.onStep(), policy2.onStep() );
1.156 + }
1.157 +
1.158 + bool onStick() {
1.159 + return cmb.evaluate( policy1.onStick(), policy2.onStick() );
1.160 + }
1.161 +
1.162 + bool onImprove( const typename TS::Value &best ) {
1.163 + return cmb.evaluate( policy1.onImprove(best),
1.164 + policy2.onImprove(best) );
1.165 + }
1.166 +
1.167 + private:
1.168 + COMBINATION cmb;
1.169 + };
1.170 + };
1.171 +
1.172 +
1.173 + /// \brief IterationPolicy limits the number of iterations and the
1.174 + /// number of iterations without improvement
1.175 + template< typename TS >
1.176 + struct IterationPolicy {
1.177 + IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {}
1.178 + IterationPolicy( const long int itl, const long int noimpritl )
1.179 + : _it_lim(itl), _noimpr_it_lim(noimpritl)
1.180 + {}
1.181 +
1.182 + void target( TS *ts ) {}
1.183 +
1.184 + void reset() {
1.185 + _it = _noimpr_it = 0;
1.186 + }
1.187 +
1.188 + bool onStep() {
1.189 + ++_it; ++_noimpr_it;
1.190 + return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
1.191 + }
1.192 +
1.193 + bool onStick() {
1.194 + return false;
1.195 + }
1.196 +
1.197 + bool onImprove( const typename TS::Value &best ) {
1.198 + _noimpr_it = 0;
1.199 + return true;
1.200 + }
1.201 +
1.202 + long int iterationLimit() const {
1.203 + return _it_lim;
1.204 + }
1.205 +
1.206 + void iterationLimit( const long int itl ) {
1.207 + _it_lim = itl;
1.208 + }
1.209 +
1.210 + long int noImprovementIterationLimit() const {
1.211 + return _noimpr_it_lim;
1.212 + }
1.213 +
1.214 + void noImprovementIterationLimit( const long int noimpritl ) {
1.215 + _noimpr_it_lim = noimpritl;
1.216 + }
1.217 +
1.218 + private:
1.219 + long int _it_lim, _noimpr_it_lim;
1.220 + long int _it, _noimpr_it;
1.221 + };
1.222 +
1.223 + /// \brief HeightPolicy stops the search when a given height is reached or
1.224 + /// exceeds
1.225 + template< typename TS >
1.226 + struct HeightPolicy {
1.227 + typedef typename TS::Value Value;
1.228 +
1.229 + HeightPolicy() : _height_lim(), _found(false) {}
1.230 + HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}
1.231 +
1.232 + void target( TS *ts ) {}
1.233 +
1.234 + void reset() {
1.235 + _found = false;
1.236 + }
1.237 +
1.238 + bool onStep() {
1.239 + return !_found;
1.240 + }
1.241 +
1.242 + bool onStick() {
1.243 + return false;
1.244 + }
1.245 +
1.246 + bool onImprove( const Value &best ) {
1.247 + typename TS::Better better;
1.248 + _found = better(best, _height_lim) || (best == _height_lim);
1.249 + return !_found;
1.250 + }
1.251 +
1.252 + Value heightLimi() const {
1.253 + return _height_lim;
1.254 + }
1.255 +
1.256 + void heightLimi( const Value &hl ) {
1.257 + _height_lim = hl;
1.258 + }
1.259 +
1.260 + private:
1.261 + Value _height_lim;
1.262 + bool _found;
1.263 + };
1.264 +
1.265 + /// \brief TimePolicy limits the time for searching.
1.266 + template< typename TS >
1.267 + struct TimePolicy {
1.268 + TimePolicy() : _time_lim(60.0), _timeisup(false) {}
1.269 + TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}
1.270 +
1.271 + void target( TS *ts ) {}
1.272 +
1.273 + void reset() {
1.274 + _timeisup = false;
1.275 + _t.reset();
1.276 + }
1.277 +
1.278 + bool onStep() {
1.279 + update();
1.280 + return !_timeisup;
1.281 + }
1.282 +
1.283 + bool onStick() {
1.284 + return false;
1.285 + }
1.286 +
1.287 + bool onImprove( const typename TS::Value &best ) {
1.288 + update();
1.289 + return !_timeisup;
1.290 + }
1.291 +
1.292 + double timeLimit() const {
1.293 + return _time_lim;
1.294 + }
1.295 +
1.296 + void setTimeLimit( const double tl ) {
1.297 + _time_lim = tl;
1.298 + update();
1.299 + }
1.300 +
1.301 + private:
1.302 + lemon::Timer _t;
1.303 + double _time_lim;
1.304 + bool _timeisup;
1.305 +
1.306 + inline void update() {
1.307 + _timeisup = _t.realTime() > _time_lim;
1.308 + }
1.309 + };
1.310 +
1.311 +
1.312 +
1.313 + /// \brief TabuSearch main class
1.314 + ///
1.315 + /// This class offers the implementation of tabu-search algorithm. The
1.316 + /// tabu-serach is a local-search. It starts from a specified point of the
1.317 + /// problem's graph representation, and in every step it goes to the localy
1.318 + /// best next Node except those in tabu set. The maximum size of this tabu
1.319 + /// set defines how many Node will be remembered. The best Node ever found
1.320 + /// will also stored, so we wont lose it, even is the search continues.
1.321 + /// The class can be used on any kind of Graph and with any kind of Value
1.322 + /// with a total-settlement on it.
1.323 + ///
1.324 + /// \param _Graph The graph type the algorithm runs on.
1.325 + /// \param _Value The values' type associated to the nodes.
1.326 + /// \param _Policy Controlls the search. Determinates when to stop, or how
1.327 + /// manage stuck search. Default value is \ref IterationPolicy .
1.328 + /// \param _Traits Collection of needed types. Default value is
1.329 + /// \ref TabuSearchDefaultTraits .
1.330 + ///
1.331 + /// \author Szabadkai Mark
1.332 +#ifdef DOXYGEN
1.333 + template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
1.334 +#else
1.335 + template< typename GRAPH, typename VALUE,
1.336 + template<typename> class POLICY = IterationPolicy,
1.337 + typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
1.338 +#endif
1.339 + class TabuSearch
1.340 + {
1.341 + public:
1.342 +
1.343 + /// \brief Thrown by setting the size of the tabu-set and the given size
1.344 + /// is less than 2.
1.345 + class BadParameterError : public lemon::LogicError {
1.346 + public:
1.347 + virtual const char* exceptionName() const {
1.348 + return "lemon::TabuSearch::BadParameterError";
1.349 + }
1.350 + };
1.351 +
1.352 + ///Public types
1.353 + typedef TabuSearch<GRAPH,VALUE,POLICY,TRAITS> SelfType;
1.354 +
1.355 + typedef typename TRAITS::Graph Graph;
1.356 + typedef typename TRAITS::Node Node;
1.357 + typedef typename TRAITS::Value Value;
1.358 + typedef typename TRAITS::HeightMap HeightMap;
1.359 + typedef typename TRAITS::Better Better;
1.360 + typedef typename std::deque< Node >::const_iterator TabuIterator;
1.361 +
1.362 + typedef POLICY<SelfType> Policy;
1.363 +
1.364 + protected:
1.365 + typedef typename TRAITS::EdgeIt EdgeIt;
1.366 +
1.367 + const Graph &gr;
1.368 + const HeightMap &height;
1.369 + /// The tabu set. Teh current node is the first
1.370 + std::deque< Node > tabu;
1.371 + /// Maximal tabu size
1.372 + unsigned int mts;
1.373 + /// The best Node found
1.374 + Node b;
1.375 +
1.376 + Better better;
1.377 + Policy pol;
1.378 +
1.379 + public:
1.380 + /// \brief Constructor
1.381 + ///
1.382 + /// \param graph the graph the algorithm will run on.
1.383 + /// \param hm the height map used by the algorithm.
1.384 + /// \param tabusz the maximal size of the tabu set. Default value is 3
1.385 + /// \param p the Policy controlling the search.
1.386 + TabuSearch( const Graph &graph, const HeightMap &hm,
1.387 + const int tabusz = 3, Policy p = Policy() )
1.388 + : gr(graph), height(hm), mts(tabusz), pol(p)
1.389 + {
1.390 + pol.target(this);
1.391 + }
1.392 +
1.393 + /// \brief Destructor
1.394 + ~TabuSearch() {
1.395 + pol.target(NULL);
1.396 + }
1.397 +
1.398 + /// Set/Get the size of the tabu set
1.399 + void tabuSize( const unsigned int size )
1.400 + {
1.401 + if( size < 2 )
1.402 + throw BadParameterError( "Tabu size must be at least 2!" );
1.403 + mts = size;
1.404 + while( mts < tabu.size() )
1.405 + tabu.pop_back();
1.406 + }
1.407 +
1.408 + unsigned int tabuSize() const {
1.409 + return mts;
1.410 + }
1.411 +
1.412 + /// Set/Get Policy
1.413 + void policy( Policy p ) {
1.414 + pol.target(NULL);
1.415 + pol = p;
1.416 + pol.target(this);
1.417 + }
1.418 +
1.419 + Policy& policy() {
1.420 + return pol;
1.421 + }
1.422 +
1.423 + /// \name Execution control
1.424 + /// The simplest way to execute the algorithm is to use the member
1.425 + /// functions called \c run( 'startnode' ).
1.426 + ///@{
1.427 +
1.428 + /// \brief Initializes the internal data.
1.429 + ///
1.430 + /// \param startn The start node where the search begins.
1.431 + void init( const Node startn ) {
1.432 + tabu.clear();
1.433 + tabu.push_front( startn );
1.434 + b = startn;
1.435 + pol.reset();
1.436 + }
1.437 +
1.438 + /// \brief Does one iteration
1.439 + ///
1.440 + /// If the Policy allows it searches for the best next node, then steps
1.441 + /// onto it.
1.442 + /// \return %False if one Policy condition wants to stop the search.
1.443 + bool step()
1.444 + {
1.445 + ///Request premmision from ControllPolicy
1.446 + if( !pol.onStep() )
1.447 + return false;
1.448 +
1.449 + ///Find the best next potential node
1.450 + Node n; bool found = false;
1.451 + for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
1.452 + {
1.453 + Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
1.454 + bool wrong = false;
1.455 + for( int i = 1; i != (signed int)tabu.size(); ++i )
1.456 + if( m == tabu[i] ) {
1.457 + wrong = true;
1.458 + break;
1.459 + }
1.460 + if( wrong )
1.461 + continue;
1.462 +
1.463 + if( !found ) {
1.464 + n = m;
1.465 + found = true;
1.466 + } else
1.467 + if( better(height[m], height[n]) ) {
1.468 + n = m;
1.469 + }
1.470 + }
1.471 +
1.472 + ///Handle stuck search
1.473 + if( !found ) {
1.474 + return pol.onStick();
1.475 + }
1.476 +
1.477 + ///Move on...
1.478 + tabu.push_front(n);
1.479 + while( mts < tabu.size() ) {
1.480 + tabu.pop_back();
1.481 + }
1.482 + if( better(height[n], height[b]) ) {
1.483 + b = n;
1.484 + if( !pol.onImprove(height[b]) )
1.485 + return false;
1.486 + }
1.487 +
1.488 + return true;
1.489 + }
1.490 +
1.491 + /// \brief Runs a search while the Policy stops it.
1.492 + ///
1.493 + /// \param startn The start node where the search begins.
1.494 + inline void run( const Node startn ) {
1.495 + std::cin.unsetf( std::ios_base::skipws );
1.496 + char c;
1.497 + init( startn );
1.498 + while( step() )
1.499 + std::cin >> c;
1.500 + std::cin.setf( std::ios_base::skipws );
1.501 + }
1.502 +
1.503 + ///@}
1.504 +
1.505 + /// \name Query Functions
1.506 + /// The result of the TabuSearch algorithm can be obtained using these
1.507 + /// functions.\n
1.508 + ///@{
1.509 +
1.510 + /// \brief The node, the search is standing on.
1.511 + inline Node current() const {
1.512 + return tabu[0];
1.513 + }
1.514 +
1.515 + /// \brief The best node found until now.
1.516 + inline Node best() const {
1.517 + return b;
1.518 + }
1.519 +
1.520 + /// \brief Beginning to iterate on the current tabu set.
1.521 + inline TabuIterator tabu_begin() const {
1.522 + return tabu.begin();
1.523 + }
1.524 +
1.525 + /// \brief Ending to iterate on the current tabu set.
1.526 + inline TabuIterator tabu_end() const {
1.527 + return tabu.end();
1.528 + }
1.529 +
1.530 + ///@}
1.531 + };
1.532 +}
1.533 +#endif