1.1 --- a/src/work/akos/simann.h Mon Feb 07 17:35:25 2005 +0000
1.2 +++ b/src/work/akos/simann.h Tue Feb 08 11:27:03 2005 +0000
1.3 @@ -1,39 +1,62 @@
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 - virtual void mutate() = 0;
1.41 - virtual void revert() = 0;
1.42 - virtual void saveAsBest() = 0;
1.43 + /*! \brief Step to a neighbouring state. */
1.44 + virtual void mutate() {}
1.45 + /*! \brief Reverts the last mutate(). */
1.46 + virtual void revert() {}
1.47 + /*! \brief Saves the current solution as the best one. */
1.48 + virtual void saveAsBest() {}
1.49 public:
1.50 + /*! \brief Constructor. */
1.51 SimAnnBase() {
1.52 best_cost = prev_cost = prev_prev_cost = INFTY;
1.53 }
1.54 + /*! \brief Sets the controller class to use. */
1.55 void setController(Controller &_controller) {
1.56 controller = &_controller;
1.57 controller->setBase(this);
1.58 }
1.59 + /*! \brief Returns the cost of the current solution. */
1.60 double getCurrCost() const { return curr_cost; }
1.61 + /*! \brief Returns the cost of the previous solution. */
1.62 double getPrevCost() const { return prev_cost; }
1.63 + /*! \brief Returns the cost of the best solution. */
1.64 double getBestCost() const { return best_cost; }
1.65 + /*! \brief Starts the annealing process. */
1.66 void run() {
1.67 controller->init();
1.68 do {
1.69 @@ -55,7 +78,9 @@
1.70 /*! \brief A base class for controllers. */
1.71 class Controller {
1.72 public:
1.73 + /*! \brief Pointer to the simulated annealing base class. */
1.74 SimAnnBase *base;
1.75 + /*! \brief Initializes the controller. */
1.76 virtual void init() {}
1.77 /*! \brief This is called when a neighbouring state gets accepted. */
1.78 virtual void acceptEvent() {}
1.79 @@ -65,38 +90,48 @@
1.80 virtual void improveEvent() {}
1.81 /*! \brief This is called when a neighbouring state gets rejected. */
1.82 virtual void rejectEvent() {}
1.83 + /*! \brief Sets the simulated annealing base class to use. */
1.84 virtual void setBase(SimAnnBase *_base) { base = _base; }
1.85 - /*! */
1.86 + /*! \brief Decides whether to continue the annealing process or not. */
1.87 virtual bool next() = 0;
1.88 - /*! */
1.89 + /*! \brief Decides whether to accept the current solution or not. */
1.90 virtual bool accept() = 0;
1.91 };
1.92 };
1.93
1.94 + /*! \brief Simulated annealing class. */
1.95 template <typename E>
1.96 class SimAnn : public SimAnnBase {
1.97 private:
1.98 + /*! \brief Pointer to the current entity. */
1.99 E *curr_ent;
1.100 + /*! \brief Pointer to the best entity. */
1.101 E *best_ent;
1.102 public:
1.103 + /*! \brief Constructor. */
1.104 SimAnn() : SimAnnBase() {}
1.105 + /*! \brief Sets the initial entity. */
1.106 void setEntity(E &ent) {
1.107 curr_ent = new E(ent);
1.108 best_ent = new E(ent);
1.109 curr_cost = curr_ent->getCost();
1.110 }
1.111 + /*! \brief Returns the best found entity. */
1.112 E getBestEntity() { return *best_ent; }
1.113 + /*! \brief Step to a neighbouring state. */
1.114 void mutate() {
1.115 prev_prev_cost = prev_cost;
1.116 prev_cost = curr_cost;
1.117 curr_ent->mutate();
1.118 curr_cost = curr_ent->getCost();
1.119 }
1.120 + /*! \brief Reverts the last mutate(). */
1.121 void revert() {
1.122 curr_ent->revert();
1.123 curr_cost = prev_cost;
1.124 prev_cost = prev_prev_cost;
1.125 }
1.126 + /*! \brief Saves the current solution as the best one. */
1.127 void saveAsBest() {
1.128 delete(best_ent);
1.129 best_ent = new E(*curr_ent);
1.130 @@ -104,26 +139,38 @@
1.131 }
1.132 };
1.133
1.134 + /*! \brief Skeleton of an entity class. */
1.135 class EntitySkeleton {
1.136 public:
1.137 - /*! \return the cost of the entity */
1.138 + /*! \brief Returns the cost of the entity. */
1.139 double getCost() { return 0.0; }
1.140 /*! \brief Makes a minor change to the entity. */
1.141 void mutate() {}
1.142 /*! \brief Restores the entity to its previous state i.e. reverts the
1.143 - * effects of the last mutate.
1.144 + * effects of the last mutate().
1.145 */
1.146 void revert() {}
1.147 };
1.148
1.149 - /*! \brief A simple controller for the simulated annealing class.
1.150 - * \todo Find a way to set the various parameters.
1.151 - */
1.152 + /*! \brief A simple controller for the simulated annealing class. */
1.153 class SimpleController : public SimAnnBase::Controller {
1.154 public:
1.155 - long iter, last_impr, max_iter, max_no_impr;
1.156 - double temp, ann_fact;
1.157 - /*! \param _max_iter maximum number of iterations
1.158 + /*! \brief Number of iterations. */
1.159 + long iter;
1.160 + /*! \brief Number of iterations which did not improve the solution since
1.161 + * the last improvement. */
1.162 + long last_impr;
1.163 + /*! \brief Maximum number of iterations. */
1.164 + long max_iter;
1.165 + /*! \brief Maximum number of iterations which do not improve the
1.166 + * solution. */
1.167 + long max_no_impr;
1.168 + /*! \brief Temperature. */
1.169 + double temp;
1.170 + /*! \brief Annealing factor. */
1.171 + double ann_fact;
1.172 + /*! \brief Constructor.
1.173 + * \param _max_iter maximum number of iterations
1.174 * \param _max_no_impr maximum number of consecutive iterations which do
1.175 * not yield a better solution
1.176 * \param _temp initial temperature
1.177 @@ -136,17 +183,24 @@
1.178 void acceptEvent() {
1.179 iter++;
1.180 }
1.181 + /*! \brief This is called when the accepted neighbouring state's cost is
1.182 + * less than the best found one's.
1.183 + */
1.184 void improveEvent() {
1.185 last_impr = iter;
1.186 }
1.187 + /*! \brief This is called when a neighbouring state gets rejected. */
1.188 void rejectEvent() {
1.189 iter++;
1.190 }
1.191 + /*! \brief Decides whether to continue the annealing process or not. Also
1.192 + * decreases the temperature. */
1.193 bool next() {
1.194 temp *= ann_fact;
1.195 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
1.196 return !quit;
1.197 }
1.198 + /*! \brief Decides whether to accept the current solution or not. */
1.199 bool accept() {
1.200 double cost_diff = base->getPrevCost() - base->getCurrCost();
1.201 if (cost_diff < 0.0) {
1.202 @@ -161,29 +215,27 @@
1.203
1.204 /*! \brief A controller with preset running time for the simulated annealing
1.205 * class.
1.206 - * \todo Find a better name.
1.207 */
1.208 class AdvancedController : public SimAnnBase::Controller {
1.209 private:
1.210 Timer timer;
1.211 /*! \param time the elapsed time in seconds */
1.212 virtual double threshold(double time) {
1.213 - // 1 / log(x)
1.214 - /*
1.215 - static double xm = 5.0 / end_time;
1.216 - static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
1.217 - return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
1.218 - */
1.219 return (-1.0) * start_threshold / end_time * time + start_threshold;
1.220 }
1.221 public:
1.222 - double alpha, beta, gamma;
1.223 - double end_time, start_time;
1.224 + double alpha;
1.225 + double beta;
1.226 + double gamma;
1.227 + double end_time;
1.228 + double start_time;
1.229 double start_threshold;
1.230 double avg_cost;
1.231 - double temp, ann_fact;
1.232 + double temp;
1.233 + double ann_fact;
1.234 bool warmup;
1.235 - /*! \param _end_time running time in seconds
1.236 + /*! \brief Constructor.
1.237 + * \param _end_time running time in seconds
1.238 * \param _alpha parameter used to calculate the running average
1.239 * \param _beta parameter used to decrease the annealing factor
1.240 * \param _gamma parameter used to increase the temperature
1.241 @@ -194,6 +246,7 @@
1.242 void init() {
1.243 avg_cost = base->getCurrCost();
1.244 }
1.245 + /*! \brief This is called when a neighbouring state gets accepted. */
1.246 void acceptEvent() {
1.247 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
1.248 if (warmup) {
1.249 @@ -202,17 +255,13 @@
1.250 if (cnt >= 100) {
1.251 // calculate starting threshold and starting temperature
1.252 start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
1.253 - //temp = max_cost_diff / log(0.5);
1.254 temp = 10000.0;
1.255 warmup = false;
1.256 timer.reset();
1.257 }
1.258 }
1.259 }
1.260 - void improveEvent() {
1.261 - }
1.262 - void rejectEvent() {
1.263 - }
1.264 + /*! \brief Decides whether to continue the annealing process or not. */
1.265 bool next() {
1.266 if (warmup) {
1.267 return true;
1.268 @@ -226,12 +275,13 @@
1.269 else {
1.270 // increase the temperature
1.271 temp *= gamma;
1.272 - ann_fact = 0.99999999;
1.273 + ann_fact = 0.99999999; // !!!!!!!!!!!
1.274 }
1.275 temp *= ann_fact;
1.276 return elapsed_time < end_time;
1.277 }
1.278 }
1.279 + /*! \brief Decides whether to accept the current solution or not. */
1.280 bool accept() {
1.281 if (warmup) {
1.282 // we accept eveything during the "warm up" phase
1.283 @@ -249,6 +299,8 @@
1.284 }
1.285 };
1.286
1.287 +/// @}
1.288 +
1.289 }
1.290
1.291 #endif