1.1 --- a/src/work/akos/simann.h	Mon Nov 22 09:12:33 2004 +0000
     1.2 +++ b/src/work/akos/simann.h	Mon Nov 22 14:39:40 2004 +0000
     1.3 @@ -3,7 +3,7 @@
     1.4  
     1.5  #include <cstdlib>
     1.6  #include <cmath>
     1.7 -#include <sys/time.h>
     1.8 +#include <lemon/time_measure.h>
     1.9  
    1.10  namespace lemon {
    1.11  
    1.12 @@ -30,12 +30,12 @@
    1.13        controller = &_controller;
    1.14        controller->setBase(this);
    1.15      }
    1.16 -    double getCurrCost() { return curr_cost; }
    1.17 -    double getPrevCost() { return prev_cost; }
    1.18 -    double getBestCost() { return best_cost; }
    1.19 +    double getCurrCost() const { return curr_cost; }
    1.20 +    double getPrevCost() const { return prev_cost; }
    1.21 +    double getBestCost() const { return best_cost; }
    1.22      void run() {
    1.23        controller->init();
    1.24 -      while (controller->next()) {
    1.25 +      do {
    1.26          mutate();
    1.27          if (controller->accept()) {
    1.28            controller->acceptEvent();
    1.29 @@ -48,7 +48,7 @@
    1.30            revert();
    1.31            controller->rejectEvent();
    1.32          }
    1.33 -      }
    1.34 +      } while (controller->next());
    1.35      }
    1.36  
    1.37      /*! \brief A base class for controllers. */
    1.38 @@ -72,6 +72,7 @@
    1.39      };
    1.40    };
    1.41  
    1.42 +  /*! \todo atgondolni mi is ez a prev_cost */
    1.43    template <typename E>
    1.44    class SimAnn : public SimAnnBase {
    1.45    private:
    1.46 @@ -85,10 +86,12 @@
    1.47      }
    1.48      E getBestEntity() { return *best_ent; }
    1.49      void mutate() {
    1.50 -      curr_ent->mutate();
    1.51 +      prev_cost = curr_cost;
    1.52 +      curr_cost = curr_ent->mutate();
    1.53      }
    1.54      void revert() {
    1.55        curr_ent->revert();
    1.56 +      curr_cost = prev_cost;
    1.57      }
    1.58      void saveAsBest() {
    1.59        *best_ent = *curr_ent;
    1.60 @@ -140,8 +143,13 @@
    1.61        return !quit;
    1.62      }
    1.63      bool accept() {
    1.64 -      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
    1.65 -        temp));
    1.66 +      double cost_diff = base->getPrevCost() - base->getCurrCost();
    1.67 +      if (cost_diff < 0.0) {
    1.68 +        return (drand48() <= exp(cost_diff / temp));
    1.69 +      }
    1.70 +      else {
    1.71 +        return true;
    1.72 +      }
    1.73      }
    1.74    };
    1.75  
    1.76 @@ -151,51 +159,90 @@
    1.77     */
    1.78    class AdvancedController : public SimAnnBase::Controller {
    1.79    private:
    1.80 +    Timer timer;
    1.81      /*! \param time the elapsed time in seconds */
    1.82 -    double threshold(double time) { return 0.0; }
    1.83 +    virtual double threshold(double time) {
    1.84 +      // this is the function 1 / log(x) scaled and offset
    1.85 +      static double xm = 5.0 / end_time;
    1.86 +      static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
    1.87 +      return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
    1.88 +    }
    1.89    public:
    1.90      double alpha, beta, gamma;
    1.91      double end_time, start_time;
    1.92 +    double start_threshold;
    1.93      double avg_cost;
    1.94      double temp, ann_fact;
    1.95 -    /*! \param _end_time running_time
    1.96 +    bool warmup;
    1.97 +    long iter;
    1.98 +    /*! \param _end_time running time in seconds
    1.99       *  \param _alpha parameter used to calculate the running average
   1.100       *  \param _beta parameter used to decrease the annealing factor
   1.101       *  \param _gamma parameter used to increase the temperature
   1.102       */
   1.103      AdvancedController(double _end_time, double _alpha = 0.2,
   1.104      double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
   1.105 -    gamma(_gamma), end_time(_end_time) {}
   1.106 +    gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true),
   1.107 +    iter(0) {}
   1.108      void init() {
   1.109 -      timeval tv;
   1.110 -      gettimeofday(&tv, 0);
   1.111 -      start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;
   1.112 +      avg_cost = base->getCurrCost();
   1.113      }
   1.114      void acceptEvent() {
   1.115        avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
   1.116 +      iter++;
   1.117      }
   1.118      void improveEvent() {
   1.119      }
   1.120      void rejectEvent() {
   1.121 +      iter++;
   1.122      }
   1.123      bool next() {
   1.124 -      timeval tv;
   1.125 -      gettimeofday(&tv, 0);
   1.126 -      double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
   1.127 -      if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
   1.128 -	// decrease the annealing factor
   1.129 -        ann_fact *= beta;
   1.130 +      if (warmup) {
   1.131 +        static double max_cost_diff = 0.0;
   1.132 +        double cost_diff = base->getCurrCost() - base->getPrevCost();
   1.133 +        // jo ez igy egyaltalan? -> prev_cost
   1.134 +        if ((cost_diff > 0.0) && (cost_diff > max_cost_diff)) {
   1.135 +          max_cost_diff = cost_diff;
   1.136 +        }
   1.137 +        // How to set the starting temperature when all the 100 first
   1.138 +        // iterations improve the solution?
   1.139 +        if (iter > 100) {
   1.140 +          // calculate starting threshold and starting temperature
   1.141 +          start_threshold = fabs(base->getBestCost() - avg_cost);
   1.142 +          temp = exp(max_cost_diff) / 0.5;
   1.143 +          warmup = false;
   1.144 +          timer.reset();
   1.145 +        }
   1.146 +        return true;
   1.147        }
   1.148        else {
   1.149 -        // increase the temperature
   1.150 -        temp *= gamma;
   1.151 +        double elapsed_time = timer.getRealTime();
   1.152 +        if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
   1.153 +          // decrease the annealing factor
   1.154 +          ann_fact *= beta;
   1.155 +        }
   1.156 +        else {
   1.157 +          // increase the temperature
   1.158 +          temp *= gamma;
   1.159 +        }
   1.160 +        temp *= ann_fact;
   1.161 +        return elapsed_time < end_time;
   1.162        }
   1.163 -      temp *= ann_fact;
   1.164 -      return elapsed_time < end_time;
   1.165      }
   1.166      bool accept() {
   1.167 -      return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
   1.168 -        temp));
   1.169 +      if (warmup) {
   1.170 +        // we accept eveything during the "warm up" phase
   1.171 +        return true;
   1.172 +      }
   1.173 +      else {
   1.174 +        double cost_diff = base->getPrevCost() - base->getCurrCost();
   1.175 +        if (cost_diff < 0.0) {
   1.176 +          return (drand48() <= exp(cost_diff / temp));
   1.177 +        }
   1.178 +        else {
   1.179 +          return true;
   1.180 +        }
   1.181 +      }
   1.182      }
   1.183    };
   1.184