1.1 --- a/src/work/akos/simann.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,328 +0,0 @@
1.4 -#ifndef LEMON_SIMANN_H
1.5 -#define LEMON_SIMANN_H
1.6 -
1.7 -/// \ingroup experimental
1.8 -/// \file
1.9 -/// \brief Simulated annealing framework.
1.10 -/// \author Akos Ladanyi
1.11 -
1.12 -#include <cstdlib>
1.13 -#include <cmath>
1.14 -#include <lemon/time_measure.h>
1.15 -
1.16 -namespace lemon {
1.17 -
1.18 -/// \addtogroup experimental
1.19 -/// @{
1.20 -
1.21 - const double INFTY = 1e24;
1.22 -
1.23 - /*! \brief Simulated annealing base class. */
1.24 - class SimAnnBase {
1.25 - public:
1.26 - class Controller;
1.27 - private:
1.28 - /*! Pointer to the controller. */
1.29 - Controller *controller;
1.30 - protected:
1.31 - /*! \brief Cost of the current solution. */
1.32 - double curr_cost;
1.33 - /*! \brief Cost of the best solution. */
1.34 - double best_cost;
1.35 - /*! \brief Cost of the previous solution. */
1.36 - double prev_cost;
1.37 - /*! \brief Cost of the solution preceding the previous one. */
1.38 - double prev_prev_cost;
1.39 -
1.40 - /*! \brief Step to a neighbouring state. */
1.41 - virtual void mutate() = 0;
1.42 - /*! \brief Reverts the last mutate(). */
1.43 - virtual void revert() = 0;
1.44 - /*! \brief Saves the current solution as the best one. */
1.45 - virtual void saveAsBest() = 0;
1.46 - public:
1.47 - /*! \brief Constructor. */
1.48 - SimAnnBase() {
1.49 - best_cost = prev_cost = prev_prev_cost = INFTY;
1.50 - }
1.51 - /*! \brief Sets the controller class to use. */
1.52 - void setController(Controller &_controller) {
1.53 - controller = &_controller;
1.54 - controller->setBase(this);
1.55 - }
1.56 - /*! \brief Returns the cost of the current solution. */
1.57 - double getCurrCost() const { return curr_cost; }
1.58 - /*! \brief Returns the cost of the previous solution. */
1.59 - double getPrevCost() const { return prev_cost; }
1.60 - /*! \brief Returns the cost of the best solution. */
1.61 - double getBestCost() const { return best_cost; }
1.62 - /*! \brief Starts the annealing process. */
1.63 - void run() {
1.64 - controller->init();
1.65 - do {
1.66 - curr_cost=mutate();
1.67 - if (controller->accept()) {
1.68 - controller->acceptEvent();
1.69 - if (curr_cost < best_cost) {
1.70 - saveAsBest();
1.71 - controller->improveEvent();
1.72 - }
1.73 - }
1.74 - else {
1.75 - revert();
1.76 - controller->rejectEvent();
1.77 - }
1.78 - } while (controller->next());
1.79 - }
1.80 -
1.81 - /*! \brief A base class for controllers. */
1.82 - class Controller {
1.83 - public:
1.84 - /*! \brief Pointer to the simulated annealing base class. */
1.85 - SimAnnBase *base;
1.86 - /*! \brief Initializes the controller. */
1.87 - virtual void init() {}
1.88 - /*! \brief This is called when a neighbouring state gets accepted. */
1.89 - virtual void acceptEvent() {}
1.90 - /*! \brief This is called when the accepted neighbouring state's cost is
1.91 - * less than the best found one's.
1.92 - */
1.93 - virtual void improveEvent() {}
1.94 - /*! \brief This is called when a neighbouring state gets rejected. */
1.95 - virtual void rejectEvent() {}
1.96 - /*! \brief Sets the simulated annealing base class to use. */
1.97 - virtual void setBase(SimAnnBase *_base) { base = _base; }
1.98 - /*! \brief Decides whether to continue the annealing process or not. */
1.99 - virtual bool next() = 0;
1.100 - /*! \brief Decides whether to accept the current solution or not. */
1.101 - virtual bool accept() = 0;
1.102 - };
1.103 - };
1.104 -
1.105 - /*! \brief Simulated annealing class. */
1.106 - template <typename E>
1.107 - class SimAnn : public SimAnnBase {
1.108 - private:
1.109 - /*! \brief Pointer to the current entity. */
1.110 - E *curr_ent;
1.111 - /*! \brief Pointer to the best entity. */
1.112 - E *best_ent;
1.113 - public:
1.114 - /*! \brief Constructor. */
1.115 - SimAnn() : SimAnnBase() {}
1.116 - /*! \brief Sets the initial entity. */
1.117 - void setEntity(E &ent) {
1.118 - curr_ent = new E(ent);
1.119 - best_ent = new E(ent);
1.120 - curr_cost = curr_ent->getCost();
1.121 - }
1.122 - /*! \brief Returns the best found entity. */
1.123 - E getBestEntity() { return *best_ent; }
1.124 - /*! \brief Step to a neighbouring state. */
1.125 - void mutate() {
1.126 - prev_prev_cost = prev_cost;
1.127 - prev_cost = curr_cost;
1.128 - curr_ent->mutate();
1.129 - curr_cost = curr_ent->getCost();
1.130 - }
1.131 - /*! \brief Reverts the last mutate(). */
1.132 - void revert() {
1.133 - curr_ent->revert();
1.134 - curr_cost = prev_cost;
1.135 - prev_cost = prev_prev_cost;
1.136 - }
1.137 - /*! \brief Saves the current solution as the best one. */
1.138 - void saveAsBest() {
1.139 - delete(best_ent);
1.140 - best_ent = new E(*curr_ent);
1.141 - best_cost = curr_cost;
1.142 - }
1.143 - };
1.144 -
1.145 - /*! \brief Skeleton of an entity class. */
1.146 - class EntitySkeleton {
1.147 - public:
1.148 - /*! \brief Returns the cost of the entity. */
1.149 - double getCost() { return 0.0; }
1.150 - /*! \brief Makes a minor change to the entity. */
1.151 - void mutate() {}
1.152 - /*! \brief Restores the entity to its previous state i.e. reverts the
1.153 - * effects of the last mutate().
1.154 - */
1.155 - void revert() {}
1.156 - };
1.157 -
1.158 - /*! \brief A simple controller for the simulated annealing class. */
1.159 - class SimpleController : public SimAnnBase::Controller {
1.160 - public:
1.161 - /*! \brief Number of iterations. */
1.162 - long iter;
1.163 - /*! \brief Number of iterations which did not improve the solution since
1.164 - * the last improvement. */
1.165 - long last_impr;
1.166 - /*! \brief Maximum number of iterations. */
1.167 - long max_iter;
1.168 - /*! \brief Maximum number of iterations which do not improve the
1.169 - * solution. */
1.170 - long max_no_impr;
1.171 - /*! \brief Temperature. */
1.172 - double temp;
1.173 - /*! \brief Annealing factor. */
1.174 - double ann_fact;
1.175 - /*! \brief Constructor.
1.176 - * \param _max_iter maximum number of iterations
1.177 - * \param _max_no_impr maximum number of consecutive iterations which do
1.178 - * not yield a better solution
1.179 - * \param _temp initial temperature
1.180 - * \param _ann_fact annealing factor
1.181 - */
1.182 - SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
1.183 - double _temp = 1000.0, double _ann_fact = 0.9999) : iter(0), last_impr(0),
1.184 - max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
1.185 - ann_fact(_ann_fact) {}
1.186 - /*! \brief This is called when a neighbouring state gets accepted. */
1.187 - void acceptEvent() {
1.188 - iter++;
1.189 - }
1.190 - /*! \brief This is called when the accepted neighbouring state's cost is
1.191 - * less than the best found one's.
1.192 - */
1.193 - void improveEvent() {
1.194 - last_impr = iter;
1.195 - }
1.196 - /*! \brief This is called when a neighbouring state gets rejected. */
1.197 - void rejectEvent() {
1.198 - iter++;
1.199 - }
1.200 - /*! \brief Decides whether to continue the annealing process or not. Also
1.201 - * decreases the temperature. */
1.202 - bool next() {
1.203 - temp *= ann_fact;
1.204 - bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
1.205 - return !quit;
1.206 - }
1.207 - /*! \brief Decides whether to accept the current solution or not. */
1.208 - bool accept() {
1.209 - double cost_diff = base->getPrevCost() - base->getCurrCost();
1.210 - if (cost_diff < 0.0) {
1.211 - bool ret = drand48() <= exp(cost_diff / temp);
1.212 - return ret;
1.213 - }
1.214 - else {
1.215 - return true;
1.216 - }
1.217 - }
1.218 - };
1.219 -
1.220 - /*! \brief A controller with preset running time for the simulated annealing
1.221 - * class.
1.222 - *
1.223 - * With this controller you can set the running time of the annealing
1.224 - * process in advance. It works the following way: the controller measures
1.225 - * a kind of divergence. The divergence is the difference of the average
1.226 - * cost of the recently found solutions the cost of the best found one. In
1.227 - * case this divergence is greater than a given threshold, then we decrease
1.228 - * the annealing factor, that is we cool the system faster. In case the
1.229 - * divergence is lower than the threshold, then we increase the temperature.
1.230 - * The threshold is a function of the elapsed time which reaches zero at the
1.231 - * desired end time.
1.232 - */
1.233 - class AdvancedController : public SimAnnBase::Controller {
1.234 - private:
1.235 - Timer timer;
1.236 - /*! \param time the elapsed time in seconds */
1.237 - virtual double threshold(double time) {
1.238 - return (-1.0) * start_threshold / end_time * time + start_threshold;
1.239 - }
1.240 - public:
1.241 - double alpha;
1.242 - double beta;
1.243 - double gamma;
1.244 - /*! \brief The time at the end of the algorithm. */
1.245 - double end_time;
1.246 - /*! \brief The time at the start of the algorithm. */
1.247 - double start_time;
1.248 - /*! \brief Starting threshold. */
1.249 - double start_threshold;
1.250 - /*! \brief Average cost of recent solutions. */
1.251 - double avg_cost;
1.252 - /*! \brief Temperature. */
1.253 - double temp;
1.254 - /*! \brief Annealing factor. */
1.255 - double ann_fact;
1.256 - /*! \brief Initial annealing factor. */
1.257 - double init_ann_fact;
1.258 - bool warmup;
1.259 - /*! \brief Constructor.
1.260 - * \param _end_time running time in seconds
1.261 - * \param _alpha parameter used to calculate the running average
1.262 - * \param _beta parameter used to decrease the annealing factor
1.263 - * \param _gamma parameter used to increase the temperature
1.264 - * \param _ann_fact initial annealing factor
1.265 - */
1.266 - AdvancedController(double _end_time, double _alpha = 0.2,
1.267 - double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
1.268 - alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
1.269 - ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true) {}
1.270 - void init() {
1.271 - avg_cost = base->getCurrCost();
1.272 - }
1.273 - /*! \brief This is called when a neighbouring state gets accepted. */
1.274 - void acceptEvent() {
1.275 - avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
1.276 - if (warmup) {
1.277 - static int cnt = 0;
1.278 - cnt++;
1.279 - if (cnt >= 100) {
1.280 - // calculate starting threshold and starting temperature
1.281 - start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
1.282 - temp = 10000.0;
1.283 - warmup = false;
1.284 - timer.reset();
1.285 - }
1.286 - }
1.287 - }
1.288 - /*! \brief Decides whether to continue the annealing process or not. */
1.289 - bool next() {
1.290 - if (warmup) {
1.291 - return true;
1.292 - }
1.293 - else {
1.294 - double elapsed_time = timer.getRealTime();
1.295 - if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
1.296 - // decrease the annealing factor
1.297 - ann_fact *= beta;
1.298 - }
1.299 - else {
1.300 - // increase the temperature
1.301 - temp *= gamma;
1.302 - // reset the annealing factor
1.303 - ann_fact = init_ann_fact;
1.304 - }
1.305 - temp *= ann_fact;
1.306 - return elapsed_time < end_time;
1.307 - }
1.308 - }
1.309 - /*! \brief Decides whether to accept the current solution or not. */
1.310 - bool accept() {
1.311 - if (warmup) {
1.312 - // we accept eveything during the "warm up" phase
1.313 - return true;
1.314 - }
1.315 - else {
1.316 - double cost_diff = base->getPrevCost() - base->getCurrCost();
1.317 - if (cost_diff < 0.0) {
1.318 - return (drand48() <= exp(cost_diff / temp));
1.319 - }
1.320 - else {
1.321 - return true;
1.322 - }
1.323 - }
1.324 - }
1.325 - };
1.326 -
1.327 -/// @}
1.328 -
1.329 -}
1.330 -
1.331 -#endif