diff -r 93ac8c521fe5 -r 4bc163d55528 lemon/simann.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/simann.h	Tue Aug 16 20:17:43 2005 +0000
@@ -0,0 +1,348 @@
+#ifndef LEMON_SIMANN_H
+#define LEMON_SIMANN_H
+
+/// \ingroup experimental
+/// \file
+/// \brief Simulated annealing framework.
+/// \author Akos Ladanyi
+
+#include <cstdlib>
+#include <cmath>
+#include <lemon/time_measure.h>
+
+namespace lemon {
+
+/// \addtogroup experimental
+/// @{
+
+  /*! \brief A base class for controllers. */
+  class ControllerBase {
+    friend class SimAnnBase;
+  public:
+    /*! \brief Pointer to the simulated annealing base class. */
+    SimAnnBase *simann;
+    /*! \brief Initializes the controller. */
+    virtual void init() {}
+    /*! \brief This is called when a neighbouring state gets accepted. */
+    virtual void acceptEvent() {}
+    /*! \brief This is called when the accepted neighbouring state's cost is
+     *  less than the best found one's.
+     */
+    virtual void improveEvent() {}
+    /*! \brief This is called when a neighbouring state gets rejected. */
+    virtual void rejectEvent() {}
+    /*! \brief Decides whether to continue the annealing process or not. */
+    virtual bool next() = 0;
+    /*! \brief Decides whether to accept the current solution or not. */
+    virtual bool accept() = 0;
+  };
+
+  /*! \brief Skeleton of an entity class. */
+  class EntityBase {
+  public:
+    /*! \brief Makes a minor change to the entity.
+     *  \return the new cost
+     */
+    virtual double mutate() = 0;
+    /*! \brief Restores the entity to its previous state i.e. reverts the
+     *  effects of the last mutate().
+     */
+    virtual void revert() = 0;
+    /*! \brief Makes a copy of the entity. */
+    virtual EntityBase* clone() = 0;
+    /*! \brief Makes a major change to the entity. */
+    virtual void randomize() = 0;
+  };
+
+  /*! \brief Simulated annealing base class. */
+  class SimAnnBase {
+  private:
+    /*! Pointer to the controller. */
+    ControllerBase *controller;
+    /*! \brief Cost of the current solution. */
+    double curr_cost;
+    /*! \brief Cost of the best solution. */
+    double best_cost;
+    /*! \brief Cost of the previous solution. */
+    double prev_cost;
+    /*! \brief Cost of the solution preceding the previous one. */
+    double prev_prev_cost;
+    /*! \brief Number of iterations. */
+    long iter;
+    /*! \brief Number of iterations which did not improve the solution since
+     *  the last improvement. */
+    long last_impr;
+  protected:
+    /*! \brief Step to a neighbouring state. */
+    virtual double mutate() = 0;
+    /*! \brief Reverts the last mutate(). */
+    virtual void revert() = 0;
+    /*! \brief Saves the current solution as the best one. */
+    virtual void saveAsBest() = 0;
+    /*! \brief Does initializations before each run. */
+    virtual void init() {
+      controller->init();
+      curr_cost = prev_cost = prev_prev_cost = best_cost =
+        std::numeric_limits<double>::infinity();
+      iter = last_impr = 0;
+    }
+  public:
+    /*! \brief Sets the controller class to use. */
+    void setController(ControllerBase &_controller) {
+      controller = &_controller;
+      controller->simann = this;
+    }
+    /*! \brief Returns the cost of the current solution. */
+    double getCurrCost() const { return curr_cost; }
+    /*! \brief Returns the cost of the previous solution. */
+    double getPrevCost() const { return prev_cost; }
+    /*! \brief Returns the cost of the best solution. */
+    double getBestCost() const { return best_cost; }
+    /*! \brief Returns the number of iterations. */
+    long getIter() const { return iter; }
+    /*! \brief Returns the number of the last iteration when the solution was
+     *  improved.
+     */
+    long getLastImpr() const { return last_impr; }
+    /*! \brief Performs one iteration. */
+    bool step() {
+      iter++;
+      prev_prev_cost = prev_cost;
+      prev_cost = curr_cost;
+      curr_cost = mutate();
+      if (controller->accept()) {
+        controller->acceptEvent();
+        last_impr = iter;
+        if (curr_cost < best_cost) {
+          best_cost = curr_cost;
+          saveAsBest();
+          controller->improveEvent();
+        }
+      }
+      else {
+        revert();
+        curr_cost = prev_cost;
+        prev_cost = prev_prev_cost;
+        controller->rejectEvent();
+      }
+      return controller->next();
+    }
+    /*! \brief Performs a given number of iterations.
+     *  \param n the number of iterations
+     */
+    bool step(int n) {
+      for(; n > 0 && step(); --n) ;
+      return !n;
+    }
+    /*! \brief Starts the annealing process. */
+    void run() {
+      init();
+      do { } while (step());
+    }
+  };
+
+  /*! \brief Simulated annealing class. */
+  class SimAnn : public SimAnnBase {
+  private:
+    /*! \brief Pointer to the current entity. */
+    EntityBase *curr_ent;
+    /*! \brief Pointer to the best entity. */
+    EntityBase *best_ent;
+    /*! \brief Does initializations before each run. */
+    void init() {
+      SimAnnBase::init();
+      if (best_ent) delete best_ent;
+      best_ent = NULL;
+      curr_ent->randomize();
+    }
+  public:
+    /*! \brief Constructor. */
+    SimAnn() : curr_ent(NULL), best_ent(NULL) {}
+    /*! \brief Destructor. */
+    virtual ~SimAnn() {
+      if (best_ent) delete best_ent;
+    }
+    /*! \brief Step to a neighbouring state. */
+    double mutate() {
+      return curr_ent->mutate();
+    }
+    /*! \brief Reverts the last mutate(). */
+    void revert() {
+      curr_ent->revert();
+    }
+    /*! \brief Saves the current solution as the best one. */
+    void saveAsBest() { 
+      if (best_ent) delete best_ent;
+      best_ent = curr_ent->clone();
+    }
+    /*! \brief Sets the current entity. */
+    void setEntity(EntityBase &_ent) {
+      curr_ent = &_ent;
+    }
+    /*! \brief Returns a copy of the best found entity. */
+    EntityBase* getBestEntity() { return best_ent->clone(); }
+  };
+
+  /*! \brief A simple controller for the simulated annealing class. */
+  class SimpleController : public ControllerBase {
+  public:
+    /*! \brief Maximum number of iterations. */
+    long max_iter;
+    /*! \brief Maximum number of iterations which do not improve the
+     *  solution. */
+    long max_no_impr;
+    /*! \brief Temperature. */
+    double temp;
+    /*! \brief Annealing factor. */
+    double ann_fact;
+    /*! \brief Constructor.
+     *  \param _max_iter maximum number of iterations
+     *  \param _max_no_impr maximum number of consecutive iterations which do
+     *         not yield a better solution
+     *  \param _temp initial temperature
+     *  \param _ann_fact annealing factor
+     */
+    SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
+    double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
+      max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
+    {
+      srand48(time(0));
+    }
+    /*! \brief This is called when a neighbouring state gets accepted. */
+    void acceptEvent() {}
+    /*! \brief This is called when the accepted neighbouring state's cost is
+     *  less than the best found one's.
+     */
+    void improveEvent() {}
+    /*! \brief This is called when a neighbouring state gets rejected. */
+    void rejectEvent() {}
+    /*! \brief Decides whether to continue the annealing process or not. Also
+     *  decreases the temperature. */
+    bool next() {
+      temp *= ann_fact;
+      bool quit = (simann->getIter() > max_iter) ||
+        (simann->getIter() - simann->getLastImpr() > max_no_impr);
+      return !quit;
+    }
+    /*! \brief Decides whether to accept the current solution or not. */
+    bool accept() {
+      double cost_diff = simann->getPrevCost() - simann->getCurrCost();
+      return (drand48() <= exp(cost_diff / temp));
+    }
+  };
+
+  /*! \brief A controller with preset running time for the simulated annealing
+   *  class.
+   *
+   *  With this controller you can set the running time of the annealing
+   *  process in advance. It works the following way: the controller measures
+   *  a kind of divergence. The divergence is the difference of the average
+   *  cost of the recently found solutions the cost of the best found one. In
+   *  case this divergence is greater than a given threshold, then we decrease
+   *  the annealing factor, that is we cool the system faster. In case the
+   *  divergence is lower than the threshold, then we increase the temperature.
+   *  The threshold is a function of the elapsed time which reaches zero at the
+   *  desired end time.
+   */
+  class AdvancedController : public ControllerBase {
+  private:
+    Timer timer;
+    /*! \param time the elapsed time in seconds */
+    virtual double threshold(double time) {
+      return (-1.0) * start_threshold / end_time * time + start_threshold;
+    }
+  public:
+    double alpha;
+    double beta;
+    double gamma;
+    /*! \brief The time at the end of the algorithm. */
+    double end_time;
+    /*! \brief The time at the start of the algorithm. */
+    double start_time;
+    /*! \brief Starting threshold. */
+    double start_threshold;
+    /*! \brief Average cost of recent solutions. */
+    double avg_cost;
+    /*! \brief Temperature. */
+    double temp;
+    /*! \brief Annealing factor. */
+    double ann_fact;
+    /*! \brief Initial annealing factor. */
+    double init_ann_fact;
+    bool warmup;
+    /*! \brief Constructor.
+     *  \param _end_time running time in seconds
+     *  \param _alpha parameter used to calculate the running average
+     *  \param _beta parameter used to decrease the annealing factor
+     *  \param _gamma parameter used to increase the temperature
+     *  \param _ann_fact initial annealing factor
+     */
+    AdvancedController(double _end_time, double _alpha = 0.2,
+    double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
+    alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
+    ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)
+    {
+      srand48(time(0));
+    }
+    void init() {
+      avg_cost = simann->getCurrCost();
+    }
+    /*! \brief This is called when a neighbouring state gets accepted. */
+    void acceptEvent() {
+      avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
+      if (warmup) {
+        static int cnt = 0;
+        cnt++;
+        if (cnt >= 100) {
+          // calculate starting threshold and starting temperature
+          start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
+          temp = 10000.0;
+          warmup = false;
+          timer.reset();
+        }
+      }
+    }
+    /*! \brief Decides whether to continue the annealing process or not. */
+    bool next() {
+      if (warmup) {
+        return true;
+      }
+      else {
+        double elapsed_time = timer.getRealTime();
+        if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
+          // decrease the annealing factor
+          ann_fact *= beta;
+        }
+        else {
+          // increase the temperature
+          temp *= gamma;
+          // reset the annealing factor
+          ann_fact = init_ann_fact;
+        }
+        temp *= ann_fact;
+        return elapsed_time < end_time;
+      }
+    }
+    /*! \brief Decides whether to accept the current solution or not. */
+    bool accept() {
+      if (warmup) {
+        // we accept eveything during the "warm up" phase
+        return true;
+      }
+      else {
+        double cost_diff = simann->getPrevCost() - simann->getCurrCost();
+        if (cost_diff < 0.0) {
+          return (drand48() <= exp(cost_diff / temp));
+        }
+        else {
+          return true;
+        }
+      }
+    }
+  };
+
+/// @}
+
+}
+
+#endif