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() {}
39 /*! \brief Reverts the last mutate(). */
40 virtual void revert() {}
41 /*! \brief Saves the current solution as the best one. */
42 virtual void saveAsBest() {}
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) {}
186 /*! \brief This is called when the accepted neighbouring state's cost is
187 * less than the best found one's.
189 void improveEvent() {
192 /*! \brief This is called when a neighbouring state gets rejected. */
196 /*! \brief Decides whether to continue the annealing process or not. Also
197 * decreases the temperature. */
200 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
203 /*! \brief Decides whether to accept the current solution or not. */
205 double cost_diff = base->getPrevCost() - base->getCurrCost();
206 if (cost_diff < 0.0) {
207 bool ret = drand48() <= exp(cost_diff / temp);
216 /*! \brief A controller with preset running time for the simulated annealing
219 class AdvancedController : public SimAnnBase::Controller {
222 /*! \param time the elapsed time in seconds */
223 virtual double threshold(double time) {
224 return (-1.0) * start_threshold / end_time * time + start_threshold;
232 double start_threshold;
237 /*! \brief Constructor.
238 * \param _end_time running time in seconds
239 * \param _alpha parameter used to calculate the running average
240 * \param _beta parameter used to decrease the annealing factor
241 * \param _gamma parameter used to increase the temperature
243 AdvancedController(double _end_time, double _alpha = 0.2,
244 double _beta = 0.9, double _gamma = 1.6) : alpha(_alpha), beta(_beta),
245 gamma(_gamma), end_time(_end_time), ann_fact(0.99999999), warmup(true) {}
247 avg_cost = base->getCurrCost();
249 /*! \brief This is called when a neighbouring state gets accepted. */
251 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
256 // calculate starting threshold and starting temperature
257 start_threshold = 5.0 * fabs(base->getBestCost() - avg_cost);
264 /*! \brief Decides whether to continue the annealing process or not. */
270 double elapsed_time = timer.getRealTime();
271 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
272 // decrease the annealing factor
276 // increase the temperature
278 ann_fact = 0.99999999; // !!!!!!!!!!!
281 return elapsed_time < end_time;
284 /*! \brief Decides whether to accept the current solution or not. */
287 // we accept eveything during the "warm up" phase
291 double cost_diff = base->getPrevCost() - base->getCurrCost();
292 if (cost_diff < 0.0) {
293 return (drand48() <= exp(cost_diff / temp));