A sample file.
4 /// \ingroup experimental
6 /// \brief Simulated annealing framework.
7 /// \author Akos Ladanyi
11 #include <lemon/time_measure.h>
15 /// \addtogroup experimental
18 const double INFTY = 1e24;
20 /*! \brief Simulated annealing base class. */
25 /*! Pointer to the controller. */
26 Controller *controller;
28 /*! \brief Cost of the current solution. */
30 /*! \brief Cost of the best solution. */
32 /*! \brief Cost of the previous solution. */
34 /*! \brief Cost of the solution preceding the previous one. */
35 double prev_prev_cost;
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;
44 /*! \brief Constructor. */
46 best_cost = prev_cost = prev_prev_cost = INFTY;
48 /*! \brief Sets the controller class to use. */
49 void setController(Controller &_controller) {
50 controller = &_controller;
51 controller->setBase(this);
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. */
64 if (controller->accept()) {
65 controller->acceptEvent();
66 if (curr_cost < best_cost) {
68 controller->improveEvent();
73 controller->rejectEvent();
75 } while (controller->next());
78 /*! \brief A base class for controllers. */
81 /*! \brief Pointer to the simulated annealing base class. */
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.
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;
102 /*! \brief Simulated annealing class. */
103 template <typename E>
104 class SimAnn : public SimAnnBase {
106 /*! \brief Pointer to the current entity. */
108 /*! \brief Pointer to the best entity. */
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();
119 /*! \brief Returns the best found entity. */
120 E getBestEntity() { return *best_ent; }
121 /*! \brief Step to a neighbouring state. */
123 prev_prev_cost = prev_cost;
124 prev_cost = curr_cost;
126 curr_cost = curr_ent->getCost();
128 /*! \brief Reverts the last mutate(). */
131 curr_cost = prev_cost;
132 prev_cost = prev_prev_cost;
134 /*! \brief Saves the current solution as the best one. */
137 best_ent = new E(*curr_ent);
138 best_cost = curr_cost;
142 /*! \brief Skeleton of an entity class. */
143 class EntitySkeleton {
145 /*! \brief Returns the cost of the entity. */
146 double getCost() { return 0.0; }
147 /*! \brief Makes a minor change to the entity. */
149 /*! \brief Restores the entity to its previous state i.e. reverts the
150 * effects of the last mutate().
155 /*! \brief A simple controller for the simulated annealing class. */
156 class SimpleController : public SimAnnBase::Controller {
158 /*! \brief Number of iterations. */
160 /*! \brief Number of iterations which did not improve the solution since
161 * the last improvement. */
163 /*! \brief Maximum number of iterations. */
165 /*! \brief Maximum number of iterations which do not improve the
168 /*! \brief Temperature. */
170 /*! \brief Annealing factor. */
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
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. */
187 /*! \brief This is called when the accepted neighbouring state's cost is
188 * less than the best found one's.
190 void improveEvent() {
193 /*! \brief This is called when a neighbouring state gets rejected. */
197 /*! \brief Decides whether to continue the annealing process or not. Also
198 * decreases the temperature. */
201 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
204 /*! \brief Decides whether to accept the current solution or not. */
206 double cost_diff = base->getPrevCost() - base->getCurrCost();
207 if (cost_diff < 0.0) {
208 bool ret = drand48() <= exp(cost_diff / temp);
217 /*! \brief A controller with preset running time for the simulated annealing
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
230 class AdvancedController : public SimAnnBase::Controller {
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;
241 /*! \brief The time at the end of the algorithm. */
243 /*! \brief The time at the start of the algorithm. */
245 /*! \brief Starting threshold. */
246 double start_threshold;
247 /*! \brief Average cost of recent solutions. */
249 /*! \brief Temperature. */
251 /*! \brief Annealing factor. */
253 /*! \brief Initial annealing factor. */
254 double init_ann_fact;
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
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) {}
268 avg_cost = base->getCurrCost();
270 /*! \brief This is called when a neighbouring state gets accepted. */
272 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
277 // calculate starting threshold and starting temperature
278 start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
285 /*! \brief Decides whether to continue the annealing process or not. */
291 double elapsed_time = timer.getRealTime();
292 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
293 // decrease the annealing factor
297 // increase the temperature
299 // reset the annealing factor
300 ann_fact = init_ann_fact;
303 return elapsed_time < end_time;
306 /*! \brief Decides whether to accept the current solution or not. */
309 // we accept eveything during the "warm up" phase
313 double cost_diff = base->getPrevCost() - base->getCurrCost();
314 if (cost_diff < 0.0) {
315 return (drand48() <= exp(cost_diff / temp));