COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/akos/simann.h @ 1173:099978eee03f

Last change on this file since 1173:099978eee03f was 1150:c20bcf71efe3, checked in by Alpar Juttner, 20 years ago

Minor changes.

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