COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 1633:4bc163d55528

Last change on this file since 1633:4bc163d55528 was 1633:4bc163d55528, checked in by Alpar Juttner, 14 years ago

Move simann.h to trunk/lemon

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