COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/tabu_search.h @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2370:ed6539025f27, checked in by Balazs Dezso, 13 years ago

Some documentation changes

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