COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 1920:e9e27c5a53bf

Last change on this file since 1920:e9e27c5a53bf was 1918:09415ae11103, checked in by Akos Ladanyi, 14 years ago

more doc

File size: 11.9 KB
Line 
1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
3
4/// \ingroup experimental
5/// \file
6/// \brief Simulated annealing framework.
7///
8/// \todo A test and some demo should be added
9/// \todo Doc should be improved
10/// \author Akos Ladanyi
11
12#include <cstdlib>
13#include <cmath>
14#include <limits>
15#include <lemon/time_measure.h>
16
17namespace lemon {
18
19/// \addtogroup experimental
20/// @{
21
22  /// \brief A base class for controllers.
23  class ControllerBase {
24  public:
25    friend class SimAnnBase;
26    /// \brief Pointer to the simulated annealing base class.
27    SimAnnBase *simann;
28    /// \brief Initializes the controller.
29    virtual void init() {}
30    /// \brief This is called by the simulated annealing class when a
31    /// neighbouring state gets accepted.
32    virtual void acceptEvent() {}
33    /// \brief This is called by the simulated annealing class when the
34    /// accepted neighbouring state's cost is less than the best found one's.
35    virtual void improveEvent() {}
36    /// \brief This is called by the simulated annealing class when a
37    /// neighbouring state gets rejected.
38    virtual void rejectEvent() {}
39    /// \brief Decides whether to continue the annealing process or not.
40    virtual bool next() = 0;
41    /// \brief Decides whether to accept the current solution or not.
42    virtual bool accept() = 0;
43    /// \brief Destructor.
44    virtual ~ControllerBase() {}
45  };
46
47  /// \brief Skeleton of an entity class.
48  class EntityBase {
49  public:
50    /// \brief Makes a minor change to the entity.
51    /// \return the new cost
52    virtual double mutate() = 0;
53    /// \brief Restores the entity to its previous state i.e. reverts the
54    /// effects of the last mutate().
55    virtual void revert() = 0;
56    /// \brief Makes a copy of the entity.
57    virtual EntityBase* clone() = 0;
58    /// \brief Makes a major change to the entity.
59    virtual void randomize() = 0;
60    /// \brief Destructor.
61    virtual ~EntityBase() {}
62  };
63
64  /// \brief Simulated annealing abstract base class.
65  /// Can be used to derive a custom simulated annealing class if \ref SimAnn
66  /// doesn't fit your needs.
67  class SimAnnBase {
68  private:
69    /// \brief Pointer to the controller.
70    ControllerBase *controller;
71    /// \brief Cost of the current solution.
72    double curr_cost;
73    /// \brief Cost of the best solution.
74    double best_cost;
75    /// \brief Cost of the previous solution.
76    double prev_cost;
77    /// \brief Cost of the solution preceding the previous one.
78    double prev_prev_cost;
79    /// \brief Number of iterations.
80    long iter;
81    /// \brief Number of iterations which did not improve the solution since
82    /// the last improvement.
83    long last_impr;
84  protected:
85    /// \brief Step to a neighbouring state.
86    virtual double mutate() = 0;
87    /// \brief Reverts the last mutate().
88    virtual void revert() = 0;
89    /// \brief Saves the current solution as the best one.
90    virtual void saveAsBest() = 0;
91    /// \brief Does initializations before each run.
92    virtual void init() {
93      controller->init();
94      curr_cost = prev_cost = prev_prev_cost = best_cost =
95        std::numeric_limits<double>::infinity();
96      iter = last_impr = 0;
97    }
98  public:
99    /// \brief Sets the controller class to use.
100    void setController(ControllerBase &_controller) {
101      controller = &_controller;
102      controller->simann = this;
103    }
104    /// \brief Returns the cost of the current solution.
105    double getCurrCost() const { return curr_cost; }
106    /// \brief Returns the cost of the previous solution.
107    double getPrevCost() const { return prev_cost; }
108    /// \brief Returns the cost of the best solution.
109    double getBestCost() const { return best_cost; }
110    /// \brief Returns the number of iterations done.
111    long getIter() const { return iter; }
112    /// \brief Returns the ordinal number of the last iteration when the
113    /// solution was improved.
114    long getLastImpr() const { return last_impr; }
115    /// \brief Performs one iteration.
116    bool step() {
117      iter++;
118      prev_prev_cost = prev_cost;
119      prev_cost = curr_cost;
120      curr_cost = mutate();
121      if (controller->accept()) {
122        controller->acceptEvent();
123        last_impr = iter;
124        if (curr_cost < best_cost) {
125          best_cost = curr_cost;
126          saveAsBest();
127          controller->improveEvent();
128        }
129      }
130      else {
131        revert();
132        curr_cost = prev_cost;
133        prev_cost = prev_prev_cost;
134        controller->rejectEvent();
135      }
136      return controller->next();
137    }
138    /// \brief Performs a given number of iterations.
139    /// \param n the number of iterations
140    bool step(int n) {
141      for(; n > 0 && step(); --n) ;
142      return !n;
143    }
144    /// \brief Starts the annealing process.
145    void run() {
146      init();
147      do { } while (step());
148    }
149    /// \brief Destructor.
150    virtual ~SimAnnBase() {}
151  };
152
153  /// \brief Simulated annealing class.
154  class SimAnn : public SimAnnBase {
155  private:
156    /// \brief Pointer to the current entity.
157    EntityBase *curr_ent;
158    /// \brief Pointer to the best entity.
159    EntityBase *best_ent;
160    /// \brief Does initializations before each run.
161    void init() {
162      SimAnnBase::init();
163      if (best_ent) delete best_ent;
164      best_ent = NULL;
165      curr_ent->randomize();
166    }
167  public:
168    /// \brief Constructor.
169    SimAnn() : curr_ent(NULL), best_ent(NULL) {}
170    /// \brief Destructor.
171    virtual ~SimAnn() {
172      if (best_ent) delete best_ent;
173    }
174    /// \brief Step to a neighbouring state.
175    double mutate() {
176      return curr_ent->mutate();
177    }
178    /// \brief Reverts the last mutate().
179    void revert() {
180      curr_ent->revert();
181    }
182    /// \brief Saves the current solution as the best one.
183    void saveAsBest() {
184      if (best_ent) delete best_ent;
185      best_ent = curr_ent->clone();
186    }
187    /// \brief Sets the current entity.
188    void setEntity(EntityBase &_ent) {
189      curr_ent = &_ent;
190    }
191    /// \brief Returns a copy of the best found entity.
192    EntityBase* getBestEntity() { return best_ent->clone(); }
193  };
194
195  /// \brief A simple controller for the simulated annealing class.
196  /// This controller starts from a given initial temperature and evenly
197  /// decreases it.
198  class SimpleController : public ControllerBase {
199  private:
200    /// \brief Maximum number of iterations.
201    long max_iter;
202    /// \brief Maximum number of iterations which do not improve the
203    /// solution.
204    long max_no_impr;
205    /// \brief Temperature.
206    double temp;
207    /// \brief Annealing factor.
208    double ann_fact;
209    /// \brief Constructor.
210    /// \param _max_iter maximum number of iterations
211    /// \param _max_no_impr maximum number of consecutive iterations which do
212    ///        not yield a better solution
213    /// \param _temp initial temperature
214    /// \param _ann_fact annealing factor
215  public:
216    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
217    double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
218      max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
219    {
220      srand48(time(0));
221    }
222    /// \brief This is called when a neighbouring state gets accepted.
223    void acceptEvent() {}
224    /// \brief This is called when the accepted neighbouring state's cost is
225    /// less than the best found one's.
226    void improveEvent() {}
227    /// \brief This is called when a neighbouring state gets rejected.
228    void rejectEvent() {}
229    /// \brief Decides whether to continue the annealing process or not. Also
230    /// decreases the temperature.
231    bool next() {
232      temp *= ann_fact;
233      bool quit = (simann->getIter() > max_iter) ||
234        (simann->getIter() - simann->getLastImpr() > max_no_impr);
235      return !quit;
236    }
237    /// \brief Decides whether to accept the current solution or not.
238    bool accept() {
239      double cost_diff = simann->getCurrCost() - simann->getPrevCost();
240      return (drand48() <= exp(-(cost_diff / temp)));
241    }
242    /// \brief Destructor.
243    virtual ~SimpleController() {}
244  };
245
246  /// \brief A controller with preset running time for the simulated annealing
247  /// class.
248  /// With this controller you can set the running time of the annealing
249  /// process in advance. It works the following way: the controller measures
250  /// a kind of divergence. The divergence is the difference of the average
251  /// cost of the recently found solutions the cost of the best found one. In
252  /// case this divergence is greater than a given threshold, then we decrease
253  /// the annealing factor, that is we cool the system faster. In case the
254  /// divergence is lower than the threshold, then we increase the temperature.
255  /// The threshold is a function of the elapsed time which reaches zero at the
256  /// desired end time.
257  class AdvancedController : public ControllerBase {
258  private:
259    /// \brief Timer class to measure the elapsed time.
260    Timer timer;
261    /// \brief Calculates the threshold value.
262    /// \param time the elapsed time in seconds
263    virtual double threshold(double time) {
264      return (-1.0) * start_threshold / end_time * time + start_threshold;
265    }
266    /// \brief Parameter used to calculate the running average.
267    double alpha;
268    /// \brief Parameter used to decrease the annealing factor.
269    double beta;
270    /// \brief Parameter used to increase the temperature.
271    double gamma;
272    /// \brief The time at the end of the algorithm.
273    double end_time;
274    /// \brief The time at the start of the algorithm.
275    double start_time;
276    /// \brief Starting threshold.
277    double start_threshold;
278    /// \brief Average cost of recent solutions.
279    double avg_cost;
280    /// \brief Temperature.
281    double temp;
282    /// \brief Annealing factor.
283    double ann_fact;
284    /// \brief Initial annealing factor.
285    double init_ann_fact;
286    /// \brief True when the annealing process has been started.
287    bool start;
288  public:
289    /// \brief Constructor.
290    /// \param _end_time running time in seconds
291    /// \param _alpha parameter used to calculate the running average
292    /// \param _beta parameter used to decrease the annealing factor
293    /// \param _gamma parameter used to increase the temperature
294    /// \param _ann_fact initial annealing factor
295    AdvancedController(double _end_time, double _alpha = 0.2,
296    double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
297    alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
298    ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
299    {
300      srand48(time(0));
301    }
302    /// \brief Does initializations before each run.
303    void init() {
304      avg_cost = simann->getCurrCost();
305    }
306    /// \brief This is called when a neighbouring state gets accepted.
307    void acceptEvent() {
308      avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
309      if (!start) {
310        static int cnt = 0;
311        cnt++;
312        if (cnt >= 100) {
313          // calculate starting threshold and starting temperature
314          start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
315          temp = 10000.0;
316          start = true;
317          timer.restart();
318        }
319      }
320    }
321    /// \brief Decides whether to continue the annealing process or not.
322    bool next() {
323      if (!start) {
324        return true;
325      }
326      else {
327        double elapsed_time = timer.realTime();
328        if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
329          // decrease the annealing factor
330          ann_fact *= beta;
331        }
332        else {
333          // increase the temperature
334          temp *= gamma;
335          // reset the annealing factor
336          ann_fact = init_ann_fact;
337        }
338        temp *= ann_fact;
339        return elapsed_time < end_time;
340      }
341    }
342    /// \brief Decides whether to accept the current solution or not.
343    bool accept() {
344      if (!start) {
345        return true;
346      }
347      else {
348        double cost_diff = simann->getCurrCost() - simann->getPrevCost();
349        return (drand48() <= exp(-(cost_diff / temp)));
350      }
351    }
352    /// \brief Destructor.
353    virtual ~AdvancedController() {}
354  };
355
356/// @}
357
358}
359
360#endif
Note: See TracBrowser for help on using the repository browser.