COIN-OR::LEMON - Graph Library

Changeset 1018:68beae6758a7 in lemon-0.x


Ignore:
Timestamp:
11/22/04 15:39:40 (19 years ago)
Author:
Akos Ladanyi
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1408
Message:

Use lemon::Timer for time measuring. Added the threshold() function and initial threshold and temperature calculation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/akos/simann.h

    r1000 r1018  
    44#include <cstdlib>
    55#include <cmath>
    6 #include <sys/time.h>
     6#include <lemon/time_measure.h>
    77
    88namespace lemon {
     
    3131      controller->setBase(this);
    3232    }
    33     double getCurrCost() { return curr_cost; }
    34     double getPrevCost() { return prev_cost; }
    35     double getBestCost() { return best_cost; }
     33    double getCurrCost() const { return curr_cost; }
     34    double getPrevCost() const { return prev_cost; }
     35    double getBestCost() const { return best_cost; }
    3636    void run() {
    3737      controller->init();
    38       while (controller->next()) {
     38      do {
    3939        mutate();
    4040        if (controller->accept()) {
     
    4949          controller->rejectEvent();
    5050        }
    51       }
     51      } while (controller->next());
    5252    }
    5353
     
    7373  };
    7474
     75  /*! \todo atgondolni mi is ez a prev_cost */
    7576  template <typename E>
    7677  class SimAnn : public SimAnnBase {
     
    8687    E getBestEntity() { return *best_ent; }
    8788    void mutate() {
    88       curr_ent->mutate();
     89      prev_cost = curr_cost;
     90      curr_cost = curr_ent->mutate();
    8991    }
    9092    void revert() {
    9193      curr_ent->revert();
     94      curr_cost = prev_cost;
    9295    }
    9396    void saveAsBest() {
     
    141144    }
    142145    bool accept() {
    143       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
    144         temp));
     146      double cost_diff = base->getPrevCost() - base->getCurrCost();
     147      if (cost_diff < 0.0) {
     148        return (drand48() <= exp(cost_diff / temp));
     149      }
     150      else {
     151        return true;
     152      }
    145153    }
    146154  };
     
    152160  class AdvancedController : public SimAnnBase::Controller {
    153161  private:
     162    Timer timer;
    154163    /*! \param time the elapsed time in seconds */
    155     double threshold(double time) { return 0.0; }
     164    virtual double threshold(double time) {
     165      // this is the function 1 / log(x) scaled and offset
     166      static double xm = 5.0 / end_time;
     167      static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
     168      return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
     169    }
    156170  public:
    157171    double alpha, beta, gamma;
    158172    double end_time, start_time;
     173    double start_threshold;
    159174    double avg_cost;
    160175    double temp, ann_fact;
    161     /*! \param _end_time running_time
     176    bool warmup;
     177    long iter;
     178    /*! \param _end_time running time in seconds
    162179     *  \param _alpha parameter used to calculate the running average
    163180     *  \param _beta parameter used to decrease the annealing factor
     
    166183    AdvancedController(double _end_time, double _alpha = 0.2,
    167184    double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
    168     gamma(_gamma), end_time(_end_time) {}
     185    gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true),
     186    iter(0) {}
    169187    void init() {
    170       timeval tv;
    171       gettimeofday(&tv, 0);
    172       start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;
     188      avg_cost = base->getCurrCost();
    173189    }
    174190    void acceptEvent() {
    175191      avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
     192      iter++;
    176193    }
    177194    void improveEvent() {
    178195    }
    179196    void rejectEvent() {
     197      iter++;
    180198    }
    181199    bool next() {
    182       timeval tv;
    183       gettimeofday(&tv, 0);
    184       double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;
    185       if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
    186         // decrease the annealing factor
    187         ann_fact *= beta;
     200      if (warmup) {
     201        static double max_cost_diff = 0.0;
     202        double cost_diff = base->getCurrCost() - base->getPrevCost();
     203        // jo ez igy egyaltalan? -> prev_cost
     204        if ((cost_diff > 0.0) && (cost_diff > max_cost_diff)) {
     205          max_cost_diff = cost_diff;
     206        }
     207        // How to set the starting temperature when all the 100 first
     208        // iterations improve the solution?
     209        if (iter > 100) {
     210          // calculate starting threshold and starting temperature
     211          start_threshold = fabs(base->getBestCost() - avg_cost);
     212          temp = exp(max_cost_diff) / 0.5;
     213          warmup = false;
     214          timer.reset();
     215        }
     216        return true;
    188217      }
    189218      else {
    190         // increase the temperature
    191         temp *= gamma;
    192       }
    193       temp *= ann_fact;
    194       return elapsed_time < end_time;
     219        double elapsed_time = timer.getRealTime();
     220        if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
     221          // decrease the annealing factor
     222          ann_fact *= beta;
     223        }
     224        else {
     225          // increase the temperature
     226          temp *= gamma;
     227        }
     228        temp *= ann_fact;
     229        return elapsed_time < end_time;
     230      }
    195231    }
    196232    bool accept() {
    197       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /
    198         temp));
     233      if (warmup) {
     234        // we accept eveything during the "warm up" phase
     235        return true;
     236      }
     237      else {
     238        double cost_diff = base->getPrevCost() - base->getCurrCost();
     239        if (cost_diff < 0.0) {
     240          return (drand48() <= exp(cost_diff / temp));
     241        }
     242        else {
     243          return true;
     244        }
     245      }
    199246    }
    200247  };
Note: See TracChangeset for help on using the changeset viewer.