49 controller->rejectEvent(); |
49 controller->rejectEvent(); |
50 } |
50 } |
51 } |
51 } |
52 } |
52 } |
53 |
53 |
|
54 /*! \brief A base class for controllers. */ |
54 class Controller { |
55 class Controller { |
55 public: |
56 public: |
56 SimAnnBase *base; |
57 SimAnnBase *base; |
57 virtual void init() {} |
58 virtual void init() {} |
|
59 /*! \brief This is called when a neighbouring state gets accepted. */ |
58 virtual void acceptEvent() {} |
60 virtual void acceptEvent() {} |
|
61 /*! \brief This is called when the accepted neighbouring state's cost is |
|
62 * less than the best found one's. |
|
63 */ |
59 virtual void improveEvent() {} |
64 virtual void improveEvent() {} |
|
65 /*! \brief This is called when a neighbouring state gets rejected. */ |
60 virtual void rejectEvent() {} |
66 virtual void rejectEvent() {} |
61 virtual void setBase(SimAnnBase *_base) { base = _base; } |
67 virtual void setBase(SimAnnBase *_base) { base = _base; } |
|
68 /*! */ |
62 virtual bool next() = 0; |
69 virtual bool next() = 0; |
|
70 /*! */ |
63 virtual bool accept() = 0; |
71 virtual bool accept() = 0; |
64 }; |
72 }; |
65 }; |
73 }; |
66 |
74 |
67 template <typename E> |
75 template <typename E> |
104 * \todo Find a way to set the various parameters. |
112 * \todo Find a way to set the various parameters. |
105 */ |
113 */ |
106 class SimpleController : public SimAnnBase::Controller { |
114 class SimpleController : public SimAnnBase::Controller { |
107 public: |
115 public: |
108 long iter, last_impr, max_iter, max_no_impr; |
116 long iter, last_impr, max_iter, max_no_impr; |
109 double temp, annealing_factor; |
117 double temp, ann_fact; |
110 SimpleController() { |
118 /*! \param _max_iter maximum number of iterations |
111 iter = last_impr = 0; |
119 * \param _max_no_impr maximum number of consecutive iterations which do |
112 max_iter = 500000; |
120 * not yield a better solution |
113 max_no_impr = 20000; |
121 * \param _temp initial temperature |
114 annealing_factor = 0.9999; |
122 * \param _ann_fact annealing factor |
115 temp = 1000; |
123 */ |
116 } |
124 SimpleController(long _max_iter = 500000, long _max_no_impr = 20000, |
|
125 double _temp = 1000, double _ann_fact = 0.9999) : iter(0), last_impr(0), |
|
126 max_iter(_max_iter), max_no_impr(_max_no_impr), temp(_temp), |
|
127 ann_fact(_ann_fact) {} |
117 void acceptEvent() { |
128 void acceptEvent() { |
118 iter++; |
129 iter++; |
119 } |
130 } |
120 void improveEvent() { |
131 void improveEvent() { |
121 last_impr = iter; |
132 last_impr = iter; |
122 } |
133 } |
123 void rejectEvent() { |
134 void rejectEvent() { |
124 iter++; |
135 iter++; |
125 } |
136 } |
126 bool next() { |
137 bool next() { |
127 temp *= annealing_factor; |
138 temp *= ann_fact; |
128 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr); |
139 bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr); |
129 return !quit; |
140 return !quit; |
130 } |
141 } |
131 bool accept() { |
142 bool accept() { |
132 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / |
143 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / |
138 * class. |
149 * class. |
139 * \todo Find a better name. |
150 * \todo Find a better name. |
140 */ |
151 */ |
141 class AdvancedController : public SimAnnBase::Controller { |
152 class AdvancedController : public SimAnnBase::Controller { |
142 private: |
153 private: |
143 double threshold() { return 0.0; } |
154 /*! \param time the elapsed time in seconds */ |
144 public: |
155 double threshold(double time) { return 0.0; } |
145 double alpha; |
156 public: |
146 double temp; |
157 double alpha, beta, gamma; |
|
158 double end_time, start_time; |
147 double avg_cost; |
159 double avg_cost; |
148 double start_time, end_time; |
160 double temp, ann_fact; |
|
161 /*! \param _end_time running_time |
|
162 * \param _alpha parameter used to calculate the running average |
|
163 * \param _beta parameter used to decrease the annealing factor |
|
164 * \param _gamma parameter used to increase the temperature |
|
165 */ |
|
166 AdvancedController(double _end_time, double _alpha = 0.2, |
|
167 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta), |
|
168 gamma(_gamma), end_time(_end_time) {} |
149 void init() { |
169 void init() { |
150 timeval tv; |
170 timeval tv; |
151 gettimeofday(&tv, 0); |
171 gettimeofday(&tv, 0); |
152 start_time = tv.tv_sec + double(tv.tv_usec) / 1e6; |
172 start_time = tv.tv_sec + double(tv.tv_usec) / 1e6; |
153 } |
173 } |
157 void improveEvent() { |
177 void improveEvent() { |
158 } |
178 } |
159 void rejectEvent() { |
179 void rejectEvent() { |
160 } |
180 } |
161 bool next() { |
181 bool next() { |
162 // abs(avg_cost - base->getBestCost()) |
|
163 // ha nagy: cooling factor novelese |
|
164 // ha kicsi: homerseklet novelese |
|
165 // de mennyivel? |
|
166 timeval tv; |
182 timeval tv; |
167 gettimeofday(&tv, 0); |
183 gettimeofday(&tv, 0); |
168 double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time; |
184 double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time; |
|
185 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { |
|
186 // decrease the annealing factor |
|
187 ann_fact *= beta; |
|
188 } |
|
189 else { |
|
190 // increase the temperature |
|
191 temp *= gamma; |
|
192 } |
|
193 temp *= ann_fact; |
169 return elapsed_time < end_time; |
194 return elapsed_time < end_time; |
170 } |
195 } |
171 bool accept() { |
196 bool accept() { |
172 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / |
197 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / |
173 temp)); |
198 temp)); |