Functions added to set the edges/corners of the bounding box directly.
4 /// \ingroup experimental
6 /// \brief Simulated annealing framework.
8 /// \todo A test and some demo should be added
9 /// \todo Doc should be improved
10 /// \author Akos Ladanyi
15 #include <lemon/time_measure.h>
19 /// \addtogroup experimental
22 /// \brief A base class for controllers.
23 class ControllerBase {
25 friend class SimAnnBase;
26 /// \brief Pointer to the simulated annealing base class.
28 /// \brief Initializes the controller.
29 virtual void init() {}
30 /// \brief This is called by the simulated annealing class when a
31 /// neighbouring state gets accepted.
32 virtual void acceptEvent() {}
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.
35 virtual void improveEvent() {}
36 /// \brief This is called by the simulated annealing class when a
37 /// neighbouring state gets rejected.
38 virtual void rejectEvent() {}
39 /// \brief Decides whether to continue the annealing process or not.
40 virtual bool next() = 0;
41 /// \brief Decides whether to accept the current solution or not.
42 virtual bool accept() = 0;
43 /// \brief Destructor.
44 virtual ~ControllerBase() {}
47 /// \brief Skeleton of an entity class.
50 /// \brief Makes a minor change to the entity.
51 /// \return the new cost
52 virtual double mutate() = 0;
53 /// \brief Restores the entity to its previous state i.e. reverts the
54 /// effects of the last mutate().
55 virtual void revert() = 0;
56 /// \brief Makes a copy of the entity.
57 virtual EntityBase* clone() = 0;
58 /// \brief Makes a major change to the entity.
59 virtual void randomize() = 0;
60 /// \brief Destructor.
61 virtual ~EntityBase() {}
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.
69 /// \brief Pointer to the controller.
70 ControllerBase *controller;
71 /// \brief Cost of the current solution.
73 /// \brief Cost of the best solution.
75 /// \brief Cost of the previous solution.
77 /// \brief Cost of the solution preceding the previous one.
78 double prev_prev_cost;
79 /// \brief Number of iterations.
81 /// \brief Number of iterations which did not improve the solution since
82 /// the last improvement.
85 /// \brief Step to a neighbouring state.
86 virtual double mutate() = 0;
87 /// \brief Reverts the last mutate().
88 virtual void revert() = 0;
89 /// \brief Saves the current solution as the best one.
90 virtual void saveAsBest() = 0;
91 /// \brief Does initializations before each run.
94 curr_cost = prev_cost = prev_prev_cost = best_cost =
95 std::numeric_limits<double>::infinity();
99 /// \brief Sets the controller class to use.
100 void setController(ControllerBase &_controller) {
101 controller = &_controller;
102 controller->simann = this;
104 /// \brief Returns the cost of the current solution.
105 double getCurrCost() const { return curr_cost; }
106 /// \brief Returns the cost of the previous solution.
107 double getPrevCost() const { return prev_cost; }
108 /// \brief Returns the cost of the best solution.
109 double getBestCost() const { return best_cost; }
110 /// \brief Returns the number of iterations done.
111 long getIter() const { return iter; }
112 /// \brief Returns the ordinal number of the last iteration when the
113 /// solution was improved.
114 long getLastImpr() const { return last_impr; }
115 /// \brief Performs one iteration.
118 prev_prev_cost = prev_cost;
119 prev_cost = curr_cost;
120 curr_cost = mutate();
121 if (controller->accept()) {
122 controller->acceptEvent();
124 if (curr_cost < best_cost) {
125 best_cost = curr_cost;
127 controller->improveEvent();
132 curr_cost = prev_cost;
133 prev_cost = prev_prev_cost;
134 controller->rejectEvent();
136 return controller->next();
138 /// \brief Performs a given number of iterations.
139 /// \param n the number of iterations
141 for(; n > 0 && step(); --n) ;
144 /// \brief Starts the annealing process.
147 do { } while (step());
149 /// \brief Destructor.
150 virtual ~SimAnnBase() {}
153 /// \brief Simulated annealing class.
154 class SimAnn : public SimAnnBase {
156 /// \brief Pointer to the current entity.
157 EntityBase *curr_ent;
158 /// \brief Pointer to the best entity.
159 EntityBase *best_ent;
160 /// \brief Does initializations before each run.
163 if (best_ent) delete best_ent;
165 curr_ent->randomize();
168 /// \brief Constructor.
169 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
170 /// \brief Destructor.
172 if (best_ent) delete best_ent;
174 /// \brief Step to a neighbouring state.
176 return curr_ent->mutate();
178 /// \brief Reverts the last mutate().
182 /// \brief Saves the current solution as the best one.
184 if (best_ent) delete best_ent;
185 best_ent = curr_ent->clone();
187 /// \brief Sets the current entity.
188 void setEntity(EntityBase &_ent) {
191 /// \brief Returns a copy of the best found entity.
192 EntityBase* getBestEntity() { return best_ent->clone(); }
195 /// \brief A simple controller for the simulated annealing class.
196 /// This controller starts from a given initial temperature and evenly
198 class SimpleController : public ControllerBase {
200 /// \brief Maximum number of iterations.
202 /// \brief Maximum number of iterations which do not improve the
205 /// \brief Temperature.
207 /// \brief Annealing factor.
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
216 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
217 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
218 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
222 /// \brief This is called when a neighbouring state gets accepted.
223 void acceptEvent() {}
224 /// \brief This is called when the accepted neighbouring state's cost is
225 /// less than the best found one's.
226 void improveEvent() {}
227 /// \brief This is called when a neighbouring state gets rejected.
228 void rejectEvent() {}
229 /// \brief Decides whether to continue the annealing process or not. Also
230 /// decreases the temperature.
233 bool quit = (simann->getIter() > max_iter) ||
234 (simann->getIter() - simann->getLastImpr() > max_no_impr);
237 /// \brief Decides whether to accept the current solution or not.
239 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
240 return (drand48() <= exp(-(cost_diff / temp)));
242 /// \brief Destructor.
243 virtual ~SimpleController() {}
246 /// \brief A controller with preset running time for the simulated annealing
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.
257 class AdvancedController : public ControllerBase {
259 /// \brief Timer class to measure the elapsed time.
261 /// \brief Calculates the threshold value.
262 /// \param time the elapsed time in seconds
263 virtual double threshold(double time) {
264 return (-1.0) * start_threshold / end_time * time + start_threshold;
266 /// \brief Parameter used to calculate the running average.
268 /// \brief Parameter used to decrease the annealing factor.
270 /// \brief Parameter used to increase the temperature.
272 /// \brief The time at the end of the algorithm.
274 /// \brief The time at the start of the algorithm.
276 /// \brief Starting threshold.
277 double start_threshold;
278 /// \brief Average cost of recent solutions.
280 /// \brief Temperature.
282 /// \brief Annealing factor.
284 /// \brief Initial annealing factor.
285 double init_ann_fact;
286 /// \brief True when the annealing process has been started.
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
295 AdvancedController(double _end_time, double _alpha = 0.2,
296 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
297 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
298 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
302 /// \brief Does initializations before each run.
304 avg_cost = simann->getCurrCost();
306 /// \brief This is called when a neighbouring state gets accepted.
308 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
313 // calculate starting threshold and starting temperature
314 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
321 /// \brief Decides whether to continue the annealing process or not.
327 double elapsed_time = timer.realTime();
328 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
329 // decrease the annealing factor
333 // increase the temperature
335 // reset the annealing factor
336 ann_fact = init_ann_fact;
339 return elapsed_time < end_time;
342 /// \brief Decides whether to accept the current solution or not.
348 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
349 return (drand48() <= exp(-(cost_diff / temp)));
352 /// \brief Destructor.
353 virtual ~AdvancedController() {}