Turn off 32 bit only tests, cont'd.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_SIMANN_H
20 #define LEMON_SIMANN_H
22 /// \ingroup experimental
24 /// \brief Simulated annealing framework.
26 /// \todo A test and some demo should be added
27 /// \todo Doc should be improved
28 /// \author Akos Ladanyi
33 #include <lemon/time_measure.h>
34 #include <lemon/random.h>
38 /// \addtogroup experimental
43 /// \brief A base class for controllers.
44 class ControllerBase {
46 friend class SimAnnBase;
47 /// \brief Pointer to the simulated annealing base class.
49 /// \brief Initializes the controller.
50 virtual void init() {}
51 /// \brief This is called by the simulated annealing class when a
52 /// neighbouring state gets accepted.
53 virtual void acceptEvent() {}
54 /// \brief This is called by the simulated annealing class when the
55 /// accepted neighbouring state's cost is less than the best found one's.
56 virtual void improveEvent() {}
57 /// \brief This is called by the simulated annealing class when a
58 /// neighbouring state gets rejected.
59 virtual void rejectEvent() {}
60 /// \brief Decides whether to continue the annealing process or not.
61 virtual bool next() = 0;
62 /// \brief Decides whether to accept the current solution or not.
63 virtual bool accept() = 0;
64 /// \brief Destructor.
65 virtual ~ControllerBase() {}
68 /// \brief Skeleton of an entity class.
71 /// \brief Makes a minor change to the entity.
72 /// \return the new cost
73 virtual double mutate() = 0;
74 /// \brief Restores the entity to its previous state i.e. reverts the
75 /// effects of the last mutate().
76 virtual void revert() = 0;
77 /// \brief Makes a copy of the entity.
78 virtual EntityBase* clone() = 0;
79 /// \brief Makes a major change to the entity.
80 virtual void randomize() = 0;
81 /// \brief Destructor.
82 virtual ~EntityBase() {}
85 /// \brief Simulated annealing abstract base class.
86 /// Can be used to derive a custom simulated annealing class if \ref SimAnn
87 /// doesn't fit your needs.
90 /// \brief Pointer to the controller.
91 ControllerBase *controller;
92 /// \brief Cost of the current solution.
94 /// \brief Cost of the best solution.
96 /// \brief Cost of the previous solution.
98 /// \brief Cost of the solution preceding the previous one.
99 double prev_prev_cost;
100 /// \brief Number of iterations.
102 /// \brief Number of iterations which did not improve the solution since
103 /// the last improvement.
106 /// \brief Step to a neighbouring state.
107 virtual double mutate() = 0;
108 /// \brief Reverts the last mutate().
109 virtual void revert() = 0;
110 /// \brief Saves the current solution as the best one.
111 virtual void saveAsBest() = 0;
112 /// \brief Does initializations before each run.
113 virtual void init() {
115 curr_cost = prev_cost = prev_prev_cost = best_cost =
116 std::numeric_limits<double>::infinity();
117 iter = last_impr = 0;
120 /// \brief Sets the controller class to use.
121 void setController(ControllerBase &_controller) {
122 controller = &_controller;
123 controller->simann = this;
125 /// \brief Returns the cost of the current solution.
126 double getCurrCost() const { return curr_cost; }
127 /// \brief Returns the cost of the previous solution.
128 double getPrevCost() const { return prev_cost; }
129 /// \brief Returns the cost of the best solution.
130 double getBestCost() const { return best_cost; }
131 /// \brief Returns the number of iterations done.
132 long getIter() const { return iter; }
133 /// \brief Returns the ordinal number of the last iteration when the
134 /// solution was improved.
135 long getLastImpr() const { return last_impr; }
136 /// \brief Performs one iteration.
139 prev_prev_cost = prev_cost;
140 prev_cost = curr_cost;
141 curr_cost = mutate();
142 if (controller->accept()) {
143 controller->acceptEvent();
145 if (curr_cost < best_cost) {
146 best_cost = curr_cost;
148 controller->improveEvent();
153 curr_cost = prev_cost;
154 prev_cost = prev_prev_cost;
155 controller->rejectEvent();
157 return controller->next();
159 /// \brief Performs a given number of iterations.
160 /// \param n the number of iterations
162 for(; n > 0 && step(); --n) ;
165 /// \brief Starts the annealing process.
168 do { } while (step());
170 /// \brief Destructor.
171 virtual ~SimAnnBase() {}
174 /// \brief Simulated annealing class.
175 class SimAnn : public SimAnnBase {
177 /// \brief Pointer to the current entity.
178 EntityBase *curr_ent;
179 /// \brief Pointer to the best entity.
180 EntityBase *best_ent;
181 /// \brief Does initializations before each run.
184 if (best_ent) delete best_ent;
186 curr_ent->randomize();
189 /// \brief Constructor.
190 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
191 /// \brief Destructor.
193 if (best_ent) delete best_ent;
195 /// \brief Step to a neighbouring state.
197 return curr_ent->mutate();
199 /// \brief Reverts the last mutate().
203 /// \brief Saves the current solution as the best one.
205 if (best_ent) delete best_ent;
206 best_ent = curr_ent->clone();
208 /// \brief Sets the current entity.
209 void setEntity(EntityBase &_ent) {
212 /// \brief Returns a copy of the best found entity.
213 EntityBase* getBestEntity() { return best_ent->clone(); }
216 /// \brief A simple controller for the simulated annealing class.
217 /// This controller starts from a given initial temperature and evenly
219 class SimpleController : public ControllerBase {
221 /// \brief Maximum number of iterations.
223 /// \brief Maximum number of iterations which do not improve the
226 /// \brief Temperature.
228 /// \brief Annealing factor.
230 /// \brief Constructor.
231 /// \param _max_iter maximum number of iterations
232 /// \param _max_no_impr maximum number of consecutive iterations which do
233 /// not yield a better solution
234 /// \param _temp initial temperature
235 /// \param _ann_fact annealing factor
237 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
238 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
239 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
242 /// \brief This is called when a neighbouring state gets accepted.
243 void acceptEvent() {}
244 /// \brief This is called when the accepted neighbouring state's cost is
245 /// less than the best found one's.
246 void improveEvent() {}
247 /// \brief This is called when a neighbouring state gets rejected.
248 void rejectEvent() {}
249 /// \brief Decides whether to continue the annealing process or not. Also
250 /// decreases the temperature.
253 bool quit = (simann->getIter() > max_iter) ||
254 (simann->getIter() - simann->getLastImpr() > max_no_impr);
257 /// \brief Decides whether to accept the current solution or not.
259 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
260 return (rnd() <= exp(-(cost_diff / temp)));
262 /// \brief Destructor.
263 virtual ~SimpleController() {}
266 /// \brief A controller with preset running time for the simulated annealing
268 /// With this controller you can set the running time of the annealing
269 /// process in advance. It works the following way: the controller measures
270 /// a kind of divergence. The divergence is the difference of the average
271 /// cost of the recently found solutions the cost of the best found one. In
272 /// case this divergence is greater than a given threshold, then we decrease
273 /// the annealing factor, that is we cool the system faster. In case the
274 /// divergence is lower than the threshold, then we increase the temperature.
275 /// The threshold is a function of the elapsed time which reaches zero at the
276 /// desired end time.
277 class AdvancedController : public ControllerBase {
279 /// \brief Timer class to measure the elapsed time.
281 /// \brief Calculates the threshold value.
282 /// \param time the elapsed time in seconds
283 virtual double threshold(double time) {
284 return (-1.0) * start_threshold / end_time * time + start_threshold;
286 /// \brief Parameter used to calculate the running average.
288 /// \brief Parameter used to decrease the annealing factor.
290 /// \brief Parameter used to increase the temperature.
292 /// \brief The time at the end of the algorithm.
294 /// \brief The time at the start of the algorithm.
296 /// \brief Starting threshold.
297 double start_threshold;
298 /// \brief Average cost of recent solutions.
300 /// \brief Temperature.
302 /// \brief Annealing factor.
304 /// \brief Initial annealing factor.
305 double init_ann_fact;
306 /// \brief True when the annealing process has been started.
309 /// \brief Constructor.
310 /// \param _end_time running time in seconds
311 /// \param _alpha parameter used to calculate the running average
312 /// \param _beta parameter used to decrease the annealing factor
313 /// \param _gamma parameter used to increase the temperature
314 /// \param _ann_fact initial annealing factor
315 AdvancedController(double _end_time, double _alpha = 0.2,
316 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
317 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
318 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
321 /// \brief Does initializations before each run.
323 avg_cost = simann->getCurrCost();
325 /// \brief This is called when a neighbouring state gets accepted.
327 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
332 // calculate starting threshold and starting temperature
333 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
340 /// \brief Decides whether to continue the annealing process or not.
346 double elapsed_time = timer.realTime();
347 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
348 // decrease the annealing factor
352 // increase the temperature
354 // reset the annealing factor
355 ann_fact = init_ann_fact;
358 return elapsed_time < end_time;
361 /// \brief Decides whether to accept the current solution or not.
367 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
368 return (rnd() <= exp(-(cost_diff / temp)));
371 /// \brief Destructor.
372 virtual ~AdvancedController() {}