1.1 --- a/lemon/simann.h Sun Jan 29 22:04:48 2006 +0000
1.2 +++ b/lemon/simann.h Sun Jan 29 22:06:10 2006 +0000
1.3 @@ -11,6 +11,7 @@
1.4
1.5 #include <cstdlib>
1.6 #include <cmath>
1.7 +#include <limits>
1.8 #include <lemon/time_measure.h>
1.9
1.10 namespace lemon {
1.11 @@ -18,71 +19,76 @@
1.12 /// \addtogroup experimental
1.13 /// @{
1.14
1.15 - /*! \brief A base class for controllers. */
1.16 + /// \brief A base class for controllers.
1.17 class ControllerBase {
1.18 + public:
1.19 friend class SimAnnBase;
1.20 - public:
1.21 - /*! \brief Pointer to the simulated annealing base class. */
1.22 + /// \brief Pointer to the simulated annealing base class.
1.23 SimAnnBase *simann;
1.24 - /*! \brief Initializes the controller. */
1.25 + /// \brief Initializes the controller.
1.26 virtual void init() {}
1.27 - /*! \brief This is called when a neighbouring state gets accepted. */
1.28 + /// \brief This is called by the simulated annealing class when a
1.29 + /// neighbouring state gets accepted.
1.30 virtual void acceptEvent() {}
1.31 - /*! \brief This is called when the accepted neighbouring state's cost is
1.32 - * less than the best found one's.
1.33 - */
1.34 + /// \brief This is called by the simulated annealing class when the
1.35 + /// accepted neighbouring state's cost is less than the best found one's.
1.36 virtual void improveEvent() {}
1.37 - /*! \brief This is called when a neighbouring state gets rejected. */
1.38 + /// \brief This is called by the simulated annealing class when a
1.39 + /// neighbouring state gets rejected.
1.40 virtual void rejectEvent() {}
1.41 - /*! \brief Decides whether to continue the annealing process or not. */
1.42 + /// \brief Decides whether to continue the annealing process or not.
1.43 virtual bool next() = 0;
1.44 - /*! \brief Decides whether to accept the current solution or not. */
1.45 + /// \brief Decides whether to accept the current solution or not.
1.46 virtual bool accept() = 0;
1.47 + /// \brief Destructor.
1.48 + virtual ~ControllerBase() {}
1.49 };
1.50
1.51 - /*! \brief Skeleton of an entity class. */
1.52 + /// \brief Skeleton of an entity class.
1.53 class EntityBase {
1.54 public:
1.55 - /*! \brief Makes a minor change to the entity.
1.56 - * \return the new cost
1.57 - */
1.58 + /// \brief Makes a minor change to the entity.
1.59 + /// \return the new cost
1.60 virtual double mutate() = 0;
1.61 - /*! \brief Restores the entity to its previous state i.e. reverts the
1.62 - * effects of the last mutate().
1.63 - */
1.64 + /// \brief Restores the entity to its previous state i.e. reverts the
1.65 + /// effects of the last mutate().
1.66 virtual void revert() = 0;
1.67 - /*! \brief Makes a copy of the entity. */
1.68 + /// \brief Makes a copy of the entity.
1.69 virtual EntityBase* clone() = 0;
1.70 - /*! \brief Makes a major change to the entity. */
1.71 + /// \brief Makes a major change to the entity.
1.72 virtual void randomize() = 0;
1.73 + /// \brief Destructor.
1.74 + virtual ~EntityBase() {}
1.75 };
1.76
1.77 - /*! \brief Simulated annealing base class. */
1.78 + /// \brief Simulated annealing abstract base class.
1.79 + /// Can be used to derive a custom simulated annealing class if \ref SimAnn
1.80 + /// doesn't fit your needs.
1.81 class SimAnnBase {
1.82 private:
1.83 - /*! Pointer to the controller. */
1.84 + /// \brief Pointer to the controller.
1.85 ControllerBase *controller;
1.86 - /*! \brief Cost of the current solution. */
1.87 + /// \brief Cost of the current solution.
1.88 double curr_cost;
1.89 - /*! \brief Cost of the best solution. */
1.90 + /// \brief Cost of the best solution.
1.91 double best_cost;
1.92 - /*! \brief Cost of the previous solution. */
1.93 + /// \brief Cost of the previous solution.
1.94 double prev_cost;
1.95 - /*! \brief Cost of the solution preceding the previous one. */
1.96 + /// \brief Cost of the solution preceding the previous one.
1.97 double prev_prev_cost;
1.98 - /*! \brief Number of iterations. */
1.99 + /// \brief Number of iterations.
1.100 long iter;
1.101 - /*! \brief Number of iterations which did not improve the solution since
1.102 - * the last improvement. */
1.103 + /// \brief Number of iterations which did not improve the solution since
1.104 + /// the last improvement.
1.105 long last_impr;
1.106 protected:
1.107 - /*! \brief Step to a neighbouring state. */
1.108 + /// \brief Step to a neighbouring state.
1.109 virtual double mutate() = 0;
1.110 - /*! \brief Reverts the last mutate(). */
1.111 + /// \brief Reverts the last mutate().
1.112 virtual void revert() = 0;
1.113 - /*! \brief Saves the current solution as the best one. */
1.114 + /// \brief Saves the current solution as the best one.
1.115 virtual void saveAsBest() = 0;
1.116 - /*! \brief Does initializations before each run. */
1.117 + /// \brief Does initializations before each run.
1.118 virtual void init() {
1.119 controller->init();
1.120 curr_cost = prev_cost = prev_prev_cost = best_cost =
1.121 @@ -90,24 +96,23 @@
1.122 iter = last_impr = 0;
1.123 }
1.124 public:
1.125 - /*! \brief Sets the controller class to use. */
1.126 + /// \brief Sets the controller class to use.
1.127 void setController(ControllerBase &_controller) {
1.128 controller = &_controller;
1.129 controller->simann = this;
1.130 }
1.131 - /*! \brief Returns the cost of the current solution. */
1.132 + /// \brief Returns the cost of the current solution.
1.133 double getCurrCost() const { return curr_cost; }
1.134 - /*! \brief Returns the cost of the previous solution. */
1.135 + /// \brief Returns the cost of the previous solution.
1.136 double getPrevCost() const { return prev_cost; }
1.137 - /*! \brief Returns the cost of the best solution. */
1.138 + /// \brief Returns the cost of the best solution.
1.139 double getBestCost() const { return best_cost; }
1.140 - /*! \brief Returns the number of iterations. */
1.141 + /// \brief Returns the number of iterations done.
1.142 long getIter() const { return iter; }
1.143 - /*! \brief Returns the number of the last iteration when the solution was
1.144 - * improved.
1.145 - */
1.146 + /// \brief Returns the ordinal number of the last iteration when the
1.147 + /// solution was improved.
1.148 long getLastImpr() const { return last_impr; }
1.149 - /*! \brief Performs one iteration. */
1.150 + /// \brief Performs one iteration.
1.151 bool step() {
1.152 iter++;
1.153 prev_prev_cost = prev_cost;
1.154 @@ -130,28 +135,29 @@
1.155 }
1.156 return controller->next();
1.157 }
1.158 - /*! \brief Performs a given number of iterations.
1.159 - * \param n the number of iterations
1.160 - */
1.161 + /// \brief Performs a given number of iterations.
1.162 + /// \param n the number of iterations
1.163 bool step(int n) {
1.164 for(; n > 0 && step(); --n) ;
1.165 return !n;
1.166 }
1.167 - /*! \brief Starts the annealing process. */
1.168 + /// \brief Starts the annealing process.
1.169 void run() {
1.170 init();
1.171 do { } while (step());
1.172 }
1.173 + /// \brief Destructor.
1.174 + virtual ~SimAnnBase() {}
1.175 };
1.176
1.177 - /*! \brief Simulated annealing class. */
1.178 + /// \brief Simulated annealing class.
1.179 class SimAnn : public SimAnnBase {
1.180 private:
1.181 - /*! \brief Pointer to the current entity. */
1.182 + /// \brief Pointer to the current entity.
1.183 EntityBase *curr_ent;
1.184 - /*! \brief Pointer to the best entity. */
1.185 + /// \brief Pointer to the best entity.
1.186 EntityBase *best_ent;
1.187 - /*! \brief Does initializations before each run. */
1.188 + /// \brief Does initializations before each run.
1.189 void init() {
1.190 SimAnnBase::init();
1.191 if (best_ent) delete best_ent;
1.192 @@ -159,159 +165,166 @@
1.193 curr_ent->randomize();
1.194 }
1.195 public:
1.196 - /*! \brief Constructor. */
1.197 + /// \brief Constructor.
1.198 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
1.199 - /*! \brief Destructor. */
1.200 + /// \brief Destructor.
1.201 virtual ~SimAnn() {
1.202 if (best_ent) delete best_ent;
1.203 }
1.204 - /*! \brief Step to a neighbouring state. */
1.205 + /// \brief Step to a neighbouring state.
1.206 double mutate() {
1.207 return curr_ent->mutate();
1.208 }
1.209 - /*! \brief Reverts the last mutate(). */
1.210 + /// \brief Reverts the last mutate().
1.211 void revert() {
1.212 curr_ent->revert();
1.213 }
1.214 - /*! \brief Saves the current solution as the best one. */
1.215 + /// \brief Saves the current solution as the best one.
1.216 void saveAsBest() {
1.217 if (best_ent) delete best_ent;
1.218 best_ent = curr_ent->clone();
1.219 }
1.220 - /*! \brief Sets the current entity. */
1.221 + /// \brief Sets the current entity.
1.222 void setEntity(EntityBase &_ent) {
1.223 curr_ent = &_ent;
1.224 }
1.225 - /*! \brief Returns a copy of the best found entity. */
1.226 + /// \brief Returns a copy of the best found entity.
1.227 EntityBase* getBestEntity() { return best_ent->clone(); }
1.228 };
1.229
1.230 - /*! \brief A simple controller for the simulated annealing class. */
1.231 + /// \brief A simple controller for the simulated annealing class.
1.232 + /// This controller starts from a given initial temperature and evenly
1.233 + /// decreases it.
1.234 class SimpleController : public ControllerBase {
1.235 + private:
1.236 + /// \brief Maximum number of iterations.
1.237 + long max_iter;
1.238 + /// \brief Maximum number of iterations which do not improve the
1.239 + /// solution.
1.240 + long max_no_impr;
1.241 + /// \brief Temperature.
1.242 + double temp;
1.243 + /// \brief Annealing factor.
1.244 + double ann_fact;
1.245 + /// \brief Constructor.
1.246 + /// \param _max_iter maximum number of iterations
1.247 + /// \param _max_no_impr maximum number of consecutive iterations which do
1.248 + /// not yield a better solution
1.249 + /// \param _temp initial temperature
1.250 + /// \param _ann_fact annealing factor
1.251 public:
1.252 - /*! \brief Maximum number of iterations. */
1.253 - long max_iter;
1.254 - /*! \brief Maximum number of iterations which do not improve the
1.255 - * solution. */
1.256 - long max_no_impr;
1.257 - /*! \brief Temperature. */
1.258 - double temp;
1.259 - /*! \brief Annealing factor. */
1.260 - double ann_fact;
1.261 - /*! \brief Constructor.
1.262 - * \param _max_iter maximum number of iterations
1.263 - * \param _max_no_impr maximum number of consecutive iterations which do
1.264 - * not yield a better solution
1.265 - * \param _temp initial temperature
1.266 - * \param _ann_fact annealing factor
1.267 - */
1.268 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
1.269 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
1.270 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
1.271 {
1.272 srand48(time(0));
1.273 }
1.274 - /*! \brief This is called when a neighbouring state gets accepted. */
1.275 + /// \brief This is called when a neighbouring state gets accepted.
1.276 void acceptEvent() {}
1.277 - /*! \brief This is called when the accepted neighbouring state's cost is
1.278 - * less than the best found one's.
1.279 - */
1.280 + /// \brief This is called when the accepted neighbouring state's cost is
1.281 + /// less than the best found one's.
1.282 void improveEvent() {}
1.283 - /*! \brief This is called when a neighbouring state gets rejected. */
1.284 + /// \brief This is called when a neighbouring state gets rejected.
1.285 void rejectEvent() {}
1.286 - /*! \brief Decides whether to continue the annealing process or not. Also
1.287 - * decreases the temperature. */
1.288 + /// \brief Decides whether to continue the annealing process or not. Also
1.289 + /// decreases the temperature.
1.290 bool next() {
1.291 temp *= ann_fact;
1.292 bool quit = (simann->getIter() > max_iter) ||
1.293 (simann->getIter() - simann->getLastImpr() > max_no_impr);
1.294 return !quit;
1.295 }
1.296 - /*! \brief Decides whether to accept the current solution or not. */
1.297 + /// \brief Decides whether to accept the current solution or not.
1.298 bool accept() {
1.299 - double cost_diff = simann->getPrevCost() - simann->getCurrCost();
1.300 - return (drand48() <= exp(cost_diff / temp));
1.301 + double cost_diff = simann->getCurrCost() - simann->getPrevCost();
1.302 + return (drand48() <= exp(-(cost_diff / temp)));
1.303 }
1.304 + /// \brief Destructor.
1.305 + virtual ~SimpleController() {}
1.306 };
1.307
1.308 - /*! \brief A controller with preset running time for the simulated annealing
1.309 - * class.
1.310 - *
1.311 - * With this controller you can set the running time of the annealing
1.312 - * process in advance. It works the following way: the controller measures
1.313 - * a kind of divergence. The divergence is the difference of the average
1.314 - * cost of the recently found solutions the cost of the best found one. In
1.315 - * case this divergence is greater than a given threshold, then we decrease
1.316 - * the annealing factor, that is we cool the system faster. In case the
1.317 - * divergence is lower than the threshold, then we increase the temperature.
1.318 - * The threshold is a function of the elapsed time which reaches zero at the
1.319 - * desired end time.
1.320 - */
1.321 + /// \brief A controller with preset running time for the simulated annealing
1.322 + /// class.
1.323 + /// With this controller you can set the running time of the annealing
1.324 + /// process in advance. It works the following way: the controller measures
1.325 + /// a kind of divergence. The divergence is the difference of the average
1.326 + /// cost of the recently found solutions the cost of the best found one. In
1.327 + /// case this divergence is greater than a given threshold, then we decrease
1.328 + /// the annealing factor, that is we cool the system faster. In case the
1.329 + /// divergence is lower than the threshold, then we increase the temperature.
1.330 + /// The threshold is a function of the elapsed time which reaches zero at the
1.331 + /// desired end time.
1.332 class AdvancedController : public ControllerBase {
1.333 private:
1.334 + /// \brief Timer class to measure the elapsed time.
1.335 Timer timer;
1.336 - /*! \param time the elapsed time in seconds */
1.337 + /// \brief Calculates the threshold value.
1.338 + /// \param time the elapsed time in seconds
1.339 virtual double threshold(double time) {
1.340 return (-1.0) * start_threshold / end_time * time + start_threshold;
1.341 }
1.342 + /// \brief Parameter used to calculate the running average.
1.343 + double alpha;
1.344 + /// \brief Parameter used to decrease the annealing factor.
1.345 + double beta;
1.346 + /// \brief Parameter used to increase the temperature.
1.347 + double gamma;
1.348 + /// \brief The time at the end of the algorithm.
1.349 + double end_time;
1.350 + /// \brief The time at the start of the algorithm.
1.351 + double start_time;
1.352 + /// \brief Starting threshold.
1.353 + double start_threshold;
1.354 + /// \brief Average cost of recent solutions.
1.355 + double avg_cost;
1.356 + /// \brief Temperature.
1.357 + double temp;
1.358 + /// \brief Annealing factor.
1.359 + double ann_fact;
1.360 + /// \brief Initial annealing factor.
1.361 + double init_ann_fact;
1.362 + /// \brief True when the annealing process has been started.
1.363 + bool start;
1.364 public:
1.365 - double alpha;
1.366 - double beta;
1.367 - double gamma;
1.368 - /*! \brief The time at the end of the algorithm. */
1.369 - double end_time;
1.370 - /*! \brief The time at the start of the algorithm. */
1.371 - double start_time;
1.372 - /*! \brief Starting threshold. */
1.373 - double start_threshold;
1.374 - /*! \brief Average cost of recent solutions. */
1.375 - double avg_cost;
1.376 - /*! \brief Temperature. */
1.377 - double temp;
1.378 - /*! \brief Annealing factor. */
1.379 - double ann_fact;
1.380 - /*! \brief Initial annealing factor. */
1.381 - double init_ann_fact;
1.382 - bool warmup;
1.383 - /*! \brief Constructor.
1.384 - * \param _end_time running time in seconds
1.385 - * \param _alpha parameter used to calculate the running average
1.386 - * \param _beta parameter used to decrease the annealing factor
1.387 - * \param _gamma parameter used to increase the temperature
1.388 - * \param _ann_fact initial annealing factor
1.389 - */
1.390 + /// \brief Constructor.
1.391 + /// \param _end_time running time in seconds
1.392 + /// \param _alpha parameter used to calculate the running average
1.393 + /// \param _beta parameter used to decrease the annealing factor
1.394 + /// \param _gamma parameter used to increase the temperature
1.395 + /// \param _ann_fact initial annealing factor
1.396 AdvancedController(double _end_time, double _alpha = 0.2,
1.397 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
1.398 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
1.399 - ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)
1.400 + ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
1.401 {
1.402 srand48(time(0));
1.403 }
1.404 + /// \brief Does initializations before each run.
1.405 void init() {
1.406 avg_cost = simann->getCurrCost();
1.407 }
1.408 - /*! \brief This is called when a neighbouring state gets accepted. */
1.409 + /// \brief This is called when a neighbouring state gets accepted.
1.410 void acceptEvent() {
1.411 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
1.412 - if (warmup) {
1.413 + if (!start) {
1.414 static int cnt = 0;
1.415 cnt++;
1.416 if (cnt >= 100) {
1.417 // calculate starting threshold and starting temperature
1.418 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
1.419 temp = 10000.0;
1.420 - warmup = false;
1.421 + start = true;
1.422 timer.restart();
1.423 }
1.424 }
1.425 }
1.426 - /*! \brief Decides whether to continue the annealing process or not. */
1.427 + /// \brief Decides whether to continue the annealing process or not.
1.428 bool next() {
1.429 - if (warmup) {
1.430 + if (!start) {
1.431 return true;
1.432 }
1.433 else {
1.434 - double elapsed_time = timer.getRealTime();
1.435 + double elapsed_time = timer.realTime();
1.436 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
1.437 // decrease the annealing factor
1.438 ann_fact *= beta;
1.439 @@ -326,22 +339,18 @@
1.440 return elapsed_time < end_time;
1.441 }
1.442 }
1.443 - /*! \brief Decides whether to accept the current solution or not. */
1.444 + /// \brief Decides whether to accept the current solution or not.
1.445 bool accept() {
1.446 - if (warmup) {
1.447 - // we accept eveything during the "warm up" phase
1.448 + if (!start) {
1.449 return true;
1.450 }
1.451 else {
1.452 - double cost_diff = simann->getPrevCost() - simann->getCurrCost();
1.453 - if (cost_diff < 0.0) {
1.454 - return (drand48() <= exp(cost_diff / temp));
1.455 - }
1.456 - else {
1.457 - return true;
1.458 - }
1.459 + double cost_diff = simann->getCurrCost() - simann->getPrevCost();
1.460 + return (drand48() <= exp(-(cost_diff / temp)));
1.461 }
1.462 }
1.463 + /// \brief Destructor.
1.464 + virtual ~AdvancedController() {}
1.465 };
1.466
1.467 /// @}