Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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>
40 /// \brief A base class for controllers.
41 class ControllerBase {
43 friend class SimAnnBase;
44 /// \brief Pointer to the simulated annealing base class.
46 /// \brief Initializes the controller.
47 virtual void init() {}
48 /// \brief This is called by the simulated annealing class when a
49 /// neighbouring state gets accepted.
50 virtual void acceptEvent() {}
51 /// \brief This is called by the simulated annealing class when the
52 /// accepted neighbouring state's cost is less than the best found one's.
53 virtual void improveEvent() {}
54 /// \brief This is called by the simulated annealing class when a
55 /// neighbouring state gets rejected.
56 virtual void rejectEvent() {}
57 /// \brief Decides whether to continue the annealing process or not.
58 virtual bool next() = 0;
59 /// \brief Decides whether to accept the current solution or not.
60 virtual bool accept() = 0;
61 /// \brief Destructor.
62 virtual ~ControllerBase() {}
65 /// \brief Skeleton of an entity class.
68 /// \brief Makes a minor change to the entity.
69 /// \return the new cost
70 virtual double mutate() = 0;
71 /// \brief Restores the entity to its previous state i.e. reverts the
72 /// effects of the last mutate().
73 virtual void revert() = 0;
74 /// \brief Makes a copy of the entity.
75 virtual EntityBase* clone() = 0;
76 /// \brief Makes a major change to the entity.
77 virtual void randomize() = 0;
78 /// \brief Destructor.
79 virtual ~EntityBase() {}
82 /// \brief Simulated annealing abstract base class.
84 /// Can be used to derive a custom simulated annealing class if \ref SimAnn
85 /// doesn't fit your needs.
88 /// \brief Pointer to the controller.
89 ControllerBase *controller;
90 /// \brief Cost of the current solution.
92 /// \brief Cost of the best solution.
94 /// \brief Cost of the previous solution.
96 /// \brief Cost of the solution preceding the previous one.
97 double prev_prev_cost;
98 /// \brief Number of iterations.
100 /// \brief Number of iterations which did not improve the solution since
101 /// the last improvement.
104 /// \brief Step to a neighbouring state.
105 virtual double mutate() = 0;
106 /// \brief Reverts the last mutate().
107 virtual void revert() = 0;
108 /// \brief Saves the current solution as the best one.
109 virtual void saveAsBest() = 0;
110 /// \brief Does initializations before each run.
111 virtual void init() {
113 curr_cost = prev_cost = prev_prev_cost = best_cost =
114 std::numeric_limits<double>::infinity();
115 iter = last_impr = 0;
118 /// \brief Sets the controller class to use.
119 void setController(ControllerBase &_controller) {
120 controller = &_controller;
121 controller->simann = this;
123 /// \brief Returns the cost of the current solution.
124 double getCurrCost() const { return curr_cost; }
125 /// \brief Returns the cost of the previous solution.
126 double getPrevCost() const { return prev_cost; }
127 /// \brief Returns the cost of the best solution.
128 double getBestCost() const { return best_cost; }
129 /// \brief Returns the number of iterations done.
130 long getIter() const { return iter; }
131 /// \brief Returns the ordinal number of the last iteration when the
132 /// solution was improved.
133 long getLastImpr() const { return last_impr; }
134 /// \brief Performs one iteration.
137 prev_prev_cost = prev_cost;
138 prev_cost = curr_cost;
139 curr_cost = mutate();
140 if (controller->accept()) {
141 controller->acceptEvent();
143 if (curr_cost < best_cost) {
144 best_cost = curr_cost;
146 controller->improveEvent();
151 curr_cost = prev_cost;
152 prev_cost = prev_prev_cost;
153 controller->rejectEvent();
155 return controller->next();
157 /// \brief Performs a given number of iterations.
158 /// \param n the number of iterations
160 for(; n > 0 && step(); --n) ;
163 /// \brief Starts the annealing process.
166 do { } while (step());
168 /// \brief Destructor.
169 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.
218 /// This controller starts from a given initial temperature and evenly
220 class SimpleController : public ControllerBase {
222 /// \brief Maximum number of iterations.
224 /// \brief Maximum number of iterations which do not improve the
227 /// \brief Temperature.
229 /// \brief Annealing factor.
231 /// \brief Constructor.
232 /// \param _max_iter maximum number of iterations
233 /// \param _max_no_impr maximum number of consecutive iterations which do
234 /// not yield a better solution
235 /// \param _temp initial temperature
236 /// \param _ann_fact annealing factor
238 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
239 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
240 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
243 /// \brief This is called when a neighbouring state gets accepted.
244 void acceptEvent() {}
245 /// \brief This is called when the accepted neighbouring state's cost is
246 /// less than the best found one's.
247 void improveEvent() {}
248 /// \brief This is called when a neighbouring state gets rejected.
249 void rejectEvent() {}
250 /// \brief Decides whether to continue the annealing process or not. Also
251 /// decreases the temperature.
254 bool quit = (simann->getIter() > max_iter) ||
255 (simann->getIter() - simann->getLastImpr() > max_no_impr);
258 /// \brief Decides whether to accept the current solution or not.
260 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
261 return (rnd() <= exp(-(cost_diff / temp)));
263 /// \brief Destructor.
264 virtual ~SimpleController() {}
267 /// \brief A controller with preset running time for the simulated annealing
270 /// With this controller you can set the running time of the annealing
271 /// process in advance. It works the following way: the controller measures
272 /// a kind of divergence. The divergence is the difference of the average
273 /// cost of the recently found solutions the cost of the best found one. In
274 /// case this divergence is greater than a given threshold, then we decrease
275 /// the annealing factor, that is we cool the system faster. In case the
276 /// divergence is lower than the threshold, then we increase the temperature.
277 /// The threshold is a function of the elapsed time which reaches zero at the
278 /// desired end time.
279 class AdvancedController : public ControllerBase {
281 /// \brief Timer class to measure the elapsed time.
283 /// \brief Calculates the threshold value.
284 /// \param time the elapsed time in seconds
285 virtual double threshold(double time) {
286 return (-1.0) * start_threshold / end_time * time + start_threshold;
288 /// \brief Parameter used to calculate the running average.
290 /// \brief Parameter used to decrease the annealing factor.
292 /// \brief Parameter used to increase the temperature.
294 /// \brief The time at the end of the algorithm.
296 /// \brief The time at the start of the algorithm.
298 /// \brief Starting threshold.
299 double start_threshold;
300 /// \brief Average cost of recent solutions.
302 /// \brief Temperature.
304 /// \brief Annealing factor.
306 /// \brief Initial annealing factor.
307 double init_ann_fact;
308 /// \brief True when the annealing process has been started.
311 /// \brief Constructor.
312 /// \param _end_time running time in seconds
313 /// \param _alpha parameter used to calculate the running average
314 /// \param _beta parameter used to decrease the annealing factor
315 /// \param _gamma parameter used to increase the temperature
316 /// \param _ann_fact initial annealing factor
317 AdvancedController(double _end_time, double _alpha = 0.2,
318 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
319 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
320 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
323 /// \brief Does initializations before each run.
325 avg_cost = simann->getCurrCost();
327 /// \brief This is called when a neighbouring state gets accepted.
329 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
334 // calculate starting threshold and starting temperature
335 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
342 /// \brief Decides whether to continue the annealing process or not.
348 double elapsed_time = timer.realTime();
349 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
350 // decrease the annealing factor
354 // increase the temperature
356 // reset the annealing factor
357 ann_fact = init_ann_fact;
360 return elapsed_time < end_time;
363 /// \brief Decides whether to accept the current solution or not.
369 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
370 return (rnd() <= exp(-(cost_diff / temp)));
373 /// \brief Destructor.
374 virtual ~AdvancedController() {}