Added this in order to prevent losing it.
6 #include <lemon/time_measure.h>
10 const double INFTY = 1e24;
16 Controller *controller;
21 double prev_prev_cost;
23 virtual void mutate() = 0;
24 virtual void revert() = 0;
25 virtual void saveAsBest() = 0;
28 best_cost = prev_cost = prev_prev_cost = INFTY;
30 void setController(Controller &_controller) {
31 controller = &_controller;
32 controller->setBase(this);
34 double getCurrCost() const { return curr_cost; }
35 double getPrevCost() const { return prev_cost; }
36 double getBestCost() const { return best_cost; }
41 if (controller->accept()) {
42 controller->acceptEvent();
43 if (curr_cost < best_cost) {
45 controller->improveEvent();
50 controller->rejectEvent();
52 } while (controller->next());
55 /*! \brief A base class for controllers. */
59 virtual void init() {}
60 /*! \brief This is called when a neighbouring state gets accepted. */
61 virtual void acceptEvent() {}
62 /*! \brief This is called when the accepted neighbouring state's cost is
63 * less than the best found one's.
65 virtual void improveEvent() {}
66 /*! \brief This is called when a neighbouring state gets rejected. */
67 virtual void rejectEvent() {}
68 virtual void setBase(SimAnnBase *_base) { base = _base; }
70 virtual bool next() = 0;
72 virtual bool accept() = 0;
77 class SimAnn : public SimAnnBase {
82 SimAnn() : SimAnnBase() {}
83 void setEntity(E &ent) {
84 curr_ent = new E(ent);
85 best_ent = new E(ent);
86 curr_cost = curr_ent->getCost();
88 E getBestEntity() { return *best_ent; }
90 prev_prev_cost = prev_cost;
91 prev_cost = curr_cost;
93 curr_cost = curr_ent->getCost();
97 curr_cost = prev_cost;
98 prev_cost = prev_prev_cost;
101 *best_ent = *curr_ent;
102 best_cost = curr_cost;
106 class EntitySkeleton {
108 /*! \return the cost of the entity */
109 double getCost() { return 0.0; }
110 /*! \brief Makes a minor change to the entity. */
112 /*! \brief Restores the entity to its previous state i.e. reverts the
113 * effects of the last mutate.
118 /*! \brief A simple controller for the simulated annealing class.
119 * \todo Find a way to set the various parameters.
121 class SimpleController : public SimAnnBase::Controller {
123 long iter, last_impr, max_iter, max_no_impr;
124 double temp, ann_fact;
125 /*! \param _max_iter maximum number of iterations
126 * \param _max_no_impr maximum number of consecutive iterations which do
127 * not yield a better solution
128 * \param _temp initial temperature
129 * \param _ann_fact annealing factor
131 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000,
132 double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0),
133 max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp),
134 ann_fact(_ann_fact) {}
138 void improveEvent() {
146 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);
150 double cost_diff = base->getPrevCost() - base->getCurrCost();
151 if (cost_diff < 0.0) {
152 return (drand48() <= exp(cost_diff / temp));
160 /*! \brief A controller with preset running time for the simulated annealing
162 * \todo Find a better name.
164 class AdvancedController : public SimAnnBase::Controller {
167 /*! \param time the elapsed time in seconds */
168 virtual double threshold(double time) {
169 // this is the function 1 / log(x) scaled and offset
170 static double xm = 5.0 / end_time;
171 static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2));
172 return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2));
175 double alpha, beta, gamma;
176 double end_time, start_time;
177 double start_threshold;
179 double temp, ann_fact;
181 /*! \param _end_time running time in seconds
182 * \param _alpha parameter used to calculate the running average
183 * \param _beta parameter used to decrease the annealing factor
184 * \param _gamma parameter used to increase the temperature
186 AdvancedController(double _end_time, double _alpha = 0.2,
187 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta),
188 gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true) {}
190 avg_cost = base->getCurrCost();
193 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;
195 static double max_cost_diff = 0.0;
196 static int incr_cnt = 0;
197 double cost_diff = base->getCurrCost() - base->getPrevCost();
198 if (cost_diff > 0.0) {
200 if (cost_diff > max_cost_diff) {
201 max_cost_diff = cost_diff;
204 if (incr_cnt >= 100) {
205 // calculate starting threshold and starting temperature
206 start_threshold = fabs(base->getBestCost() - avg_cost);
207 temp = max_cost_diff / log(0.5);
213 void improveEvent() {
222 double elapsed_time = timer.getRealTime();
223 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) {
224 // decrease the annealing factor
228 // increase the temperature
232 return elapsed_time < end_time;
237 // we accept eveything during the "warm up" phase
241 double cost_diff = base->getPrevCost() - base->getCurrCost();
242 if (cost_diff < 0.0) {
243 return (drand48() <= exp(cost_diff / temp));