Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/akos/simann.h
changeset 1106 0a7d604a9763
parent 1023 3268fef5d623
child 1142 450f794dca81
equal deleted inserted replaced
6:5a3f66210c5c 7:37dcb90c4739 
    96       curr_ent->revert();
 
    96       curr_ent->revert();
 
    97       curr_cost = prev_cost;
 
    97       curr_cost = prev_cost;
 
    98       prev_cost = prev_prev_cost;
 
    98       prev_cost = prev_prev_cost;
 
    99     }
 
    99     }
 
   100     void saveAsBest() {
 
   100     void saveAsBest() {
 
   101       *best_ent = *curr_ent;
 
   101       delete(best_ent);
 
       
   102       best_ent = new E(*curr_ent);
 
   102       best_cost = curr_cost;
 
   103       best_cost = curr_cost;
 
   103     }
 
   104     }
 
   104   };
 
   105   };
 
   105 
   106 
   106   class EntitySkeleton {
 
   107   class EntitySkeleton {
 
   127      *         not yield a better solution
 
   128      *         not yield a better solution
 
   128      *  \param _temp initial temperature
 
   129      *  \param _temp initial temperature
 
   129      *  \param _ann_fact annealing factor
 
   130      *  \param _ann_fact annealing factor
 
   130      */
 
   131      */
 
   131     SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
 
   132     SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
 
   132     double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0),
 
   133     double _temp = 1000.0, double _ann_fact = 0.9999) : iter(0), last_impr(0),
 
   133     max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
 
   134     max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
 
   134     ann_fact(_ann_fact) {}
 
   135     ann_fact(_ann_fact) {}
 
   135     void acceptEvent() {
 
   136     void acceptEvent() {
 
   136       iter++;
 
   137       iter++;
 
   137     }
 
   138     }
 
   147       return !quit;
 
   148       return !quit;
 
   148     }
 
   149     }
 
   149     bool accept() {
 
   150     bool accept() {
 
   150       double cost_diff = base->getPrevCost() - base->getCurrCost();
 
   151       double cost_diff = base->getPrevCost() - base->getCurrCost();
 
   151       if (cost_diff < 0.0) {
 
   152       if (cost_diff < 0.0) {
 
   152         return (drand48() <= exp(cost_diff / temp));
 
   153         bool ret = drand48() <= exp(cost_diff / temp);
 
       
   154         return ret;
 
   153       }
 
   155       }
 
   154       else {
 
   156       else {
 
   155         return true;
 
   157         return true;
 
   156       }
 
   158       }
 
   157     }
 
   159     }
 
   164   class AdvancedController : public SimAnnBase::Controller {
 
   166   class AdvancedController : public SimAnnBase::Controller {
 
   165   private:
 
   167   private:
 
   166     Timer timer;
 
   168     Timer timer;
 
   167     /*! \param time the elapsed time in seconds */
 
   169     /*! \param time the elapsed time in seconds */
 
   168     virtual double threshold(double time) {
 
   170     virtual double threshold(double time) {
 
   169       // this is the function 1 / log(x) scaled and offset
 
   171       // 1 / log(x)
 
       
   172       /*
 
   170       static double xm = 5.0 / end_time;
 
   173       static double xm = 5.0 / end_time;
 
   171       static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
 
   174       static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
 
   172       return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
 
   175       return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
 
       
   176       */
 
       
   177       return (-1.0) * start_threshold / end_time * time + start_threshold;
 
   173     }
 
   178     }
 
   174   public:
 
   179   public:
 
   175     double alpha, beta, gamma;
 
   180     double alpha, beta, gamma;
 
   176     double end_time, start_time;
 
   181     double end_time, start_time;
 
   177     double start_threshold;
 
   182     double start_threshold;
 
   182      *  \param _alpha parameter used to calculate the running average
 
   187      *  \param _alpha parameter used to calculate the running average
 
   183      *  \param _beta parameter used to decrease the annealing factor
 
   188      *  \param _beta parameter used to decrease the annealing factor
 
   184      *  \param _gamma parameter used to increase the temperature
 
   189      *  \param _gamma parameter used to increase the temperature
 
   185      */
 
   190      */
 
   186     AdvancedController(double _end_time, double _alpha = 0.2,
 
   191     AdvancedController(double _end_time, double _alpha = 0.2,
 
   187     double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
 
   192     double _beta = 0.9, double _gamma = 1.6) : alpha(_alpha), beta(_beta),
 
   188     gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true) {}
 
   193     gamma(_gamma), end_time(_end_time), ann_fact(0.99999999), warmup(true) {}
 
   189     void init() {
 
   194     void init() {
 
   190       avg_cost = base->getCurrCost();
 
   195       avg_cost = base->getCurrCost();
 
   191     }
 
   196     }
 
   192     void acceptEvent() {
 
   197     void acceptEvent() {
 
   193       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
 
   198       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
 
   194       if (warmup) {
 
   199       if (warmup) {
 
   195         static double max_cost_diff = 0.0;
 
   200         static int cnt = 0;
 
   196         static int incr_cnt = 0;
 
   201         cnt++;
 
   197         double cost_diff = base->getCurrCost() - base->getPrevCost();
 
   202         if (cnt >= 100) {
 
   198         if (cost_diff > 0.0) {
 
       
   199           incr_cnt++;
 
       
   200           if (cost_diff > max_cost_diff) {
 
       
   201             max_cost_diff = cost_diff;
 
       
   202           }
 
       
   203         }
 
       
   204         if (incr_cnt >= 100) {
 
       
   205           // calculate starting threshold and starting temperature
 
   203           // calculate starting threshold and starting temperature
 
   206           start_threshold = fabs(base->getBestCost() - avg_cost);
 
   204           start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
 
   207           temp = max_cost_diff / log(0.5);
 
   205           //temp = max_cost_diff / log(0.5);
 
       
   206           temp = 10000.0;
 
   208           warmup = false;
 
   207           warmup = false;
 
   209           timer.reset();
 
   208           timer.reset();
 
   210         }
 
   209         }
 
   211       }
 
   210       }
 
   212     }
 
   211     }
 
   225           ann_fact *= beta;
 
   224           ann_fact *= beta;
 
   226         }
 
   225         }
 
   227         else {
 
   226         else {
 
   228           // increase the temperature
 
   227           // increase the temperature
 
   229           temp *= gamma;
 
   228           temp *= gamma;
 
       
   229           ann_fact = 0.99999999;
 
   230         }
 
   230         }
 
   231         temp *= ann_fact;
 
   231         temp *= ann_fact;
 
   232         return elapsed_time < end_time;
 
   232         return elapsed_time < end_time;
 
   233       }
 
   233       }
 
   234     }
 
   234     }
lemon-0.x