removed the fit to window form the toolbar and the menu since its current implementation is broken
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));