# HG changeset patch
# User ladanyi
# Date 1138572370 0
# Node ID 09415ae11103d45885cb305db0068986247facf1
# Parent  87d3518d73d8f0c6b7e3d8bdb492bdbe3a6d4be4
more doc

diff -r 87d3518d73d8 -r 09415ae11103 lemon/simann.h
--- a/lemon/simann.h	Sun Jan 29 22:04:48 2006 +0000
+++ b/lemon/simann.h	Sun Jan 29 22:06:10 2006 +0000
@@ -11,6 +11,7 @@
 
 #include <cstdlib>
 #include <cmath>
+#include <limits>
 #include <lemon/time_measure.h>
 
 namespace lemon {
@@ -18,71 +19,76 @@
 /// \addtogroup experimental
 /// @{
 
-  /*! \brief A base class for controllers. */
+  /// \brief A base class for controllers.
   class ControllerBase {
+  public:
     friend class SimAnnBase;
-  public:
-    /*! \brief Pointer to the simulated annealing base class. */
+    /// \brief Pointer to the simulated annealing base class.
     SimAnnBase *simann;
-    /*! \brief Initializes the controller. */
+    /// \brief Initializes the controller.
     virtual void init() {}
-    /*! \brief This is called when a neighbouring state gets accepted. */
+    /// \brief This is called by the simulated annealing class 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.
-     */
+    /// \brief This is called by the simulated annealing class 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. */
+    /// \brief This is called by the simulated annealing class when a
+    /// neighbouring state gets rejected.
     virtual void rejectEvent() {}
-    /*! \brief Decides whether to continue the annealing process or not. */
+    /// \brief Decides whether to continue the annealing process or not.
     virtual bool next() = 0;
-    /*! \brief Decides whether to accept the current solution or not. */
+    /// \brief Decides whether to accept the current solution or not.
     virtual bool accept() = 0;
+    /// \brief Destructor.
+    virtual ~ControllerBase() {}
   };
 
-  /*! \brief Skeleton of an entity class. */
+  /// \brief Skeleton of an entity class.
   class EntityBase {
   public:
-    /*! \brief Makes a minor change to the entity.
-     *  \return the new cost
-     */
+    /// \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().
-     */
+    /// \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. */
+    /// \brief Makes a copy of the entity.
     virtual EntityBase* clone() = 0;
-    /*! \brief Makes a major change to the entity. */
+    /// \brief Makes a major change to the entity.
     virtual void randomize() = 0;
+    /// \brief Destructor.
+    virtual ~EntityBase() {}
   };
 
-  /*! \brief Simulated annealing base class. */
+  /// \brief Simulated annealing abstract base class.
+  /// Can be used to derive a custom simulated annealing class if \ref SimAnn
+  /// doesn't fit your needs.
   class SimAnnBase {
   private:
-    /*! Pointer to the controller. */
+    /// \brief Pointer to the controller.
     ControllerBase *controller;
-    /*! \brief Cost of the current solution. */
+    /// \brief Cost of the current solution.
     double curr_cost;
-    /*! \brief Cost of the best solution. */
+    /// \brief Cost of the best solution.
     double best_cost;
-    /*! \brief Cost of the previous solution. */
+    /// \brief Cost of the previous solution.
     double prev_cost;
-    /*! \brief Cost of the solution preceding the previous one. */
+    /// \brief Cost of the solution preceding the previous one.
     double prev_prev_cost;
-    /*! \brief Number of iterations. */
+    /// \brief Number of iterations.
     long iter;
-    /*! \brief Number of iterations which did not improve the solution since
-     *  the last improvement. */
+    /// \brief Number of iterations which did not improve the solution since
+    /// the last improvement.
     long last_impr;
   protected:
-    /*! \brief Step to a neighbouring state. */
+    /// \brief Step to a neighbouring state.
     virtual double mutate() = 0;
-    /*! \brief Reverts the last mutate(). */
+    /// \brief Reverts the last mutate().
     virtual void revert() = 0;
-    /*! \brief Saves the current solution as the best one. */
+    /// \brief Saves the current solution as the best one.
     virtual void saveAsBest() = 0;
-    /*! \brief Does initializations before each run. */
+    /// \brief Does initializations before each run.
     virtual void init() {
       controller->init();
       curr_cost = prev_cost = prev_prev_cost = best_cost =
@@ -90,24 +96,23 @@
       iter = last_impr = 0;
     }
   public:
-    /*! \brief Sets the controller class to use. */
+    /// \brief Sets the controller class to use.
     void setController(ControllerBase &_controller) {
       controller = &_controller;
       controller->simann = this;
     }
-    /*! \brief Returns the cost of the current solution. */
+    /// \brief Returns the cost of the current solution.
     double getCurrCost() const { return curr_cost; }
-    /*! \brief Returns the cost of the previous solution. */
+    /// \brief Returns the cost of the previous solution.
     double getPrevCost() const { return prev_cost; }
-    /*! \brief Returns the cost of the best solution. */
+    /// \brief Returns the cost of the best solution.
     double getBestCost() const { return best_cost; }
-    /*! \brief Returns the number of iterations. */
+    /// \brief Returns the number of iterations done.
     long getIter() const { return iter; }
-    /*! \brief Returns the number of the last iteration when the solution was
-     *  improved.
-     */
+    /// \brief Returns the ordinal number of the last iteration when the
+    /// solution was improved.
     long getLastImpr() const { return last_impr; }
-    /*! \brief Performs one iteration. */
+    /// \brief Performs one iteration.
     bool step() {
       iter++;
       prev_prev_cost = prev_cost;
@@ -130,28 +135,29 @@
       }
       return controller->next();
     }
-    /*! \brief Performs a given number of iterations.
-     *  \param n the number of iterations
-     */
+    /// \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. */
+    /// \brief Starts the annealing process.
     void run() {
       init();
       do { } while (step());
     }
+    /// \brief Destructor.
+    virtual ~SimAnnBase() {}
   };
 
