Lemon Graph Format uses label instead of id named map.
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
14 #include <lemon/time_measure.h>
18 /// \addtogroup experimental
21 /*! \brief A base class for controllers. */
22 class ControllerBase {
23 friend class SimAnnBase;
25 /*! \brief Pointer to the simulated annealing base class. */
27 /*! \brief Initializes the controller. */
28 virtual void init() {}
29 /*! \brief This is called when a neighbouring state gets accepted. */
30 virtual void acceptEvent() {}
31 /*! \brief This is called when the accepted neighbouring state's cost is
32 * less than the best found one's.
34 virtual void improveEvent() {}
35 /*! \brief This is called when a neighbouring state gets rejected. */
36 virtual void rejectEvent() {}
37 /*! \brief Decides whether to continue the annealing process or not. */
38 virtual bool next() = 0;
39 /*! \brief Decides whether to accept the current solution or not. */
40 virtual bool accept() = 0;
43 /*! \brief Skeleton of an entity class. */
46 /*! \brief Makes a minor change to the entity.
47 * \return the new cost
49 virtual double mutate() = 0;
50 /*! \brief Restores the entity to its previous state i.e. reverts the
51 * effects of the last mutate().
53 virtual void revert() = 0;
54 /*! \brief Makes a copy of the entity. */
55 virtual EntityBase* clone() = 0;
56 /*! \brief Makes a major change to the entity. */
57 virtual void randomize() = 0;
60 /*! \brief Simulated annealing base class. */
63 /*! Pointer to the controller. */
64 ControllerBase *controller;
65 /*! \brief Cost of the current solution. */
67 /*! \brief Cost of the best solution. */
69 /*! \brief Cost of the previous solution. */
71 /*! \brief Cost of the solution preceding the previous one. */
72 double prev_prev_cost;
73 /*! \brief Number of iterations. */
75 /*! \brief Number of iterations which did not improve the solution since
76 * the last improvement. */
79 /*! \brief Step to a neighbouring state. */
80 virtual double mutate() = 0;
81 /*! \brief Reverts the last mutate(). */
82 virtual void revert() = 0;
83 /*! \brief Saves the current solution as the best one. */
84 virtual void saveAsBest() = 0;
85 /*! \brief Does initializations before each run. */
88 curr_cost = prev_cost = prev_prev_cost = best_cost =
89 std::numeric_limits<double>::infinity();
93 /*! \brief Sets the controller class to use. */
94 void setController(ControllerBase &_controller) {
95 controller = &_controller;
96 controller->simann = this;
98 /*! \brief Returns the cost of the current solution. */
99 double getCurrCost() const { return curr_cost; }
100 /*! \brief Returns the cost of the previous solution. */
101 double getPrevCost() const { return prev_cost; }
102 /*! \brief Returns the cost of the best solution. */
103 double getBestCost() const { return best_cost; }
104 /*! \brief Returns the number of iterations. */
105 long getIter() const { return iter; }
106 /*! \brief Returns the number of the last iteration when the solution was
109 long getLastImpr() const { return last_impr; }
110 /*! \brief Performs one iteration. */
113 prev_prev_cost = prev_cost;
114 prev_cost = curr_cost;
115 curr_cost = mutate();
116 if (controller->accept()) {
117 controller->acceptEvent();
119 if (curr_cost < best_cost) {
120 best_cost = curr_cost;
122 controller->improveEvent();
127 curr_cost = prev_cost;
128 prev_cost = prev_prev_cost;
129 controller->rejectEvent();
131 return controller->next();
133 /*! \brief Performs a given number of iterations.
134 * \param n the number of iterations
137 for(; n > 0 && step(); --n) ;
140 /*! \brief Starts the annealing process. */
143 do { } while (step());
147 /*! \brief Simulated annealing class. */
148 class SimAnn : public SimAnnBase {
150 /*! \brief Pointer to the current entity. */
151 EntityBase *curr_ent;
152 /*! \brief Pointer to the best entity. */
153 EntityBase *best_ent;
154 /*! \brief Does initializations before each run. */
157 if (best_ent) delete best_ent;
159 curr_ent->randomize();
162 /*! \brief Constructor. */
163 SimAnn() : curr_ent(NULL), best_ent(NULL) {}
164 /*! \brief Destructor. */
166 if (best_ent) delete best_ent;
168 /*! \brief Step to a neighbouring state. */
170 return curr_ent->mutate();
172 /*! \brief Reverts the last mutate(). */
176 /*! \brief Saves the current solution as the best one. */
178 if (best_ent) delete best_ent;
179 best_ent = curr_ent->clone();
181 /*! \brief Sets the current entity. */
182 void setEntity(EntityBase &_ent) {
185 /*! \brief Returns a copy of the best found entity. */
186 EntityBase* getBestEntity() { return best_ent->clone(); }
189 /*! \brief A simple controller for the simulated annealing class. */
190 class SimpleController : public ControllerBase {
192 /*! \brief Maximum number of iterations. */
194 /*! \brief Maximum number of iterations which do not improve the
197 /*! \brief Temperature. */
199 /*! \brief Annealing factor. */
201 /*! \brief Constructor.
202 * \param _max_iter maximum number of iterations
203 * \param _max_no_impr maximum number of consecutive iterations which do
204 * not yield a better solution
205 * \param _temp initial temperature
206 * \param _ann_fact annealing factor
208 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
209 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
210 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
214 /*! \brief This is called when a neighbouring state gets accepted. */
215 void acceptEvent() {}
216 /*! \brief This is called when the accepted neighbouring state's cost is
217 * less than the best found one's.
219 void improveEvent() {}
220 /*! \brief This is called when a neighbouring state gets rejected. */
221 void rejectEvent() {}
222 /*! \brief Decides whether to continue the annealing process or not. Also
223 * decreases the temperature. */
226 bool quit = (simann->getIter() > max_iter) ||
227 (simann->getIter() - simann->getLastImpr() > max_no_impr);
230 /*! \brief Decides whether to accept the current solution or not. */
232 double cost_diff = simann->getPrevCost() - simann->getCurrCost();
233 return (drand48() <= exp(cost_diff / temp));
237 /*! \brief A controller with preset running time for the simulated annealing
240 * With this controller you can set the running time of the annealing
241 * process in advance. It works the following way: the controller measures
242 * a kind of divergence. The divergence is the difference of the average
243 * cost of the recently found solutions the cost of the best found one. In
244 * case this divergence is greater than a given threshold, then we decrease
245 * the annealing factor, that is we cool the system faster. In case the
246 * divergence is lower than the threshold, then we increase the temperature.
247 * The threshold is a function of the elapsed time which reaches zero at the
250 class AdvancedController : public ControllerBase {
253 /*! \param time the elapsed time in seconds */
254 virtual double threshold(double time) {
255 return (-1.0) * start_threshold / end_time * time + start_threshold;
261 /*! \brief The time at the end of the algorithm. */
263 /*! \brief The time at the start of the algorithm. */
265 /*! \brief Starting threshold. */
266 double start_threshold;
267 /*! \brief Average cost of recent solutions. */
269 /*! \brief Temperature. */
271 /*! \brief Annealing factor. */
273 /*! \brief Initial annealing factor. */
274 double init_ann_fact;
276 /*! \brief Constructor.
277 * \param _end_time running time in seconds
278 * \param _alpha parameter used to calculate the running average
279 * \param _beta parameter used to decrease the annealing factor
280 * \param _gamma parameter used to increase the temperature
281 * \param _ann_fact initial annealing factor
283 AdvancedController(double _end_time, double _alpha = 0.2,
284 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) :
285 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
286 ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true)
291 avg_cost = simann->getCurrCost();
293 /*! \brief This is called when a neighbouring state gets accepted. */
295 avg_cost = alpha * simann->getCurrCost() + (1.0 - alpha) * avg_cost;
300 // calculate starting threshold and starting temperature
301 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
308 /*! \brief Decides whether to continue the annealing process or not. */
314 double elapsed_time = timer.getRealTime();
315 if (fabs(avg_cost - simann->getBestCost()) > threshold(elapsed_time)) {
316 // decrease the annealing factor
320 // increase the temperature
322 // reset the annealing factor
323 ann_fact = init_ann_fact;
326 return elapsed_time < end_time;
329 /*! \brief Decides whether to accept the current solution or not. */
332 // we accept eveything during the "warm up" phase
336 double cost_diff = simann->getPrevCost() - simann->getCurrCost();
337 if (cost_diff < 0.0) {
338 return (drand48() <= exp(cost_diff / temp));