1.1 --- a/lemon/Makefile.am Thu Apr 27 13:10:23 2006 +0000
1.2 +++ b/lemon/Makefile.am Thu Apr 27 14:53:23 2006 +0000
1.3 @@ -78,6 +78,7 @@
1.4 simann.h \
1.5 smart_graph.h \
1.6 sub_graph.h \
1.7 + tabu_search.h \
1.8 time_measure.h \
1.9 topology.h \
1.10 ugraph_adaptor.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/tabu_search.h Thu Apr 27 14:53:23 2006 +0000
2.3 @@ -0,0 +1,530 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +
2.23 +#ifndef LEMON_TABU_SEARCH_H
2.24 +#define LEMON_TABU_SEARCH_H
2.25 +
2.26 +/// \ingroup experimental
2.27 +/// \file
2.28 +/// \brief TabuSearch algorithm.
2.29 +///
2.30 +/// \author Szabadkai Mark
2.31 +
2.32 +#include <lemon/bits/utility.h>
2.33 +#include <lemon/error.h>
2.34 +#include <lemon/time_measure.h>
2.35 +#include <functional>
2.36 +#include <deque>
2.37 +
2.38 +
2.39 +namespace lemon {
2.40 +
2.41 + /// \brief Default Traits for TabuSearch class.
2.42 + ///
2.43 + /// This template defines the needed types for the \ref TabuSearch class.
2.44 + /// Is main purpos is to simplify the main class's template interface,
2.45 + /// but it provides the EdgeIt type, passing to the concrete graph wheter
2.46 + /// it is directed or undirected.
2.47 +#ifdef DOXYGEN
2.48 + template< typename GRAPH, typename VALUE,
2.49 + typename HEIGHTMAP, typename BETTER, bool UNDIR >
2.50 +#else
2.51 + template< typename GRAPH, typename VALUE,
2.52 + typename HEIGHTMAP = typename GRAPH::template NodeMap<VALUE>,
2.53 + typename BETTER = std::less<VALUE>,
2.54 + bool UNDIR = UndirectedTagIndicator<GRAPH>::value >
2.55 +#endif
2.56 + struct TabuSearchDefaultTraits {
2.57 + typedef VALUE Value;
2.58 + typedef BETTER Better;
2.59 +
2.60 + typedef GRAPH Graph;
2.61 + typedef typename GRAPH::Node Node;
2.62 + typedef HEIGHTMAP HeightMap;
2.63 +
2.64 + typedef typename GRAPH::IncEdgeIt EdgeIt;
2.65 + };
2.66 +
2.67 + template< typename GRAPH, typename VALUE,
2.68 + typename HEIGHTMAP, typename BETTER >
2.69 + struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
2.70 + typedef VALUE Value;
2.71 + typedef BETTER Better;
2.72 +
2.73 + typedef GRAPH Graph;
2.74 + typedef typename GRAPH::Node Node;
2.75 + typedef HEIGHTMAP HeightMap;
2.76 +
2.77 + typedef typename GRAPH::OutEdgeIt EdgeIt;
2.78 + };
2.79 +
2.80 +
2.81 +
2.82 + /// \brief Policy hierarchy to controll the search algorithm.
2.83 + ///
2.84 + /// The fallowing template hierarchy offers a clean interface to define own
2.85 + /// policies, and combine existing ones.
2.86 + template< typename TS >
2.87 + struct TabuSearchPolicyConcept {
2.88 + void target( TS *ts ) {}
2.89 +
2.90 + void reset() {}
2.91 + bool onStep() { return false; }
2.92 + bool onStick() { return false; }
2.93 + bool onImprove( const typename TS::Value &best ) { return false; }
2.94 + };
2.95 +
2.96 + template< typename TS >
2.97 + struct YesPolicy {
2.98 + void target( TS *ts ) {}
2.99 +
2.100 + void reset() {}
2.101 + bool onStep() { return true; }
2.102 + bool onStick() { return true; }
2.103 + bool onImprove( const typename TS::Value &best ) { return true; }
2.104 + };
2.105 +
2.106 + template< typename TS >
2.107 + struct NoPolicy : public TabuSearchPolicyConcept<TS> {};
2.108 +
2.109 + /// \brief Some basic methode, how tow Policies can be combined
2.110 + struct PolicyAndCombination {
2.111 + static bool evaluate( const bool r1, const bool r2 ) {
2.112 + return r1 && r2;
2.113 + }
2.114 + };
2.115 +
2.116 + struct PolicyOrCombination {
2.117 + static bool evaluate( const bool r1, const bool r2 ) {
2.118 + return r1 || r2;
2.119 + }
2.120 + };
2.121 +
2.122 + /// \brief CombinePolicies
2.123 + ///
2.124 + /// It combines tow policies using the given combination methode (mainly
2.125 + /// some of the basic logical methodes) to create a new one.
2.126 +#ifdef DOXYGEN
2.127 + template< template<typename> class CP1, template<typename> class CP2,
2.128 + typename COMBINATION >
2.129 +#else
2.130 + template< template<typename> class CP1, template<typename> class CP2,
2.131 + typename COMBINATION = PolicyAndCombination >
2.132 +#endif
2.133 + struct CombinePolicies {
2.134 + template< typename TS >
2.135 + struct Policy {
2.136 + typedef CP1<TS> Policy1;
2.137 + typedef CP2<TS> Policy2;
2.138 +
2.139 + Policy1 policy1;
2.140 + Policy2 policy2;
2.141 +
2.142 + inline Policy() : policy1(), policy2() {}
2.143 + inline Policy( const Policy1 &cp1, const Policy2 &cp2 )
2.144 + : policy1(cp1), policy2(cp2) {}
2.145 +
2.146 + void target( TS *ts ) {
2.147 + policy1.target(ts), policy2.target(ts);
2.148 + };
2.149 +
2.150 + void reset() {
2.151 + policy1.reset(), policy2.reset();
2.152 + }
2.153 +
2.154 + bool onStep() {
2.155 + return cmb.evaluate( policy1.onStep(), policy2.onStep() );
2.156 + }
2.157 +
2.158 + bool onStick() {
2.159 + return cmb.evaluate( policy1.onStick(), policy2.onStick() );
2.160 + }
2.161 +
2.162 + bool onImprove( const typename TS::Value &best ) {
2.163 + return cmb.evaluate( policy1.onImprove(best),
2.164 + policy2.onImprove(best) );
2.165 + }
2.166 +
2.167 + private:
2.168 + COMBINATION cmb;
2.169 + };
2.170 + };
2.171 +
2.172 +
2.173 + /// \brief IterationPolicy limits the number of iterations and the
2.174 + /// number of iterations without improvement
2.175 + template< typename TS >
2.176 + struct IterationPolicy {
2.177 + IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {}
2.178 + IterationPolicy( const long int itl, const long int noimpritl )
2.179 + : _it_lim(itl), _noimpr_it_lim(noimpritl)
2.180 + {}
2.181 +
2.182 + void target( TS *ts ) {}
2.183 +
2.184 + void reset() {
2.185 + _it = _noimpr_it = 0;
2.186 + }
2.187 +
2.188 + bool onStep() {
2.189 + ++_it; ++_noimpr_it;
2.190 + return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
2.191 + }
2.192 +
2.193 + bool onStick() {
2.194 + return false;
2.195 + }
2.196 +
2.197 + bool onImprove( const typename TS::Value &best ) {
2.198 + _noimpr_it = 0;
2.199 + return true;
2.200 + }
2.201 +
2.202 + long int iterationLimit() const {
2.203 + return _it_lim;
2.204 + }
2.205 +
2.206 + void iterationLimit( const long int itl ) {
2.207 + _it_lim = itl;
2.208 + }
2.209 +
2.210 + long int noImprovementIterationLimit() const {
2.211 + return _noimpr_it_lim;
2.212 + }
2.213 +
2.214 + void noImprovementIterationLimit( const long int noimpritl ) {
2.215 + _noimpr_it_lim = noimpritl;
2.216 + }
2.217 +
2.218 + private:
2.219 + long int _it_lim, _noimpr_it_lim;
2.220 + long int _it, _noimpr_it;
2.221 + };
2.222 +
2.223 + /// \brief HeightPolicy stops the search when a given height is reached or
2.224 + /// exceeds
2.225 + template< typename TS >
2.226 + struct HeightPolicy {
2.227 + typedef typename TS::Value Value;
2.228 +
2.229 + HeightPolicy() : _height_lim(), _found(false) {}
2.230 + HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}
2.231 +
2.232 + void target( TS *ts ) {}
2.233 +
2.234 + void reset() {
2.235 + _found = false;
2.236 + }
2.237 +
2.238 + bool onStep() {
2.239 + return !_found;
2.240 + }
2.241 +
2.242 + bool onStick() {
2.243 + return false;
2.244 + }
2.245 +
2.246 + bool onImprove( const Value &best ) {
2.247 + typename TS::Better better;
2.248 + _found = better(best, _height_lim) || (best == _height_lim);
2.249 + return !_found;
2.250 + }
2.251 +
2.252 + Value heightLimi() const {
2.253 + return _height_lim;
2.254 + }
2.255 +
2.256 + void heightLimi( const Value &hl ) {
2.257 + _height_lim = hl;
2.258 + }
2.259 +
2.260 + private:
2.261 + Value _height_lim;
2.262 + bool _found;
2.263 + };
2.264 +
2.265 + /// \brief TimePolicy limits the time for searching.
2.266 + template< typename TS >
2.267 + struct TimePolicy {
2.268 + TimePolicy() : _time_lim(60.0), _timeisup(false) {}
2.269 + TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}
2.270 +
2.271 + void target( TS *ts ) {}
2.272 +
2.273 + void reset() {
2.274 + _timeisup = false;
2.275 + _t.reset();
2.276 + }
2.277 +
2.278 + bool onStep() {
2.279 + update();
2.280 + return !_timeisup;
2.281 + }
2.282 +
2.283 + bool onStick() {
2.284 + return false;
2.285 + }
2.286 +
2.287 + bool onImprove( const typename TS::Value &best ) {
2.288 + update();
2.289 + return !_timeisup;
2.290 + }
2.291 +
2.292 + double timeLimit() const {
2.293 + return _time_lim;
2.294 + }
2.295 +
2.296 + void setTimeLimit( const double tl ) {
2.297 + _time_lim = tl;
2.298 + update();
2.299 + }
2.300 +
2.301 + private:
2.302 + lemon::Timer _t;
2.303 + double _time_lim;
2.304 + bool _timeisup;
2.305 +
2.306 + inline void update() {
2.307 + _timeisup = _t.realTime() > _time_lim;
2.308 + }
2.309 + };
2.310 +
2.311 +
2.312 +
2.313 + /// \brief TabuSearch main class
2.314 + ///
2.315 + /// This class offers the implementation of tabu-search algorithm. The
2.316 + /// tabu-serach is a local-search. It starts from a specified point of the
2.317 + /// problem's graph representation, and in every step it goes to the localy
2.318 + /// best next Node except those in tabu set. The maximum size of this tabu
2.319 + /// set defines how many Node will be remembered. The best Node ever found
2.320 + /// will also stored, so we wont lose it, even is the search continues.
2.321 + /// The class can be used on any kind of Graph and with any kind of Value
2.322 + /// with a total-settlement on it.
2.323 + ///
2.324 + /// \param _Graph The graph type the algorithm runs on.
2.325 + /// \param _Value The values' type associated to the nodes.
2.326 + /// \param _Policy Controlls the search. Determinates when to stop, or how
2.327 + /// manage stuck search. Default value is \ref IterationPolicy .
2.328 + /// \param _Traits Collection of needed types. Default value is
2.329 + /// \ref TabuSearchDefaultTraits .
2.330 + ///
2.331 + /// \author Szabadkai Mark
2.332 +#ifdef DOXYGEN
2.333 + template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
2.334 +#else
2.335 + template< typename GRAPH, typename VALUE,
2.336 + template<typename> class POLICY = IterationPolicy,
2.337 + typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
2.338 +#endif
2.339 + class TabuSearch
2.340 + {
2.341 + public:
2.342 +
2.343 + /// \brief Thrown by setting the size of the tabu-set and the given size
2.344 + /// is less than 2.
2.345 + class BadParameterError : public lemon::LogicError {
2.346 + public:
2.347 + virtual const char* exceptionName() const {
2.348 + return "lemon::TabuSearch::BadParameterError";
2.349 + }
2.350 + };
2.351 +
2.352 + ///Public types
2.353 + typedef TabuSearch<GRAPH,VALUE,POLICY,TRAITS> SelfType;
2.354 +
2.355 + typedef typename TRAITS::Graph Graph;
2.356 + typedef typename TRAITS::Node Node;
2.357 + typedef typename TRAITS::Value Value;
2.358 + typedef typename TRAITS::HeightMap HeightMap;
2.359 + typedef typename TRAITS::Better Better;
2.360 + typedef typename std::deque< Node >::const_iterator TabuIterator;
2.361 +
2.362 + typedef POLICY<SelfType> Policy;
2.363 +
2.364 + protected:
2.365 + typedef typename TRAITS::EdgeIt EdgeIt;
2.366 +
2.367 + const Graph &gr;
2.368 + const HeightMap &height;
2.369 + /// The tabu set. Teh current node is the first
2.370 + std::deque< Node > tabu;
2.371 + /// Maximal tabu size
2.372 + unsigned int mts;
2.373 + /// The best Node found
2.374 + Node b;
2.375 +
2.376 + Better better;
2.377 + Policy pol;
2.378 +
2.379 + public:
2.380 + /// \brief Constructor
2.381 + ///
2.382 + /// \param graph the graph the algorithm will run on.
2.383 + /// \param hm the height map used by the algorithm.
2.384 + /// \param tabusz the maximal size of the tabu set. Default value is 3
2.385 + /// \param p the Policy controlling the search.
2.386 + TabuSearch( const Graph &graph, const HeightMap &hm,
2.387 + const int tabusz = 3, Policy p = Policy() )
2.388 + : gr(graph), height(hm), mts(tabusz), pol(p)
2.389 + {
2.390 + pol.target(this);
2.391 + }
2.392 +
2.393 + /// \brief Destructor
2.394 + ~TabuSearch() {
2.395 + pol.target(NULL);
2.396 + }
2.397 +
2.398 + /// Set/Get the size of the tabu set
2.399 + void tabuSize( const unsigned int size )
2.400 + {
2.401 + if( size < 2 )
2.402 + throw BadParameterError( "Tabu size must be at least 2!" );
2.403 + mts = size;
2.404 + while( mts < tabu.size() )
2.405 + tabu.pop_back();
2.406 + }
2.407 +
2.408 + unsigned int tabuSize() const {
2.409 + return mts;
2.410 + }
2.411 +
2.412 + /// Set/Get Policy
2.413 + void policy( Policy p ) {
2.414 + pol.target(NULL);
2.415 + pol = p;
2.416 + pol.target(this);
2.417 + }
2.418 +
2.419 + Policy& policy() {
2.420 + return pol;
2.421 + }
2.422 +
2.423 + /// \name Execution control
2.424 + /// The simplest way to execute the algorithm is to use the member
2.425 + /// functions called \c run( 'startnode' ).
2.426 + ///@{
2.427 +
2.428 + /// \brief Initializes the internal data.
2.429 + ///
2.430 + /// \param startn The start node where the search begins.
2.431 + void init( const Node startn ) {
2.432 + tabu.clear();
2.433 + tabu.push_front( startn );
2.434 + b = startn;
2.435 + pol.reset();
2.436 + }
2.437 +
2.438 + /// \brief Does one iteration
2.439 + ///
2.440 + /// If the Policy allows it searches for the best next node, then steps
2.441 + /// onto it.
2.442 + /// \return %False if one Policy condition wants to stop the search.
2.443 + bool step()
2.444 + {
2.445 + ///Request premmision from ControllPolicy
2.446 + if( !pol.onStep() )
2.447 + return false;
2.448 +
2.449 + ///Find the best next potential node
2.450 + Node n; bool found = false;
2.451 + for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
2.452 + {
2.453 + Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
2.454 + bool wrong = false;
2.455 + for( int i = 1; i != (signed int)tabu.size(); ++i )
2.456 + if( m == tabu[i] ) {
2.457 + wrong = true;
2.458 + break;
2.459 + }
2.460 + if( wrong )
2.461 + continue;
2.462 +
2.463 + if( !found ) {
2.464 + n = m;
2.465 + found = true;
2.466 + } else
2.467 + if( better(height[m], height[n]) ) {
2.468 + n = m;
2.469 + }
2.470 + }
2.471 +
2.472 + ///Handle stuck search
2.473 + if( !found ) {
2.474 + return pol.onStick();
2.475 + }
2.476 +
2.477 + ///Move on...
2.478 + tabu.push_front(n);
2.479 + while( mts < tabu.size() ) {
2.480 + tabu.pop_back();
2.481 + }
2.482 + if( better(height[n], height[b]) ) {
2.483 + b = n;
2.484 + if( !pol.onImprove(height[b]) )
2.485 + return false;
2.486 + }
2.487 +
2.488 + return true;
2.489 + }
2.490 +
2.491 + /// \brief Runs a search while the Policy stops it.
2.492 + ///
2.493 + /// \param startn The start node where the search begins.
2.494 + inline void run( const Node startn ) {
2.495 + std::cin.unsetf( std::ios_base::skipws );
2.496 + char c;
2.497 + init( startn );
2.498 + while( step() )
2.499 + std::cin >> c;
2.500 + std::cin.setf( std::ios_base::skipws );
2.501 + }
2.502 +
2.503 + ///@}
2.504 +
2.505 + /// \name Query Functions
2.506 + /// The result of the TabuSearch algorithm can be obtained using these
2.507 + /// functions.\n
2.508 + ///@{
2.509 +
2.510 + /// \brief The node, the search is standing on.
2.511 + inline Node current() const {
2.512 + return tabu[0];
2.513 + }
2.514 +
2.515 + /// \brief The best node found until now.
2.516 + inline Node best() const {
2.517 + return b;
2.518 + }
2.519 +
2.520 + /// \brief Beginning to iterate on the current tabu set.
2.521 + inline TabuIterator tabu_begin() const {
2.522 + return tabu.begin();
2.523 + }
2.524 +
2.525 + /// \brief Ending to iterate on the current tabu set.
2.526 + inline TabuIterator tabu_end() const {
2.527 + return tabu.end();
2.528 + }
2.529 +
2.530 + ///@}
2.531 + };
2.532 +}
2.533 +#endif