# HG changeset patch
# User ladanyi
# Date 1107862023 0
# Node ID 450f794dca81f1c2efebb8a4280663846cb5f8cb
# Parent  e5ee2726abe4d6d05393b37a4b32af5f1a42a244
more docs

diff -r e5ee2726abe4 -r 450f794dca81 src/work/akos/simann.h
--- a/src/work/akos/simann.h	Mon Feb 07 17:35:25 2005 +0000
+++ b/src/work/akos/simann.h	Tue Feb 08 11:27:03 2005 +0000
@@ -1,39 +1,62 @@
 #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
+/// @{
+
   const double INFTY = 1e24;
 
+  /*! \brief Simulated annealing base class. */
   class SimAnnBase {
   public:
     class Controller;
   private:
+    /*! Pointer to the controller. */
     Controller *controller;
   protected:
+    /*! \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;
 
-    virtual void mutate() = 0;
-    virtual void revert() = 0;
-    virtual void saveAsBest() = 0;
+    /*! \brief Step to a neighbouring state. */
+    virtual void mutate() {}
+    /*! \brief Reverts the last mutate(). */
+    virtual void revert() {}
+    /*! \brief Saves the current solution as the best one. */
+    virtual void saveAsBest() {}
   public:
+    /*! \brief Constructor. */
     SimAnnBase() {
       best_cost = prev_cost = prev_prev_cost = INFTY;
     }
+    /*! \brief Sets the controller class to use. */
     void setController(Controller &_controller) {
       controller = &_controller;
       controller->setBase(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 Starts the annealing process. */
     void run() {
       controller->init();
       do {
@@ -55,7 +78,9 @@
     /*! \brief A base class for controllers. */
     class Controller {
     public:
+      /*! \brief Pointer to the simulated annealing base class. */
       SimAnnBase *base;
+      /*! \brief Initializes the controller. */
       virtual void init() {}
       /*! \brief This is called when a neighbouring state gets accepted. */
       virtual void acceptEvent() {}
@@ -65,38 +90,48 @@
       virtual void improveEvent() {}
       /*! \brief This is called when a neighbouring state gets rejected. */
       virtual void rejectEvent() {}
+      /*! \brief Sets the simulated annealing base class to use. */
       virtual void setBase(SimAnnBase *_base) { base = _base; }
-      /*! */
+      /*! \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 Simulated annealing class. */
   template <typename E>
   class SimAnn : public SimAnnBase {
   private:
+    /*! \brief Pointer to the current entity. */
     E *curr_ent;
+    /*! \brief Pointer to the best entity. */
     E *best_ent;
   public:
+    /*! \brief Constructor. */
     SimAnn() : SimAnnBase() {}
+    /*! \brief Sets the initial entity. */
     void setEntity(E &ent) {
       curr_ent = new E(ent);
       best_ent = new E(ent);
       curr_cost = curr_ent->getCost();
     }
+    /*! \brief Returns the best found entity. */
     E getBestEntity() { return *best_ent; }
+    /*! \brief Step to a neighbouring state. */
     void mutate() {
       prev_prev_cost = prev_cost;
       prev_cost = curr_cost;
       curr_ent->mutate();
       curr_cost = curr_ent->getCost();
     }
+    /*! \brief Reverts the last mutate(). */
     void revert() {
       curr_ent->revert();
       curr_cost = prev_cost;
       prev_cost = prev_prev_cost;
     }
+    /*! \brief Saves the current solution as the best one. */
     void saveAsBest() {
       delete(best_ent);
       best_ent = new E(*curr_ent);
@@ -104,26 +139,38 @@
     }
   };
 
+  /*! \brief Skeleton of an entity class. */
   class EntitySkeleton {
   public:
-    /*! \return the cost of the entity */
+    /*! \brief Returns the cost of the entity. */
     double getCost() { return 0.0; }
     /*! \brief Makes a minor change to the entity. */
     void mutate() {}
     /*! \brief Restores the entity to its previous state i.e. reverts the
-     *  effects of the last mutate.
+     *  effects of the last mutate().
      */
     void revert() {}
   };
 
-  /*! \brief A simple controller for the simulated annealing class.
-   *  \todo Find a way to set the various parameters.
-   */
+  /*! \brief A simple controller for the simulated annealing class. */
   class SimpleController : public SimAnnBase::Controller {
   public:
-    long iter, last_impr, max_iter, max_no_impr;
-    double temp, ann_fact;
-    /*! \param _max_iter maximum number of iterations
+    /*! \brief Number of iterations. */
+    long iter;
+    /*! \brief Number of iterations which did not improve the solution since
+     *  the last improvement. */
+    long last_impr;
+    /*! \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
@@ -136,17 +183,24 @@
     void acceptEvent() {
       iter++;
     }
+    /*! \brief This is called when the accepted neighbouring state's cost is
+     *  less than the best found one's.
+     */
     void improveEvent() {
       last_impr = iter;
     }
+    /*! \brief This is called when a neighbouring state gets rejected. */
     void rejectEvent() {
       iter++;
     }
+    /*! \brief Decides whether to continue the annealing process or not. Also
+     *  decreases the temperature. */
     bool next() {
       temp *= ann_fact;
       bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
       return !quit;
     }
+    /*! \brief Decides whether to accept the current solution or not. */
     bool accept() {
       double cost_diff = base->getPrevCost() - base->getCurrCost();
       if (cost_diff < 0.0) {
@@ -161,29 +215,27 @@
 
   /*! \brief A controller with preset running time for the simulated annealing
    *  class.
-   *  \todo Find a better name.
    */
   class AdvancedController : public SimAnnBase::Controller {
   private:
     Timer timer;
     /*! \param time the elapsed time in seconds */
     virtual double threshold(double time) {
-      // 1 / log(x)
-      /*
-      static double xm = 5.0 / end_time;
-      static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
-      return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
-      */
       return (-1.0) * start_threshold / end_time * time + start_threshold;
     }
   public:
-    double alpha, beta, gamma;
-    double end_time, start_time;
+    double alpha;
+    double beta;
+    double gamma;
+    double end_time;
+    double start_time;
     double start_threshold;
     double avg_cost;
-    double temp, ann_fact;
+    double temp;
+    double ann_fact;
     bool warmup;
-    /*! \param _end_time running time in seconds
+    /*! \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
@@ -194,6 +246,7 @@
     void init() {
       avg_cost = base->getCurrCost();
     }
+    /*! \brief This is called when a neighbouring state gets accepted. */
     void acceptEvent() {
       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
       if (warmup) {
@@ -202,17 +255,13 @@
         if (cnt >= 100) {
           // calculate starting threshold and starting temperature
           start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
-          //temp = max_cost_diff / log(0.5);
           temp = 10000.0;
           warmup = false;
           timer.reset();
         }
       }
     }
-    void improveEvent() {
-    }
-    void rejectEvent() {
-    }
+    /*! \brief Decides whether to continue the annealing process or not. */
     bool next() {
       if (warmup) {
         return true;
@@ -226,12 +275,13 @@
         else {
           // increase the temperature
           temp *= gamma;
-          ann_fact = 0.99999999;
+          ann_fact = 0.99999999; // !!!!!!!!!!!
         }
         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
@@ -249,6 +299,8 @@
     }
   };
 
+/// @}
+
 }
 
 #endif