Changeset 1918:09415ae11103 in lemon0.x for lemon
 Timestamp:
 01/29/06 23:06:10 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2493
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/simann.h
r1847 r1918 12 12 #include <cstdlib> 13 13 #include <cmath> 14 #include <limits> 14 15 #include <lemon/time_measure.h> 15 16 … … 19 20 /// @{ 20 21 21 / *! \brief A base class for controllers. */22 /// \brief A base class for controllers. 22 23 class ControllerBase { 24 public: 23 25 friend class SimAnnBase; 24 public: 25 /*! \brief Pointer to the simulated annealing base class. */ 26 /// \brief Pointer to the simulated annealing base class. 26 27 SimAnnBase *simann; 27 / *! \brief Initializes the controller. */28 /// \brief Initializes the controller. 28 29 virtual void init() {} 29 /*! \brief This is called when a neighbouring state gets accepted. */ 30 /// \brief This is called by the simulated annealing class when a 31 /// neighbouring state gets accepted. 30 32 virtual void acceptEvent() {} 31 /*! \brief This is called when the accepted neighbouring state's cost is 32 * less than the best found one's. 33 */ 33 /// \brief This is called by the simulated annealing class when the 34 /// accepted neighbouring state's cost is less than the best found one's. 34 35 virtual void improveEvent() {} 35 /*! \brief This is called when a neighbouring state gets rejected. */ 36 /// \brief This is called by the simulated annealing class when a 37 /// neighbouring state gets rejected. 36 38 virtual void rejectEvent() {} 37 / *! \brief Decides whether to continue the annealing process or not. */39 /// \brief Decides whether to continue the annealing process or not. 38 40 virtual bool next() = 0; 39 / *! \brief Decides whether to accept the current solution or not. */41 /// \brief Decides whether to accept the current solution or not. 40 42 virtual bool accept() = 0; 41 }; 42 43 /*! \brief Skeleton of an entity class. */ 43 /// \brief Destructor. 44 virtual ~ControllerBase() {} 45 }; 46 47 /// \brief Skeleton of an entity class. 44 48 class EntityBase { 45 49 public: 46 /*! \brief Makes a minor change to the entity. 47 * \return the new cost 48 */ 50 /// \brief Makes a minor change to the entity. 51 /// \return the new cost 49 52 virtual double mutate() = 0; 50 /*! \brief Restores the entity to its previous state i.e. reverts the 51 * effects of the last mutate(). 52 */ 53 /// \brief Restores the entity to its previous state i.e. reverts the 54 /// effects of the last mutate(). 53 55 virtual void revert() = 0; 54 / *! \brief Makes a copy of the entity. */56 /// \brief Makes a copy of the entity. 55 57 virtual EntityBase* clone() = 0; 56 / *! \brief Makes a major change to the entity. */58 /// \brief Makes a major change to the entity. 57 59 virtual void randomize() = 0; 58 }; 59 60 /*! \brief Simulated annealing base class. */ 60 /// \brief Destructor. 61 virtual ~EntityBase() {} 62 }; 63 64 /// \brief Simulated annealing abstract base class. 65 /// Can be used to derive a custom simulated annealing class if \ref SimAnn 66 /// doesn't fit your needs. 61 67 class SimAnnBase { 62 68 private: 63 / *! Pointer to the controller. */69 /// \brief Pointer to the controller. 64 70 ControllerBase *controller; 65 / *! \brief Cost of the current solution. */71 /// \brief Cost of the current solution. 66 72 double curr_cost; 67 / *! \brief Cost of the best solution. */73 /// \brief Cost of the best solution. 68 74 double best_cost; 69 / *! \brief Cost of the previous solution. */75 /// \brief Cost of the previous solution. 70 76 double prev_cost; 71 / *! \brief Cost of the solution preceding the previous one. */77 /// \brief Cost of the solution preceding the previous one. 72 78 double prev_prev_cost; 73 / *! \brief Number of iterations. */79 /// \brief Number of iterations. 74 80 long iter; 75 / *!\brief Number of iterations which did not improve the solution since76 * the last improvement. */81 /// \brief Number of iterations which did not improve the solution since 82 /// the last improvement. 77 83 long last_impr; 78 84 protected: 79 / *! \brief Step to a neighbouring state. */85 /// \brief Step to a neighbouring state. 80 86 virtual double mutate() = 0; 81 / *! \brief Reverts the last mutate(). */87 /// \brief Reverts the last mutate(). 82 88 virtual void revert() = 0; 83 / *! \brief Saves the current solution as the best one. */89 /// \brief Saves the current solution as the best one. 84 90 virtual void saveAsBest() = 0; 85 / *! \brief Does initializations before each run. */91 /// \brief Does initializations before each run. 86 92 virtual void init() { 87 93 controller>init(); … … 91 97 } 92 98 public: 93 / *! \brief Sets the controller class to use. */99 /// \brief Sets the controller class to use. 94 100 void setController(ControllerBase &_controller) { 95 101 controller = &_controller; 96 102 controller>simann = this; 97 103 } 98 / *! \brief Returns the cost of the current solution. */104 /// \brief Returns the cost of the current solution. 99 105 double getCurrCost() const { return curr_cost; } 100 / *! \brief Returns the cost of the previous solution. */106 /// \brief Returns the cost of the previous solution. 101 107 double getPrevCost() const { return prev_cost; } 102 / *! \brief Returns the cost of the best solution. */108 /// \brief Returns the cost of the best solution. 103 109 double getBestCost() const { return best_cost; } 104 / *! \brief Returns the number of iterations. */110 /// \brief Returns the number of iterations done. 105 111 long getIter() const { return iter; } 106 /*! \brief Returns the number of the last iteration when the solution was 107 * improved. 108 */ 112 /// \brief Returns the ordinal number of the last iteration when the 113 /// solution was improved. 109 114 long getLastImpr() const { return last_impr; } 110 / *! \brief Performs one iteration. */115 /// \brief Performs one iteration. 111 116 bool step() { 112 117 iter++; … … 131 136 return controller>next(); 132 137 } 133 /*! \brief Performs a given number of iterations. 134 * \param n the number of iterations 135 */ 138 /// \brief Performs a given number of iterations. 139 /// \param n the number of iterations 136 140 bool step(int n) { 137 141 for(; n > 0 && step(); n) ; 138 142 return !n; 139 143 } 140 / *! \brief Starts the annealing process. */144 /// \brief Starts the annealing process. 141 145 void run() { 142 146 init(); 143 147 do { } while (step()); 144 148 } 145 }; 146 147 /*! \brief Simulated annealing class. */ 149 /// \brief Destructor. 150 virtual ~SimAnnBase() {} 151 }; 152 153 /// \brief Simulated annealing class. 148 154 class SimAnn : public SimAnnBase { 149 155 private: 150 / *! \brief Pointer to the current entity. */156 /// \brief Pointer to the current entity. 151 157 EntityBase *curr_ent; 152 / *! \brief Pointer to the best entity. */158 /// \brief Pointer to the best entity. 153 159 EntityBase *best_ent; 154 / *! \brief Does initializations before each run. */160 /// \brief Does initializations before each run. 155 161 void init() { 156 162 SimAnnBase::init(); … … 160 166 } 161 167 public: 162 / *! \brief Constructor. */168 /// \brief Constructor. 163 169 SimAnn() : curr_ent(NULL), best_ent(NULL) {} 164 / *! \brief Destructor. */170 /// \brief Destructor. 165 171 virtual ~SimAnn() { 166 172 if (best_ent) delete best_ent; 167 173 } 168 / *! \brief Step to a neighbouring state. */174 /// \brief Step to a neighbouring state. 169 175 double mutate() { 170 176 return curr_ent>mutate(); 171 177 } 172 / *! \brief Reverts the last mutate(). */178 /// \brief Reverts the last mutate(). 173 179 void revert() { 174 180 curr_ent>revert(); 175 181 } 176 / *! \brief Saves the current solution as the best one. */182 /// \brief Saves the current solution as the best one. 177 183 void saveAsBest() { 178 184 if (best_ent) delete best_ent; 179 185 best_ent = curr_ent>clone(); 180 186 } 181 / *! \brief Sets the current entity. */187 /// \brief Sets the current entity. 182 188 void setEntity(EntityBase &_ent) { 183 189 curr_ent = &_ent; 184 190 } 185 / *! \brief Returns a copy of the best found entity. */191 /// \brief Returns a copy of the best found entity. 186 192 EntityBase* getBestEntity() { return best_ent>clone(); } 187 193 }; 188 194 189 /*! \brief A simple controller for the simulated annealing class. */ 195 /// \brief A simple controller for the simulated annealing class. 196 /// This controller starts from a given initial temperature and evenly 197 /// decreases it. 190 198 class SimpleController : public ControllerBase { 191 p ublic:192 / *! \brief Maximum number of iterations. */199 private: 200 /// \brief Maximum number of iterations. 193 201 long max_iter; 194 / *!\brief Maximum number of iterations which do not improve the195 * solution. */202 /// \brief Maximum number of iterations which do not improve the 203 /// solution. 196 204 long max_no_impr; 197 / *! \brief Temperature. */205 /// \brief Temperature. 198 206 double temp; 199 / *! \brief Annealing factor. */207 /// \brief Annealing factor. 200 208 double ann_fact; 201 / *!\brief Constructor.202 *\param _max_iter maximum number of iterations203 *\param _max_no_impr maximum number of consecutive iterations which do204 *not yield a better solution205 *\param _temp initial temperature206 *\param _ann_fact annealing factor207 */209 /// \brief Constructor. 210 /// \param _max_iter maximum number of iterations 211 /// \param _max_no_impr maximum number of consecutive iterations which do 212 /// not yield a better solution 213 /// \param _temp initial temperature 214 /// \param _ann_fact annealing factor 215 public: 208 216 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000, 209 217 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter), … … 212 220 srand48(time(0)); 213 221 } 214 / *! \brief This is called when a neighbouring state gets accepted. */222 /// \brief This is called when a neighbouring state gets accepted. 215 223 void acceptEvent() {} 216 /*! \brief This is called when the accepted neighbouring state's cost is 217 * less than the best found one's. 218 */ 224 /// \brief This is called when the accepted neighbouring state's cost is 225 /// less than the best found one's. 219 226 void improveEvent() {} 220 / *! \brief This is called when a neighbouring state gets rejected. */227 /// \brief This is called when a neighbouring state gets rejected. 221 228 void rejectEvent() {} 222 / *!\brief Decides whether to continue the annealing process or not. Also223 * decreases the temperature. */229 /// \brief Decides whether to continue the annealing process or not. Also 230 /// decreases the temperature. 224 231 bool next() { 225 232 temp *= ann_fact; … … 228 235 return !quit; 229 236 } 230 / *! \brief Decides whether to accept the current solution or not. */237 /// \brief Decides whether to accept the current solution or not. 231 238 bool accept() { 232 double cost_diff = simann>get PrevCost()  simann>getCurrCost();233 return (drand48() <= exp( cost_diff / temp));234 } 235 };236 237 /*! \brief A controller with preset running time for the simulated annealing238 * class. 239 *240 * With this controller you can set the running time of the annealing241 * process in advance. It works the following way: the controller measures242 * a kind of divergence. The divergence is the difference of the average243 * cost of the recently found solutions the cost of the best found one. In244 * case this divergence is greater than a given threshold, then we decrease245 * the annealing factor, that is we cool the system faster. In case the246 * divergence is lower than the threshold, then we increase the temperature.247 * The threshold is a function of the elapsed time which reaches zero at the248 * desired end time.249 */239 double cost_diff = simann>getCurrCost()  simann>getPrevCost(); 240 return (drand48() <= exp((cost_diff / temp))); 241 } 242 /// \brief Destructor. 243 virtual ~SimpleController() {} 244 }; 245 246 /// \brief A controller with preset running time for the simulated annealing 247 /// class. 248 /// With this controller you can set the running time of the annealing 249 /// process in advance. It works the following way: the controller measures 250 /// a kind of divergence. The divergence is the difference of the average 251 /// cost of the recently found solutions the cost of the best found one. In 252 /// case this divergence is greater than a given threshold, then we decrease 253 /// the annealing factor, that is we cool the system faster. In case the 254 /// divergence is lower than the threshold, then we increase the temperature. 255 /// The threshold is a function of the elapsed time which reaches zero at the 256 /// desired end time. 250 257 class AdvancedController : public ControllerBase { 251 258 private: 259 /// \brief Timer class to measure the elapsed time. 252 260 Timer timer; 253 /*! \param time the elapsed time in seconds */ 261 /// \brief Calculates the threshold value. 262 /// \param time the elapsed time in seconds 254 263 virtual double threshold(double time) { 255 264 return (1.0) * start_threshold / end_time * time + start_threshold; 256 265 } 257 public:266 /// \brief Parameter used to calculate the running average. 258 267 double alpha; 268 /// \brief Parameter used to decrease the annealing factor. 259 269 double beta; 270 /// \brief Parameter used to increase the temperature. 260 271 double gamma; 261 / *! \brief The time at the end of the algorithm. */272 /// \brief The time at the end of the algorithm. 262 273 double end_time; 263 / *! \brief The time at the start of the algorithm. */274 /// \brief The time at the start of the algorithm. 264 275 double start_time; 265 / *! \brief Starting threshold. */276 /// \brief Starting threshold. 266 277 double start_threshold; 267 / *! \brief Average cost of recent solutions. */278 /// \brief Average cost of recent solutions. 268 279 double avg_cost; 269 / *! \brief Temperature. */280 /// \brief Temperature. 270 281 double temp; 271 / *! \brief Annealing factor. */282 /// \brief Annealing factor. 272 283 double ann_fact; 273 / *! \brief Initial annealing factor. */284 /// \brief Initial annealing factor. 274 285 double init_ann_fact; 275 bool warmup; 276 /*! \brief Constructor. 277 * \param _end_time running time in seconds 278 * \param _alpha parameter used to calculate the running average 279 * \param _beta parameter used to decrease the annealing factor 280 * \param _gamma parameter used to increase the temperature 281 * \param _ann_fact initial annealing factor 282 */ 286 /// \brief True when the annealing process has been started. 287 bool start; 288 public: 289 /// \brief Constructor. 290 /// \param _end_time running time in seconds 291 /// \param _alpha parameter used to calculate the running average 292 /// \param _beta parameter used to decrease the annealing factor 293 /// \param _gamma parameter used to increase the temperature 294 /// \param _ann_fact initial annealing factor 283 295 AdvancedController(double _end_time, double _alpha = 0.2, 284 296 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) : 285 297 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time), 286 ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)298 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false) 287 299 { 288 300 srand48(time(0)); 289 301 } 302 /// \brief Does initializations before each run. 290 303 void init() { 291 304 avg_cost = simann>getCurrCost(); 292 305 } 293 / *! \brief This is called when a neighbouring state gets accepted. */306 /// \brief This is called when a neighbouring state gets accepted. 294 307 void acceptEvent() { 295 308 avg_cost = alpha * simann>getCurrCost() + (1.0  alpha) * avg_cost; 296 if ( warmup) {309 if (!start) { 297 310 static int cnt = 0; 298 311 cnt++; … … 301 314 start_threshold = 5.0 * fabs(simann>getBestCost()  avg_cost); 302 315 temp = 10000.0; 303 warmup = false;316 start = true; 304 317 timer.restart(); 305 318 } 306 319 } 307 320 } 308 / *! \brief Decides whether to continue the annealing process or not. */321 /// \brief Decides whether to continue the annealing process or not. 309 322 bool next() { 310 if ( warmup) {323 if (!start) { 311 324 return true; 312 325 } 313 326 else { 314 double elapsed_time = timer. getRealTime();327 double elapsed_time = timer.realTime(); 315 328 if (fabs(avg_cost  simann>getBestCost()) > threshold(elapsed_time)) { 316 329 // decrease the annealing factor … … 327 340 } 328 341 } 329 / *! \brief Decides whether to accept the current solution or not. */342 /// \brief Decides whether to accept the current solution or not. 330 343 bool accept() { 331 if (warmup) { 332 // we accept eveything during the "warm up" phase 344 if (!start) { 333 345 return true; 334 346 } 335 347 else { 336 double cost_diff = simann>getPrevCost()  simann>getCurrCost(); 337 if (cost_diff < 0.0) { 338 return (drand48() <= exp(cost_diff / temp)); 339 } 340 else { 341 return true; 342 } 343 } 344 } 348 double cost_diff = simann>getCurrCost()  simann>getPrevCost(); 349 return (drand48() <= exp((cost_diff / temp))); 350 } 351 } 352 /// \brief Destructor. 353 virtual ~AdvancedController() {} 345 354 }; 346 355
Note: See TracChangeset
for help on using the changeset viewer.