ladanyi@942: #ifndef LEMON_SIMANN_H
ladanyi@942: #define LEMON_SIMANN_H
ladanyi@918: 
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@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@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@942:     // returns the new cost
ladanyi@942:     double mutate() { return 0.0; }
ladanyi@942:     // restores the entity to its previous state i.e. reverts the effects of
ladanyi@942:     // the last mutate()
ladanyi@942:     void revert() {}
ladanyi@942:   };
ladanyi@942: 
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@957:       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / temp));
ladanyi@956:     }
ladanyi@956:   };
ladanyi@956: 
ladanyi@942: }
ladanyi@918: 
ladanyi@918: #endif