COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 1933:a876a3d6a4c7

Last change on this file since 1933:a876a3d6a4c7 was 1932:c65711e5a26d, checked in by Balazs Dezso, 14 years ago

Bug fix
friend does not declares type

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