14 class Controller; |
14 class Controller; |
15 private: |
15 private: |
16 Controller *controller; |
16 Controller *controller; |
17 protected: |
17 protected: |
18 double curr_cost; |
18 double curr_cost; |
|
19 double best_cost; |
19 double prev_cost; |
20 double prev_cost; |
20 double best_cost; |
21 double prev_prev_cost; |
21 |
22 |
22 virtual void mutate() = 0; |
23 virtual void mutate() = 0; |
23 virtual void revert() = 0; |
24 virtual void revert() = 0; |
24 virtual void saveAsBest() = 0; |
25 virtual void saveAsBest() = 0; |
25 public: |
26 public: |
26 SimAnnBase() { |
27 SimAnnBase() { |
27 curr_cost = prev_cost = best_cost = INFTY; |
28 best_cost = prev_cost = prev_prev_cost = INFTY; |
28 } |
29 } |
29 void setController(Controller &_controller) { |
30 void setController(Controller &_controller) { |
30 controller = &_controller; |
31 controller = &_controller; |
31 controller->setBase(this); |
32 controller->setBase(this); |
32 } |
33 } |
70 /*! */ |
71 /*! */ |
71 virtual bool accept() = 0; |
72 virtual bool accept() = 0; |
72 }; |
73 }; |
73 }; |
74 }; |
74 |
75 |
75 /*! \todo atgondolni mi is ez a prev_cost */ |
|
76 template <typename E> |
76 template <typename E> |
77 class SimAnn : public SimAnnBase { |
77 class SimAnn : public SimAnnBase { |
78 private: |
78 private: |
79 E *curr_ent; |
79 E *curr_ent; |
80 E *best_ent; |
80 E *best_ent; |
81 public: |
81 public: |
82 SimAnn() : SimAnnBase() {} |
82 SimAnn() : SimAnnBase() {} |
83 void setEntity(E &ent) { |
83 void setEntity(E &ent) { |
84 curr_ent = new E(ent); |
84 curr_ent = new E(ent); |
85 best_ent = new E(ent); |
85 best_ent = new E(ent); |
|
86 curr_cost = curr_ent->getCost(); |
86 } |
87 } |
87 E getBestEntity() { return *best_ent; } |
88 E getBestEntity() { return *best_ent; } |
88 void mutate() { |
89 void mutate() { |
|
90 prev_prev_cost = prev_cost; |
89 prev_cost = curr_cost; |
91 prev_cost = curr_cost; |
90 curr_cost = curr_ent->mutate(); |
92 curr_ent->mutate(); |
|
93 curr_cost = curr_ent->getCost(); |
91 } |
94 } |
92 void revert() { |
95 void revert() { |
93 curr_ent->revert(); |
96 curr_ent->revert(); |
94 curr_cost = prev_cost; |
97 curr_cost = prev_cost; |
|
98 prev_cost = prev_prev_cost; |
95 } |
99 } |
96 void saveAsBest() { |
100 void saveAsBest() { |
97 *best_ent = *curr_ent; |
101 *best_ent = *curr_ent; |
98 best_cost = curr_cost; |
102 best_cost = curr_cost; |
99 } |
103 } |
100 }; |
104 }; |
101 |
105 |
102 class EntitySkeleton { |
106 class EntitySkeleton { |
103 public: |
107 public: |
104 /*! \brief Makes a minor change to the entity. |
108 /*! \return the cost of the entity */ |
105 * \return the new cost |
109 double getCost() { return 0.0; } |
106 */ |
110 /*! \brief Makes a minor change to the entity. */ |
107 double mutate() { return 0.0; } |
111 void mutate() {} |
108 /*! \brief Restores the entity to its previous state i.e. reverts the |
112 /*! \brief Restores the entity to its previous state i.e. reverts the |
109 * effects of the last mutate. |
113 * effects of the last mutate. |
110 */ |
114 */ |
111 void revert() {} |
115 void revert() {} |
112 }; |
116 }; |
172 double end_time, start_time; |
176 double end_time, start_time; |
173 double start_threshold; |
177 double start_threshold; |
174 double avg_cost; |
178 double avg_cost; |
175 double temp, ann_fact; |
179 double temp, ann_fact; |
176 bool warmup; |
180 bool warmup; |
177 long iter; |
|
178 /*! \param _end_time running time in seconds |
181 /*! \param _end_time running time in seconds |
179 * \param _alpha parameter used to calculate the running average |
182 * \param _alpha parameter used to calculate the running average |
180 * \param _beta parameter used to decrease the annealing factor |
183 * \param _beta parameter used to decrease the annealing factor |
181 * \param _gamma parameter used to increase the temperature |
184 * \param _gamma parameter used to increase the temperature |
182 */ |
185 */ |
183 AdvancedController(double _end_time, double _alpha = 0.2, |
186 AdvancedController(double _end_time, double _alpha = 0.2, |
184 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta), |
187 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta), |
185 gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true), |
188 gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true) {} |
186 iter(0) {} |
|
187 void init() { |
189 void init() { |
188 avg_cost = base->getCurrCost(); |
190 avg_cost = base->getCurrCost(); |
189 } |
191 } |
190 void acceptEvent() { |
192 void acceptEvent() { |
191 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost; |
193 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost; |
192 iter++; |
194 if (warmup) { |
|
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) { |
|
199 incr_cnt++; |
|
200 if (cost_diff > max_cost_diff) { |
|
201 max_cost_diff = cost_diff; |
|
202 } |
|
203 } |
|
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); |
|
208 warmup = false; |
|
209 timer.reset(); |
|
210 } |
|
211 } |
193 } |
212 } |
194 void improveEvent() { |
213 void improveEvent() { |
195 } |
214 } |
196 void rejectEvent() { |
215 void rejectEvent() { |
197 iter++; |
|
198 } |
216 } |
199 bool next() { |
217 bool next() { |
200 if (warmup) { |
218 if (warmup) { |
201 static double max_cost_diff = 0.0; |
|
202 double cost_diff = base->getCurrCost() - base->getPrevCost(); |
|
203 // jo ez igy egyaltalan? -> prev_cost |
|
204 if ((cost_diff > 0.0) && (cost_diff > max_cost_diff)) { |
|
205 max_cost_diff = cost_diff; |
|
206 } |
|
207 // How to set the starting temperature when all the 100 first |
|
208 // iterations improve the solution? |
|
209 if (iter > 100) { |
|
210 // calculate starting threshold and starting temperature |
|
211 start_threshold = fabs(base->getBestCost() - avg_cost); |
|
212 temp = exp(max_cost_diff) / 0.5; |
|
213 warmup = false; |
|
214 timer.reset(); |
|
215 } |
|
216 return true; |
219 return true; |
217 } |
220 } |
218 else { |
221 else { |
219 double elapsed_time = timer.getRealTime(); |
222 double elapsed_time = timer.getRealTime(); |
220 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { |
223 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { |