COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 2118:54350d5c316a

Last change on this file since 2118:54350d5c316a was 2035:e92071fadd3f, checked in by Balazs Dezso, 14 years ago

More mingw compatibility

Implementation of the drand48 functions

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