COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 1000:7f4d07047ed8

Last change on this file since 1000:7f4d07047ed8 was 1000:7f4d07047ed8, checked in by Akos Ladanyi, 16 years ago

Some comments and minor additions to the AdvancedController?.

File size: 5.4 KB
Line 
1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
3
4#include <cstdlib>
5#include <cmath>
6#include <sys/time.h>
7
8namespace lemon {
9
10  const double INFTY = 1e24;
11
12  class SimAnnBase {
13  public:
14    class Controller;
15  private:
16    Controller *controller;
17  protected:
18    double curr_cost;
19    double prev_cost;
20    double best_cost;
21
22    virtual void mutate() = 0;
23    virtual void revert() = 0;
24    virtual void saveAsBest() = 0;
25  public:
26    SimAnnBase() {
27      curr_cost = prev_cost = best_cost = INFTY;
28    }
29    void setController(Controller &_controller) {
30      controller = &_controller;
31      controller->setBase(this);
32    }
33    double getCurrCost() { return curr_cost; }
34    double getPrevCost() { return prev_cost; }
35    double getBestCost() { return best_cost; }
36    void run() {
37      controller->init();
38      while (controller->next()) {
39        mutate();
40        if (controller->accept()) {
41          controller->acceptEvent();
42          if (curr_cost < best_cost) {
43            saveAsBest();
44            controller->improveEvent();
45          }
46        }
47        else {
48          revert();
49          controller->rejectEvent();
50        }
51      }
52    }
53
54    /*! \brief A base class for controllers. */
55    class Controller {
56    public:
57      SimAnnBase *base;
58      virtual void init() {}
59      /*! \brief This is called when a neighbouring state gets accepted. */
60      virtual void acceptEvent() {}
61      /*! \brief This is called when the accepted neighbouring state's cost is
62       *  less than the best found one's.
63       */
64      virtual void improveEvent() {}
65      /*! \brief This is called when a neighbouring state gets rejected. */
66      virtual void rejectEvent() {}
67      virtual void setBase(SimAnnBase *_base) { base = _base; }
68      /*! */
69      virtual bool next() = 0;
70      /*! */
71      virtual bool accept() = 0;
72    };
73  };
74
75  template <typename E>
76  class SimAnn : public SimAnnBase {
77  private:
78    E *curr_ent;
79    E *best_ent;
80  public:
81    SimAnn() : SimAnnBase() {}
82    void setEntity(E &ent) {
83      curr_ent = new E(ent);
84      best_ent = new E(ent);
85    }
86    E getBestEntity() { return *best_ent; }
87    void mutate() {
88      curr_ent->mutate();
89    }
90    void revert() {
91      curr_ent->revert();
92    }
93    void saveAsBest() {
94      *best_ent = *curr_ent;
95      best_cost = curr_cost;
96    }
97  };
98
99  class EntitySkeleton {
100  public:
101    /*! \brief Makes a minor change to the entity.
102     *  \return the new cost
103     */
104    double mutate() { return 0.0; }
105    /*! \brief Restores the entity to its previous state i.e. reverts the
106     *  effects of the last mutate.
107     */
108    void revert() {}
109  };
110
111  /*! \brief A simple controller for the simulated annealing class.
112   *  \todo Find a way to set the various parameters.
113   */
114  class SimpleController : public SimAnnBase::Controller {
115  public:
116    long iter, last_impr, max_iter, max_no_impr;
117    double temp, ann_fact;
118    /*! \param _max_iter maximum number of iterations
119     *  \param _max_no_impr maximum number of consecutive iterations which do
120     *         not yield a better solution
121     *  \param _temp initial temperature
122     *  \param _ann_fact annealing factor
123     */
124    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
125    double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0),
126    max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
127    ann_fact(_ann_fact) {}
128    void acceptEvent() {
129      iter++;
130    }
131    void improveEvent() {
132      last_impr = iter;
133    }
134    void rejectEvent() {
135      iter++;
136    }
137    bool next() {
138      temp *= ann_fact;
139      bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
140      return !quit;
141    }
142    bool accept() {
143      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
144        temp));
145    }
146  };
147
148  /*! \brief A controller with preset running time for the simulated annealing
149   *  class.
150   *  \todo Find a better name.
151   */
152  class AdvancedController : public SimAnnBase::Controller {
153  private:
154    /*! \param time the elapsed time in seconds */
155    double threshold(double time) { return 0.0; }
156  public:
157    double alpha, beta, gamma;
158    double end_time, start_time;
159    double avg_cost;
160    double temp, ann_fact;
161    /*! \param _end_time running_time
162     *  \param _alpha parameter used to calculate the running average
163     *  \param _beta parameter used to decrease the annealing factor
164     *  \param _gamma parameter used to increase the temperature
165     */
166    AdvancedController(double _end_time, double _alpha = 0.2,
167    double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
168    gamma(_gamma), end_time(_end_time) {}
169    void init() {
170      timeval tv;
171      gettimeofday(&tv, 0);
172      start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;
173    }
174    void acceptEvent() {
175      avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
176    }
177    void improveEvent() {
178    }
179    void rejectEvent() {
180    }
181    bool next() {
182      timeval tv;
183      gettimeofday(&tv, 0);
184      double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
185      if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
186        // decrease the annealing factor
187        ann_fact *= beta;
188      }
189      else {
190        // increase the temperature
191        temp *= gamma;
192      }
193      temp *= ann_fact;
194      return elapsed_time < end_time;
195    }
196    bool accept() {
197      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
198        temp));
199    }
200  };
201
202}
203
204#endif
Note: See TracBrowser for help on using the repository browser.