Changeset 1018:68beae6758a7 in lemon-0.x for src/work/akos
- Timestamp:
- 11/22/04 15:39:40 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1408
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/akos/simann.h
r1000 r1018 4 4 #include <cstdlib> 5 5 #include <cmath> 6 #include < sys/time.h>6 #include <lemon/time_measure.h> 7 7 8 8 namespace lemon { … … 31 31 controller->setBase(this); 32 32 } 33 double getCurrCost() { return curr_cost; }34 double getPrevCost() { return prev_cost; }35 double getBestCost() { return best_cost; }33 double getCurrCost() const { return curr_cost; } 34 double getPrevCost() const { return prev_cost; } 35 double getBestCost() const { return best_cost; } 36 36 void run() { 37 37 controller->init(); 38 while (controller->next()){38 do { 39 39 mutate(); 40 40 if (controller->accept()) { … … 49 49 controller->rejectEvent(); 50 50 } 51 } 51 } while (controller->next()); 52 52 } 53 53 … … 73 73 }; 74 74 75 /*! \todo atgondolni mi is ez a prev_cost */ 75 76 template <typename E> 76 77 class SimAnn : public SimAnnBase { … … 86 87 E getBestEntity() { return *best_ent; } 87 88 void mutate() { 88 curr_ent->mutate(); 89 prev_cost = curr_cost; 90 curr_cost = curr_ent->mutate(); 89 91 } 90 92 void revert() { 91 93 curr_ent->revert(); 94 curr_cost = prev_cost; 92 95 } 93 96 void saveAsBest() { … … 141 144 } 142 145 bool accept() { 143 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / 144 temp)); 146 double cost_diff = base->getPrevCost() - base->getCurrCost(); 147 if (cost_diff < 0.0) { 148 return (drand48() <= exp(cost_diff / temp)); 149 } 150 else { 151 return true; 152 } 145 153 } 146 154 }; … … 152 160 class AdvancedController : public SimAnnBase::Controller { 153 161 private: 162 Timer timer; 154 163 /*! \param time the elapsed time in seconds */ 155 double threshold(double time) { return 0.0; } 164 virtual double threshold(double time) { 165 // this is the function 1 / log(x) scaled and offset 166 static double xm = 5.0 / end_time; 167 static double ym = start_threshold / (1 / log(1.2) - 1 / log(5.0 + 1.2)); 168 return ym * (1 / log(xm * time + 1.2) - 1 / log(5.0 + 1.2)); 169 } 156 170 public: 157 171 double alpha, beta, gamma; 158 172 double end_time, start_time; 173 double start_threshold; 159 174 double avg_cost; 160 175 double temp, ann_fact; 161 /*! \param _end_time running_time 176 bool warmup; 177 long iter; 178 /*! \param _end_time running time in seconds 162 179 * \param _alpha parameter used to calculate the running average 163 180 * \param _beta parameter used to decrease the annealing factor … … 166 183 AdvancedController(double _end_time, double _alpha = 0.2, 167 184 double _beta = 0.9, double _gamma = 1.2) : alpha(_alpha), beta(_beta), 168 gamma(_gamma), end_time(_end_time) {} 185 gamma(_gamma), end_time(_end_time), ann_fact(0.9999), warmup(true), 186 iter(0) {} 169 187 void init() { 170 timeval tv; 171 gettimeofday(&tv, 0); 172 start_time = tv.tv_sec + double(tv.tv_usec) / 1e6; 188 avg_cost = base->getCurrCost(); 173 189 } 174 190 void acceptEvent() { 175 191 avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost; 192 iter++; 176 193 } 177 194 void improveEvent() { 178 195 } 179 196 void rejectEvent() { 197 iter++; 180 198 } 181 199 bool next() { 182 timeval tv; 183 gettimeofday(&tv, 0); 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; 200 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; 188 217 } 189 218 else { 190 // increase the temperature 191 temp *= gamma; 192 } 193 temp *= ann_fact; 194 return elapsed_time < end_time; 219 double elapsed_time = timer.getRealTime(); 220 if (fabs(avg_cost - base->getBestCost()) > threshold(elapsed_time)) { 221 // decrease the annealing factor 222 ann_fact *= beta; 223 } 224 else { 225 // increase the temperature 226 temp *= gamma; 227 } 228 temp *= ann_fact; 229 return elapsed_time < end_time; 230 } 195 231 } 196 232 bool accept() { 197 return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() / 198 temp)); 233 if (warmup) { 234 // we accept eveything during the "warm up" phase 235 return true; 236 } 237 else { 238 double cost_diff = base->getPrevCost() - base->getCurrCost(); 239 if (cost_diff < 0.0) { 240 return (drand48() <= exp(cost_diff / temp)); 241 } 242 else { 243 return true; 244 } 245 } 199 246 } 200 247 };
Note: See TracChangeset
for help on using the changeset viewer.