ladanyi@942: #ifndef LEMON_SIMANN_H
ladanyi@942: #define LEMON_SIMANN_H
ladanyi@918: 
ladanyi@966: #include <cstdlib>
ladanyi@966: #include <cmath>
ladanyi@966: #include <sys/time.h>
ladanyi@966: 
ladanyi@942: namespace lemon {
ladanyi@918: 
ladanyi@942:   const double INFTY = 1e24;
ladanyi@918: 
ladanyi@942:   class SimAnnBase {
ladanyi@918:   public:
ladanyi@942:     class Controller;
ladanyi@942:   private:
ladanyi@942:     Controller *controller;
ladanyi@942:   protected:
ladanyi@942:     double curr_cost;
ladanyi@942:     double prev_cost;
ladanyi@942:     double best_cost;
ladanyi@918: 
ladanyi@942:     virtual void mutate() = 0;
ladanyi@942:     virtual void revert() = 0;
ladanyi@942:     virtual void saveAsBest() = 0;
ladanyi@942:   public:
ladanyi@942:     SimAnnBase() {
ladanyi@942:       curr_cost = prev_cost = best_cost = INFTY;
ladanyi@942:     }
ladanyi@957:     void setController(Controller &_controller) {
ladanyi@957:       controller = &_controller;
ladanyi@957:       controller->setBase(this);
ladanyi@957:     }
ladanyi@957:     double getCurrCost() { return curr_cost; }
ladanyi@957:     double getPrevCost() { return prev_cost; }
ladanyi@942:     double getBestCost() { return best_cost; }
ladanyi@942:     void run() {
ladanyi@966:       controller->init();
ladanyi@942:       while (controller->next()) {
ladanyi@942:         mutate();
ladanyi@957:         if (controller->accept()) {
ladanyi@942:           controller->acceptEvent();
ladanyi@942:           if (curr_cost < best_cost) {
ladanyi@942:             saveAsBest();
ladanyi@942:             controller->improveEvent();
ladanyi@942:           }
ladanyi@942:         }
ladanyi@942:         else {
ladanyi@942:           revert();
ladanyi@942:           controller->rejectEvent();
ladanyi@942:         }
ladanyi@918:       }
ladanyi@918:     }
ladanyi@918: 
ladanyi@942:     class Controller {
ladanyi@942:     public:
ladanyi@957:       SimAnnBase *base;
ladanyi@966:       virtual void init() {}
ladanyi@942:       virtual void acceptEvent() {}
ladanyi@942:       virtual void improveEvent() {}
ladanyi@942:       virtual void rejectEvent() {}
ladanyi@957:       virtual void setBase(SimAnnBase *_base) { base = _base; }
ladanyi@942:       virtual bool next() = 0;
ladanyi@957:       virtual bool accept() = 0;
ladanyi@942:     };
ladanyi@942:   };
ladanyi@918: 
ladanyi@942:   template <typename E>
ladanyi@942:   class SimAnn : public SimAnnBase {
ladanyi@942:   private:
ladanyi@942:     E *curr_ent;
ladanyi@942:     E *best_ent;
ladanyi@942:   public:
ladanyi@957:     SimAnn() : SimAnnBase() {}
ladanyi@957:     void setEntity(E &ent) {
ladanyi@957:       curr_ent = new E(ent);
ladanyi@957:       best_ent = new E(ent);
ladanyi@942:     }
ladanyi@942:     E getBestEntity() { return *best_ent; }
ladanyi@942:     void mutate() {
ladanyi@942:       curr_ent->mutate();
ladanyi@942:     }
ladanyi@942:     void revert() {
ladanyi@942:       curr_ent->revert();
ladanyi@942:     }
ladanyi@942:     void saveAsBest() {
ladanyi@942:       *best_ent = *curr_ent;
ladanyi@942:       best_cost = curr_cost;
ladanyi@942:     }
ladanyi@942:   };
ladanyi@942: 
ladanyi@956:   class EntitySkeleton {
ladanyi@942:   public:
ladanyi@966:     /*! \brief Makes a minor change to the entity.
ladanyi@966:      *  \return the new cost
ladanyi@966:      */
ladanyi@942:     double mutate() { return 0.0; }
ladanyi@966:     /*! \brief Restores the entity to its previous state i.e. reverts the
ladanyi@966:      *  effects of the last mutate.
ladanyi@966:      */
ladanyi@942:     void revert() {}
ladanyi@942:   };
ladanyi@942: 
ladanyi@966:   /*! \brief A simple controller for the simulated annealing class.
ladanyi@966:    *  \todo Find a way to set the various parameters.
ladanyi@966:    */
ladanyi@956:   class SimpleController : public SimAnnBase::Controller {
ladanyi@956:   public:
ladanyi@956:     long iter, last_impr, max_iter, max_no_impr;
ladanyi@956:     double temp, annealing_factor;
ladanyi@957:     SimpleController() {
ladanyi@956:       iter = last_impr = 0;
ladanyi@956:       max_iter = 500000;
ladanyi@956:       max_no_impr = 20000;
ladanyi@956:       annealing_factor = 0.9999;
ladanyi@956:       temp = 1000;
ladanyi@956:     }
ladanyi@956:     void acceptEvent() {
ladanyi@956:       iter++;
ladanyi@956:     }
ladanyi@956:     void improveEvent() {
ladanyi@956:       last_impr = iter;
ladanyi@956:     }
ladanyi@956:     void rejectEvent() {
ladanyi@956:       iter++;
ladanyi@956:     }
ladanyi@956:     bool next() {
ladanyi@956:       temp *= annealing_factor;
ladanyi@956:       bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
ladanyi@956:       return !quit;
ladanyi@956:     }
ladanyi@957:     bool accept() {
ladanyi@966:       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
ladanyi@966:         temp));
ladanyi@966:     }
ladanyi@966:   };
ladanyi@966: 
ladanyi@966:   /*! \brief A controller with preset running time for the simulated annealing
ladanyi@966:    *  class.
ladanyi@966:    *  \todo Find a better name.
ladanyi@966:    */
ladanyi@966:   class AdvancedController : public SimAnnBase::Controller {
ladanyi@966:   private:
ladanyi@966:     double threshold() { return 0.0; }
ladanyi@966:   public:
ladanyi@966:     double alpha;
ladanyi@966:     double temp;
ladanyi@966:     double avg_cost;
ladanyi@966:     double start_time, end_time;
ladanyi@966:     void init() {
ladanyi@966:       timeval tv;
ladanyi@966:       gettimeofday(&tv, 0);
ladanyi@966:       start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;
ladanyi@966:     }
ladanyi@966:     void acceptEvent() {
ladanyi@966:       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
ladanyi@966:     }
ladanyi@966:     void improveEvent() {
ladanyi@966:     }
ladanyi@966:     void rejectEvent() {
ladanyi@966:     }
ladanyi@966:     bool next() {
ladanyi@966:       // abs(avg_cost - base->getBestCost())
ladanyi@966:       // ha nagy: cooling factor novelese
ladanyi@966:       // ha kicsi: homerseklet novelese
ladanyi@966:       // de mennyivel?
ladanyi@966:       timeval tv;
ladanyi@966:       gettimeofday(&tv, 0);
ladanyi@966:       double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
ladanyi@966:       return elapsed_time < end_time;
ladanyi@966:     }
ladanyi@966:     bool accept() {
ladanyi@966:       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
ladanyi@966:         temp));
ladanyi@956:     }
ladanyi@956:   };
ladanyi@956: 
ladanyi@942: }
ladanyi@918: 
ladanyi@918: #endif