ladanyi@942: #ifndef LEMON_SIMANN_H ladanyi@942: #define LEMON_SIMANN_H ladanyi@918: ladanyi@966: #include ladanyi@966: #include ladanyi@966: #include 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@1000: /*! \brief A base class for controllers. */ ladanyi@942: class Controller { ladanyi@942: public: ladanyi@957: SimAnnBase *base; ladanyi@966: virtual void init() {} ladanyi@1000: /*! \brief This is called when a neighbouring state gets accepted. */ ladanyi@942: virtual void acceptEvent() {} ladanyi@1000: /*! \brief This is called when the accepted neighbouring state's cost is ladanyi@1000: * less than the best found one's. ladanyi@1000: */ ladanyi@942: virtual void improveEvent() {} ladanyi@1000: /*! \brief This is called when a neighbouring state gets rejected. */ ladanyi@942: virtual void rejectEvent() {} ladanyi@957: virtual void setBase(SimAnnBase *_base) { base = _base; } ladanyi@1000: /*! */ ladanyi@942: virtual bool next() = 0; ladanyi@1000: /*! */ ladanyi@957: virtual bool accept() = 0; ladanyi@942: }; ladanyi@942: }; ladanyi@918: ladanyi@942: template 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@1000: double temp, ann_fact; ladanyi@1000: /*! \param _max_iter maximum number of iterations ladanyi@1000: * \param _max_no_impr maximum number of consecutive iterations which do ladanyi@1000: * not yield a better solution ladanyi@1000: * \param _temp initial temperature ladanyi@1000: * \param _ann_fact annealing factor ladanyi@1000: */ ladanyi@1000: SimpleController(long _max_iter = 500000, long _max_no_impr = 20000, ladanyi@1000: double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0), ladanyi@1000: max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp), ladanyi@1000: ann_fact(_ann_fact) {} 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@1000: temp *= ann_fact; 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@1000: /*! \param time the elapsed time in seconds */ ladanyi@1000: double threshold(double time) { return 0.0; } ladanyi@966: public: ladanyi@1000: double alpha, beta, gamma; ladanyi@1000: double end_time, start_time; ladanyi@966: double avg_cost; ladanyi@1000: double temp, ann_fact; ladanyi@1000: /*! \param _end_time running_time ladanyi@1000: * \param _alpha parameter used to calculate the running average ladanyi@1000: * \param _beta parameter used to decrease the annealing factor ladanyi@1000: * \param _gamma parameter used to increase the temperature ladanyi@1000: */ ladanyi@1000: AdvancedController(double _end_time, double _alpha = 0.2, ladanyi@1000: double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta), ladanyi@1000: gamma(_gamma), end_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: timeval tv; ladanyi@966: gettimeofday(&tv, 0); ladanyi@966: double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time; ladanyi@1000: if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { ladanyi@1000: // decrease the annealing factor ladanyi@1000: ann_fact *= beta; ladanyi@1000: } ladanyi@1000: else { ladanyi@1000: // increase the temperature ladanyi@1000: temp *= gamma; ladanyi@1000: } ladanyi@1000: temp *= ann_fact; 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