COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 1874:396831fa7012

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