COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 1978:ef2d00e46897

Last change on this file since 1978:ef2d00e46897 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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