- Gamma distributon random variable.
- Test file for random.h
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_TABU_SEARCH_H
20 #define LEMON_TABU_SEARCH_H
24 /// \brief TabuSearch algorithm.
26 /// \author Szabadkai Mark
28 #include <lemon/bits/utility.h>
29 #include <lemon/error.h>
30 #include <lemon/time_measure.h>
37 /// \brief Default Traits for TabuSearch class.
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.
44 template< typename GRAPH, typename VALUE,
45 typename HEIGHTMAP, typename BETTER, bool UNDIR >
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 >
52 struct TabuSearchDefaultTraits {
54 typedef BETTER Better;
57 typedef typename GRAPH::Node Node;
58 typedef HEIGHTMAP HeightMap;
60 typedef typename GRAPH::IncEdgeIt EdgeIt;
63 template< typename GRAPH, typename VALUE,
64 typename HEIGHTMAP, typename BETTER >
65 struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
67 typedef BETTER Better;
70 typedef typename GRAPH::Node Node;
71 typedef HEIGHTMAP HeightMap;
73 typedef typename GRAPH::OutEdgeIt EdgeIt;
78 /// \brief Policy hierarchy to controll the search algorithm.
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 ) {}
87 bool onStep() { return false; }
88 bool onStick() { return false; }
89 bool onImprove( const typename TS::Value &best ) { return false; }
92 template< typename TS >
94 void target( TS *ts ) {}
97 bool onStep() { return true; }
98 bool onStick() { return true; }
99 bool onImprove( const typename TS::Value &best ) { return true; }
102 template< typename TS >
103 struct NoPolicy : public TabuSearchPolicyConcept<TS> {};
105 /// \brief Some basic methode, how tow Policies can be combined
106 struct PolicyAndCombination {
107 static bool evaluate( const bool r1, const bool r2 ) {
112 struct PolicyOrCombination {
113 static bool evaluate( const bool r1, const bool r2 ) {
118 /// \brief CombinePolicies
120 /// It combines tow policies using the given combination methode (mainly
121 /// some of the basic logical methodes) to create a new one.
123 template< template<typename> class CP1, template<typename> class CP2,
124 typename COMBINATION >
126 template< template<typename> class CP1, template<typename> class CP2,
127 typename COMBINATION = PolicyAndCombination >
129 struct CombinePolicies {
130 template< typename TS >
132 typedef CP1<TS> Policy1;
133 typedef CP2<TS> Policy2;
138 inline Policy() : policy1(), policy2() {}
139 inline Policy( const Policy1 &cp1, const Policy2 &cp2 )
140 : policy1(cp1), policy2(cp2) {}
142 void target( TS *ts ) {
143 policy1.target(ts), policy2.target(ts);
147 policy1.reset(), policy2.reset();
151 return cmb.evaluate( policy1.onStep(), policy2.onStep() );
155 return cmb.evaluate( policy1.onStick(), policy2.onStick() );
158 bool onImprove( const typename TS::Value &best ) {
159 return cmb.evaluate( policy1.onImprove(best),
160 policy2.onImprove(best) );
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)
178 void target( TS *ts ) {}
181 _it = _noimpr_it = 0;
186 return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
193 bool onImprove( const typename TS::Value &best ) {
198 long int iterationLimit() const {
202 void iterationLimit( const long int itl ) {
206 long int noImprovementIterationLimit() const {
207 return _noimpr_it_lim;
210 void noImprovementIterationLimit( const long int noimpritl ) {
211 _noimpr_it_lim = noimpritl;
215 long int _it_lim, _noimpr_it_lim;
216 long int _it, _noimpr_it;
219 /// \brief HeightPolicy stops the search when a given height is reached or
221 template< typename TS >
222 struct HeightPolicy {
223 typedef typename TS::Value Value;
225 HeightPolicy() : _height_lim(), _found(false) {}
226 HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}
228 void target( TS *ts ) {}
242 bool onImprove( const Value &best ) {
243 typename TS::Better better;
244 _found = better(best, _height_lim) || (best == _height_lim);
248 Value heightLimi() const {
252 void heightLimi( const Value &hl ) {
261 /// \brief TimePolicy limits the time for searching.
262 template< typename TS >
264 TimePolicy() : _time_lim(60.0), _timeisup(false) {}
265 TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}
267 void target( TS *ts ) {}
283 bool onImprove( const typename TS::Value &best ) {
288 double timeLimit() const {
292 void setTimeLimit( const double tl ) {
302 inline void update() {
303 _timeisup = _t.realTime() > _time_lim;
311 /// \brief TabuSearch main class
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.
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 .
329 /// \author Szabadkai Mark
331 template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
333 template< typename GRAPH, typename VALUE,
334 template<typename> class POLICY = IterationPolicy,
335 typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
341 /// \brief Thrown by setting the size of the tabu-set and the given size
343 class BadParameterError : public lemon::LogicError {
345 virtual const char* what() const throw() {
346 return "lemon::TabuSearch::BadParameterError";
351 typedef TabuSearch<GRAPH,VALUE,POLICY,TRAITS> SelfType;
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;
360 typedef POLICY<SelfType> Policy;
363 typedef typename TRAITS::EdgeIt EdgeIt;
366 const HeightMap &height;
367 /// The tabu set. Teh current node is the first
368 std::deque< Node > tabu;
369 /// Maximal tabu size
371 /// The best Node found
378 /// \brief Constructor
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)
391 /// \brief Destructor
396 /// Set/Get the size of the tabu set
397 void tabuSize( const unsigned int size )
400 throw BadParameterError( "Tabu size must be at least 2!" );
402 while( mts < tabu.size() )
406 unsigned int tabuSize() const {
411 void policy( Policy p ) {
421 /// \name Execution control
422 /// The simplest way to execute the algorithm is to use the member
423 /// functions called \c run( 'startnode' ).
426 /// \brief Initializes the internal data.
428 /// \param startn The start node where the search begins.
429 void init( const Node startn ) {
431 tabu.push_front( startn );
436 /// \brief Does one iteration
438 /// If the Policy allows it searches for the best next node, then steps
440 /// \return %False if one Policy condition wants to stop the search.
443 ///Request premmision from ControllPolicy
447 ///Find the best next potential node
448 Node n; bool found = false;
449 for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
451 Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
453 for( int i = 1; i != (signed int)tabu.size(); ++i )
465 if( better(height[m], height[n]) ) {
470 ///Handle stuck search
472 return pol.onStick();
477 while( mts < tabu.size() ) {
480 if( better(height[n], height[b]) ) {
482 if( !pol.onImprove(height[b]) )
489 /// \brief Runs a search while the Policy stops it.
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 );
498 std::cin.setf( std::ios_base::skipws );
503 /// \name Query Functions
504 /// The result of the TabuSearch algorithm can be obtained using these
508 /// \brief The node, the search is standing on.
509 inline Node current() const {
513 /// \brief The best node found until now.
514 inline Node best() const {
518 /// \brief Beginning to iterate on the current tabu set.
519 inline TabuIterator tabu_begin() const {
523 /// \brief Ending to iterate on the current tabu set.
524 inline TabuIterator tabu_end() const {