COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 1022:567f392d1d2e

Last change on this file since 1022:567f392d1d2e was 1018:68beae6758a7, checked in by Akos Ladanyi, 20 years ago

Use lemon::Timer for time measuring. Added the threshold() function and initial threshold and temperature calculation.

File size: 6.9 KB
Line 
1#ifndef LEMON_SIMANN_H
2#define LEMON_SIMANN_H
3
4#include <cstdlib>
5#include <cmath>
6#include <lemon/time_measure.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() const { return curr_cost; }
34    double getPrevCost() const { return prev_cost; }
35    double getBestCost() const { return best_cost; }
36    void run() {
37      controller->init();
38      do {
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      } while (controller->next());
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  /*! \todo atgondolni mi is ez a prev_cost */
76  template <typename E>
77  class SimAnn : public SimAnnBase {
78  private:
79    E *curr_ent;
80    E *best_ent;
81  public:
82    SimAnn() : SimAnnBase() {}
83    void setEntity(E &ent) {
84      curr_ent = new E(ent);
85      best_ent = new E(ent);
86    }
87    E getBestEntity() { return *best_ent; }
88    void mutate() {
89      prev_cost = curr_cost;
90      curr_cost = curr_ent->mutate();
91    }
92    void revert() {
93      curr_ent->revert();
94      curr_cost = prev_cost;
95    }
96    void saveAsBest() {
97      *best_ent = *curr_ent;
98      best_cost = curr_cost;
99    }
100  };
101
102  class EntitySkeleton {
103  public:
104    /*! \brief Makes a minor change to the entity.
105     *  \return the new cost
106     */
107    double mutate() { return 0.0; }
108    /*! \brief Restores the entity to its previous state i.e. reverts the
109     *  effects of the last mutate.
110     */
111    void revert() {}
112  };
113
114  /*! \brief A simple controller for the simulated annealing class.
115   *  \todo Find a way to set the various parameters.
116   */
117  class SimpleController : public SimAnnBase::Controller {
118  public:
119    long iter, last_impr, max_iter, max_no_impr;
120    double temp, ann_fact;
121    /*! \param _max_iter maximum number of iterations
122     *  \param _max_no_impr maximum number of consecutive iterations which do
123     *         not yield a better solution
124     *  \param _temp initial temperature
125     *  \param _ann_fact annealing factor
126     */
127    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
128    double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0),
129    max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
130    ann_fact(_ann_fact) {}
131    void acceptEvent() {
132      iter++;
133    }
134    void improveEvent() {
135      last_impr = iter;
136    }
137    void rejectEvent() {
138      iter++;
139    }
140    bool next() {
141      temp *= ann_fact;
142      bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
143      return !quit;
144    }
145    bool accept() {
146      double cost_diff = base->getPrevCost() - base->getCurrCost();
147      if (cost_diff < 0.0) {
148        return (drand48() <= exp(cost_diff / temp));
149      }
150      else {
151        return true;
152      }
153    }
154  };
155
156  /*! \brief A controller with preset running time for the simulated annealing
157   *  class.
158   *  \todo Find a better name.
159   */
160  class AdvancedController : public SimAnnBase::Controller {
161  private:
162    Timer timer;
163    /*! \param time the elapsed time in seconds */
164    virtual double threshold(double time) {
165      // this is the function 1 / log(x) scaled and offset
166      static double xm = 5.0 / end_time;
167      static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
168      return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
169    }
170  public:
171    double alpha, beta, gamma;
172    double end_time, start_time;
173    double start_threshold;
174    double avg_cost;
175    double temp, ann_fact;
176    bool warmup;
177    long iter;
178    /*! \param _end_time running time in seconds
179     *  \param _alpha parameter used to calculate the running average
180     *  \param _beta parameter used to decrease the annealing factor
181     *  \param _gamma parameter used to increase the temperature
182     */
183    AdvancedController(double _end_time, double _alpha = 0.2,
184    double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
185    gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true),
186    iter(0) {}
187    void init() {
188      avg_cost = base->getCurrCost();
189    }
190    void acceptEvent() {
191      avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
192      iter++;
193    }
194    void improveEvent() {
195    }
196    void rejectEvent() {
197      iter++;
198    }
199    bool next() {
200      if (warmup) {
201        static double max_cost_diff = 0.0;
202        double cost_diff = base->getCurrCost() - base->getPrevCost();
203        // jo ez igy egyaltalan? -> prev_cost
204        if ((cost_diff > 0.0) && (cost_diff > max_cost_diff)) {
205          max_cost_diff = cost_diff;
206        }
207        // How to set the starting temperature when all the 100 first
208        // iterations improve the solution?
209        if (iter > 100) {
210          // calculate starting threshold and starting temperature
211          start_threshold = fabs(base->getBestCost() - avg_cost);
212          temp = exp(max_cost_diff) / 0.5;
213          warmup = false;
214          timer.reset();
215        }
216        return true;
217      }
218      else {
219        double elapsed_time = timer.getRealTime();
220        if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
221          // decrease the annealing factor
222          ann_fact *= beta;
223        }
224        else {
225          // increase the temperature
226          temp *= gamma;
227        }
228        temp *= ann_fact;
229        return elapsed_time < end_time;
230      }
231    }
232    bool accept() {
233      if (warmup) {
234        // we accept eveything during the "warm up" phase
235        return true;
236      }
237      else {
238        double cost_diff = base->getPrevCost() - base->getCurrCost();
239        if (cost_diff < 0.0) {
240          return (drand48() <= exp(cost_diff / temp));
241        }
242        else {
243          return true;
244        }
245      }
246    }
247  };
248
249}
250
251#endif
Note: See TracBrowser for help on using the repository browser.