NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
4 /// \ingroup experimental
6 /// \brief Simulated annealing framework.
7 /// \author Akos Ladanyi
11 #include <lemon/time_measure.h>
15 /// \addtogroup experimental
18 /*! \brief A base class for controllers. */
19 class ControllerBase {
20 friend class SimAnnBase;
22 /*! \brief Pointer to the simulated annealing base class. */
24 /*! \brief Initializes the controller. */
25 virtual void init() {}
26 /*! \brief This is called when a neighbouring state gets accepted. */
27 virtual void acceptEvent() {}
28 /*! \brief This is called when the accepted neighbouring state's cost is
29 * less than the best found one's.
31 virtual void improveEvent() {}
32 /*! \brief This is called when a neighbouring state gets rejected. */
33 virtual void rejectEvent() {}
34 /*! \brief Decides whether to continue the annealing process or not. */
35 virtual bool next() = 0;
36 /*! \brief Decides whether to accept the current solution or not. */
37 virtual bool accept() = 0;
40 /*! \brief Skeleton of an entity class. */
43 /*! \brief Makes a minor change to the entity.
44 * \return the new cost
46 virtual double mutate() = 0;
47 /*! \brief Restores the entity to its previous state i.e. reverts the
48 * effects of the last mutate().
50 virtual void revert() = 0;
51 /*! \brief Makes a copy of the entity. */
52 virtual EntityBase* clone() = 0;
53 /*! \brief Makes a major change to the entity. */
54 virtual void randomize() = 0;
57 /*! \brief Simulated annealing base class. */
60 /*! Pointer to the controller. */
61 ControllerBase *controller;
62 /*! \brief Cost of the current solution. */
64 /*! \brief Cost of the best solution. */
66 /*! \brief Cost of the previous solution. */
68 /*! \brief Cost of the solution preceding the previous one. */
69 double prev_prev_cost;
70 /*! \brief Number of iterations. */
72 /*! \brief Number of iterations which did not improve the solution since
73 * the last improvement. */
76 /*! \brief Step to a neighbouring state. */
77 virtual double mutate() = 0;
78 /*! \brief Reverts the last mutate(). */
79 virtual void revert() = 0;
80 /*! \brief Saves the current solution as the best one. */
81 virtual void saveAsBest() = 0;
82 /*! \brief Does initializations before each run. */
85 curr_cost = prev_cost = prev_prev_cost = best_cost =
86 std::numeric_limits<double>::infinity();
90 /*! \brief Sets the controller class to use. */
91 void setController(ControllerBase &_controller) {
92 controller = &_controller;
93 controller->simann = this;
95 /*! \brief Returns the cost of the current solution. */
96 double getCurrCost() const { return curr_cost; }
97 /*! \brief Returns the cost of the previous solution. */
98 double getPrevCost() const { return prev_cost; }
99 /*! \brief Returns the cost of the best solution. */
100 double getBestCost() const { return best_cost; }
101 /*! \brief Returns the number of iterations. */
102 long getIter() const { return iter; }
103 /*! \brief Returns the number of the last iteration when the solution was
106 long getLastImpr() const { return last_impr; }
107 /*! \brief Performs one iteration. */
110 prev_prev_cost = prev_cost;
111 prev_cost = curr_cost;
112 curr_cost = mutate();
113 if (controller->accept()) {
114 controller->acceptEvent();
116 if (curr_cost < best_cost) {
117 best_cost = curr_cost;
119 controller->improveEvent();
124 curr_cost = prev_cost;
125 prev_cost = prev_prev_cost;
126 controller->rejectEvent();
128 return controller->next();
130 /*! \brief Performs a given number of iterations.
131 * \param n the number of iterations
134 for(; n > 0 && step(); --n) ;
137 /*! \brief Starts the annealing process. */
140 do { } while (step());
144 /*! \brief Simulated annealing class. */
145 class SimAnn : public SimAnnBase {
147 /*! \brief Pointer to the current entity. */
148 EntityBase *curr_ent;
149 /*! \brief Pointer to the best entity. */
150 EntityBase *best_ent;
151 /*! \brief Does initializations before each run. */
154 if (best_ent) delete best_ent;
156 curr_ent->randomize();
159 /*! \brief Constructor. */
160 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
161 /*! \brief Destructor. */
163 if (best_ent) delete best_ent;
165 /*! \brief Step to a neighbouring state. */
167 return curr_ent->mutate();
169 /*! \brief Reverts the last mutate(). */
173 /*! \brief Saves the current solution as the best one. */
175 if (best_ent) delete best_ent;
176 best_ent = curr_ent->clone();
178 /*! \brief Sets the current entity. */
179 void setEntity(EntityBase &_ent) {
182 /*! \brief Returns a copy of the best found entity. */
183 EntityBase* getBestEntity() { return best_ent->clone(); }
186 /*! \brief A simple controller for the simulated annealing class. */
187 class SimpleController : public ControllerBase {
189 /*! \brief Maximum number of iterations. */
191 /*! \brief Maximum number of iterations which do not improve the
194 /*! \brief Temperature. */
196 /*! \brief Annealing factor. */
198 /*! \brief Constructor.
199 * \param _max_iter maximum number of iterations
200 * \param _max_no_impr maximum number of consecutive iterations which do
201 * not yield a better solution
202 * \param _temp initial temperature
203 * \param _ann_fact annealing factor
205 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
206 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
207 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
211 /*! \brief This is called when a neighbouring state gets accepted. */
212 void acceptEvent() {}
213 /*! \brief This is called when the accepted neighbouring state's cost is
214 * less than the best found one's.
216 void improveEvent() {}
217 /*! \brief This is called when a neighbouring state gets rejected. */
218 void rejectEvent() {}
219 /*! \brief Decides whether to continue the annealing process or not. Also
220 * decreases the temperature. */
223 bool quit = (simann->getIter() > max_iter) ||
224 (simann->getIter() - simann->getLastImpr() > max_no_impr);
227 /*! \brief Decides whether to accept the current solution or not. */
229 double cost_diff = simann->getPrevCost() - simann->getCurrCost();
230 return (drand48() <= exp(cost_diff / temp));
234 /*! \brief A controller with preset running time for the simulated annealing
237 * With this controller you can set the running time of the annealing
238 * process in advance. It works the following way: the controller measures
239 * a kind of divergence. The divergence is the difference of the average
240 * cost of the recently found solutions the cost of the best found one. In
241 * case this divergence is greater than a given threshold, then we decrease
242 * the annealing factor, that is we cool the system faster. In case the
243 * divergence is lower than the threshold, then we increase the temperature.
244 * The threshold is a function of the elapsed time which reaches zero at the
247 class AdvancedController : public ControllerBase {
250 /*! \param time the elapsed time in seconds */
251 virtual double threshold(double time) {
252 return (-1.0) * start_threshold / end_time * time + start_threshold;
258 /*! \brief The time at the end of the algorithm. */
260 /*! \brief The time at the start of the algorithm. */
262 /*! \brief Starting threshold. */
263 double start_threshold;
264 /*! \brief Average cost of recent solutions. */
266 /*! \brief Temperature. */
268 /*! \brief Annealing factor. */
270 /*! \brief Initial annealing factor. */
271 double init_ann_fact;
273 /*! \brief Constructor.
274 * \param _end_time running time in seconds
275 * \param _alpha parameter used to calculate the running average
276 * \param _beta parameter used to decrease the annealing factor
277 * \param _gamma parameter used to increase the temperature
278 * \param _ann_fact initial annealing factor
280 AdvancedController(double _end_time, double _alpha = 0.2,
281 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
282 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
283 ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)
288 avg_cost = simann->getCurrCost();
290 /*! \brief This is called when a neighbouring state gets accepted. */
292 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
297 // calculate starting threshold and starting temperature
298 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
305 /*! \brief Decides whether to continue the annealing process or not. */
311 double elapsed_time = timer.getRealTime();
312 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
313 // decrease the annealing factor
317 // increase the temperature
319 // reset the annealing factor
320 ann_fact = init_ann_fact;
323 return elapsed_time < end_time;
326 /*! \brief Decides whether to accept the current solution or not. */
329 // we accept eveything during the "warm up" phase
333 double cost_diff = simann->getPrevCost() - simann->getCurrCost();
334 if (cost_diff < 0.0) {
335 return (drand48() <= exp(cost_diff / temp));