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