COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/tabu_search.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

File size: 13.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_TABU_SEARCH_H
20#define LEMON_TABU_SEARCH_H
21
22/// \ingroup metah
23/// \file
24/// \brief TabuSearch algorithm.
25///
26/// \author Szabadkai Mark
27
28#include <lemon/bits/utility.h>
29#include <lemon/error.h>
30#include <lemon/time_measure.h>
31#include <functional>
32#include <deque>
33
34
35namespace lemon {
36
37  /// \brief Default Traits for TabuSearch class.
38  ///
39  /// This template defines the needed types for the \ref TabuSearch class.
40  /// Is main purpos is to simplify the main class's template interface,
41  /// but it provides the EdgeIt type, passing to the concrete graph wheter
42  /// it is directed or undirected.
43#ifdef DOXYGEN
44  template< typename GRAPH, typename VALUE,
45            typename HEIGHTMAP, typename BETTER, bool UNDIR >
46#else
47  template< typename GRAPH, typename VALUE,
48            typename HEIGHTMAP = typename GRAPH::template NodeMap<VALUE>,
49            typename BETTER = std::less<VALUE>,
50            bool UNDIR = UndirectedTagIndicator<GRAPH>::value >
51#endif
52  struct TabuSearchDefaultTraits {
53    typedef  VALUE  Value;
54    typedef  BETTER  Better;
55
56    typedef  GRAPH  Graph;
57    typedef  typename GRAPH::Node  Node;
58    typedef  HEIGHTMAP  HeightMap;
59
60    typedef  typename GRAPH::IncEdgeIt  EdgeIt;
61  };
62
63  template< typename GRAPH, typename VALUE,
64            typename HEIGHTMAP, typename BETTER >
65  struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
66    typedef  VALUE  Value;
67    typedef  BETTER  Better;
68
69    typedef  GRAPH  Graph;
70    typedef  typename GRAPH::Node  Node;
71    typedef  HEIGHTMAP  HeightMap;
72
73    typedef  typename GRAPH::OutEdgeIt  EdgeIt;
74  };
75
76
77
78  /// \brief Policy hierarchy to controll the search algorithm.
79  ///
80  /// The fallowing template hierarchy offers a clean interface to define own
81  /// policies, and combine existing ones.
82  template< typename TS >
83  struct TabuSearchPolicyConcept {
84    void  target( TS *ts ) {}
85
86    void  reset()  {}
87    bool  onStep() { return false; }
88    bool  onStick() { return false; }
89    bool  onImprove( const typename TS::Value &best ) { return false; }
90  };
91
92  template< typename TS >
93  struct YesPolicy {
94    void  target( TS *ts ) {}
95
96    void  reset()  {}
97    bool  onStep() { return true; }
98    bool  onStick() { return true; }
99    bool  onImprove( const typename TS::Value &best ) { return true; }
100  };
101
102  template< typename TS >
103  struct NoPolicy : public TabuSearchPolicyConcept<TS> {};
104
105  /// \brief Some basic methode, how tow Policies can be combined
106  struct PolicyAndCombination {
107    static bool  evaluate( const bool r1, const bool r2 ) {
108      return r1 && r2;
109    }
110  };
111
112  struct PolicyOrCombination {
113    static bool  evaluate( const bool r1, const bool r2 ) {
114      return r1 || r2;
115    }
116  };
117
118  /// \brief CombinePolicies
119  ///
120  /// It combines tow policies using the given combination methode (mainly
121  /// some of the basic logical methodes) to create a new one.
122#ifdef DOXYGEN
123  template< template<typename> class CP1, template<typename> class CP2,
124            typename COMBINATION >
125#else
126  template< template<typename> class CP1, template<typename> class CP2,
127            typename COMBINATION = PolicyAndCombination >
128#endif
129  struct CombinePolicies {
130    template< typename TS >
131    struct Policy {
132      typedef CP1<TS>  Policy1;
133      typedef CP2<TS>  Policy2;
134     
135      Policy1  policy1;
136      Policy2  policy2;
137
138      inline Policy() : policy1(), policy2() {}
139      inline Policy( const Policy1 &cp1, const Policy2 &cp2 )
140        : policy1(cp1), policy2(cp2) {}
141
142      void  target( TS *ts ) {
143        policy1.target(ts), policy2.target(ts);
144      };
145
146      void  reset() {
147        policy1.reset(), policy2.reset();
148      }
149
150      bool  onStep() {
151        return cmb.evaluate( policy1.onStep(), policy2.onStep() );
152      }
153
154      bool  onStick() {
155        return cmb.evaluate( policy1.onStick(), policy2.onStick() );
156      }
157
158      bool  onImprove( const typename TS::Value &best ) {
159        return cmb.evaluate( policy1.onImprove(best),
160                             policy2.onImprove(best) );
161      }
162
163    private:
164      COMBINATION cmb;
165    };
166  };
167
168
169  /// \brief IterationPolicy limits the number of iterations and the
170  /// number of iterations without improvement
171  template< typename TS >
172  struct IterationPolicy {
173    IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {}
174    IterationPolicy( const long int itl, const long int noimpritl )
175      : _it_lim(itl), _noimpr_it_lim(noimpritl)
176    {}
177
178    void  target( TS *ts ) {}
179
180    void  reset() {
181      _it = _noimpr_it = 0;
182    }
183
184    bool  onStep() {
185      ++_it; ++_noimpr_it;
186      return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
187    }
188               
189    bool  onStick() {
190      return false;
191    }
192
193    bool  onImprove( const typename TS::Value &best ) {
194      _noimpr_it = 0;
195      return true;
196    }
197
198    long int  iterationLimit() const {
199      return _it_lim;
200    }
201
202    void  iterationLimit( const long int itl ) {
203      _it_lim = itl;
204    }
205
206    long int  noImprovementIterationLimit() const {
207      return _noimpr_it_lim;
208    }
209
210    void  noImprovementIterationLimit( const long int noimpritl ) {
211      _noimpr_it_lim = noimpritl;
212    }
213
214  private:
215    long int  _it_lim, _noimpr_it_lim;
216    long int  _it, _noimpr_it;
217  };
218
219  /// \brief HeightPolicy stops the search when a given height is reached or
220  /// exceeds
221  template< typename TS >
222  struct HeightPolicy {
223    typedef typename TS::Value  Value;
224
225    HeightPolicy() : _height_lim(), _found(false) {}
226    HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}
227
228    void  target( TS *ts ) {}
229
230    void  reset() {
231      _found = false;
232    }
233
234    bool  onStep() {
235      return !_found;
236    }
237
238    bool  onStick() {
239      return false;
240    }
241
242    bool  onImprove( const Value &best ) {
243      typename TS::Better  better;
244      _found = better(best, _height_lim) || (best == _height_lim);
245      return !_found;
246    }
247
248    Value  heightLimi() const {
249      return _height_lim;
250    }
251
252    void  heightLimi( const Value &hl ) {
253      _height_lim = hl;
254    }
255
256  private:
257    Value  _height_lim;
258    bool  _found;
259  };
260
261  /// \brief TimePolicy limits the time for searching.
262  template< typename TS >
263  struct TimePolicy {
264    TimePolicy() : _time_lim(60.0), _timeisup(false) {}
265    TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}
266
267    void  target( TS *ts ) {}
268
269    void  reset() {
270      _timeisup = false;
271      _t.reset();
272    }
273
274    bool  onStep() {
275      update();
276      return !_timeisup;
277    }
278
279    bool  onStick() {
280      return false;
281    }
282
283    bool  onImprove( const typename TS::Value &best ) {
284      update();
285      return !_timeisup;
286    }
287
288    double timeLimit() const {
289      return _time_lim;
290    }
291
292    void  setTimeLimit( const double tl ) {
293      _time_lim = tl;
294      update();
295    }
296
297  private:
298    lemon::Timer  _t;
299    double  _time_lim;
300    bool  _timeisup;
301
302    inline void  update() {
303      _timeisup = _t.realTime() > _time_lim;
304    }
305  };
306
307
308
309  /// \ingroup metah
310  ///
311  /// \brief TabuSearch main class
312  ///
313  /// This class offers the implementation of tabu-search algorithm. The
314  /// tabu-serach is a local-search. It starts from a specified point of the
315  /// problem's graph representation, and in every step it goes to the localy
316  /// best next Node except those in tabu set. The maximum size of this tabu
317  /// set defines how many Node will be remembered. The best Node ever found
318  /// will also stored, so we wont lose it, even is the search continues.
319  /// The class can be used on any kind of Graph and with any kind of Value
320  /// with a total-settlement on it.
321  ///
322  /// \param _Graph The graph type the algorithm runs on.
323  /// \param _Value The values' type associated to the nodes.
324  /// \param _Policy Controlls the search. Determinates when to stop, or how
325  /// manage stuck search. Default value is \ref IterationPolicy .
326  /// \param _Traits Collection of needed types. Default value is
327  /// \ref TabuSearchDefaultTraits .
328  ///
329  /// \author Szabadkai Mark
330#ifdef DOXYGEN
331  template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
332#else
333  template< typename GRAPH, typename VALUE,
334            template<typename> class POLICY = IterationPolicy,
335            typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
336#endif
337  class TabuSearch
338  {
339  public:
340
341    /// \brief Thrown by setting the size of the tabu-set and the given size
342    /// is less than 2.
343    class BadParameterError : public lemon::LogicError {
344    public:
345      virtual const char* what() const throw() {
346        return "lemon::TabuSearch::BadParameterError";
347      }
348    };
349
350    ///Public types
351    typedef  TabuSearch<GRAPH,VALUE,POLICY,TRAITS>  SelfType;
352
353    typedef  typename TRAITS::Graph  Graph;
354    typedef  typename TRAITS::Node  Node;
355    typedef  typename TRAITS::Value  Value;
356    typedef  typename TRAITS::HeightMap  HeightMap;
357    typedef  typename TRAITS::Better  Better;
358    typedef  typename std::deque< Node >::const_iterator  TabuIterator;
359
360    typedef  POLICY<SelfType>  Policy;
361
362  protected:
363    typedef  typename TRAITS::EdgeIt  EdgeIt;
364
365    const Graph  &gr;
366    const HeightMap  &height;
367    /// The tabu set. Teh current node is the first
368    std::deque< Node >  tabu;
369    /// Maximal tabu size
370    unsigned int  mts;
371    /// The best Node found
372    Node  b;
373
374    Better  better;
375    Policy  pol;
376
377  public:
378    /// \brief Constructor
379    ///
380    /// \param graph the graph the algorithm will run on.
381    /// \param hm the height map used by the algorithm.
382    /// \param tabusz the maximal size of the tabu set. Default value is 3
383    /// \param p the Policy controlling the search.
384    TabuSearch( const Graph &graph, const HeightMap &hm,
385                const int tabusz = 3, Policy p = Policy() )
386      : gr(graph), height(hm), mts(tabusz), pol(p)
387    {
388      pol.target(this);
389    }
390
391    /// \brief Destructor
392    ~TabuSearch() {
393      pol.target(NULL);
394    }
395
396    /// Set/Get the size of the tabu set
397    void  tabuSize( const unsigned int size )
398    {
399      if( size < 2 )
400      throw BadParameterError( "Tabu size must be at least 2!" );
401      mts = size;
402      while( mts < tabu.size() )
403      tabu.pop_back();
404    }
405
406    unsigned int  tabuSize() const {
407      return mts;
408    }
409
410    /// Set/Get Policy
411    void  policy( Policy p ) {
412      pol.target(NULL);
413      pol = p;
414      pol.target(this);
415    }
416               
417    Policy& policy()  {
418      return pol;
419    }
420
421    /// \name Execution control
422    /// The simplest way to execute the algorithm is to use the member
423    /// functions called \c run( 'startnode' ).
424    ///@{
425
426    /// \brief Initializes the internal data.
427    ///
428    /// \param startn The start node where the search begins.
429    void  init( const Node startn ) {
430      tabu.clear();
431      tabu.push_front( startn );
432      b = startn;
433      pol.reset();
434    }
435
436    /// \brief Does one iteration
437    ///
438    /// If the Policy allows it searches for the best next node, then steps
439    /// onto it.
440    /// \return %False if one Policy condition wants to stop the search.
441    bool  step()
442    {
443      ///Request premmision from ControllPolicy
444      if( !pol.onStep() )
445      return false;
446       
447      ///Find the best next potential node
448      Node n; bool found = false;
449      for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
450      {
451        Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
452        bool wrong = false;
453        for( int i = 1; i != (signed int)tabu.size(); ++i )
454          if( m == tabu[i] ) {
455            wrong = true;
456            break;
457          }
458        if( wrong )
459          continue;
460
461        if( !found ) {
462          n = m;
463          found = true;
464        } else
465          if( better(height[m], height[n]) ) {
466            n = m;
467          }
468      }
469
470      ///Handle stuck search
471      if( !found ) {
472        return pol.onStick();
473      }
474
475      ///Move on...
476      tabu.push_front(n);
477      while( mts < tabu.size() ) {
478        tabu.pop_back();
479      }
480      if( better(height[n], height[b]) ) {
481        b = n;
482        if( !pol.onImprove(height[b]) )
483        return false;
484      }
485
486      return true;
487    }
488
489    /// \brief Runs a search while the Policy stops it.
490    ///
491    /// \param startn The start node where the search begins.
492    inline void  run( const Node startn ) {
493      std::cin.unsetf( std::ios_base::skipws );
494      char c;
495      init( startn );
496      while( step() )
497      std::cin >> c;
498      std::cin.setf( std::ios_base::skipws );
499    }
500
501    ///@}
502
503    /// \name Query Functions
504    /// The result of the TabuSearch algorithm can be obtained using these
505    /// functions.\n
506    ///@{
507
508    /// \brief The node, the search is standing on.
509    inline Node  current() const {
510      return tabu[0];
511    }
512
513    /// \brief The best node found until now.
514    inline Node  best() const {
515      return b;
516    }
517
518    /// \brief Beginning to iterate on the current tabu set.
519    inline TabuIterator  tabu_begin() const {
520      return tabu.begin();
521    }
522
523    /// \brief Ending to iterate on the current tabu set.
524    inline TabuIterator  tabu_end() const {
525      return tabu.end();
526    }
527
528    ///@}
529  };
530}
531#endif
Note: See TracBrowser for help on using the repository browser.