1 #ifndef LEMON_SIMANN_H |
|
2 #define LEMON_SIMANN_H |
|
3 |
|
4 /// \ingroup experimental |
|
5 /// \file |
|
6 /// \brief Simulated annealing framework. |
|
7 /// \author Akos Ladanyi |
|
8 |
|
9 #include <cstdlib> |
|
10 #include <cmath> |
|
11 #include <lemon/time_measure.h> |
|
12 |
|
13 namespace lemon { |
|
14 |
|
15 /// \addtogroup experimental |
|
16 /// @{ |
|
17 |
|
18 const double INFTY = 1e24; |
|
19 |
|
20 /*! \brief Simulated annealing base class. */ |
|
21 class SimAnnBase { |
|
22 public: |
|
23 class Controller; |
|
24 private: |
|
25 /*! Pointer to the controller. */ |
|
26 Controller *controller; |
|
27 protected: |
|
28 /*! \brief Cost of the current solution. */ |
|
29 double curr_cost; |
|
30 /*! \brief Cost of the best solution. */ |
|
31 double best_cost; |
|
32 /*! \brief Cost of the previous solution. */ |
|
33 double prev_cost; |
|
34 /*! \brief Cost of the solution preceding the previous one. */ |
|
35 double prev_prev_cost; |
|
36 |
|
37 /*! \brief Step to a neighbouring state. */ |
|
38 virtual void mutate() = 0; |
|
39 /*! \brief Reverts the last mutate(). */ |
|
40 virtual void revert() = 0; |
|
41 /*! \brief Saves the current solution as the best one. */ |
|
42 virtual void saveAsBest() = 0; |
|
43 public: |
|
44 /*! \brief Constructor. */ |
|
45 SimAnnBase() { |
|
46 best_cost = prev_cost = prev_prev_cost = INFTY; |
|
47 } |
|
48 /*! \brief Sets the controller class to use. */ |
|
49 void setController(Controller &_controller) { |
|
50 controller = &_controller; |
|
51 controller->setBase(this); |
|
52 } |
|
53 /*! \brief Returns the cost of the current solution. */ |
|
54 double getCurrCost() const { return curr_cost; } |
|
55 /*! \brief Returns the cost of the previous solution. */ |
|
56 double getPrevCost() const { return prev_cost; } |
|
57 /*! \brief Returns the cost of the best solution. */ |
|
58 double getBestCost() const { return best_cost; } |
|
59 /*! \brief Starts the annealing process. */ |
|
60 void run() { |
|
61 controller->init(); |
|
62 do { |
|
63 curr_cost=mutate(); |
|
64 if (controller->accept()) { |
|
65 controller->acceptEvent(); |
|
66 if (curr_cost < best_cost) { |
|
67 saveAsBest(); |
|
68 controller->improveEvent(); |
|
69 } |
|
70 } |
|
71 else { |
|
72 revert(); |
|
73 controller->rejectEvent(); |
|
74 } |
|
75 } while (controller->next()); |
|
76 } |
|
77 |
|
78 /*! \brief A base class for controllers. */ |
|
79 class Controller { |
|
80 public: |
|
81 /*! \brief Pointer to the simulated annealing base class. */ |
|
82 SimAnnBase *base; |
|
83 /*! \brief Initializes the controller. */ |
|
84 virtual void init() {} |
|
85 /*! \brief This is called when a neighbouring state gets accepted. */ |
|
86 virtual void acceptEvent() {} |
|
87 /*! \brief This is called when the accepted neighbouring state's cost is |
|
88 * less than the best found one's. |
|
89 */ |
|
90 virtual void improveEvent() {} |
|
91 /*! \brief This is called when a neighbouring state gets rejected. */ |
|
92 virtual void rejectEvent() {} |
|
93 /*! \brief Sets the simulated annealing base class to use. */ |
|
94 virtual void setBase(SimAnnBase *_base) { base = _base; } |
|
95 /*! \brief Decides whether to continue the annealing process or not. */ |
|
96 virtual bool next() = 0; |
|
97 /*! \brief Decides whether to accept the current solution or not. */ |
|
98 virtual bool accept() = 0; |
|
99 }; |
|
100 }; |
|
101 |
|
102 /*! \brief Simulated annealing class. */ |
|
103 template <typename E> |
|
104 class SimAnn : public SimAnnBase { |
|
105 private: |
|
106 /*! \brief Pointer to the current entity. */ |
|
107 E *curr_ent; |
|
108 /*! \brief Pointer to the best entity. */ |
|
109 E *best_ent; |
|
110 public: |
|
111 /*! \brief Constructor. */ |
|
112 SimAnn() : SimAnnBase() {} |
|
113 /*! \brief Sets the initial entity. */ |
|
114 void setEntity(E &ent) { |
|
115 curr_ent = new E(ent); |
|
116 best_ent = new E(ent); |
|
117 curr_cost = curr_ent->getCost(); |
|
118 } |
|
119 /*! \brief Returns the best found entity. */ |
|
120 E getBestEntity() { return *best_ent; } |
|
121 /*! \brief Step to a neighbouring state. */ |
|
122 void mutate() { |
|
123 prev_prev_cost = prev_cost; |
|
124 prev_cost = curr_cost; |
|
125 curr_ent->mutate(); |
|
126 curr_cost = curr_ent->getCost(); |
|
127 } |
|
128 /*! \brief Reverts the last mutate(). */ |
|
129 void revert() { |
|
130 curr_ent->revert(); |
|
131 curr_cost = prev_cost; |
|
132 prev_cost = prev_prev_cost; |
|
133 } |
|
134 /*! \brief Saves the current solution as the best one. */ |
|
135 void saveAsBest() { |
|
136 delete(best_ent); |
|
137 best_ent = new E(*curr_ent); |
|
138 best_cost = curr_cost; |
|
139 } |
|
140 }; |
|
141 |
|
142 /*! \brief Skeleton of an entity class. */ |
|
143 class EntitySkeleton { |
|
144 public: |
|
145 /*! \brief Returns the cost of the entity. */ |
|
146 double getCost() { return 0.0; } |
|
147 /*! \brief Makes a minor change to the entity. */ |
|
148 void mutate() {} |
|
149 /*! \brief Restores the entity to its previous state i.e. reverts the |
|
150 * effects of the last mutate(). |
|
151 */ |
|
152 void revert() {} |
|
153 }; |
|
154 |
|
155 /*! \brief A simple controller for the simulated annealing class. */ |
|
156 class SimpleController : public SimAnnBase::Controller { |
|
157 public: |
|
158 /*! \brief Number of iterations. */ |
|
159 long iter; |
|
160 /*! \brief Number of iterations which did not improve the solution since |
|
161 * the last improvement. */ |
|
162 long last_impr; |
|
163 /*! \brief Maximum number of iterations. */ |
|
164 long max_iter; |
|
165 /*! \brief Maximum number of iterations which do not improve the |
|
166 * solution. */ |
|
167 long max_no_impr; |
|
168 /*! \brief Temperature. */ |
|
169 double temp; |
|
170 /*! \brief Annealing factor. */ |
|
171 double ann_fact; |
|
172 /*! \brief Constructor. |
|
173 * \param _max_iter maximum number of iterations |
|
174 * \param _max_no_impr maximum number of consecutive iterations which do |
|
175 * not yield a better solution |
|
176 * \param _temp initial temperature |
|
177 * \param _ann_fact annealing factor |
|
178 */ |
|
179 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000, |
|
180 double _temp = 1000.0, double _ann_fact = 0.9999) : iter(0), last_impr(0), |
|
181 max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp), |
|
182 ann_fact(_ann_fact) {} |
|
183 /*! \brief This is called when a neighbouring state gets accepted. */ |
|
184 void acceptEvent() { |
|
185 iter++; |
|
186 } |
|
187 /*! \brief This is called when the accepted neighbouring state's cost is |
|
188 * less than the best found one's. |
|
189 */ |
|
190 void improveEvent() { |
|
191 last_impr = iter; |
|
192 } |
|
193 /*! \brief This is called when a neighbouring state gets rejected. */ |
|
194 void rejectEvent() { |
|
195 iter++; |
|
196 } |
|
197 /*! \brief Decides whether to continue the annealing process or not. Also |
|
198 * decreases the temperature. */ |
|
199 bool next() { |
|
200 temp *= ann_fact; |
|
201 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr); |
|
202 return !quit; |
|
203 } |
|
204 /*! \brief Decides whether to accept the current solution or not. */ |
|
205 bool accept() { |
|
206 double cost_diff = base->getPrevCost() - base->getCurrCost(); |
|
207 if (cost_diff < 0.0) { |
|
208 bool ret = drand48() <= exp(cost_diff / temp); |
|
209 return ret; |
|
210 } |
|
211 else { |
|
212 return true; |
|
213 } |
|
214 } |
|
215 }; |
|
216 |
|
217 /*! \brief A controller with preset running time for the simulated annealing |
|
218 * class. |
|
219 * |
|
220 * With this controller you can set the running time of the annealing |
|
221 * process in advance. It works the following way: the controller measures |
|
222 * a kind of divergence. The divergence is the difference of the average |
|
223 * cost of the recently found solutions the cost of the best found one. In |
|
224 * case this divergence is greater than a given threshold, then we decrease |
|
225 * the annealing factor, that is we cool the system faster. In case the |
|
226 * divergence is lower than the threshold, then we increase the temperature. |
|
227 * The threshold is a function of the elapsed time which reaches zero at the |
|
228 * desired end time. |
|
229 */ |
|
230 class AdvancedController : public SimAnnBase::Controller { |
|
231 private: |
|
232 Timer timer; |
|
233 /*! \param time the elapsed time in seconds */ |
|
234 virtual double threshold(double time) { |
|
235 return (-1.0) * start_threshold / end_time * time + start_threshold; |
|
236 } |
|
237 public: |
|
238 double alpha; |
|
239 double beta; |
|
240 double gamma; |
|
241 /*! \brief The time at the end of the algorithm. */ |
|
242 double end_time; |
|
243 /*! \brief The time at the start of the algorithm. */ |
|
244 double start_time; |
|
245 /*! \brief Starting threshold. */ |
|
246 double start_threshold; |
|
247 /*! \brief Average cost of recent solutions. */ |
|
248 double avg_cost; |
|
249 /*! \brief Temperature. */ |
|
250 double temp; |
|
251 /*! \brief Annealing factor. */ |
|
252 double ann_fact; |
|
253 /*! \brief Initial annealing factor. */ |
|
254 double init_ann_fact; |
|
255 bool warmup; |
|
256 /*! \brief Constructor. |
|
257 * \param _end_time running time in seconds |
|
258 * \param _alpha parameter used to calculate the running average |
|
259 * \param _beta parameter used to decrease the annealing factor |
|
260 * \param _gamma parameter used to increase the temperature |
|
261 * \param _ann_fact initial annealing factor |
|
262 */ |
|
263 AdvancedController(double _end_time, double _alpha = 0.2, |
|
264 double _beta = 0.9, double _gamma = 1.6, double _ann_fact = 0.9999) : |
|
265 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time), |
|
266 ann_fact(_ann_fact), init_ann_fact(_ann_fact), warmup(true) {} |
|
267 void init() { |
|
268 avg_cost = base->getCurrCost(); |
|
269 } |
|
270 /*! \brief This is called when a neighbouring state gets accepted. */ |
|
271 void acceptEvent() { |
|
272 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost; |
|
273 if (warmup) { |
|
274 static int cnt = 0; |
|
275 cnt++; |
|
276 if (cnt >= 100) { |
|
277 // calculate starting threshold and starting temperature |
|
278 start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost); |
|
279 temp = 10000.0; |
|
280 warmup = false; |
|
281 timer.reset(); |
|
282 } |
|
283 } |
|
284 } |
|
285 /*! \brief Decides whether to continue the annealing process or not. */ |
|
286 bool next() { |
|
287 if (warmup) { |
|
288 return true; |
|
289 } |
|
290 else { |
|
291 double elapsed_time = timer.getRealTime(); |
|
292 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { |
|
293 // decrease the annealing factor |
|
294 ann_fact *= beta; |
|
295 } |
|
296 else { |
|
297 // increase the temperature |
|
298 temp *= gamma; |
|
299 // reset the annealing factor |
|
300 ann_fact = init_ann_fact; |
|
301 } |
|
302 temp *= ann_fact; |
|
303 return elapsed_time < end_time; |
|
304 } |
|
305 } |
|
306 /*! \brief Decides whether to accept the current solution or not. */ |
|
307 bool accept() { |
|
308 if (warmup) { |
|
309 // we accept eveything during the "warm up" phase |
|
310 return true; |
|
311 } |
|
312 else { |
|
313 double cost_diff = base->getPrevCost() - base->getCurrCost(); |
|
314 if (cost_diff < 0.0) { |
|
315 return (drand48() <= exp(cost_diff / temp)); |
|
316 } |
|
317 else { |
|
318 return true; |
|
319 } |
|
320 } |
|
321 } |
|
322 }; |
|
323 |
|
324 /// @} |
|
325 |
|
326 } |
|
327 |
|
328 #endif |
|