COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/simann.h @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2370:ed6539025f27, checked in by Balazs Dezso, 13 years ago

Some documentation changes

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