Changeset 1142:450f794dca81 in lemon-0.x
- Timestamp:
- 02/08/05 12:27:03 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1541
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/akos/simann.h
r1096 r1142 1 1 #ifndef LEMON_SIMANN_H 2 2 #define LEMON_SIMANN_H 3 4 /// \ingroup experimental 5 /// \file 6 /// \brief Simulated annealing framework. 7 /// \author Akos Ladanyi 3 8 4 9 #include <cstdlib> … … 8 13 namespace lemon { 9 14 15 /// \addtogroup experimental 16 /// @{ 17 10 18 const double INFTY = 1e24; 11 19 20 /*! \brief Simulated annealing base class. */ 12 21 class SimAnnBase { 13 22 public: 14 23 class Controller; 15 24 private: 25 /*! Pointer to the controller. */ 16 26 Controller *controller; 17 27 protected: 28 /*! \brief Cost of the current solution. */ 18 29 double curr_cost; 30 /*! \brief Cost of the best solution. */ 19 31 double best_cost; 32 /*! \brief Cost of the previous solution. */ 20 33 double prev_cost; 34 /*! \brief Cost of the solution preceding the previous one. */ 21 35 double prev_prev_cost; 22 36 23 virtual void mutate() = 0; 24 virtual void revert() = 0; 25 virtual void saveAsBest() = 0; 26 public: 37 /*! \brief Step to a neighbouring state. */ 38 virtual void mutate() {} 39 /*! \brief Reverts the last mutate(). */ 40 virtual void revert() {} 41 /*! \brief Saves the current solution as the best one. */ 42 virtual void saveAsBest() {} 43 public: 44 /*! \brief Constructor. */ 27 45 SimAnnBase() { 28 46 best_cost = prev_cost = prev_prev_cost = INFTY; 29 47 } 48 /*! \brief Sets the controller class to use. */ 30 49 void setController(Controller &_controller) { 31 50 controller = &_controller; 32 51 controller->setBase(this); 33 52 } 53 /*! \brief Returns the cost of the current solution. */ 34 54 double getCurrCost() const { return curr_cost; } 55 /*! \brief Returns the cost of the previous solution. */ 35 56 double getPrevCost() const { return prev_cost; } 57 /*! \brief Returns the cost of the best solution. */ 36 58 double getBestCost() const { return best_cost; } 59 /*! \brief Starts the annealing process. */ 37 60 void run() { 38 61 controller->init(); … … 56 79 class Controller { 57 80 public: 81 /*! \brief Pointer to the simulated annealing base class. */ 58 82 SimAnnBase *base; 83 /*! \brief Initializes the controller. */ 59 84 virtual void init() {} 60 85 /*! \brief This is called when a neighbouring state gets accepted. */ … … 66 91 /*! \brief This is called when a neighbouring state gets rejected. */ 67 92 virtual void rejectEvent() {} 93 /*! \brief Sets the simulated annealing base class to use. */ 68 94 virtual void setBase(SimAnnBase *_base) { base = _base; } 69 /*! */95 /*! \brief Decides whether to continue the annealing process or not. */ 70 96 virtual bool next() = 0; 71 /*! */97 /*! \brief Decides whether to accept the current solution or not. */ 72 98 virtual bool accept() = 0; 73 99 }; 74 100 }; 75 101 102 /*! \brief Simulated annealing class. */ 76 103 template <typename E> 77 104 class SimAnn : public SimAnnBase { 78 105 private: 106 /*! \brief Pointer to the current entity. */ 79 107 E *curr_ent; 108 /*! \brief Pointer to the best entity. */ 80 109 E *best_ent; 81 110 public: 111 /*! \brief Constructor. */ 82 112 SimAnn() : SimAnnBase() {} 113 /*! \brief Sets the initial entity. */ 83 114 void setEntity(E &ent) { 84 115 curr_ent = new E(ent); … … 86 117 curr_cost = curr_ent->getCost(); 87 118 } 119 /*! \brief Returns the best found entity. */ 88 120 E getBestEntity() { return *best_ent; } 121 /*! \brief Step to a neighbouring state. */ 89 122 void mutate() { 90 123 prev_prev_cost = prev_cost; … … 93 126 curr_cost = curr_ent->getCost(); 94 127 } 128 /*! \brief Reverts the last mutate(). */ 95 129 void revert() { 96 130 curr_ent->revert(); … … 98 132 prev_cost = prev_prev_cost; 99 133 } 134 /*! \brief Saves the current solution as the best one. */ 100 135 void saveAsBest() { 101 136 delete(best_ent); … … 105 140 }; 106 141 142 /*! \brief Skeleton of an entity class. */ 107 143 class EntitySkeleton { 108 144 public: 109 /*! \ return the cost of the entity*/145 /*! \brief Returns the cost of the entity. */ 110 146 double getCost() { return 0.0; } 111 147 /*! \brief Makes a minor change to the entity. */ 112 148 void mutate() {} 113 149 /*! \brief Restores the entity to its previous state i.e. reverts the 114 * effects of the last mutate .150 * effects of the last mutate(). 115 151 */ 116 152 void revert() {} 117 153 }; 118 154 119 /*! \brief A simple controller for the simulated annealing class. 120 * \todo Find a way to set the various parameters. 121 */ 155 /*! \brief A simple controller for the simulated annealing class. */ 122 156 class SimpleController : public SimAnnBase::Controller { 123 157 public: 124 long iter, last_impr, max_iter, max_no_impr; 125 double temp, ann_fact; 126 /*! \param _max_iter maximum number of iterations 158 /*! \brief Number of iterations. */ 159 long iter; 160 /*! \brief Number of iterations which did not improve the solution since 161 * the last improvement. */ 162 long last_impr; 163 /*! \brief Maximum number of iterations. */ 164 long max_iter; 165 /*! \brief Maximum number of iterations which do not improve the 166 * solution. */ 167 long max_no_impr; 168 /*! \brief Temperature. */ 169 double temp; 170 /*! \brief Annealing factor. */ 171 double ann_fact; 172 /*! \brief Constructor. 173 * \param _max_iter maximum number of iterations 127 174 * \param _max_no_impr maximum number of consecutive iterations which do 128 175 * not yield a better solution … … 137 184 iter++; 138 185 } 186 /*! \brief This is called when the accepted neighbouring state's cost is 187 * less than the best found one's. 188 */ 139 189 void improveEvent() { 140 190 last_impr = iter; 141 191 } 192 /*! \brief This is called when a neighbouring state gets rejected. */ 142 193 void rejectEvent() { 143 194 iter++; 144 195 } 196 /*! \brief Decides whether to continue the annealing process or not. Also 197 * decreases the temperature. */ 145 198 bool next() { 146 199 temp *= ann_fact; … … 148 201 return !quit; 149 202 } 203 /*! \brief Decides whether to accept the current solution or not. */ 150 204 bool accept() { 151 205 double cost_diff = base->getPrevCost() - base->getCurrCost(); … … 162 216 /*! \brief A controller with preset running time for the simulated annealing 163 217 * class. 164 * \todo Find a better name.165 218 */ 166 219 class AdvancedController : public SimAnnBase::Controller { … … 169 222 /*! \param time the elapsed time in seconds */ 170 223 virtual double threshold(double time) { 171 // 1 / log(x)172 /*173 static double xm = 5.0 / end_time;174 static double ym = start_threshold / (1 / log(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 224 return (-1.0) * start_threshold / end_time * time + start_threshold; 178 225 } 179 226 public: 180 double alpha, beta, gamma; 181 double end_time, start_time; 227 double alpha; 228 double beta; 229 double gamma; 230 double end_time; 231 double start_time; 182 232 double start_threshold; 183 233 double avg_cost; 184 double temp, ann_fact; 234 double temp; 235 double ann_fact; 185 236 bool warmup; 186 /*! \param _end_time running time in seconds 237 /*! \brief Constructor. 238 * \param _end_time running time in seconds 187 239 * \param _alpha parameter used to calculate the running average 188 240 * \param _beta parameter used to decrease the annealing factor … … 195 247 avg_cost = base->getCurrCost(); 196 248 } 249 /*! \brief This is called when a neighbouring state gets accepted. */ 197 250 void acceptEvent() { 198 251 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost; … … 203 256 // calculate starting threshold and starting temperature 204 257 start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost); 205 //temp = max_cost_diff / log(0.5);206 258 temp = 10000.0; 207 259 warmup = false; … … 210 262 } 211 263 } 212 void improveEvent() { 213 } 214 void rejectEvent() { 215 } 264 /*! \brief Decides whether to continue the annealing process or not. */ 216 265 bool next() { 217 266 if (warmup) { … … 227 276 // increase the temperature 228 277 temp *= gamma; 229 ann_fact = 0.99999999; 278 ann_fact = 0.99999999; // !!!!!!!!!!! 230 279 } 231 280 temp *= ann_fact; … … 233 282 } 234 283 } 284 /*! \brief Decides whether to accept the current solution or not. */ 235 285 bool accept() { 236 286 if (warmup) { … … 250 300 }; 251 301 302 /// @} 303 252 304 } 253 305
Note: See TracChangeset
for help on using the changeset viewer.