-  /*! \brief Simulated annealing class. */
+  /// \brief Simulated annealing class.
   class SimAnn : public SimAnnBase {
   private:
-    /*! \brief Pointer to the current entity. */
+    /// \brief Pointer to the current entity.
     EntityBase *curr_ent;
-    /*! \brief Pointer to the best entity. */
+    /// \brief Pointer to the best entity.
     EntityBase *best_ent;
-    /*! \brief Does initializations before each run. */
+    /// \brief Does initializations before each run.
     void init() {
       SimAnnBase::init();
       if (best_ent) delete best_ent;
@@ -159,159 +165,166 @@
       curr_ent->randomize();
     }
   public:
-    /*! \brief Constructor. */
+    /// \brief Constructor.
     SimAnn() : curr_ent(NULL), best_ent(NULL) {}
-    /*! \brief Destructor. */
+    /// \brief Destructor.
     virtual ~SimAnn() {
       if (best_ent) delete best_ent;
     }
-    /*! \brief Step to a neighbouring state. */
+    /// \brief Step to a neighbouring state.
     double mutate() {
       return curr_ent->mutate();
     }
-    /*! \brief Reverts the last mutate(). */
+    /// \brief Reverts the last mutate().
     void revert() {
       curr_ent->revert();
     }
-    /*! \brief Saves the current solution as the best one. */
+    /// \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. */
+    /// \brief Sets the current entity.
     void setEntity(EntityBase &_ent) {
       curr_ent = &_ent;
     }
-    /*! \brief Returns a copy of the best found entity. */
+    /// \brief Returns a copy of the best found entity.
     EntityBase* getBestEntity() { return best_ent->clone(); }
   };
 
-  /*! \brief A simple controller for the simulated annealing class. */
+  /// \brief A simple controller for the simulated annealing class.
+  /// This controller starts from a given initial temperature and evenly
+  /// decreases it.
   class SimpleController : public ControllerBase {
+  private:
+    /// \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
   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. */
+    /// \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.
-     */
+    /// \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. */
+    /// \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. */
+    /// \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. */
+    /// \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));
+      double cost_diff = simann->getCurrCost() - simann->getPrevCost();
+      return (drand48() <= exp(-(cost_diff / temp)));
     }
+    /// \brief Destructor.
+    virtual ~SimpleController() {}
   };
 
-  /*! \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.
-   */
+  /// \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:
+    /// \brief Timer class to measure the elapsed time.
     Timer timer;
-    /*! \param time the elapsed time in seconds */
+    /// \brief Calculates the threshold value.
+    /// \param time the elapsed time in seconds
     virtual double threshold(double time) {
       return (-1.0) * start_threshold / end_time * time + start_threshold;
     }
+    /// \brief Parameter used to calculate the running average.
+    double alpha;
+    /// \brief Parameter used to decrease the annealing factor.
+    double beta;
+    /// \brief Parameter used to increase the temperature.
+    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;
+    /// \brief True when the annealing process has been started.
+    bool start;
   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
-     */
+    /// \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)
+    ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
     {
       srand48(time(0));
     }
+    /// \brief Does initializations before each run.
     void init() {
       avg_cost = simann->getCurrCost();
     }
-    /*! \brief This is called when a neighbouring state gets accepted. */
+    /// \brief This is called when a neighbouring state gets accepted.
     void acceptEvent() {
       avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
-      if (warmup) {
+      if (!start) {
         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;
+          start = true;
           timer.restart();
         }
       }
     }
-    /*! \brief Decides whether to continue the annealing process or not. */
+    /// \brief Decides whether to continue the annealing process or not.
     bool next() {
-      if (warmup) {
+      if (!start) {
         return true;
       }
       else {
-        double elapsed_time = timer.getRealTime();
+        double elapsed_time = timer.realTime();
         if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
           // decrease the annealing factor
           ann_fact *= beta;
@@ -326,22 +339,18 @@
         return elapsed_time < end_time;
       }
     }
-    /*! \brief Decides whether to accept the current solution or not. */
+    /// \brief Decides whether to accept the current solution or not.
     bool accept() {
-      if (warmup) {
-        // we accept eveything during the "warm up" phase
+      if (!start) {
         return true;
       }
       else {
-        double cost_diff = simann->getPrevCost() - simann->getCurrCost();
-        if (cost_diff < 0.0) {
-          return (drand48() <= exp(cost_diff / temp));
-        }
-        else {
-          return true;
-        }
+        double cost_diff = simann->getCurrCost() - simann->getPrevCost();
+        return (drand48() <= exp(-(cost_diff / temp)));
       }
     }
+    /// \brief Destructor.
+    virtual ~AdvancedController() {}
   };
 
 /// @}