COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 2349:c945f577a66d

Last change on this file since 2349:c945f577a66d was 2304:108d6db4f32a, checked in by Akos Ladanyi, 17 years ago

Doc fix.

File size: 12.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_SIMANN_H
20#define LEMON_SIMANN_H
21
22/// \ingroup experimental
23/// \file
24/// \brief Simulated annealing framework.
25///
26/// \todo A test and some demo should be added
27/// \todo Doc should be improved
28/// \author Akos Ladanyi
29
30#include <cstdlib>
31#include <cmath>
32#include <limits>
33#include <lemon/time_measure.h>
34#include <lemon/random.h>
35
36namespace lemon {
37
38/// \addtogroup experimental
39/// @{
40
41  class SimAnnBase;
42
43  /// \brief A base class for controllers.
44  class ControllerBase {
45  public:
46    friend class SimAnnBase;
47    /// \brief Pointer to the simulated annealing base class.
48    SimAnnBase *simann;
49    /// \brief Initializes the controller.
50    virtual void init() {}
51    /// \brief This is called by the simulated annealing class when a
52    /// neighbouring state gets accepted.
53    virtual void acceptEvent() {}
54    /// \brief This is called by the simulated annealing class when the
55    /// accepted neighbouring state's cost is less than the best found one's.
56    virtual void improveEvent() {}
57    /// \brief This is called by the simulated annealing class when a
58    /// neighbouring state gets rejected.
59    virtual void rejectEvent() {}
60    /// \brief Decides whether to continue the annealing process or not.
61    virtual bool next() = 0;
62    /// \brief Decides whether to accept the current solution or not.
63    virtual bool accept() = 0;
64    /// \brief Destructor.
65    virtual ~ControllerBase() {}
66  };
67
68  /// \brief Skeleton of an entity class.
69  class EntityBase {
70  public:
71    /// \brief Makes a minor change to the entity.
72    /// \return the new cost
73    virtual double mutate() = 0;
74    /// \brief Restores the entity to its previous state i.e. reverts the
75    /// effects of the last mutate().
76    virtual void revert() = 0;
77    /// \brief Makes a copy of the entity.
78    virtual EntityBase* clone() = 0;
79    /// \brief Makes a major change to the entity.
80    virtual void randomize() = 0;
81    /// \brief Destructor.
82    virtual ~EntityBase() {}
83  };
84
85  /// \brief Simulated annealing abstract base class.
86  ///
87  /// Can be used to derive a custom simulated annealing class if \ref SimAnn
88  /// doesn't fit your needs.
89  class SimAnnBase {
90  private:
91    /// \brief Pointer to the controller.
92    ControllerBase *controller;
93    /// \brief Cost of the current solution.
94    double curr_cost;
95    /// \brief Cost of the best solution.
96    double best_cost;
97    /// \brief Cost of the previous solution.
98    double prev_cost;
99    /// \brief Cost of the solution preceding the previous one.
100    double prev_prev_cost;
101    /// \brief Number of iterations.
102    long iter;
103    /// \brief Number of iterations which did not improve the solution since
104    /// the last improvement.
105    long last_impr;
106  protected:
107    /// \brief Step to a neighbouring state.
108    virtual double mutate() = 0;
109    /// \brief Reverts the last mutate().
110    virtual void revert() = 0;
111    /// \brief Saves the current solution as the best one.
112    virtual void saveAsBest() = 0;
113    /// \brief Does initializations before each run.
114    virtual void init() {
115      controller->init();
116      curr_cost = prev_cost = prev_prev_cost = best_cost =
117        std::numeric_limits<double>::infinity();
118      iter = last_impr = 0;
119    }
120  public:
121    /// \brief Sets the controller class to use.
122    void setController(ControllerBase &_controller) {
123      controller = &_controller;
124      controller->simann = this;
125    }
126    /// \brief Returns the cost of the current solution.
127    double getCurrCost() const { return curr_cost; }
128    /// \brief Returns the cost of the previous solution.
129    double getPrevCost() const { return prev_cost; }
130    /// \brief Returns the cost of the best solution.
131    double getBestCost() const { return best_cost; }
132    /// \brief Returns the number of iterations done.
133    long getIter() const { return iter; }
134    /// \brief Returns the ordinal number of the last iteration when the
135    /// solution was improved.
136    long getLastImpr() const { return last_impr; }
137    /// \brief Performs one iteration.
138    bool step() {
139      iter++;
140      prev_prev_cost = prev_cost;
141      prev_cost = curr_cost;
142      curr_cost = mutate();
143      if (controller->accept()) {
144        controller->acceptEvent();
145        last_impr = iter;
146        if (curr_cost < best_cost) {
147          best_cost = curr_cost;
148          saveAsBest();
149          controller->improveEvent();
150        }
151      }
152      else {
153        revert();
154        curr_cost = prev_cost;
155        prev_cost = prev_prev_cost;
156        controller->rejectEvent();
157      }
158      return controller->next();
159    }
160    /// \brief Performs a given number of iterations.
161    /// \param n the number of iterations
162    bool step(int n) {
163      for(; n > 0 && step(); --n) ;
164      return !n;
165    }
166    /// \brief Starts the annealing process.
167    void run() {
168      init();
169      do { } while (step());
170    }
171    /// \brief Destructor.
172    virtual ~SimAnnBase() {}
173  };
174
175  /// \brief Simulated annealing class.
176  class SimAnn : public SimAnnBase {
177  private:
178    /// \brief Pointer to the current entity.
179    EntityBase *curr_ent;
180    /// \brief Pointer to the best entity.
181    EntityBase *best_ent;
182    /// \brief Does initializations before each run.
183    void init() {
184      SimAnnBase::init();
185      if (best_ent) delete best_ent;
186      best_ent = NULL;
187      curr_ent->randomize();
188    }
189  public:
190    /// \brief Constructor.
191    SimAnn() : curr_ent(NULL), best_ent(NULL) {}
192    /// \brief Destructor.
193    virtual ~SimAnn() {
194      if (best_ent) delete best_ent;
195    }
196    /// \brief Step to a neighbouring state.
197    double mutate() {
198      return curr_ent->mutate();
199    }
200    /// \brief Reverts the last mutate().
201    void revert() {
202      curr_ent->revert();
203    }
204    /// \brief Saves the current solution as the best one.
205    void saveAsBest() {
206      if (best_ent) delete best_ent;
207      best_ent = curr_ent->clone();
208    }
209    /// \brief Sets the current entity.
210    void setEntity(EntityBase &_ent) {
211      curr_ent = &_ent;
212    }
213    /// \brief Returns a copy of the best found entity.
214    EntityBase* getBestEntity() { return best_ent->clone(); }
215  };
216
217  /// \brief A simple controller for the simulated annealing class.
218  ///
219  /// This controller starts from a given initial temperature and evenly
220  /// decreases it.
221  class SimpleController : public ControllerBase {
222  private:
223    /// \brief Maximum number of iterations.
224    long max_iter;
225    /// \brief Maximum number of iterations which do not improve the
226    /// solution.
227    long max_no_impr;
228    /// \brief Temperature.
229    double temp;
230    /// \brief Annealing factor.
231    double ann_fact;
232    /// \brief Constructor.
233    /// \param _max_iter maximum number of iterations
234    /// \param _max_no_impr maximum number of consecutive iterations which do
235    ///        not yield a better solution
236    /// \param _temp initial temperature
237    /// \param _ann_fact annealing factor
238  public:
239    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
240    double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
241      max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
242    {
243    }
244    /// \brief This is called when a neighbouring state gets accepted.
245    void acceptEvent() {}
246    /// \brief This is called when the accepted neighbouring state's cost is
247    /// less than the best found one's.
248    void improveEvent() {}
249    /// \brief This is called when a neighbouring state gets rejected.
250    void rejectEvent() {}
251    /// \brief Decides whether to continue the annealing process or not. Also
252    /// decreases the temperature.
253    bool next() {
254      temp *= ann_fact;
255      bool quit = (simann->getIter() > max_iter) ||
256        (simann->getIter() - simann->getLastImpr() > max_no_impr);
257      return !quit;
258    }
259    /// \brief Decides whether to accept the current solution or not.
260    bool accept() {
261      double cost_diff = simann->getCurrCost() - simann->getPrevCost();
262      return (rnd() <= exp(-(cost_diff / temp)));
263    }
264    /// \brief Destructor.
265    virtual ~SimpleController() {}
266  };
267
268  /// \brief A controller with preset running time for the simulated annealing
269  /// class.
270  ///
271  /// With this controller you can set the running time of the annealing
272  /// process in advance. It works the following way: the controller measures
273  /// a kind of divergence. The divergence is the difference of the average
274  /// cost of the recently found solutions the cost of the best found one. In
275  /// case this divergence is greater than a given threshold, then we decrease
276  /// the annealing factor, that is we cool the system faster. In case the
277  /// divergence is lower than the threshold, then we increase the temperature.
278  /// The threshold is a function of the elapsed time which reaches zero at the
279  /// desired end time.
280  class AdvancedController : public ControllerBase {
281  private:
282    /// \brief Timer class to measure the elapsed time.
283    Timer timer;
284    /// \brief Calculates the threshold value.
285    /// \param time the elapsed time in seconds
286    virtual double threshold(double time) {
287      return (-1.0) * start_threshold / end_time * time + start_threshold;
288    }
289    /// \brief Parameter used to calculate the running average.
290    double alpha;
291    /// \brief Parameter used to decrease the annealing factor.
292    double beta;
293    /// \brief Parameter used to increase the temperature.
294    double gamma;
295    /// \brief The time at the end of the algorithm.
296    double end_time;
297    /// \brief The time at the start of the algorithm.
298    double start_time;
299    /// \brief Starting threshold.
300    double start_threshold;
301    /// \brief Average cost of recent solutions.
302    double avg_cost;
303    /// \brief Temperature.
304    double temp;
305    /// \brief Annealing factor.
306    double ann_fact;
307    /// \brief Initial annealing factor.
308    double init_ann_fact;
309    /// \brief True when the annealing process has been started.
310    bool start;
311  public:
312    /// \brief Constructor.
313    /// \param _end_time running time in seconds
314    /// \param _alpha parameter used to calculate the running average
315    /// \param _beta parameter used to decrease the annealing factor
316    /// \param _gamma parameter used to increase the temperature
317    /// \param _ann_fact initial annealing factor
318    AdvancedController(double _end_time, double _alpha = 0.2,
319    double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
320    alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
321    ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
322    {
323    }
324    /// \brief Does initializations before each run.
325    void init() {
326      avg_cost = simann->getCurrCost();
327    }
328    /// \brief This is called when a neighbouring state gets accepted.
329    void acceptEvent() {
330      avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
331      if (!start) {
332        static int cnt = 0;
333        cnt++;
334        if (cnt >= 100) {
335          // calculate starting threshold and starting temperature
336          start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
337          temp = 10000.0;
338          start = true;
339          timer.restart();
340        }
341      }
342    }
343    /// \brief Decides whether to continue the annealing process or not.
344    bool next() {
345      if (!start) {
346        return true;
347      }
348      else {
349        double elapsed_time = timer.realTime();
350        if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
351          // decrease the annealing factor
352          ann_fact *= beta;
353        }
354        else {
355          // increase the temperature
356          temp *= gamma;
357          // reset the annealing factor
358          ann_fact = init_ann_fact;
359        }
360        temp *= ann_fact;
361        return elapsed_time < end_time;
362      }
363    }
364    /// \brief Decides whether to accept the current solution or not.
365    bool accept() {
366      if (!start) {
367        return true;
368      }
369      else {
370        double cost_diff = simann->getCurrCost() - simann->getPrevCost();
371        return (rnd() <= exp(-(cost_diff / temp)));
372      }
373    }
374    /// \brief Destructor.
375    virtual ~AdvancedController() {}
376  };
377
378/// @}
379
380}
381
382#endif
Note: See TracBrowser for help on using the repository browser.